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

[Sean Kelly]

== Quote from Don (nospam at 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