www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - X[]==Y[] is 7X slower than it should be -- why?

reply Don <nospam nospam.com.au> writes:
I've been doing some timing tests, and found that the built-in array 
comparison is amazingly slow.

Given:
uint [2000] X, Y;

bool b = (X[] == Y[]);

on my Pentium M, this takes ~30000 cycles in the case where both arrays 
are equal.
It's not hard to write an optimal asm routine; this takes 4000 cycles 
(7.5 times faster).
But, it's also possible to perform the comparison in simple D code, 
something like:

int compareArrays(uint [] x, uint y[])
{
     for (int i=0; i<x.length; ++i) {
         if (x[i] != y[i]) return x[i]-y[i];
     }
     return 0;
}

and this takes 6000 cycles when compiled with -release -O, 5X better 
than the built-in version.

So, why is the built-in compare so slow? Using the CPU performance counters:
X[]==Y[] --> 10000 branches, 35000 memory loads, 30000 cycles.
for loop --> 4000 branches, 6000 memory loads, 6000 cycles.
asm      --> 4000 branches, 4000 memory loads, 4000 cycles.

What's it doing? Is it doing a byte-by-byte comparison? (it shouldn't do 
that even for strings). Is it doing bounds checking for every array 
element?? (even with -release -O)

There's significant optimisation potential here.
Jun 20 2008
next sibling parent janderson <askme me.com> writes:
Don wrote:

 I've been doing some timing tests, and found that the built-in array 
 comparison is amazingly slow.
 
 Given:
 uint [2000] X, Y;
 
 bool b = (X[] == Y[]);
 
 on my Pentium M, this takes ~30000 cycles in the case where both arrays 
 are equal.
 It's not hard to write an optimal asm routine; this takes 4000 cycles 
 (7.5 times faster).
 But, it's also possible to perform the comparison in simple D code, 
 something like:
 
 int compareArrays(uint [] x, uint y[])
 {
     for (int i=0; i<x.length; ++i) {
         if (x[i] != y[i]) return x[i]-y[i];
     }
     return 0;
 }
 
 and this takes 6000 cycles when compiled with -release -O, 5X better 
 than the built-in version.
 
 So, why is the built-in compare so slow? Using the CPU performance 
 counters:
 X[]==Y[] --> 10000 branches, 35000 memory loads, 30000 cycles.
 for loop --> 4000 branches, 6000 memory loads, 6000 cycles.
 asm      --> 4000 branches, 4000 memory loads, 4000 cycles.
 
 What's it doing? Is it doing a byte-by-byte comparison? (it shouldn't do 
 that even for strings). Is it doing bounds checking for every array 
 element?? (even with -release -O)
 
 There's significant optimisation potential here.


I haven't looked but this is probably somewhere in the front end code. 
You could always summit a patch.

-Joel
Jun 20 2008
prev sibling next sibling parent "Unknown W. Brackets" <unknown simplemachines.org> writes:
When in doubt, dump the assembly and compare.  I wish I had free time, 
this sounds interesting, I wonder what it's doing.

-[Unknown]


Don wrote:

 I've been doing some timing tests, and found that the built-in array 
 comparison is amazingly slow.
 
 Given:
 uint [2000] X, Y;
 
 bool b = (X[] == Y[]);
 
 on my Pentium M, this takes ~30000 cycles in the case where both arrays 
 are equal.
 It's not hard to write an optimal asm routine; this takes 4000 cycles 
 (7.5 times faster).
 But, it's also possible to perform the comparison in simple D code, 
 something like:
 
 int compareArrays(uint [] x, uint y[])
 {
     for (int i=0; i<x.length; ++i) {
         if (x[i] != y[i]) return x[i]-y[i];
     }
     return 0;
 }
 
 and this takes 6000 cycles when compiled with -release -O, 5X better 
 than the built-in version.
 
 So, why is the built-in compare so slow? Using the CPU performance 
 counters:
 X[]==Y[] --> 10000 branches, 35000 memory loads, 30000 cycles.
 for loop --> 4000 branches, 6000 memory loads, 6000 cycles.
 asm      --> 4000 branches, 4000 memory loads, 4000 cycles.
 
 What's it doing? Is it doing a byte-by-byte comparison? (it shouldn't do 
 that even for strings). Is it doing bounds checking for every array 
 element?? (even with -release -O)
 
 There's significant optimisation potential here.
