c++ - 并行快速排序 boost::thread

Question

我编写了一个快速排序算法的就地实现，它的性能非常好(1024 个元素为 0.8 毫秒)。我想如果我在多个线程上实现它，我可以让它执行得更快，所以我尝试使用 boost::thread 并且列表排序完美但它比我的顺序版本(1539.3ms)花费了 1500 倍。我尝试将线程数限制为不同的数字，但似乎没有什么比原始版本快。这似乎是这种情况的任何原因？是否有人成功实现了并行就地快速排序？

Answer 1

一般建议:

• 不要并行化小型工作负载，它不会起作用(只需尝试测量操作系统创建新线程需要多长时间，将其与您的 8 毫秒进行比较)。你低估了这个成本。
  • 每个不同的线程仍然应该有相当大的工作量，否则退回到单线程。
• 如果可能不要锁定。如果你锁定，你只是给了你的 CPU 什么都不做的机会。
• 不要在不同线程上共享数据。那是:
  • 首先不要访问相同的数据进行写入(从不)
  • 不要访问内存中“关闭”的数据(虚假共享效应)
• 使用任务库而不是线程(boost.threadpool 是我喜欢的，但也有其他的同样好)。
  • 不要杀死已创建的线程，让它们等待更多工作
• 运行的线程数不要超过您拥有的处理器数量(如果您有超线程或类似技术，则为逻辑处理器)。
• 使用 CPU 亲和性将线程锁定在给定核心上(如何取决于您的操作系统)。

编辑:尝试使用 100 万个元素或其他元素，因为 1000 个真的很小。然后尝试绘制每个线程的效率与数组大小的曲线。