对数组的不同元素进行多次锁定
multiple locks on different elements of an array
如果我有 8 个线程和一个包含 1,000,000,000 个元素的数组，我可以有 1,000,000,000 个 mutices，其中索引表示数组中被锁定和写入的元素。然而，这对我来说相当浪费并且需要大量内存。
有没有办法只使用 8 个 mutices 并具有相同的功能？
这取决于访问模式，你有办法有效地划分工作吗？基本上，您可以将数组分成 8 个块（或尽可能多的块）并用互斥锁覆盖每个部分，但如果访问模式是随机的，您仍然会遇到很多冲突。
您的系统支持 TSX 吗？这将是一个典型的例子，只有一个全局锁，并让线程忽略它，除非发生实际冲突。
在这里大声思考......并不确定这会有多有效，但是：
您可以创建锁定某些索引的方法：
vector<int> mutexed_slots;
std::mutex mtx;
bool lock_element(int index)
{
std::lock_guard<std::mutex> lock(mtx);
// Check if item is in the mutexed list
if ( !std::find(mutexed_slots.begin(), mutexed_slots.end(), index) != vector.end() )
{
// If its not then add it - now that array value is safe from other threads
mutexed_slots.emplace_back(index);
return true;
}
return false;
}
void unlock_element(int index)
{
std::lock_guard<std::mutex> lock(mtx);
// No need to check because you will only unlock the element that you accessed (unless you are a very naughty boy indeed)
vec.erase(vec.begin() + index);
}
注意：这是一个想法的开始，所以不要太用力敲它！它也是未经测试的伪代码。它并不是真正打算作为最终答案 - 而是作为起点。请添加评论以改进或建议is/isn不合理。
进一步的观点：
- 可能有更高效的 STL 可供使用
- 您可能可以将所有这些与您的数据一起包装在 class 中
- 您需要遍历
lock_element() 直到它 returns 为真 - 现在又不太好。这个机制可以改进。
- 每个线程都需要记住他们当前正在处理哪个索引，以便他们只解锁那个特定的索引 - 同样，这可以更多地集成在 class 中以确保该行为。
但作为一个概念 - 可行吗？我认为如果您需要非常快速的访问（也许您需要），这可能不是那么有效，想法？
更新
如果每个 thread/worker "registers" 在 mutexed_slots 中都有自己的条目，这可能会更有效率。那么向量中就不会有 push_back/remove（start/end 处除外）。所以每个线程只设置它已锁定的索引——如果它没有锁定任何东西，那么它就被设置为 -1（或类似的）。我认为还有更多这样的效率改进需要进行。同样，一个完整的 class 为您完成所有这些将是实现它的方法。
测试/结果
我为此做了一个测试，只是因为我很喜欢那种东西。我的实现是 here
我认为它是一个 public github 回购 - 欢迎您看一看。但我将结果发布在顶级自述文件中（因此请稍微滚动一下以查看它们）。我实施了一些改进，例如：
- 在运行-time
保护阵列没有insert/removal
不需要 lock_guard 来执行 "unlock" 因为我不依赖 std::atomic 索引。
下面是我的总结打印输出：
总结：
当工作量为 1 毫秒（执行每个动作所花费的时间）时，完成的工作量为：
- 9808 受保护
8117 正常
注意这些值各不相同，有时正常值更高，似乎没有明显的赢家。
当工作负载为 0 毫秒（基本上增加几个计数器）时，完成的工作量为：
- 9791264 受保护
- 29307829 正常
所以在这里您可以看到使用互斥保护会使工作速度减慢大约三分之一 (1/3)。这个比率在测试之间是一致的。
我也 运行 对 1 名工人进行了相同的测试，并且相同的比率大致成立。但是，当我缩小数组（~1000 个元素）时，完成的工作量仍然与工作负载为 1ms 时大致相同。但是当工作量很轻时，我得到的结果如下：
- 5621311
39157931
大约慢了 7 倍。
结论
- 数组越大，冲突越少 - 性能越好。
- 工作负载（每项）越长，使用保护机制的差异就越不明显。
看来锁定通常只是增加开销，比增加几个计数器慢 2-3 倍。这可能被实际碰撞所扭曲，因为（从结果来看）记录的最长锁定时间是巨大的 40 毫秒——但这是在工作时间非常快的时候，所以发生了很多碰撞（每次碰撞约 8 次成功锁定）。
您可以编写一个 class 来在特定索引需要时即时创建锁，std::optional 会对此有所帮助（前面的 C++17 代码）：
class IndexLocker {
public:
explicit IndexLocker(size_t size) : index_locks_(size) {}
std::mutex& get_lock(size_t i) {
if (std::lock_guard guard(instance_lock_); index_locks_[i] == std::nullopt) {
index_locks_[i].emplace();
}
return *index_locks_[i];
}
private:
std::vector<std::optional<std::mutex>> index_locks_;
std::mutex instance_lock_;
};
您也可以使用 std::unique_ptr 来最小化堆栈-space 但保持相同的语义：
class IndexLocker {
public:
explicit IndexLocker(size_t size) : index_locks_(size) {}
std::mutex& get_lock(size_t i) {
if (std::lock_guard guard(instance_lock_); index_locks_[i] == nullptr) {
index_locks_[i] = std::make_unique<std::mutex>();
}
return *index_locks_[i];
}
private:
std::vector<std::unique_ptr<std::mutex>> index_locks_;
std::mutex instance_lock_;
};
使用此 class 并不一定意味着您需要创建所有 1,000,000 个元素。您可以使用模运算将储物柜视为 "hash table" 个互斥锁：
constexpr size_t kLockLimit = 8;
IndexLocker index_locker(kLockLimit);
auto thread_code = [&](size_t i) {
std::lock_guard guard(index_locker.get_lock(i % kLockLimit));
// Do work with lock.
};
值得一提的是，"hash table" 方法很容易造成死锁（例如，get_lock(0) 后跟 get_lock(16)）。但是，如果每个线程一次只处理一个元素，那么这应该不是问题。
细粒度锁定还有其他权衡。原子操作是昂贵的，因此锁定每个元素的并行算法可能比顺序版本花费更长的时间。
如何有效锁定取决于。数组元素是否依赖于数组中的其他元素？你主要是在读书吗？主要是写作？
I don't want to split the array into 8 parts because that will cause a
high likelihood of waiting (access is random). The elements of the
array are a class that I will write that will be multiple Golomb coded
values.
我不认为有 8 个互斥体是解决问题的方法。如果给定的锁保护数组部分，则不能在不引入竞争条件（使互斥锁毫无意义）的情况下在并行执行过程中将其切换为保护不同的部分。
数组项小吗？如果可以将它们减少到 8 个字节，则可以使用 alignas(8) 声明 class 并实例化 std::atomic<YourClass> 对象。 （大小取决于体系结构。验证 is_lock_free() returns 为真。）这可能会开启无锁算法的可能性。危险指针的变体似乎在这里很有用。这很复杂，所以如果时间有限，最好研究其他并行方法。
如果我有 8 个线程和一个包含 1,000,000,000 个元素的数组，我可以有 1,000,000,000 个 mutices，其中索引表示数组中被锁定和写入的元素。然而，这对我来说相当浪费并且需要大量内存。
有没有办法只使用 8 个 mutices 并具有相同的功能？
这取决于访问模式，你有办法有效地划分工作吗？基本上，您可以将数组分成 8 个块（或尽可能多的块）并用互斥锁覆盖每个部分，但如果访问模式是随机的，您仍然会遇到很多冲突。
您的系统支持 TSX 吗？这将是一个典型的例子，只有一个全局锁，并让线程忽略它，除非发生实际冲突。
在这里大声思考......并不确定这会有多有效，但是：
您可以创建锁定某些索引的方法：
vector<int> mutexed_slots;
std::mutex mtx;
bool lock_element(int index)
{
std::lock_guard<std::mutex> lock(mtx);
// Check if item is in the mutexed list
if ( !std::find(mutexed_slots.begin(), mutexed_slots.end(), index) != vector.end() )
{
// If its not then add it - now that array value is safe from other threads
mutexed_slots.emplace_back(index);
return true;
}
return false;
}
void unlock_element(int index)
{
std::lock_guard<std::mutex> lock(mtx);
// No need to check because you will only unlock the element that you accessed (unless you are a very naughty boy indeed)
vec.erase(vec.begin() + index);
}
注意：这是一个想法的开始，所以不要太用力敲它！它也是未经测试的伪代码。它并不是真正打算作为最终答案 - 而是作为起点。请添加评论以改进或建议is/isn不合理。
进一步的观点：
- 可能有更高效的 STL 可供使用
- 您可能可以将所有这些与您的数据一起包装在 class 中
- 您需要遍历
lock_element()直到它 returns 为真 - 现在又不太好。这个机制可以改进。 - 每个线程都需要记住他们当前正在处理哪个索引，以便他们只解锁那个特定的索引 - 同样，这可以更多地集成在 class 中以确保该行为。
但作为一个概念 - 可行吗？我认为如果您需要非常快速的访问（也许您需要），这可能不是那么有效，想法？
更新
如果每个 thread/worker "registers" 在 mutexed_slots 中都有自己的条目，这可能会更有效率。那么向量中就不会有 push_back/remove（start/end 处除外）。所以每个线程只设置它已锁定的索引——如果它没有锁定任何东西，那么它就被设置为 -1（或类似的）。我认为还有更多这样的效率改进需要进行。同样，一个完整的 class 为您完成所有这些将是实现它的方法。
测试/结果
我为此做了一个测试，只是因为我很喜欢那种东西。我的实现是 here
我认为它是一个 public github 回购 - 欢迎您看一看。但我将结果发布在顶级自述文件中（因此请稍微滚动一下以查看它们）。我实施了一些改进，例如：
- 在运行-time 保护阵列没有insert/removal
不需要 lock_guard 来执行 "unlock" 因为我不依赖 std::atomic 索引。
下面是我的总结打印输出：
总结：
当工作量为 1 毫秒（执行每个动作所花费的时间）时，完成的工作量为：
- 9808 受保护
8117 正常
注意这些值各不相同，有时正常值更高，似乎没有明显的赢家。
当工作负载为 0 毫秒（基本上增加几个计数器）时，完成的工作量为：
- 9791264 受保护
- 29307829 正常
所以在这里您可以看到使用互斥保护会使工作速度减慢大约三分之一 (1/3)。这个比率在测试之间是一致的。
我也 运行 对 1 名工人进行了相同的测试，并且相同的比率大致成立。但是，当我缩小数组（~1000 个元素）时，完成的工作量仍然与工作负载为 1ms 时大致相同。但是当工作量很轻时，我得到的结果如下：
- 5621311
39157931
大约慢了 7 倍。
结论
- 数组越大，冲突越少 - 性能越好。
- 工作负载（每项）越长，使用保护机制的差异就越不明显。
看来锁定通常只是增加开销，比增加几个计数器慢 2-3 倍。这可能被实际碰撞所扭曲，因为（从结果来看）记录的最长锁定时间是巨大的 40 毫秒——但这是在工作时间非常快的时候，所以发生了很多碰撞（每次碰撞约 8 次成功锁定）。
您可以编写一个 class 来在特定索引需要时即时创建锁，std::optional 会对此有所帮助（前面的 C++17 代码）：
class IndexLocker {
public:
explicit IndexLocker(size_t size) : index_locks_(size) {}
std::mutex& get_lock(size_t i) {
if (std::lock_guard guard(instance_lock_); index_locks_[i] == std::nullopt) {
index_locks_[i].emplace();
}
return *index_locks_[i];
}
private:
std::vector<std::optional<std::mutex>> index_locks_;
std::mutex instance_lock_;
};
您也可以使用 std::unique_ptr 来最小化堆栈-space 但保持相同的语义：
class IndexLocker {
public:
explicit IndexLocker(size_t size) : index_locks_(size) {}
std::mutex& get_lock(size_t i) {
if (std::lock_guard guard(instance_lock_); index_locks_[i] == nullptr) {
index_locks_[i] = std::make_unique<std::mutex>();
}
return *index_locks_[i];
}
private:
std::vector<std::unique_ptr<std::mutex>> index_locks_;
std::mutex instance_lock_;
};
使用此 class 并不一定意味着您需要创建所有 1,000,000 个元素。您可以使用模运算将储物柜视为 "hash table" 个互斥锁：
constexpr size_t kLockLimit = 8;
IndexLocker index_locker(kLockLimit);
auto thread_code = [&](size_t i) {
std::lock_guard guard(index_locker.get_lock(i % kLockLimit));
// Do work with lock.
};
值得一提的是，"hash table" 方法很容易造成死锁（例如，get_lock(0) 后跟 get_lock(16)）。但是，如果每个线程一次只处理一个元素，那么这应该不是问题。
细粒度锁定还有其他权衡。原子操作是昂贵的，因此锁定每个元素的并行算法可能比顺序版本花费更长的时间。
如何有效锁定取决于。数组元素是否依赖于数组中的其他元素？你主要是在读书吗？主要是写作？
I don't want to split the array into 8 parts because that will cause a high likelihood of waiting (access is random). The elements of the array are a class that I will write that will be multiple Golomb coded values.
我不认为有 8 个互斥体是解决问题的方法。如果给定的锁保护数组部分，则不能在不引入竞争条件（使互斥锁毫无意义）的情况下在并行执行过程中将其切换为保护不同的部分。
数组项小吗？如果可以将它们减少到 8 个字节，则可以使用 alignas(8) 声明 class 并实例化 std::atomic<YourClass> 对象。 （大小取决于体系结构。验证 is_lock_free() returns 为真。）这可能会开启无锁算法的可能性。危险指针的变体似乎在这里很有用。这很复杂，所以如果时间有限，最好研究其他并行方法。