将short数组快速降级为char的最快方法

Question

将short数组快速降级为char的最快方法

3

我需要每秒处理大约2000个100元素的数组。这些数组以shorts的形式传递给我，数据存在高位中，需要进行移位和强制转换成chars类型。这是我能得到的最高效的方法，还是有更快的方式来执行此操作？（我需要跳过其中2个值）

for(int i = 0; i < 48; i++)
{
    a[i] = (char)(b[i] >> 8);
    a[i+48] = (char)(b[i+50] >> 8);
}

- pyInTheSky

你的基准测试告诉了你什么？如果你没有进行基准测试，那么你在这里就会盲目射击。将8位值向左移动8位似乎有问题。 - tadman

1

我猜你的意思是(char)(b[i] >> 8);。 - SergeyA

那段代码不能像预期的那样工作，因为强制类型转换的运算符优先级高于移位操作。 - Some programmer dude

1

为什么不将源代码重新转换为“char”，直接提取所需的值，而不是进行位移？只需确保您正确获取了尾数码即可。 - tadman

必须按照其他人的接口来操作 : \ - pyInTheSky

显示剩余8条评论

2个回答

1

你可以在这些数组周围放一个包装类，这样访问包装器的元素的代码就实际上访问了底层内存的每个其他字节。

但这可能会破坏自动向量化。除此之外，所有读取`a`的代码都要改为读取`b`并把指针增加两个字节而不是一个字节，这不应该改变成本。

然而，跳过的两个元素是问题。如果你的`operator[]`执行`if (i>=48) i+=2`，那么这个想法可能无效。使用`memmove`一次存储一个字节通常比一次存储一个字节更快得多，因此您可以考虑使用`memmove`使短整型的连续数组，即使看起来没有以更好的格式存储也可以进行索引。

关键是编写一个完全优化掉循环中的所有额外指令的包装器。在x86上，缩放索引在asm指令的常规有效地址中可用，因此如果编译器理解正在发生的事情，则它可以生成同样有效的代码。

有一组short数组将占用两倍的内存，因此缓存效应可能很重要。

所有这些都取决于您需要对字节数组执行什么操作。

如果需要转换，请使用SIMD

对于x86目标，您可以使用SIMD向量而不是逐个字符循环来获得大幅加速。对于其他您关心的编译目标，您可以编写类似的特殊版本。例如，我假设ARM NEON具有类似的洗牌功能。

在编写特定于平台的版本时，您还可以做出所有在该平台上为真的字节序和未对齐访问的假设。

#ifdef __SSE2__  // will be true for all x86-64 builds and most i386 builds
#include <immintrin.h>
static __m128i pack2(const short *p) {
    __m128i lo = _mm_loadu_si128((__m128i*)p);
    __m128i hi = _mm_loadu_si128((__m128i*)(p + 8));
    lo = _mm_srli_epi16(lo, 8);         // logical shift, not arithmetic, because we need the high byte to be zero
    hi = _mm_srli_epi16(hi, 8);
    return _mm_packus_epi16(lo, hi);    // treats input as signed, saturates to unsigned 0x0 .. 0xff range
}
#endif // SSE2

void conv(char *a, const short *b) {
#ifdef __SSE2__
    for(int i = 0; i < 48; i+=16) {
        __m128i low  = pack2(b+i);
        _mm_storeu_si128((__m128i *)(a+i), low);
        __m128i high = pack2(b+i + 50);
        _mm_storeu_si128((__m128i *)(a+i + 48), high);
    }
#else
    /*******   Fallback C version  *******/
    for(int i = 0; i < 48; i++) {
        a[i] = (char)(b[i] >> 8);
        a[i+48] = (char)(b[i+50] >> 8);
    }
#endif
}

正如您在Godbolt Compiler Explorer上看到的那样, 当每次存储16B时，gcc完全展开了循环，因为只有几次迭代。

这应该可以正常运行，但在Skylake之前的处理器上，将两个short向量进行移位后再存储会出现瓶颈。Haswell每个时钟周期只能维持一个psrli。(当移位计数是立即数时，Skylake可以维持每0.5个时钟周期一个。请参见Agner Fog的指南和insn表，链接在x86标签wiki中。)

从(__m128i*)(1 + (char*)p)加载可能会获得更好的结果，因此我们想要的字节已经在每个16位元素的低半部分中。我们仍然需要使用_mm_and_si128屏蔽掉每个元素的高半部分，而不是移位，但PAND可以在任何向量执行端口上运行，因此它具有每个时钟周期的三倍吞吐量。

更重要的是，使用AVX可以与未对齐加载结合。例如：vpand xmm0, xmm5, [rsi]，其中xmm5是_mm_set1_epi16(0x00ff)的掩码，[rsi]保存2*i + 1 + (char*)b。融合域uop吞吐量可能会成为一个问题，就像常见于具有大量加载/存储和计算的代码一样。

未对齐访问比对齐访问略慢，但至少一半的向量访问都将是未对齐的（因为跳过两个short意味着跳过4B）。在Intel SnB系列CPU上，我认为将负载分割成15:1与12:4相比，并不会使跨越缓存行边界的负载变慢。（当然，没有分割的情况肯定更快。）如果b是16B对齐的，则测试掩码版本与移位版本将很值得。

我没有为这个版本编写完整的代码，因为如果您不采取特殊预防措施，您将会读取b后面一字节的内容。如果您确保b有某种填充以使其不会到达内存页的末尾，那么这是可以接受的。

AVX2

在AVX2中，vpackuswb ymm在两个独立的通道中操作。不知道是否有必要对256b向量进行加载和掩码处理（或移位），然后使用vextracti128并在256b向量的两个半部分上进行128b打包。

或者将两个向量之间进行256b打包，然后使用vpermq（_mm256_permute4x64_epi64）进行排序：

lo = _mm256_loadu(b..);  // { b[15..8]  | b[7..0] }
hi =                     // { b[31..24] | b[23..16] }

// mask or shift
__m256i packed = _mm256_packus_epi16(lo, hi);    // [ a31..24  a15..8 | a23..16  a7..0 ]
packed = _mm256_permute4x64_epi64(packed, _MM_SHUFFLE(3, 1, 2, 0));

当然，在C版本中可以使用任何便携式优化。例如，Serge Ballesta建议在确定机器的字节顺序后，只需复制所需的字节。最好通过检查GNU C的__BYTE_ORDER__宏在编译时完成。

- Peter Cordes

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Serge Ballesta · Accepted Answer

即使移位和位运算很快，你可以尝试像其他评论中建议的那样将短数组处理为char指针。这是标准允许的，在常见的架构中也能够达到预期效果——避免了字节序问题。

因此，你可以尝试先确定你的字节序：

bool isBigEndian() {
    short i = 1;   // sets only lowest order bit
    char *ix = reinterpret_cast<char *>(&i);
    return (*ix == 0);   // will be 1 if little endian
}

您的循环现在变成了：

int shft = isBigEndian()? 0 : 1;
char * pb = reinterpret_cast<char *>(b);
for(int i = 0; i < 48; i++)
{
    a[i] = pt[2 * i + shft];
    a[i+48] = pt[2 * i + 50 + shft];
}

但是像所有低级优化一样，这必须与将在生产代码中使用的编译器和编译器选项进行基准测试。