3 ms·

For 8192 elements I also get result that their search function is faster than STL. But 8192 elements is tiny size of array where to search, for larger array I g

For 8192 elements I also get result that their search function is faster than STL. But 8192 elements is tiny size of array where to search, for larger array I get opposite - STL is faster. Here is output for 8 * 1024 * 1024 elements (~8.4million). gcc 5.2.0 on Windows x64 (i5-3210M) stl : 881 miliseconds version 1: 880 miliseconds version 2: 1607 miliseconds version 3: 1260 miliseconds version 4: 1271 miliseconds gcc 5.2.0 on Linux x86_64 (i7-4770S) stl : 629.231 miliseconds version 1: 629.436 miliseconds version 2: 897.143 miliseconds version 3: 862.827 miliseconds version 4: 863.22 miliseconds clang 3.6.2 on Linux armv7h (CuBox-i, Cortex-A9) stl : 3380.29 miliseconds version 1: 3428.9 miliseconds version 2: 3433.65 miliseconds version 3: 3391.86 miliseconds version 4: 3376.91 miliseconds Oh, and Visual Studio doesn't have "/O3" argument they say they are using for cl.exe.

nhaehnle 11y ago
This is fascinating. Do you have any idea what might cause this? A shot in the dark: Their benchmarking uses a very simple "random" generation to choose the index to search for, which is actually just a linear scan (modulo the size of the array). Could it be that with the larger array, the generated sequence of test indices happens to work nicely with the CPU's branch prediction - after all, your results show a performance drop-off for the versions that use conditional moves, and the behavior depends suspiciously on the CPU microarchitecture.