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.
