将32 0/1值打包到单个32位变量的位中的最快方法是什么？

Question

我正在使用x86或x86_64机器.我有一个数组unsigned int a[32],其所有元素的值都为0或1.我想设置单个变量,unsigned int b以便(b >> i) & 1 == a[i]为所有32个元素保持a.我在Linux上使用GCC(我猜不应该这么做).

在C中执行此操作的最快方法是什么？

Answer 1

最近的x86处理器上最快的方法可能是使用MOVMSKB系列指令,它们提取SIMD字的MSB并将它们打包成普通的整数寄存器.

我担心SIMD内在函数不是我真正的东西,但是如果你有一个配备AVX2的处理器,那么这些内容应该有用:

uint32_t bitpack(const bool array[32]) {
    __mm256i tmp = _mm256_loadu_si256((const __mm256i *) array);
    tmp = _mm256_cmpgt_epi8(tmp, _mm256_setzero_si256());
    return _mm256_movemask_epi8(tmp);
}

假设sizeof(bool) = 1.对于较旧的SSE2系统,您必须将一对128位操作串联起来.将数组对齐在32字节边界上,并应保存另一个周期左右.

Answer 2

其他答案包含一个明显的循环实现.

这是第一个变体:

unsigned int result=0;
for(unsigned i = 0; i < 32; ++i)
    result = (result<<1) + a[i];

在现代的x86 CPU上,我认为寄存器中任何距离的移位都是不变的,这个解决方案也不会更好.你的CPU可能不那么好; 这段代码最大限度地降低了长途班次的成本; 它执行32个1位移位,每个CPU都可以执行(您可以始终将结果添加到自身以获得相同的效果).其他人显示的明显的循环实现通过移动等于循环索引的距离来进行大约900(总和32)1位移位.(参见@Jongware对评论差异的测量; x86上的长时间变换不是单位时间).

让我们尝试更激进的事情.

假设您可以以某种方式将m个布尔值打包成int(通常可以为m == 1 执行此操作),并且您有两个包含此类m个打包位的实例变量i1和i2.

然后下面的代码将m*2个布尔值打包成一个int:

 (i1<<m+i2)

使用这个我们可以打包2 ^ n位如下:

 unsigned int a2[16],a4[8],a8[4],a16[2], a32[1]; // each "aN" will hold N bits of the answer

 a2[0]=(a1[0]<<1)+a2[1];  // the original bits are a1[k]; can be scalar variables or ints
 a2[1]=(a1[2]<<1)+a1[3];  //  yes, you can use "|" instead of "+"
 ...
 a2[15]=(a1[30]<<1)+a1[31];

 a4[0]=(a2[0]<<2)+a2[1];
 a4[1]=(a2[2]<<2)+a2[3];
 ...
 a4[7]=(a2[14]<<2)+a2[15];

 a8[0]=(a4[0]<<4)+a4[1];
 a8[1]=(a4[2]<<4)+a4[3];
 a8[1]=(a4[4]<<4)+a4[5];
 a8[1]=(a4[6]<<4)+a4[7];

 a16[0]=(a8[0]<<8)+a8[1]);
 a16[1]=(a8[2]<<8)+a8[3]);

 a32[0]=(a16[0]<<16)+a16[1];

假设我们友好的编译器将[k]解析为(标量)直接存储器访问(如果没有,你可以简单地用an_k替换变量an [k]),上面的代码(抽象地)抽取63次,31次写入,31次移位和31添加.(64位有明显的扩展).

在现代的x86 CPU上,我认为寄存器中任何距离的移位都是不变的.如果没有,这段代码可以最大限度地降低长途班次的成本; 它实际上有64个1位移位.

在x64机器上,除了原始布尔值a1 [k]的提取之外,我希望编译器可以调度所有其余的标量以适应寄存器,因此32个内存提取,31个移位和31个添加.很难避免提取(如果原始的布尔分散在周围)并且移位/添加匹配明显的简单循环.但是,是没有循环,所以我们避免32增量/比较/索引操作.

如果起始布尔值确实在数组中,则每个位占据底部位,否则为零字节:

bool a1[32];

那么我们可以滥用我们的内存布局知识来一次取几个:

a4[0]=((unsigned int)a1)[0]; // picks up 4 bools in one fetch
a4[1]=((unsigned int)a1)[1];
...
a4[7]=((unsigned int)a1)[7];

