6

是否可以对 std::bitset 的基础数据使用 SSE 指令?我正在使用的位集大于 unsigned long,因此 to_ulong() 方法是不够的。例如,我可以使用这样的指令:

__m128i* ptr= (__m128i*)(&my_bitset[0]);

然后按正常执行 SSE 操作?

我已经尝试在互联网上搜索很多使用带有 SSE 的 std::bitset 的人,但它似乎不是一个常见的用例。

4

4 回答 4

6

是否可以对 std::bitset 的基础数据使用 SSE 指令?

__m128i* ptr= (__m128i*)(&my_bitset[0]);

my_bitset[0]返回未指定布局的临时代理对象,其中包含指向容器/存储的指针和位索引(例如GNU C++std::bitset::reference实现)。将指向此临时代理对象的指针强制转换__m128i*为没有意义。但是 C++ 根本不允许获取临时对象的地址,因此会&my_bitset[0]导致编译器错误。


std::bitset如果/当编译器选择向量化它时,可以自动对其成员函数使用 SIMD 指令。

在这个例子中,gcc 决定使用 AVX-256 指令,而 clang 决定不使用。两种选择都不理想:

  • gcc 使用 256 位ymm寄存器生成 AVX 指令,这会降低旧 Intel CPU 上的 CPU 频率(或在强制 AVX 偏移为 0 的情况下崩溃超频)。ymm但是向量大小太小,无法证明在到处使用零星的寄存器指令时付出增加 CPU 功耗和可能降低频率的代价是合理的。

  • clang 生成 64 位通用寄存器指令,与具有 128 位xmm寄存器的 SSE 相比,它需要更多的指令字节和更多的加载/存储。CPU 每个周期只能执行固定数量的加载/存储指令(而不是字节),因此最大化每条指令加载和存储的数据量是有意义的。

此示例中的理想选择可能是使用具有 128 位xmm寄存器的 SSE 指令 - 在不降低 CPU 时钟的情况下最大限度地减少加载/存储指令的数量。这表明编译器矢量化通常并不理想。


std::bitset不幸的是,它不提供对其存储的直接访问,并且通过 C 样式转换对其进行的任何访问都可能导致未定义的行为,而不会由于布局、对齐或严格的别名违规而发出警告或错误。

std::bitset由于可移植性限制,不太可能使用任何非标准/SIMD 类型进行存储,因此将其存储转换为更广泛的 SIMD 类型几乎可以保证对齐和严格的别名冲突。有一些不可移植的方法可以解决这个问题,但这对于未来的变化来说很脆弱,这就是为什么我不建议这样做。


您可能想寻找其他考虑 SIMD 的容器,例如Vc:用于显式数据并行编程的可移植、零开销 C++ 类型。它允许在每个容器类的基础上选择 SIMD 指令类型,例如,您可能只喜欢xmm对这种特定容器类型使用 128 位寄存器指令,即使 256 位ymm寄存器可用。


gcc 和 clang 都支持通过内置函数对用 声明的类型使用向量指令__attribute__((vector_size (N))),这是另一种方式:

目前,GCC 允许在这些类型上使用以下运算符:+、-、*、/、一元减号、^、|、&、~、%。