Jun 20 2008
prev sibling next sibling parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Don" <nospam nospam.com.au> wrote in message 
news:g3ggq5$ui5$1 digitalmars.com...


 What's it doing? Is it doing a byte-by-byte comparison? (it shouldn't do 
 that even for strings). Is it doing bounds checking for every array 
 element?? (even with -release -O)


See dmd/src/phobos/internal/adi.d  The important function here is:

extern (C) int _adEq(Array a1, Array a2, TypeInfo ti)
{
    if (a1.length != a2.length)
        return 0;

    auto sz = ti.tsize();
    auto p1 = a1.ptr;
    auto p2 = a2.ptr;

    if (sz == 1)
        // We should really have a ti.isPOD() check for this
        return (memcmp(p1, p2, a1.length) == 0);

    for (size_t i = 0; i < a1.length; i++)
    {
        if (!ti.equals(p1 + i * sz, p2 + i * sz))
            return 0;
    }

    return 1;
}

If the size of an element is 1 (bytes, chars, bools), it just does memcmp. 
There's even a comment in there that memcmp should be used if the type is 
POD (plain old data, which uints are).  But otherwise, it uses the RTTI 
.equals function to compare the elements, and it doesn't even use parallel 
pointers, it does manual indexing for each element.  .equals will, for 
uints, just return true if they are equal.

What flabbergasts me is that in the uint[] typeinfo class, there is an 
equals method that uses memcmp, but it's not used unless you explicitly call 
it (or if you have a uint[][]).  Try doing

bool b = typeid(uint[]).equals(&X[], &Y[]);

and see what kind of performance you get.
Jun 20 2008
next sibling parent reply Sean Kelly <sean invisibleduck.org> writes:
== Quote from Jarrett Billingsley (kb3ctd2 yahoo.com)'s article

 "Don" <nospam nospam.com.au> wrote in message
 news:g3ggq5$ui5$1 digitalmars.com...

 What's it doing? Is it doing a byte-by-byte comparison? (it shouldn't do
 that even for strings). Is it doing bounds checking for every array
 element?? (even with -release -O)


 See dmd/src/phobos/internal/adi.d  The important function here is:
 extern (C) int _adEq(Array a1, Array a2, TypeInfo ti)
 {
     if (a1.length != a2.length)
         return 0;
     auto sz = ti.tsize();
     auto p1 = a1.ptr;
     auto p2 = a2.ptr;
     if (sz == 1)
         // We should really have a ti.isPOD() check for this
         return (memcmp(p1, p2, a1.length) == 0);
     for (size_t i = 0; i < a1.length; i++)
     {
         if (!ti.equals(p1 + i * sz, p2 + i * sz))
             return 0;
     }
     return 1;
 }
 If the size of an element is 1 (bytes, chars, bools), it just does memcmp.
 There's even a comment in there that memcmp should be used if the type is
 POD (plain old data, which uints are).  But otherwise, it uses the RTTI
 .equals function to compare the elements, and it doesn't even use parallel
 pointers, it does manual indexing for each element.  .equals will, for
 uints, just return true if they are equal.
 What flabbergasts me is that in the uint[] typeinfo class, there is an
 equals method that uses memcmp, but it's not used unless you explicitly call
 it (or if you have a uint[][]).  Try doing
 bool b = typeid(uint[]).equals(&X[], &Y[]);
 and see what kind of performance you get.


My mistake for assuming the compiler would generate the appropriate code for
this.  I'm fixing this in Tango today, assuming no problems crop up.


