faster splitter

[qznc via Digitalmars-d]

On Friday, 27 May 2016 at 18:21:06 UTC, Andrei Alexandrescu wrote:
> What you want to do here for indexed access is to match the 
> last element first. If no match, continue etc. If there's a 
> match, enter an inner loop where you don't need to check for 
> the end of the haystack. -- Andrei

Another plot twist: Sentinels look interesting.

Wilzbach [0] mentioned it in the pull request:
"Btw on a related issue - it seems like no one has actually 
bother to implement Andrei's "Fastware" sentinels in Phobos. If 
you are already in benchmarking, you might give this 
specialization for mutable RandomAccessRanges a try ;-)"

I tried it [1]. It changes the numbers from

std find:    153 ±32
manual find: 112 ±19
qznc find:   121 ±18
Chris find:  132 ±20

to

std find:    160 ±31
manual find: 118 ±24
qznc find:   109 ±13  <--- using the sentinel trick
Chris find:  142 ±27

It is normal that the numbers of the other tests change, since 
those are relative to the fastest one in each run. When qznc find 
'wins' more often, the others get more slowdown.

This means another special case for mutable ranges could be 
worthwhile.

[0] 
https://github.com/dlang/phobos/pull/4362#issuecomment-222224387
[1] 
https://github.com/qznc/find-is-too-slow/commit/043d1d2f6dced625e964e8df883ad5a45d7fe654