考虑一个N
位的比特向量(N
很大)和一个数字数组M
(M
适中,通常远小于N
),每个数字在范围0..N-1
内,指示向量的哪个比特必须设置为1
。后面的数组未排序。比特向量只是整数数组,具体来说是__m256i
,其中256个比特被打包进每个__m256i
结构中。
如何有效地将这项工作分割到多个线程中?
首选语言为C++(MSVC++2017工具集v141),汇编也可以。首选CPU为x86_64(使用内部函数也可以)。如果有任何益处,则希望使用AVX2。
考虑一个N
位的比特向量(N
很大)和一个数字数组M
(M
适中,通常远小于N
),每个数字在范围0..N-1
内,指示向量的哪个比特必须设置为1
。后面的数组未排序。比特向量只是整数数组,具体来说是__m256i
,其中256个比特被打包进每个__m256i
结构中。
如何有效地将这项工作分割到多个线程中?
首选语言为C++(MSVC++2017工具集v141),汇编也可以。首选CPU为x86_64(使用内部函数也可以)。如果有任何益处,则希望使用AVX2。
or [N + rdi], al
(没有lock
前缀)。0x1
并覆盖了线程2的存储0x2
。线程2必须注意并重试读取-修改-写入操作(可能使用lock or
使其简单化并使多次重试变得不可能),最终在冲突字节中得到0x3
。mfence
是昂贵的,但比仅使用lock or [N+rdi], al
更好的技巧在于我们可以批量操作。例如,执行32个or
指令,然后进行32次读取操作。这是mfence
开销与每个操作之间的平衡,还是增加了误共享(读取已被另一个CPU声明的缓存行)的机会。
我们可以将一组中的最后一个or
作为lock or
而不是实际的mfence
指令。这对于AMD和Intel的吞吐量都更好。例如,根据Agner Fog's tables,在Haswell/Skylake上,mfence
的吞吐量为33c中的一个,而lock add
(与or
具有相同的性能)的吞吐量为18c或19c。或者对于Ryzen,约为70c(mfence
)vs.约17c(lock add
)。
m[i]/8
) + 掩码 (1<<(m[i] & 7)
) 可以在所有操作中都保持在寄存器中。这可能不值得;因为围栏的代价太高,不能像每6个or
操作一样经常进行。使用bts
和bt
位串指令意味着我们可以将更多的索引保持在寄存器中(因为不需要移位结果),但可能不值得,因为它们很慢。避免使用类似于bts [N],eax的位串指令:它的吞吐量比为or [N + rax],dl进行索引和掩码计算要差。这是它的“完美”用例(除了我们不关心内存中位的旧值,我们只想设置它),但它的CISC负担太大。
在C语言中,函数可能如下所示:
/// UGLY HACKS AHEAD, for testing only.
// #include <immintrin.h>
#include <stddef.h>
#include <stdint.h>
void set_bits( volatile uint8_t * restrict N, const unsigned *restrict M, size_t len)
{
const int batchsize = 32;
// FIXME: loop bounds should be len-batchsize or something.
for (int i = 0 ; i < len ; i+=batchsize ) {
for (int j = 0 ; j<batchsize-1 ; j++ ) {
unsigned idx = M[i+j];
unsigned mask = 1U << (idx&7);
idx >>= 3;
N[idx] |= mask;
}
// do the last operation of the batch with a lock prefix as a memory barrier.
// seq_cst RMW is probably a full barrier on non-x86 architectures, too.
unsigned idx = M[i+batchsize-1];
unsigned mask = 1U << (idx&7);
idx >>= 3;
__atomic_fetch_or(&N[idx], mask, __ATOMIC_SEQ_CST);
// _mm_mfence();
// TODO: cache `M[]` in vector registers
for (int j = 0 ; j<batchsize ; j++ ) {
unsigned idx = M[i+j];
unsigned mask = 1U << (idx&7);
idx >>= 3;
if (! (N[idx] & mask)) {
__atomic_fetch_or(&N[idx], mask, __ATOMIC_RELAXED);
}
}
}
}
这在gcc和clang中大致符合我们的要求。汇编代码(Godbolt)可以通过多种方式更加高效,但尝试这个可能会有趣。这不是安全的:我只是在C语言中拼凑出了这个独立函数所需的汇编代码,而没有将其内联到调用者或其他任何地方。__atomic_fetch_or
并不是非原子变量的适当编译器屏障,就像asm("":::"memory")
一样。(至少C11的stdatomic
版本不是。)我应该使用传统的__sync_fetch_and_or
,它对所有内存操作都是一个完整的屏障。
atomic_uint8_t
变量上执行原子RMW操作。同时从多个线程运行此函数将会产生C11 UB,但我们只需要它在x86上工作。我使用volatile
来获取atomic
中允许异步修改的部分,而不强制N[idx] |= mask;
成为原子操作。这样做的目的是确保读取检查不被优化掉。__atomic_fetch_or
作为内存屏障,因为我知道它会在x86上工作。虽然使用seq_cst,它在其他ISA上也可能会工作,但这都是一种大型的hack。T
个线程。这是一个非常有趣的问题,因为它不能通过分区轻松并行化,不同大小的N
和M
可能需要不同的解决方案。
M
分成T
个部分,并让每个线程在其自己的M
分区上使用共享的N
。主要问题是,由于M
未排序,所有线程都可以访问N
的任何元素,因此会干扰彼此的工作。为了避免这种情况,您必须对共享的N
数组的每次修改使用原子操作,例如std::atomic::fetch_or
,否则就得想出一些锁定方案。这两种方法都可能降低性能(即使用原子操作设置位可能比等效的单线程代码慢一个数量级)。or
在最后合并它们。O(N) + O(M/T)
,而原始的单线程解决方案的复杂度为O(M)
,上面的“原子”解决方案大约为O(M/T)
4。由于我们知道N >> M
,因此在这种情况下,这可能是一个糟糕的权衡。但是,值得注意的是,每个项中的隐藏常数非常不同:来自合并步骤0的O(N)
项可以使用256位宽的vpor
指令,这意味着吞吐量接近200-500位/周期(如果缓存),而设置位的步骤,即O(M/T)
,我估计更接近1位/周期。因此,即使N
的大小是M
的10或100倍,对于适度的T,这种方法肯定可以是最佳的。
M
中的索引分成几部分,以便每个工作线程可以在N
数组的不同部分上工作。如果M
排序了,那就很简单了,但它没有排序,所以...M
分布得很好,将会很有效,首先将M
的值划分为T
个桶,桶中的值在范围[0, N/T), [N/T, 2N/T], ..., [(T-1)N/T, N)
内。也就是说,将N
分为T
个不相交的区域,然后找到落入每个区域的M
的值。您可以通过将每个线程分配一个相等大小的M
块,并让它们每个创建T
个分区,然后在最后逻辑合并1它们,以便您拥有M
的T
个分区来分散这项工作。T
,它可以以“单线程”方式设置位,即不必担心并发更新,因为每个线程都在处理N
的不相交分区2。O(M)
,第二步与单线程情况相同,因此并行化的开销是第一步。我怀疑第一步的速度范围将从与第二步相同到可能慢2-4倍,具体取决于实现和硬件,因此您可以期望在具有许多核心的机器上加速,但只有2或4个核心时可能不会更好。M
的分布不是平滑的,例如第一步创建的分区大小差异很大,它将表现不佳,因为某些线程将获得更多的工作。一个简单的策略是创建大约10 * T
个分区,而不仅仅是T
,并且在第二遍中,所有线程都从相同的分区队列中消耗,直到完成。通过这种方式,您可以更均匀地分散工作,除非数组M
非常紧密。在这种情况下,您可能需要考虑第一步的改进,该步骤首先基本上创建元素的分桶直方图,然后进行减少阶段,该阶段查看组合的直方图以创建良好的分区。1 合并的最简单的概念形式是将每个线程对M的分区复制,以便您拥有所有M的连续分区,但实际上,如果分区很大,您可以将分区保留在原处并将它们链接在一起,这会增加消费代码的复杂性,但避免了紧凑步骤。
2 为了使它从线程角度真正不相交,您需要确保N的分区落在“字节边界”上,甚至可能是缓存行边界,以避免错误共享(尽管后者可能不是一个大问题,因为它仅发生在每个分区的边缘,并且处理顺序意味着您不太可能出现争用)。
4 实际上,使用共享N的基线并发解决方案的确切“顺序”很难定义,因为会有争用,因此O(M/T)扩展将在足够大的T的情况下崩溃。如果我们假设N相当大,而T限于最多十几个核心的典型硬件并发性,那么这可能是一个可以接受的近似值。
shlx
代替xor
和bts
。 - BeeOnRopetimes 10 imul ecx,ecx
并注释掉(或不注释)lock or
块。 差异(如果有的话)低于测量噪声水平,在25M个迭代中为约750.4Mc。 - Peter Cordes集合中涉及到几种操作(A,B=集合,X=集合中的元素):
Set operation Instruction
---------------------------------------------
Intersection of A,B A and B
Union of A,B A or B
Difference of A,B A xor B
A is subset of B A and B = B
A is superset of B A and B = A
A <> B A xor B <> 0
A = B A xor B = 0
X in A BT [A],X
Add X to A BTS [A],X
Subtract X from A BTC [A],X
鉴于您可以使用布尔运算符替换集合操作,因此可以使用VPXOR
、VPAND
等。
要设置、重置或测试单个位,只需使用
mov eax,BitPosition
BT [rcx],rax
您可以使用以下代码设置一个集合是否为空(或其他内容)
vpxor ymm0,ymm0,ymm0 //ymm0 = 0
//replace the previous instruction with something else if you don't want
//to compare to zero.
vpcmpeqqq ymm1,ymm0,[mem] //compare mem qwords to 0 per qword
vpslldq ymm2,ymm1,8 //line up qw0 and 1 + qw2 + 3
vpand ymm2,ymm1,ymm2 //combine qw0/1 and qw2/3
vpsrldq ymm1,ymm2,16 //line up qw0/1 and qw2/3
vpand ymm1,ymm1,ymm2 //combine qw0123, all in the lower 64 bits.
//if the set is empty, all bits in ymm1 will be 1.
//if its not, all bits in ymm1 will be 0.
(我相信使用混合/聚集等指令可以改进此代码) 从这里,您只需扩展到更大的集合或其他操作即可。
请注意,带有内存操作数的bt
、btc
、bts
不限于64位。
以下内容将正常工作。
mov eax,1023
bts [rcx],rax //set 1024st element (first element is 0).
M
已经排序了吗?如果没有,你几乎肯定想要为单个线程进行优化。 - zzxyzstd::bitset
还是std::vector<bool>
或其他什么东西。另请参阅:如何证明std::bitset比std::vector<bool>更快?。如果你的数据尚未排序且非常大,则很难进行优化。同时避免过早优化。只有在你可以证明显而易见的方法不足以解决问题时才需要优化。对于小数据量,线程或复杂算法的开销会使代码变慢。 - Phil1970