Sean
Jun 20 2008
parent reply Sean Kelly <sean invisibleduck.org> writes:
== Quote from Sean Kelly (sean invisibleduck.org)'s article

 == Quote from Jarrett Billingsley (kb3ctd2 yahoo.com)'s article

 "Don" <nospam nospam.com.au> wrote in message
 news:g3ggq5$ui5$1 digitalmars.com...

 What's it doing? Is it doing a byte-by-byte comparison? (it shouldn't do
 that even for strings). Is it doing bounds checking for every array
 element?? (even with -release -O)


 See dmd/src/phobos/internal/adi.d  The important function here is:
 extern (C) int _adEq(Array a1, Array a2, TypeInfo ti)
 {
     if (a1.length != a2.length)
         return 0;
     auto sz = ti.tsize();
     auto p1 = a1.ptr;
     auto p2 = a2.ptr;
     if (sz == 1)
         // We should really have a ti.isPOD() check for this
         return (memcmp(p1, p2, a1.length) == 0);
     for (size_t i = 0; i < a1.length; i++)
     {
         if (!ti.equals(p1 + i * sz, p2 + i * sz))
             return 0;
     }
     return 1;
 }
 If the size of an element is 1 (bytes, chars, bools), it just does memcmp.
 There's even a comment in there that memcmp should be used if the type is
 POD (plain old data, which uints are).  But otherwise, it uses the RTTI
 .equals function to compare the elements, and it doesn't even use parallel
 pointers, it does manual indexing for each element.  .equals will, for
 uints, just return true if they are equal.
 What flabbergasts me is that in the uint[] typeinfo class, there is an
 equals method that uses memcmp, but it's not used unless you explicitly call
 it (or if you have a uint[][]).  Try doing
 bool b = typeid(uint[]).equals(&X[], &Y[]);
 and see what kind of performance you get.


 My mistake for assuming the compiler would generate the appropriate code for
 this.  I'm fixing this in Tango today, assuming no problems crop up.


Done :p

http://dsource.org/projects/tango/changeset/3651


Sean
Jun 20 2008
parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Sean Kelly" <sean invisibleduck.org> wrote in message 
news:g3gtvk$1tm7$1 digitalmars.com...

 Done :p

 http://dsource.org/projects/tango/changeset/3651


In _adCmp,

if (a1.ptr == a2.ptr)
    return 0;

erm, that's not right at all.  Two slices with the same pointer and 
different lengths.
Jun 20 2008
parent reply Sean Kelly <sean invisibleduck.org> writes:
== Quote from Jarrett Billingsley (kb3ctd2 yahoo.com)'s article

 "Sean Kelly" <sean invisibleduck.org> wrote in message
 news:g3gtvk$1tm7$1 digitalmars.com...

 Done :p

 http://dsource.org/projects/tango/changeset/3651


 In _adCmp,
 if (a1.ptr == a2.ptr)
     return 0;
 erm, that's not right at all.  Two slices with the same pointer and
 different lengths.


Darnit, you're right.  Good catch.


Sean
Jun 20 2008
parent reply Tomas Lindquist Olsen <tomas famolsen.dk> writes:
Sean Kelly wrote:

 == Quote from Jarrett Billingsley (kb3ctd2 yahoo.com)'s article

 "Sean Kelly" <sean invisibleduck.org> wrote in message
 news:g3gtvk$1tm7$1 digitalmars.com...

 Done :p

 http://dsource.org/projects/tango/changeset/3651


 In _adCmp,
 if (a1.ptr == a2.ptr)
     return 0;
 erm, that's not right at all.  Two slices with the same pointer and
 different lengths.


 
 Darnit, you're right.  Good catch.
 
 
 Sean


After having a look at this I don't see how it could work.
The TypeInfo passed to _adEq/Cmp is the *element* typeinfo, not the *array*
typeinfo.

