TL; DR 如何安全地执行单个位更新 A[n/8] |= (1<<n%8);
对于 A
是一大堆char
s(即,在使用 C++11 的 n
进行并行计算时,设置 A
的 <thread>
的 位 为真)图书馆?
我正在执行一个易于并行化的计算。我正在计算自然数的某个子集的元素,我想找到该子集中不的元素。为此,我创建了一个巨大的数组(如 A = new char[20l*1024l*1024l*1024l]
,即 20GiB)。 n
如果 n
,则此数组的 位 为真位于我的集合中。
并行执行并使用 A[n/8] |= (1<<n%8);
将位设置为真时,我似乎丢失了少量信息,据推测是由于同时处理 A
的同一字节 (每个线程必须首先读取字节,更新单个位并写回字节)。我该如何解决这个问题?有没有办法将此更新作为原子操作进行?
代码如下。 GCC 版本:g++ (Ubuntu 5.4.0-6ubuntu1~16.04.11) 5.4.0 20160609
.该机器是 8 核 Intel(R) Xeon(R) CPU E5620 @ 2.40GHz,37GB RAM。编译器选项:g++ -std=c++11 -pthread -O3
#include <iostream>
#include <thread>
typedef long long myint; // long long to be sure
const myint max_A = 20ll*1024ll*1024ll; // 20 MiB for testing
//const myint max_A = 20ll*1024ll*1024ll*1024ll; // 20 GiB in the real code
const myint n_threads = 1; // Number of threads
const myint prime = 1543; // Tested prime
char *A;
const myint max_n = 8*max_A;
inline char getA(myint n) { return A[n/8] & (1<<(n%8)); }
inline void setAtrue(myint n) { A[n/8] |= (1<<n%8); }
void run_thread(myint startpoint) {
// Calculate all values of x^2 + 2y^2 + prime*z^2 up to max_n
// We loop through x == startpoint (mod n_threads)
for(myint x = startpoint; 1*x*x < max_n; x+=n_threads)
for(myint y = 0; 1*x*x + 2*y*y < max_n; y++)
for(myint z = 0; 1*x*x + 2*y*y + prime*z*z < max_n; z++)
setAtrue(1*x*x + 2*y*y + prime*z*z);
}
int main() {
myint n;
// Only n_threads-1 threads, as we will use the master thread as well
std::thread T[n_threads-1];
// Initialize the array
A = new char[max_A]();
// Start the threads
for(n = 0; n < n_threads-1; n++) T[n] = std::thread(run_thread, n);
// We use also the master thread
run_thread(n_threads-1);
// Synchronize
for(n = 0; n < n_threads-1; n++) T[n].join();
// Print and count all elements not in the set and n != 0 (mod prime)
myint cnt = 0;
for(n=0; n<max_n; n++) if(( !getA(n) )&&( n%1543 != 0 )) {
std::cout << n << std::endl;
cnt++;
}
std::cout << "cnt = " << cnt << std::endl;
return 0;
}
当 n_threads = 1
,我得到了正确的值 cnt = 29289
.当n_threads = 7
, 我得到了 cnt = 29314
和 cnt = 29321
在两个不同的调用上,表明对单个字节的一些按位操作是同时进行的。
最佳答案
std::atomic
提供您在这里需要的所有设施:
std::array<std::atomic<char>, max_A> A;
static_assert(sizeof(A[0]) == 1, "Shall not have memory overhead");
static_assert(std::atomic<char>::is_always_lock_free,
"No software-level locking needed on common platforms");
inline char getA(myint n) { return A[n / 8] & (1 << (n % 8)); }
inline void setAtrue(myint n) { A[n / 8].fetch_or(1 << n % 8); }
getA
中的负载是原子的 (equivalent to load()
),std::atomic
甚至内置了对 or
ing 的支持存储的值与另一个值 ( fetch_or
),当然是原子的。
当初始化 A
时,for (auto& a : A) a = 0;
的天真方式将要求在每次存储后进行同步,您可以通过放弃一些来避免这种情况线程安全。 std::memory_order_release
只要求我们写入的内容对其他线程可见(但不要求其他线程的写入对我们可见)。事实上,如果你这样做
// Initialize the array
for (auto& a : A)
a.store(0, std::memory_order_release);
您无需在 x86 上进行任何程序集级同步即可获得所需的安全性。您可以在线程完成后对负载执行相反的操作,但这在 x86 上没有额外的好处(无论哪种方式,它都只是一个 mov
)。
完整代码演示:https://godbolt.org/z/nLPlv1
关于c++ - 异步写入位数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55476123/