faster splitter

[qznc via Digitalmars-d]

On Saturday, 28 May 2016 at 01:30:11 UTC, Andrei Alexandrescu 
wrote:
> On 05/27/2016 06:19 PM, qznc wrote:
>> 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.
>
> What compiler?

LDC. For DMD the numbers show no improvement:

std find:    170 ±31
manual find: 132 ±25
qznc find:   103 ±6
Chris find:  157 ±30

to

std find:    168 ±30
manual find: 131 ±25
qznc find:   104 ±8    <--- sentinel
Chris find:  155 ±29

(Caveat: Chris find has a bug, which is triggered once in the 
10000 runs each.)

The sentinel trick is only proof of concept. 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.

>> This means another special case for mutable ranges could be 
>> worthwhile.
>
> Also mind the throwing possibilities.

What do you mean? Using exceptions?


If anybody wants to replicate. It only takes a few seconds and 
there are no dependencies except dmd/ldc.

   git clone https://github.com/qznc/find-is-too-slow
   cd find-is-too-slow
   make dmd
   make ldc