With the current code, the way I read it, only arrays with elementsize==1 will
work (and only 
if the element is not a 1byte struct that overloads the comparison operators.

Am I missing something or should the compilers not be changed to pass the
*array* typeinfo if 
these optimizations are to make any sense ?

Tomas
Jun 21 2008
parent reply Sean Kelly <sean invisibleduck.org> writes:
== Quote from Tomas Lindquist Olsen (tomas famolsen.dk)'s article

 Sean Kelly wrote:

 == Quote from Jarrett Billingsley (kb3ctd2 yahoo.com)'s article

 "Sean Kelly" <sean invisibleduck.org> wrote in message
 news:g3gtvk$1tm7$1 digitalmars.com...

 Done :p

 http://dsource.org/projects/tango/changeset/3651


 In _adCmp,
 if (a1.ptr == a2.ptr)
     return 0;
 erm, that's not right at all.  Two slices with the same pointer and
 different lengths.


 Darnit, you're right.  Good catch.


 Sean


 After having a look at this I don't see how it could work.
 The TypeInfo passed to _adEq/Cmp is the *element* typeinfo, not the *array*


typeinfo.

 With the current code, the way I read it, only arrays with elementsize==1 will


work (and only

 if the element is not a 1byte struct that overloads the comparison operators.
 Am I missing something or should the compilers not be changed to pass the


*array* typeinfo if

 these optimizations are to make any sense ?


I was wondering about that.  *sigh* I guess I'll have to change it back then. 
How
terribly annoying.


Sean
Jun 22 2008
parent reply Sean Kelly <sean invisibleduck.org> writes:
== Quote from Sean Kelly (sean invisibleduck.org)'s article

 == Quote from Tomas Lindquist Olsen (tomas famolsen.dk)'s article

 Sean Kelly wrote:

 == Quote from Jarrett Billingsley (kb3ctd2 yahoo.com)'s article

 "Sean Kelly" <sean invisibleduck.org> wrote in message
 news:g3gtvk$1tm7$1 digitalmars.com...

 Done :p

 http://dsource.org/projects/tango/changeset/3651


 In _adCmp,
 if (a1.ptr == a2.ptr)
     return 0;
 erm, that's not right at all.  Two slices with the same pointer and
 different lengths.


 Darnit, you're right.  Good catch.


 Sean


 After having a look at this I don't see how it could work.
 The TypeInfo passed to _adEq/Cmp is the *element* typeinfo, not the *array*


 typeinfo.

 With the current code, the way I read it, only arrays with elementsize==1 will


 work (and only

 if the element is not a 1byte struct that overloads the comparison operators.
 Am I missing something or should the compilers not be changed to pass the


 *array* typeinfo if

 these optimizations are to make any sense ?


 I was wondering about that.  *sigh* I guess I'll have to change it back then. 
How
 terribly annoying.


Hold on.  Why would that routine get the TypeInfo for the element and not the
array?  Similar typed arrays can only be compared anyway, and the differences
between static and sdynamic arrays are irrelevant for comparisons.  What am I
missing?  I'm inclined to just file a bug report asking that this be changed.


Sean
Jun 22 2008
parent reply Tomas Lindquist Olsen <tomas famolsen.dk> writes:
Sean Kelly wrote:

 == Quote from Sean Kelly (sean invisibleduck.org)'s article

 == Quote from Tomas Lindquist Olsen (tomas famolsen.dk)'s article

 Sean Kelly wrote:

 == Quote from Jarrett Billingsley (kb3ctd2 yahoo.com)'s article

 "Sean Kelly" <sean invisibleduck.org> wrote in message
 news:g3gtvk$1tm7$1 digitalmars.com...

 Done :p

 http://dsource.org/projects/tango/changeset/3651


 In _adCmp,
 if (a1.ptr == a2.ptr)
     return 0;
 erm, that's not right at all.  Two slices with the same pointer and
 different lengths.


 Darnit, you're right.  Good catch.


 Sean


 After having a look at this I don't see how it could work.
 The TypeInfo passed to _adEq/Cmp is the *element* typeinfo, not the *array*


 typeinfo.

 With the current code, the way I read it, only arrays with elementsize==1 will


 work (and only

 if the element is not a 1byte struct that overloads the comparison operators.
 Am I missing something or should the compilers not be changed to pass the


 *array* typeinfo if

 these optimizations are to make any sense ?


 I was wondering about that.  *sigh* I guess I'll have to change it back then. 
How
 terribly annoying.


 
 Hold on.  Why would that routine get the TypeInfo for the element and not the
 array?  Similar typed arrays can only be compared anyway, and the differences
 between static and sdynamic arrays are irrelevant for comparisons.  What am I
 missing?  I'm inclined to just file a bug report asking that this be changed.
 
 
 Sean


Yeah, after writing my reply I wondered a bit about this and went on and
changed LLVMDC to pass 
the array's typeinfo :)

There's really no reason no to make this change (besides forcing people to
recompile), the 
implementation becomes *both* cleaner and faster :)
Jun 22 2008
parent Sean Kelly <sean invisibleduck.org> writes:
== Quote from Tomas Lindquist Olsen (tomas famolsen.dk)'s article

 Sean Kelly wrote:

 == Quote from Sean Kelly (sean invisibleduck.org)'s article

 == Quote from Tomas Lindquist Olsen (tomas famolsen.dk)'s article

 Sean Kelly wrote:

 == Quote from Jarrett Billingsley (kb3ctd2 yahoo.com)'s article

 "Sean Kelly" <sean invisibleduck.org> wrote in message
 news:g3gtvk$1tm7$1 digitalmars.com...

 Done :p

 http://dsource.org/projects/tango/changeset/3651


 In _adCmp,
 if (a1.ptr == a2.ptr)
     return 0;
 erm, that's not right at all.  Two slices with the same pointer and
 different lengths.


 Darnit, you're right.  Good catch.


 Sean


 After having a look at this I don't see how it could work.
 The TypeInfo passed to _adEq/Cmp is the *element* typeinfo, not the *array*


 typeinfo.

 With the current code, the way I read it, only arrays with elementsize==1 will


 work (and only

 if the element is not a 1byte struct that overloads the comparison operators.
 Am I missing something or should the compilers not be changed to pass the


 *array* typeinfo if

 these optimizations are to make any sense ?


 I was wondering about that.  *sigh* I guess I'll have to change it back then.






 How

 terribly annoying.


 Hold on.  Why would that routine get the TypeInfo for the element and not the
 array?  Similar typed arrays can only be compared anyway, and the differences
 between static and sdynamic arrays are irrelevant for comparisons.  What am I
 missing?  I'm inclined to just file a bug report asking that this be changed.


 Sean


 Yeah, after writing my reply I wondered a bit about this and went on and
changed


LLVMDC to pass

 the array's typeinfo :)
 There's really no reason no to make this change (besides forcing people to


recompile), the

 implementation becomes *both* cleaner and faster :)


Yup.  I made the change without really thinking about it because I assumed this
is
how it was already implemented.  Oh well.  There are a bunch of weird little
quirks like this is the runtime.  If only I could fix the compiler when these
things come up as well :-p


Sean

P.S. http://d.puremagic.com/issues/show_bug.cgi?id=2161
Jun 22 2008
prev sibling next sibling parent "Unknown W. Brackets" <unknown simplemachines.org> writes:
This strikes me as fairly significant for, e.g., string comparison.  Am 
I crazy?

-[Unknown]


Jarrett Billingsley wrote:

 "Don" <nospam nospam.com.au> wrote in message 
 news:g3ggq5$ui5$1 digitalmars.com...
 

 What's it doing? Is it doing a byte-by-byte comparison? (it shouldn't do 
 that even for strings). Is it doing bounds checking for every array 
 element?? (even with -release -O)


 
 See dmd/src/phobos/internal/adi.d  The important function here is:
 
 extern (C) int _adEq(Array a1, Array a2, TypeInfo ti)
 {
     if (a1.length != a2.length)
         return 0;
 
     auto sz = ti.tsize();
     auto p1 = a1.ptr;
     auto p2 = a2.ptr;
 
     if (sz == 1)
         // We should really have a ti.isPOD() check for this
         return (memcmp(p1, p2, a1.length) == 0);
 
     for (size_t i = 0; i < a1.length; i++)
     {
         if (!ti.equals(p1 + i * sz, p2 + i * sz))
             return 0;
     }
 
     return 1;
 }
 
 If the size of an element is 1 (bytes, chars, bools), it just does memcmp. 
 There's even a comment in there that memcmp should be used if the type is 
 POD (plain old data, which uints are).  But otherwise, it uses the RTTI 
 .equals function to compare the elements, and it doesn't even use parallel 
 pointers, it does manual indexing for each element.  .equals will, for 
 uints, just return true if they are equal.
 
 What flabbergasts me is that in the uint[] typeinfo class, there is an 
 equals method that uses memcmp, but it's not used unless you explicitly call 
 it (or if you have a uint[][]).  Try doing
 
 bool b = typeid(uint[]).equals(&X[], &Y[]);
 
 and see what kind of performance you get.
