我正在开发一个应用程序,该应用程序的高度优化的线性搜索将对整体性能产生很大的影响,并且我一直在尽最大努力提高性能。
我在由10,000个元素组成的 vector 上运行搜索,该 vector 最后由哨兵值界定。我在距目标元素一定距离处运行线性搜索,并测量找到该元素所花费的时间。我从一组元素中随机选择目标元素,该元素距数组开头的恒定距离是多少,以允许开始搜索。我正在使用Google's benchmark framework测量性能。
我收集的结果令我惊讶。我希望SIMD在某个时候能克服性能上的障碍,但是随着行进阵列所需距离的增加,两者之间的差距似乎会越来越大。此外,我不确定为什么展开了8次的循环在较短的距离上比展开32次的循环更快。
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
我在i5-4570上运行,并且符合clang 5.0.0。 quick-bench没有AVX,并且clang在3.8版中没有完全展开,但是它应该是可运行的。我也尝试展开SIMD以及转到AVX256指令,但是两者都使性能变差。为什么展开的循环这么快?为什么展开次数更多的循环比展开次数更少的循环表现得如此糟糕?
SIMD的经典诊断是您在SIMD中做的工作不够,但是我认为我在这里做的工作足够。
#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
最佳答案
我能做的最好的事情(请参阅quick-bench上的结果)是这样的,
int linSIMD4(const vi& arr, const int guessIx, const int x) {
auto vecX = _mm_set1_epi32(x - 1);
const int *ptr = arr.data();
int i = guessIx;
// unaligned start
int misalignment = (uintptr_t)(ptr + i) & 15;
auto arrVec = _mm_loadu_si128((__m128i*)(ptr + i));
auto cmp = _mm_cmpgt_epi32(arrVec, vecX);
int mask = _mm_movemask_ps(_mm_castsi128_ps(cmp));
if (mask)
return i + __builtin_ctz(mask);
// continue with aligned part
i += (16 - misalignment) / 4;
for (; ; i += 16) {
auto av0 = _mm_load_si128((__m128i*)(ptr + i));
auto av1 = _mm_load_si128((__m128i*)(ptr + i + 4));
auto av2 = _mm_load_si128((__m128i*)(ptr + i + 8));
auto av3 = _mm_load_si128((__m128i*)(ptr + i + 12));
auto cmp0 = _mm_cmpgt_epi32(av0, vecX);
auto cmp1 = _mm_cmpgt_epi32(av1, vecX);
auto cmp2 = _mm_cmpgt_epi32(av2, vecX);
auto cmp3 = _mm_cmpgt_epi32(av3, vecX);
auto cmp = _mm_packs_epi16(_mm_packs_epi32(cmp0, cmp1), _mm_packs_epi32(cmp2, cmp3));
int mask = _mm_movemask_epi8(cmp);
if (mask)
return i + __builtin_ctz(mask);
}
}
基本上是geza描述的内容,但是我添加了一个特殊的第一次迭代,以便为主循环对齐数据。跨缓存行边界(或页面边界)的加载较慢,这可以消除它们。小距离(没有足够的慢速负载)的开销是不值得的,另一方面,小距离(小于4)的开销应该又更快。
我还尝试过使用
linSIMD5
翻转条件((a >= b) = !(b > a)
),并使用无损AVX编码,该编码将允许合并vcmpgtd
和负载(减少融合域中的µops),但是快速测试台并不会执行AVX,因此忽略结果,然后自己尝试。底部有一个AVX2版本,我没有尝试过或对其进行过基准测试。它不使用加载/比较合并技巧(可能有帮助也可能没有帮助),但很容易适应。