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