但是这些不允许在每个容器类的基础上选择底层 SIMD 类型/指令,只允许每个具有编译器选项(如-mno-avx.

于 2021-11-09T20:31:34.910 回答
1

bitset没有标准的方式来访问其内部数据。

itsy_bitsy库提供了与其他数据类似的接口。是您所需要的,它包装具有操作位的能力的数据,但没有/操作。bitsetbit_viewinserterase

不确定您是否可以bitsy::bit_view直接使用__m128i类型,但它支持 like bitsy::bit_view<std::span<char>>,因此您可以拥有__m128i变量并将其重新解释为chars 的跨度,

于 2021-11-09T19:26:43.817 回答
1

如果您知道标准库的对象布局,则可以对整个对象使用SIMD 。bitset

大多数实现都std::bitset<>做出了明显的实现选择,即整个bitset对象的对象表示只是位,打包成连续的字节。(如果任何主流的现实世界实现不是这样,我会感到惊讶,但不能保证你可以安全地假设。)大多数人选择使用比字节宽的整数类型的数组。

如果我们只讨论实现 Intel 内部 API 的 x86 编译器,那是一组较小的实现。

至少在 GNU libstdc++ 中,最低地址块保存位 0..63,依此类推。(所以它是跨块的小端,x86 是块内字节的小端。)并且bitset[0]是低字的低字节,即加载和and eax, 1。实现可能会做出不同的选择,例如将 存储bitset[0]在最高地址块的底部,大端风格。这与 x86 bt/bts位串指令索引内存的方式不一致,但无论如何它们都很慢,所以不这样做的主要原因是将运行时变量索引转换为地址和位掩码或移位会更多工作数数。

如果您想尝试以不可移植的方式利用这一点,_mm_loadu_si128 请在std::bitset对象本身上使用,而不是在返回的位迭代器上使用&bitset[0]

#include <bitset>
#include <immintrin.h>

// being a struct or class member isn't necessary, just a handy place to put an alignas()
// for example purposes.
struct foo {
 alignas(32) std::bitset<384> bs;  // 32-byte aligned, 48 bytes total.
           // alignas(16) would be sufficient for what I'm doing with SSE2
 int x, y;                 // with or without these, the struct size is a multiple of the alignment, thus 64B.
};
  // beware that allocating this with  new  might not respect alignment before C++17


void bar(foo *pfoo)
{
    char *bsp = (char*) &(pfoo->bs);   // pointer to (the first byte of) the bitset
      // as a char* so pointer math works in bytes.
      // unfortunately load/store intrinsics require casting back to __m128i*
      // until AVX-512 when Intel realized void* would be better.

    __m128i v0 = _mm_load_si128( (__m128i*)bsp );   // aligned load of bits 0..127
    __m128i v1 = _mm_loadu_si128( vb+3 );   // unaligned load of bits 24..152 
    v0 = _mm_and_si128(v0, v1);
    _mm_store_si128(vb+16, v0);            // aligned store at another alignment boundary
}

这会编译(在 Godbolt 上使用 GCC11.2)为以下 asm:

bar(foo*):
        movdqu  xmm0, XMMWORD PTR [rdi+3]    # unaligned load has to use movdqu
        pand    xmm0, XMMWORD PTR [rdi]      # aligned load can fold into a memory operand even without AVX
        movaps  XMMWORD PTR [rdi+16], xmm0   # aligned store.  (movaps is shorter than movdqa)
        ret

使用 AVX,编译器可以选择为vmovdqa加载v0并使用未对齐的内存源操作数vpand xmm0, xmm0, [rdi+3],但我编译时没有-march=haswell演示 SSE 能够使用对齐加载内在函数的优势。(另请参阅为什么 gcc 不将 _mm256_loadu_pd 解析为单个 vmovupd? re:旧 GCC 中的调整选项。)

您甚至alignas(32) std::bitset<256> bs可以将 bitset 的该实例对齐 32 个字节,从而允许使用对齐的加载/存储,_mm256_load_si256而不是loadu. 如果您的位集不是 256 位的倍数,则最后 32 个字节的一部分中可能还有其他对象,所以不要假设它只是您可以踩到的对齐填充。对这些字节进行非原子加载/存储不是线程安全的(例如,如果您正在修改作为位集一部分的位,并将后面的字节原封不动地存储回来。)

请注意,分配比alignof(max_align_t)(x86-64 实现中通常为 16)对齐的对象仅new在 C++17 中得到很好的支持。在此之前,alignas()只有 Just Worked 用于静态和自动存储。

提醒:没有什么可以保证这是便携的

但它可能会在不是 DeathStation 9000 的 C++ 实现上工作。

如果您不能/不想手动滚动自己的位图,或者不想使用 Alex 的 itsy_bitsy 建议,该建议有记录的方式来获取数据,那么如果可以的话,这个 hack 可能是值得的不要让你的编译器以更便携的方式制作高效的 asm。

只要您的 C++ 库使用类似class bitset { private: _chunk_t _data[size]; }或类似的东西实现 bitset,就没有什么未定义的关于通过内在函数弄乱对象表示的事情。(GNU libstdc++ 使用_WordT _M_w[_Nw];

内部函数被定义为安全地为任何其他数据设置别名,就像char*. GCC/clang 通过将它们定义为may_alias类型来实现这一点。请参阅硬件 SIMD 向量指针和相应类型之间的“reinterpret_cast”是否是未定义的行为?
(不过,这确实绕过了正常的公共/私人限制。)

如果这以某种方式与某些未来的编译器版本中断,那就是你的问题。不过,我认为某些东西不太可能改变正常的std::bitset实现,使其对象表示不只是位数组。

在加载低块之前,您可以查看 asm 中的类似return pfoo->bs.to_ulong()内容并查看它加载的内容以检查设置的高位(不幸的是没有对测试进行矢量化)。这证实了这些位是我们预期的。(请参阅 Godbolt 链接)。

如果这样做,请编写一个使用_mm_set_epi32(1,0,0,0)or 的单元测试并将其存储到 bitset 中,然后确保一个 set 位在您期望的位置,在bs[96]. 这样,您将检测实现是否更改了std::bitset<>.

您也可以static_assert在尺寸上使用 a。对于像 256 位这样的大小,即使在使用orsizeof()的实现中也是常数 32 。 不过,可能会有所不同。但不会发现单词中单词或位的顺序差异。char bits[32]uint64_t bigchunks[4]sizeof(std::bitset<129>)static_assert

如果你可以使用C++20,那么位顺序的单元测试也可以放入static_assert,就像bitset方法一样constexprstd::bit_cast编译时可以使用。尽管在这种情况下,单元测试将无法使用 SSE 内在函数,并且必须使用普通的 C++ 操作。不过,您可以使用char*操作来操作对象表示的std::bitset方式与使用内在函数相同。或者更好的是,使用std::bit_cast<>which,不应该为带有 vtable 或其他东西的类型编译,至少在 constexpr 上下文中。例如,Alex在评论中建议https://godbolt.org/z/1advToGf5 。

std::bitset操作将在 C++20 中的事实constexpr可能完全排除了一些疯狂的实现选择。

于 2021-11-10T06:51:01.977 回答
0

真的很np。你需要boost::dynamic_bitset<>这些东西

https://www.generacodice.com/en/articolo/882721/extract-subset-from-boost-dynamic-bitset

最后部分

你想要的是抓住

dynamic_bitset::m_bits
于 2021-11-10T07:00:40.380 回答