a8[0]=(a4[0]<<1)+a4[1];
a8[1]=(a4[2]<<1)+a4[3];
a8[2]=(a4[4]<<1)+a4[5];
a8[3]=(a8[6]<<1)+a4[7];

a16[0]=(a8[0]<<2)+a8[1];
a16[0]=(a8[2]<<2)+a8[3];

a32[0]=(a16[0]<<4)+a16[1];

这里我们的成本是8次(4组)布尔,7班和7加.同样,没有循环开销.(同样有一个明显的64位泛化).

为了比这更快,你可能不得不进入汇编程序并使用那里可用的许多精彩和奇怪的指令(向量寄存器可能具有可能很好地工作的分散/收集操作).

一如既往,这些解决方案需要进行性能测试.

Answer 3

如果sizeof(bool) == 1那时你可以使用这里讨论的技术在快速乘法的计算机中一次打包8 bool秒到8位(更多的是128位乘法)

假设布尔变量a[0]来a[7]有他们至少显著位分别命名啊.将这8个连续的bools作为一个64位字处理并加载它们,我们将在小端机器中以相反的顺序得到这些位.现在我们将进行乘法运算(此处点为零位)

  |  a7  ||  a6  ||  a4  ||  a4  ||  a3  ||  a2  ||  a1  ||  a0  |
  .......h.......g.......f.......e.......d.......c.......b.......a
x 1000000001000000001000000001000000001000000001000000001000000001
  ????????????????????????????????????????????????????????????????
  ?......h.?.....g..?....f...?...e....?..d.....?.c......?b.......a
  ?.....g..?....f...?...e....?..d.....?.c......?b.......a
  ?....f...?...e....?..d.....?.c......?b.......a
+ ?...e....?..d.....?.c......?b.......a
  ?..d.....?.c......?b.......a
  ?.c......?b.......a
  ?b.......a
  a       
  ????????????????????????????????????????????????????????????????
= abcdefghxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

添加箭头以便更容易在幻数中看到设置位的位置.此时,在最高字节中放置了8个最低有效位,我们只需要将剩余的位屏蔽掉

所以通过使用幻数0b1000000001000000001000000001000000001000000001000000001000000001或0x8040201008040201我们有以下代码

inline int pack8b(bool* a)
{
    uint64_t t = *((uint64_t*)a);
    return (0x8040201008040201*t >> 56) & 0xFF;
}

int pack32b(bool* a)
{
    return (pack8b(a) << 24) | (pack8b(a + 8) << 16) | (pack8b(a + 16) << 8) | (pack8b(a + 24));
}

当然,您需要确保bool数组正确对齐8字节.您还可以展开代码并对其进行优化,例如仅移位一次而不是向左移动56位

对不起,我忽略了这个问题,看到了doynax的bool阵列以及误读了"32 0/1值"并认为它们是32 bool秒.当然,同样的技术也可以用于使用uint32_t128位乘法同时打包4 ,或者使用正常的64位乘法同时打包2,但它比打包字节的效率低很多

在具有BMI2的较新x86 CPU上,可以使用PEXT指令.pack8b上面的功能可以替换为

_pext_u64(*((uint64_t*)a), 0x0101010101010101ULL);

并打包2 uint32_t作为问题需要使用

_pext_u64(*((uint64_t*)a), (1ULL << 32) | 1ULL);

Answer 4

我可能会这样做：

unsigned a[32] =
{
    1, 0, 0, 1, 1, 1, 0 ,0, 1, 0, 0, 0, 1, 1, 0, 0
    , 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1
};

int main()
{
    unsigned b = 0;

    for(unsigned i = 0; i < sizeof(a) / sizeof(*a); ++i)
        b |= a[i] << i;

    printf("b: %u\n", b);
}

编译器优化很可能会展开它，但以防万一你总是可以尝试：

int main()
{
    unsigned b = 0;

    b |= a[0];
    b |= a[1] << 1;
    b |= a[2] << 2;
    b |= a[3] << 3;
    // ... etc
    b |= a[31] << 31;

    printf("b: %u\n", b);
}

Answer 5

unsigned b=0;
for(int i=31; i>=0; --i){
    b<<=1;
    b|=a[i];
}