Jun 20 2008
prev sibling parent reply "Bruce Adams" <tortoise_74 yeah.who.co.uk> writes:
On Fri, 20 Jun 2008 18:40:25 +0100, Jarrett Billingsley  =

<kb3ctd2 yahoo.com> wrote:


 "Don" <nospam nospam.com.au> wrote in message
 news:g3ggq5$ui5$1 digitalmars.com...


 What's it doing? Is it doing a byte-by-byte comparison? (it shouldn't=




 do

 that even for strings). Is it doing bounds checking for every array
 element?? (even with -release -O)


 See dmd/src/phobos/internal/adi.d  The important function here is:

 extern (C) int _adEq(Array a1, Array a2, TypeInfo ti)
 {
     if (a1.length !=3D a2.length)
         return 0;

     auto sz =3D ti.tsize();
     auto p1 =3D a1.ptr;
     auto p2 =3D a2.ptr;

     if (sz =3D=3D 1)
         // We should really have a ti.isPOD() check for this
         return (memcmp(p1, p2, a1.length) =3D=3D 0);

     for (size_t i =3D 0; i < a1.length; i++)
     {
         if (!ti.equals(p1 + i * sz, p2 + i * sz))
             return 0;
     }

     return 1;
 }


Eeek. This is no longer just a performance issues its a proper bug. For =
 =

