I'm working on an application for which a highly optimized linear search will make a big difference in the overall performance, and I've been tasked with improving performance as much as I can.
I'm running my search on a vector of 10,000 elements that is bounded by sentinel values at the end, I run the linear search at some constant distance from the target element and measure the time it took to find the element. I choose the target elements randomly from the set of elements what are after that constant distance from the beginning of the array to allow for the beginning of the search. I'm measuring the performance using Google's benchmark framework.
The results that I've collected surprise me. I expected that at some point SIMD would beat an unrolled loop for performance, but the gap between the two appears to be growing as the distance needed to travel the array grows. Additionally, I'm not sure why the loop that has been unrolled 8 times runs faster on shorter distances than the loop unrolled 32 times.
Benchmark Time CPU Iterations
---------------------------------------------------------------------
BM_Search<linUnroll<8>>/2 86 ns 86 ns 7699241
BM_Search<linUnroll<8>>/4 103 ns 103 ns 6797378
BM_Search<linUnroll<8>>/16 650 ns 650 ns 1079095
BM_Search<linUnroll<8>>/64 1365 ns 1365 ns 514196
BM_Search<linUnroll<8>>/256 3558 ns 3558 ns 196519
BM_Search<linUnroll<8>>/1024 12358 ns 12358 ns 56635
BM_Search<linUnroll<8>>/4096 47341 ns 47341 ns 14780
BM_Search<linUnroll<8>>/8192 95029 ns 95030 ns 7367
BM_Search<linUnroll<32>>/2 131 ns 131 ns 5337221
BM_Search<linUnroll<32>>/4 131 ns 131 ns 5329296
BM_Search<linUnroll<32>>/16 291 ns 291 ns 2404646
BM_Search<linUnroll<32>>/64 836 ns 836 ns 831093
BM_Search<linUnroll<32>>/256 2776 ns 2776 ns 252901
BM_Search<linUnroll<32>>/1024 10962 ns 10962 ns 63828
BM_Search<linUnroll<32>>/4096 41312 ns 41312 ns 16941
BM_Search<linUnroll<32>>/8192 83303 ns 83304 ns 8401
BM_Search<linSIMD>/2 163 ns 163 ns 4304086
BM_Search<linSIMD>/4 208 ns 208 ns 3354716
BM_Search<linSIMD>/16 366 ns 366 ns 1912122
BM_Search<linSIMD>/64 871 ns 871 ns 803854
BM_Search<linSIMD>/256 3333 ns 3334 ns 210159
BM_Search<linSIMD>/1024 11262 ns 11262 ns 62157
BM_Search<linSIMD>/4096 42656 ns 42656 ns 16413
BM_Search<linSIMD>/8192 87824 ns 87824 ns 7970
I'm running on an i5-4570, and I've complied with clang 5.0.0. quick-bench doesn't have AVX, and clang doesn't fully unroll in version 3.8, but it should be runnable. I tried unrolling the SIMD also, as well as going to AVX256 instructions, but both made the performance worse. Why is it that the unrolled loop is so much faster? Why is it that the loop with more unrolling performs so dramatically worse than the loop with less unrolling?
The classic diagnosis for SIMD is that you're not doing enough work in SIMD, but I think I'm doing enough work here.
#include <vector>
#include <cinttypes>
#include <immintrin.h>
typedef int V;
typedef std::vector<V> vi;
long linSIMD(const vi& arr, const long guessIx, const V x) {
using v4 = V __attribute__ ((vector_size (4*4)));
using dv2 = int64_t __attribute__ ((vector_size (4*4)));
constexpr int roll = 4;
constexpr union {
int32_t i32[2];
int64_t i64;
} skip = {-2,-2};
v4 xVec = {x,x,x,x};
for (int i = guessIx;; i += roll) {
v4 arrVec;
for (long j = 0; j < 4; j++) arrVec[j] = arr[i+j];
union {
v4 i32;
dv2 i64;
} cmpVec = {arrVec < xVec};
v4 cmpVec2 = {cmpVec.i32[3], cmpVec.i32[2], cmpVec.i32[1],cmpVec.i32[0]};
cmpVec.i32 += cmpVec2;
if (cmpVec.i64[0] == skip.i64) continue;
return i - cmpVec.i32[0] - cmpVec.i32[1];
}
}
long linUnroll32(const vi& arr, const long guessIx, const V x) {
constexpr int roll = 32;
for (long i = guessIx;; i += roll)
for (long j = 0; j < roll; j++)
if (arr[i+j] >= x) return i+j;
}
http://quick-bench.com/_x_v_WXLWtwvvLsObNlIxjXxS_g https://godbolt.org/g/Wyx2pS