faster splitter

[Chris via Digitalmars-d]

On Sunday, 29 May 2016 at 12:22:23 UTC, qznc wrote:
> I played around with the benchmark. Some more numbers:
>
> $ make ldc
> ldmd2 -O -release -inline -noboundscheck *.d -ofbenchmark.ldc
> ./benchmark.ldc
> E: wrong result with Chris find
> E: wrong result with Chris find
> E: wrong result with Chris find
>     std find: 153 ±25    +66 (1934)  -15 (7860)
>  manual find: 122 ±28    +80 (1812)  -17 (8134)
>    qznc find: 125 ±16    +18 (4644)  -15 (5126)
>   Chris find: 148 ±29    +75 (1976)  -18 (7915)
>  Andrei find: 114 ±23   +100 (1191)  -13 (8770)
>  (avg slowdown vs fastest; absolute deviation)
> $ make dmd
> dmd -O -release -inline -noboundscheck *.d -ofbenchmark.dmd
> ./benchmark.dmd
> E: wrong result with Chris find
> E: wrong result with Chris find
> E: wrong result with Chris find
>     std find: 160 ±27    +44 (3162)  -20 (6709)
>  manual find: 148 ±28    +54 (2701)  -19 (7178)
>    qznc find: 102 ±3     +27 ( 766)   -1 (9136)
>   Chris find: 175 ±30    +55 (2796)  -21 (7106)
>  Andrei find: 122 ±22    +46 (2554)  -14 (7351)
>  (avg slowdown vs fastest; absolute deviation)
>
> The additional numbers on the right are the ±MAD separated by 
> above or below the mean. For example Andrei find with ldc:
>
>   Andrei find: 114 ±23   +100 (1191)  -13 (8770)
>
> The mean slowdown is 114, which means 14% slower than the 
> fastest one. The mean absolute deviation (MAD) is 23. More 
> precisely, the mean deviation above the mean slowdown of 103 is 
> 100 and -13 below the mean slowdown. 1191 of the 10000 runs 
> were above the mean slowdown and 8770 below. The 39 missing 
> runs are equal to the mean slowdown.
>
> What bothers me is that changing the alphabet changes the 
> numbers so much. Currently, if you restrict the alphabets for 
> haystack and needle, the numbers change. The benchmark already 
> does a random subset on each run, but there is definitely a 
> bias.

You can avoid "E: wrong result with Chris find" by using

outer:
     for (auto i = 0; i < haystack.length-needle.length; i++)
     {
         if (haystack[i] != needle[0])
             continue;
         for (size_t j = i+1, k = 1; k < needle.length; ++j, ++k)
             if (haystack[j] != needle[k])
                 continue outer;
         return haystack[i..$];
     }

It's a tad faster.

I'm planning to test on more varied data and see where a bias may 
occur.