faster splitter

[qznc via Digitalmars-d]

On Saturday, 28 May 2016 at 12:47:59 UTC, Andrei Alexandrescu 
wrote:
> On 5/28/16 6:56 AM, qznc wrote:
>> The sentinel value is `needleBack+1`, but range elements need 
>> not
>> support addition. Finding a sentinel is hard and most 
>> certainly requires
>> more assumptions about the ranges.
>
> No need for a sentinel really so long as you first search for 
> the last element of the needle, in the haystack.
>
> Allow me to put on the table a simple brute force routine, 
> specialized for arrays with copyable elements, no custom 
> predicate etc. Far as I can tell it does no redundant work:

A nice one. Here are the numbers I got:

LDC:
     std find:	156 ±33
  manual find:	117 ±24
    qznc find:	114 ±14
   Chris find:	135 ±24
  Andrei find:	112 ±27

DMD:
     std find:	177 ±31
  manual find:	140 ±28
    qznc find:	102 ±4
   Chris find:	165 ±31
  Andrei find:	130 ±25

My sentinel idea is to have only one condition branch in the 
inner loop. Andrei find still has to `if` in the inner loop. My 
inner loop looks like this:

   haystack[scout] = cast(typeof(needleBack)) (needleBack+1); // 
place sentinel
   for (size_t j = scout + 1 - needleLength, k = 0;; ++j, ++k) { 
// no condition
     if (!binaryFun!pred(haystack[j], needle[k])) { // only 
condition
       // ... ok in here comes another, but this not as costly
     }
   }

As long as you are matching the needle, there is only one 
condition to check. There is no check for k < needleLength, 
because the check always fails for needle[$] aka haystack[scout] 
due to the sentinel.

I thought it might be slower, since we need to write to memory 
twice instead of only reading. Turns out it is faster.