Success! Find is slow no more

[Michael Brown]

Hi All,

I saw the blog post regarding the improvements to find three 
years ago. Attempted to improve upon it and failed miserably.

After watching Andrei's recent talk on fastware (when is the book 
coming out??) I thought id have another go at it. Success! I'm 
getting a 5-10% improvement over the Phobos find() on all tests - 
and it beats all over tested alternatives too.

Compiled with DMD on windows.

Search in Alice in Wonderland
        std: 103 ±1
     manual: 126 ±2
   A2Phobos: 111 ±2
      Chris: 136 ±2
     Andrei: 298 ±3
    Andrei2: 140 ±1
     Faster: 100 ±0
Search in random short strings
        std: 125 ±6
     manual: 134 ±9
   A2Phobos: 104 ±4
      Chris: 136 ±11
     Andrei: 123 ±11
    Andrei2: 110 ±6
     Faster: 101 ±2
Mismatch in random long strings
        std: 109 ±8
     manual: 183 ±66
   A2Phobos: 116 ±9
      Chris: 199 ±77
     Andrei: 331 ±140
    Andrei2: 143 ±19
     Faster: 100 ±0
Search random haystack with random needle
        std: 110 ±7
     manual: 151 ±26
   A2Phobos: 119 ±11
      Chris: 165 ±34
     Andrei: 261 ±51
    Andrei2: 145 ±17
     Faster: 101 ±2
  (avg slowdown vs fastest; absolute deviation)
CPU ID: GenuineIntel Celeron(R) Dual-Core CPU       T3500  @ 
2.10GHz

Full code here: https://github.com/mikey-b/find-is-too-slow - 
method is faster_find()

In short, it was achieved with

* Better branch prediction - The if's and loops have been 
rearranged to promote the hot path's.
* Loop unrolling - I have unrolled the loop once, so that Skip 
can be calculated on the first failure, allowing us to remove the 
branch in future iterations needed to test skip's lazy evaluation.

Kind Regards,
Mike Brown