faster splitter

[qznc via Digitalmars-d]

On Tuesday, 24 May 2016 at 09:34:30 UTC, Chris wrote:
> On Tuesday, 24 May 2016 at 07:54:38 UTC, qznc wrote:
>> Apart from advanced algorithms, find should not be slower than 
>> a naive nested-for-loop implementation.
>>
>> [0] https://issues.dlang.org/show_bug.cgi?id=16066
>
> From Phobos [1]:
>
>         /* Preprocess #2: init skip[] */
>         /* Note: This step could be made a lot faster.
>         * A simple implementation is shown here. */
>         this.skip = new size_t[needle.length];
>         foreach (a; 0 .. needle.length)
>         {
>             size_t value = 0;
>             while (value < needle.length
>                    && !needlematch(needle, a, value))
>             {
>                 ++value;
>             }
>             this.skip[needle.length - a - 1] = value;
>         }
>
> [1] 
> https://github.com/dlang/phobos/blob/master/std/algorithm/searching.d#L335

Unfortunately, it is slower. My current measurements [0]:

$ ./benchmark 10000000 10 # large haystack, few iterations
std find    took    753837231
manual find took    129561980
$ ./benchmark 10 10000000 # small haystack, many iterations
std find    took    721676721
manual find took    216418870

The nested-for-loop implementation is roughly 4 times faster!

Caveat: I'm not completely sure my benchmark is fair yet.

[0] https://github.com/qznc/find-is-too-slow