Playing SIMD

[Iakh via Digitalmars-d]

On Monday, 26 October 2015 at 11:47:56 UTC, Andrei Alexandrescu 
wrote:
> On 10/26/2015 05:48 AM, Iakh wrote:
>> On Monday, 26 October 2015 at 00:00:45 UTC, anonymous wrote:
>>> runBinary calls naiveIndexOf. You're not testing 
>>> binaryIndexOf.
>>
>> You are right.
>> This is fixed example:
>> http://dpaste.dzfl.pl/f7a54b789a21
>>
>> and results at dpaste.dzfl.pl:
>> -----
>> SIMD:   TickDuration(151000)
>> Binary: TickDuration(255000)
>> Naive:  TickDuration(459000)
>>
>> So SIMD version ~1.68 faster than binary
>
> That's a healthy margin. It may get eroded by startup/finish 
> codes that need to get to the first aligned chunk and handle 
> the misaligned data at the end, etc. But it's a solid proof of 
> concept. -- Andrei

(Binary)Searching in large sorted continuous array e. g. 1 MB of 
bytes
1 MB = 2 ^^ 20 bytes
Imagine 4 binary levels pass in 4 ticks. So 20 levels in 20 
ticks. With SIMD last 4 levels would be done in 2 or 3 ticks. For 
20 levels 18 - 19 ticks. So overall improvement is 5-10%. 
Furthermore think of cache and memory pages misses on firs levels.

IMO SIMD needed for unsorted data(strings?) or for trees.