java - 使用 minimax 的 tic-tac-toe 可以使用多少个线程？

Question

让我们以 5x5 井字游戏为例。假设轮到我的 AI 了。然后，

• 我走 25 步(基本上每个单元格，当然，如果它是合法的移动)，
• 为每个 Action 创建一个线程(总共(最多)25 个线程)，
• 对每一步都调用一个 minimax 函数，
• 然后当所有结果都来自每个线程时，
• 比较得分并选择得分最高的着法。

这是我的问题:

• 使用 25 个线程是否高效？使用 25 个线程意味着什么？

• 它是否快了 25 倍(很可能不是)？它取决于什么？当然是在计算机上，但是我如何根据计算机的资源知道可以使用多少线程呢？

• 如果我使用太多线程会怎样(我猜没什么……)？

我的想法好吗？谢谢。

Answer 1

对于典型的计算密集型应用程序，一个好的经验法则是使用与硬件核心(或超线程)一样多的线程。使用比核心更多的线程不会使您的应用程序运行得更快。相反，它会导致您的应用程序使用比必要更多的内存。每个线程通常有一个 0.5 到 1MB 的堆栈……取决于您的硬件和 Java 版本。如果你创建了太多线程，额外的内存使用会导致显着的性能损失；即更多线程 => 更慢的程序!

另一件需要考虑的事情是，在典型的 JVM 上创建 Java 线程的成本很高。因此，除非一个线程(在其生命周期内)完成足够的工作，否则您创建线程所花费的时间可能会超过在计算中使用多核所获得的时间。

最后，您可能会发现工作并未均匀分布在所有线程上，具体取决于您的 minmax 算法……和游戏状态。

---

如果我试图实现它，我会首先将它实现为一个单线程应用程序，然后:

• 对其进行基准测试以确定串行运行时计算 more 需要多长时间，
• 分析它以消除任何瓶颈
• 重新进行基准测试以查看它是否已经足够快。

当且仅当它需要更快时，我才会检查代码并(如有必要)添加一些监控以查看如何将计算分解为足够大的 block 以便并行执行。

最后，我将使用这些结果来设计和实现多线程版本。

我还会考虑替代方案......比如使用 Java 7 的 fork/join 而不是线程。

---

回答您的直接问题:

Is it efficient to use 25 threads?

可能不会。只有当你有那么多核心时它才会有效(不太可能!)。即便如此，如果您通过并行运行事物获得的 yield 多于由于与线程相关的开销而损失的 yield ，那么您只能通过使用大量线程获得良好的加速。 (换句话说，这取决于您如何有效地使用这些线程。)

What does using 25 threads mean?

我假设你的意思是你已经创建并启动了 25 个线程，无论是明确地还是使用一些现有的线程池实现。

但最重要的是，如果您有(比方说)4 个内核，那么这 25 个线程中最多 4 个可以同时执行。其他线程将等待...

Is it 25 times faster (most likely not)? What it depends on? On the computer, of course, but how can I know how many threads are okay to use based on the computer's resources?

限制性能的主要因素是核心数量。见上文。

What happens if I use too many threads (nothing I guess...)?

太多线程意味着您使用更多内存，并且由于内存带宽竞争、物理内存页面竞争、额外的垃圾收集，这会使您的应用程序运行速度变慢。这些因素取决于应用程序和平台，并且难以量化；即预测或测量。

根据您的应用程序的性质(即您实现算法的确切方式)，过多的线程可能会导致额外的锁争用和线程上下文切换。这也会使您的应用程序变慢。

如果没有看到您的实际代码，就不可能预测会发生什么。但是核心数量为您提供了可能加速的理论上限。如果您有 4 个内核，那么您无法通过多线程获得超过 4 倍的加速。