我有一些高度敏感的代码.使用SSEn和AVX的SIMD实现使用大约30条指令,而使用4096字节查找表的版本使用大约8条指令.在微基准测试中,查找表的速度提高了40%.如果我使用microbenchmark,试图使缓存无效100次迭代,它们看起来大致相同.在我的真实程序中,看起来非加载版本更快,但是很难获得可靠的良好测量,并且我已经进行了两种测量.
我只是想知道是否有一些好方法可以考虑哪种方法更适合使用,或者用于此类决策的标准基准测试技术.
我正在尝试使用SIMD内在函数编写流压缩(获取数组并删除空元素).循环的每次迭代一次处理8个元素(SIMD宽度).
使用SSE内在函数,我可以使用_mm_shuffle_epi8()进行相当有效的操作,它执行16条表查找(收集并行计算术语).shuffle索引是预先计算的,并使用位掩码查找.
for (i = 0; i < n; i += 8)
{
v8n_Data = _mm_load_si128(&data[i]);
mask = _mm_movemask_epi8(&is_valid[i]) & 0xff; // is_valid is byte array
v8n_Compacted = _mm_shuffle_epi8(v16n_ShuffleIndices[mask]);
_mm_storeu_si128(&compacted[count], v8n_Compacted);
count += bitCount[mask];
}
我的问题是现在我想为Altivec SIMD实现这个(不要问为什么 - 错误的商业决策).Altivec没有_mm_movemask_epi8()的等价物,这是一个关键因素.所以,我需要找到一种方法
模拟_mm_movemask_epi8() - 似乎很贵,有几个班次和OR
直接生成有效的shuffle指数 -
即,索引i将是未压缩数据中第i个有效元素的索引
element_valid: 0 0 1 0 1 0 0 1 0
gather_indices: x x x x x x 6 4 1
scatter_indices: 3 3 2 2 1 1 1 0 0
串行执行此操作非常简单,但我需要它是并行(SIMD).使用前缀sum生成散列索引似乎很容易,但由于AltiVec和SSE都没有散点指令,我需要收集索引.收集索引是散射指数的反函数,但是如何并行获得？我知道在GPU编程的开创性时代,将散射转换为收集是一种常见的技术,但这两种方法中没有一种看似实用.
也许如果不坚持压缩保留元素顺序将允许更有效的实现？我可以放弃.
我有一个字节数组
unsigned char* array=new unsigned char[4000000];
...
我想得到数组中所有非零元素的索引.
当然,我可以做到以下
for(int i=0;i<size;i++)
{
if(array[i]!=0) somevector.push_back(i);
}
有比这更快的算法吗？
更新1我可以看到多数回答是否定的.我希望有一些我不知道的神奇位操作.有些人建议排序,但在这种情况下并不可行.但是非常感谢你的所有答案.
更新2自此问题发布4年零4个月后,@ wim建议这个答案看起来很有希望.
我使用SIMD指令运行一系列计算。这些指令返回一个16字节的向量，结果为compare，每个字节为0x00或0xff：
0 1 2 3 4 5 6 7 15 16
compare : 0x00 0x00 0x00 0x00 0xff 0x00 0x00 0x00 ... 0xff 0x00
设置为字节的0xff意思是我需要以do_operation(i) i作为字节的位置来运行该函数。
例如，上述compare向量意味着，我需要运行以下操作序列：
do_operation(4);
do_operation(15);
这是到目前为止我想到的最快的解决方案：
for(...) {
//
// SIMD computations
//
__m128i compare = ... // Result of SIMD computations
// Extract high and low quadwords for compare vector
std::uint64_t cmp_low = (_mm_cvtsi128_si64(compare));
std::uint64_t cmp_high = (_mm_extract_epi64(compare, 1));
// Process low quadword …