Julia线程化代码结果异常：竞态条件误解与解惑

问题背景 #

这是此前问题《Fastest way to compare lists with threshold in Julia》的后续。尝试将串行代码并行化后，在大数组（P为(400000,1540)）场景下性能正常提升且结果正确，但在小数组（m=1056）且线程数>8时，BitVector B 中的部分false未被正确设置。添加ReentrantLock后问题解决，但疑惑为何会出现这种情况——因为每个线程处理不同的j值，理论上不存在竞态条件。

串行代码 #

for i = 1:l
    B[i] || continue
    for j = i + 1:l
        B[j] || continue
        if all(abs(P[i, k] - P[j, k]) <= 0.001 for k=1:1540)
            B[j] = false
        end
    end
end

并行代码 #

for i = 1:l
    B[i] || continue
    Threads.@threads for j = i + 1:l
        B[j] || continue
        if all(abs(P[i, k] - P[j, k]) <= 0.001 for k=1:1540)
            B[j] = false
        end
    end
end

问题根源 #

核心原因在于BitVector的底层存储机制：
BitVector是按位压缩存储的，每8个布尔值占用1个字节。当多个线程同时修改同一个字节内的不同位时，虽然它们操作的是不同的j对应的逻辑位，但底层需要先读取整个字节、修改对应位、再写回内存。如果两个线程的读写操作重叠，就会导致其中一个线程的修改被覆盖，最终出现位状态错误。

• 大数组场景下，j对应的位分散在大量字节中，多个线程同时操作同一字节的概率极低，因此问题不易复现；
• 小数组（1056位仅对应132字节）+多线程（>8）时，线程数量多于字节数量，必然会有多个线程同时操作同一字节，冲突概率大幅上升，从而出现异常结果。

为什么加锁能解决问题 #

ReentrantLock强制同一时间只有一个线程能对B进行写入操作，确保所有位修改对应的字节写入都是原子性的，避免了多个线程同时写入同一字节的冲突，因此能保证结果正确。大数组场景下加锁不影响性能，是因为线程间的字节冲突本来就很少，锁的竞争开销可以忽略。

替代优化方案 #

除了加锁，还可以通过以下方式避免问题：

• 改用Vector{Bool}：Vector{Bool}每个元素占用1字节，每个元素的写入是独立的字节操作，不会出现跨位的写入冲突，并行时无需加锁即可保证正确性。代价是内存占用增加，但对于小数组来说影响很小。
• 按字节拆分并行任务：将j按所属的字节分组，让每个线程处理完整的字节块，确保同一时间只有一个线程操作某个字节，既保留BitVector的内存优势，又能安全并行。

内容的提问来源于stack exchange，提问作者Okano