user defined types
there is no guarantee that memcpy will return the same result as opEqual=
s.

E.g. Imagine a class with an id field to identify specific instances.

class foo
{
    int objectId;
    int value;
}

memcmp will compare objectId whereas your op equals would only compare t=
he  =

value.
Worse than that memcmp will fail for any object with a pointer.

Why has no-one screamed about this before?

Regards,

Bruce.
Jun 27 2008
parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Bruce Adams" <tortoise_74 yeah.who.co.uk> wrote in message 
news:op.udecoog1xikks4 starquake.cybernetics...
On Fri, 20 Jun 2008 18:40:25 +0100, Jarrett Billingsley
<kb3ctd2 yahoo.com> wrote:



 extern (C) int _adEq(Array a1, Array a2, TypeInfo ti)
 {
     if (a1.length != a2.length)
         return 0;

     auto sz = ti.tsize();
     auto p1 = a1.ptr;
     auto p2 = a2.ptr;

     if (sz == 1)
         // We should really have a ti.isPOD() check for this
         return (memcmp(p1, p2, a1.length) == 0);

     for (size_t i = 0; i < a1.length; i++)
     {
         if (!ti.equals(p1 + i * sz, p2 + i * sz))
             return 0;
     }

     return 1;
 }


there is no guarantee that memcpy will return the same result as opEquals.

...

Why has no-one screamed about this before?
-----------------

Because that's not how the above function works?  It only calls memcmp if 
the compared array has elements of size 1 -- that is, byte[], ubyte[], and 
char[].  For all other types, it calls ti.equals, which will call the opCmp 
method of classes/structs, if any.
Jun 27 2008
parent reply Robert Fraser <fraserofthenight gmail.com> writes:
Jarrett Billingsley wrote:

 "Bruce Adams" <tortoise_74 yeah.who.co.uk> wrote in message 
 news:op.udecoog1xikks4 starquake.cybernetics...
 On Fri, 20 Jun 2008 18:40:25 +0100, Jarrett Billingsley
 <kb3ctd2 yahoo.com> wrote:
 
 

 extern (C) int _adEq(Array a1, Array a2, TypeInfo ti)
 {
     if (a1.length != a2.length)
         return 0;

     auto sz = ti.tsize();
     auto p1 = a1.ptr;
     auto p2 = a2.ptr;

     if (sz == 1)
         // We should really have a ti.isPOD() check for this
         return (memcmp(p1, p2, a1.length) == 0);

     for (size_t i = 0; i < a1.length; i++)
     {
         if (!ti.equals(p1 + i * sz, p2 + i * sz))
             return 0;
     }

     return 1;
 }


 
 there is no guarantee that memcpy will return the same result as opEquals.
 
 ...
 
 Why has no-one screamed about this before?
 -----------------
 
 Because that's not how the above function works?  It only calls memcmp if 
 the compared array has elements of size 1 -- that is, byte[], ubyte[], and 
 char[].  For all other types, it calls ti.equals, which will call the opCmp 
 method of classes/structs, if any. 


How about a struct of size 1?:
Jun 27 2008
parent "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Robert Fraser" <fraserofthenight gmail.com> wrote in message 
news:g42rt1$2h9r$1 digitalmars.com...

 How about a struct of size 1?:


...

