c++ - 在线程之间协调哪些线程是空闲的最有效的方法是什么？
问题描述
我正在开发一个在线程之间发送消息的程序，它查看哪些线程很忙，如果一个线程是空闲的，它会抓取第一个空闲的（或在某些情况下是多个空闲的），将其标记为已占用，将工作发送给它并做它自己的工作，然后一旦完成等待它完成。所有这一切的瓶颈部分是在线程之间协调关于哪个线程被占用。好像是一个问题，相信其他人也遇到过，有一些解决办法可以分享，但也想知道你能不能比我做得更好。
我的解决方案最终归结为：维护一个表示空闲线程索引的集合，并能够从集合中获取一个项目，获取空闲线程的索引，或者将其添加回集合中，将大小增加一。顺序不重要。我事先知道集合的固定大小。
我尝试了几种方法来做到这一点：
维护一个 unsigned long long int 并使用 '__builtin_clz'（有趣的 __builtin_ffsll 慢了 10 倍......认为我的处理器上的单个指令不支持）来计算单个指令周期中的位数并获取最低的位数并使用位掩码查找表以打开和关闭位，同时声明它们的线程号。喜欢这个版本，因为我只需要共享一个原子 unsigned long long 并且可以使用单个原子操作，但在循环中执行 'fetch_and' 直到你正确结束时比锁定和非原子地执行慢。使用锁定的版本最终更快，可能是因为线程没有陷入循环重复相同的操作等待其他人完成他们的操作。
使用链表，预先分配所有节点，维护一个头节点和一个链表，如果指向nullptr，那么我们已经到了链表的末尾。只使用锁完成此操作，因为它需要两个同时操作。
维护一个数组，该数组表示要声明的线程的所有索引。要么增加一个数组索引并返回前一个指针来声明一个线程，要么将最后一个占用的线程与被释放的线程交换并减少指针。检查是否免费。
使用 moodycamel 队列，它维护一个无锁队列。
很高兴分享 C++ 代码，但当我尝试包含它时，答案变得很长。
这三个都很快，__builtin_clzll 没有得到普遍支持，所以即使快一点，可能还不够值得，而且在不原生支持它的计算机上可能慢 10 倍，类似于 __builtin_ffsll 的速度很慢。数组和链表的速度大致相同，没有争用时数组似乎稍快一些。穆迪慢了 3 倍。
认为您可以做得更好并且有更快的方法来做到这一点？仍然是这个过程中最慢的部分，在某些情况下仍然几乎不值得付出代价。
探索方向的想法：
- 感觉应该有一种方法使用几个原子，也许是一个原子数组，一次一个，但必须在每个操作中保持集合的完整性，这使得这很棘手。大多数解决方案在某些时候需要同时完成两个操作，原子似乎可以提供比锁定我的基准测试快得多的解决方案。
- 可能能够使用锁定，但无需检查列表是否为空或交换数组中的元素
- 也许使用不同的数据结构，例如，两个数组，添加一个同时清空另一个，然后切换哪个被填充，哪个被清空。这意味着不需要交换元素，而只需交换两个指向数组的指针，并且仅当一个指针为空时。
- 可以让线程启动线程将工作添加到要完成的工作列表中，然后另一个线程可以在该线程继续运行时抓住它。最终还是需要一个类似的线程安全集。
- 看看stackoverflow上的聪明人是否看到了我还没有看到的探索方向:)
解决方案
您所需要的只是一个线程池、一个队列（a或环形缓冲区）、alist和a ，用于在将新工作项添加到队列时发出信号。dequemutexcondition_variable
packaged_task如果您需要等待每个任务的结果，请将工作项包装起来。
当向队列中添加新的工作项时，1) 锁定互斥锁，2) 添加项，3) 释放锁和 4) 调用cv::notify_one，这将解除对第一个可用线程的阻塞。
一旦基本设置开始工作，如果任务过于细粒度，可以将工作窃取添加到解决方案中以提高性能。使用主线程执行部分工作而不是仅仅等待所有任务完成也很重要。由于减少了上下文切换，这些简单（尽管笨拙）的优化通常会导致整体性能提高 15% 以上。
也不要忘记考虑虚假分享。为了安全起见，将任务项填充到 64 个字节可能是个好主意。