Shut up.  ;)
Jun 27 2008
prev sibling parent reply Sean Kelly <sean invisibleduck.org> writes:
== Quote from Don (nospam nospam.com.au)'s article

 I've been doing some timing tests, and found that the built-in array
 comparison is amazingly slow.
 Given:
 uint [2000] X, Y;
 bool b = (X[] == Y[]);
 on my Pentium M, this takes ~30000 cycles in the case where both arrays
 are equal.
 It's not hard to write an optimal asm routine; this takes 4000 cycles
 (7.5 times faster).
 But, it's also possible to perform the comparison in simple D code,
 something like:
 int compareArrays(uint [] x, uint y[])
 {
      for (int i=0; i<x.length; ++i) {
          if (x[i] != y[i]) return x[i]-y[i];
      }
      return 0;
 }
 and this takes 6000 cycles when compiled with -release -O, 5X better
 than the built-in version.
 So, why is the built-in compare so slow? Using the CPU performance counters:
 X[]==Y[] --> 10000 branches, 35000 memory loads, 30000 cycles.
 for loop --> 4000 branches, 6000 memory loads, 6000 cycles.
 asm      --> 4000 branches, 4000 memory loads, 4000 cycles.
 What's it doing? Is it doing a byte-by-byte comparison? (it shouldn't do
 that even for strings). Is it doing bounds checking for every array
 element?? (even with -release -O)
 There's significant optimisation potential here.


You can look at:

http://dsource.org/projects/phobos/browser/trunk/phobos/std/typeinfo/ti_Aint.d

And see exactly what it's doing for uint[].  See TypeInfo_Ai.equals().

Are the braces really necessary for the comparison though?  I'd just do "X ==
Y."
I wouldn't expect a speed difference, but the cycle count has be wondering if
by adding the braces the generated code is cloning the arrays before comparing
them or something like that.


Sean
Jun 20 2008
parent reply downs <default_357-line yahoo.de> writes:
Sean Kelly wrote:

 Are the braces really necessary for the comparison though?  I'd just do "X ==
Y."
 I wouldn't expect a speed difference, but the cycle count has be wondering if
 by adding the braces the generated code is cloning the arrays before comparing
 them or something like that.
 


No, array[] is just the full slice, i.e. the equivalent of [0 .. $].

It's useful for static arrays, as it effectively turns them into dynamic ones.


 
 Sean


--downs
Jun 20 2008
parent reply torhu <no spam.invalid> writes:
downs wrote:

 Sean Kelly wrote:

 Are the braces really necessary for the comparison though?  I'd just do "X ==
Y."
 I wouldn't expect a speed difference, but the cycle count has be wondering if
 by adding the braces the generated code is cloning the arrays before comparing
 them or something like that.
 


 No, array[] is just the full slice, i.e. the equivalent of [0 .. $].
 
 It's useful for static arrays, as it effectively turns them into dynamic ones.
 


I wish you didn't say that.  Yet another undocumented feature to try to 
remember?
Jun 21 2008
parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"torhu" <no spam.invalid> wrote in message 
news:g3katb$14ee$1 digitalmars.com...

 downs wrote:

 Sean Kelly wrote:

 Are the braces really necessary for the comparison though?  I'd just do 
 "X == Y."
 I wouldn't expect a speed difference, but the cycle count has be 
 wondering if
 by adding the braces the generated code is cloning the arrays before 
 comparing
 them or something like that.


 No, array[] is just the full slice, i.e. the equivalent of [0 .. $].

 It's useful for static arrays, as it effectively turns them into dynamic 
 ones.


 I wish you didn't say that.  Yet another undocumented feature to try to 
 remember?


It's not undocumented.  Look at the first slicing example here: 
http://www.digitalmars.com/d/1.0/arrays.html
Jun 21 2008
parent torhu <no spam.invalid> writes:
Jarrett Billingsley wrote:

 "torhu" <no spam.invalid> wrote in message 
 news:g3katb$14ee$1 digitalmars.com...

 downs wrote:

 Sean Kelly wrote:

 Are the braces really necessary for the comparison though?  I'd just do 
 "X == Y."
 I wouldn't expect a speed difference, but the cycle count has be 
 wondering if
 by adding the braces the generated code is cloning the arrays before 
 comparing
 them or something like that.


 No, array[] is just the full slice, i.e. the equivalent of [0 .. $].

 It's useful for static arrays, as it effectively turns them into dynamic 
 ones.


 I wish you didn't say that.  Yet another undocumented feature to try to 
 remember?


 
 It's not undocumented.  Look at the first slicing example here: 
 http://www.digitalmars.com/d/1.0/arrays.html 
 
 


I guess I was just a bit too tired when posting.  It doesn't turn them 
into dynamic arrays, it's still just a slice into a static array. 
Anyway, value comparison is defined to be the same for both static and 
dynamic arrays.
Jun 22 2008