在计算机中，线程是可以由处理器独立执行的最小指令序列，也CPU调度的基本单位。而多线程可以理解成是一项多个线程并行执行的技术，它通过共享资源，例如指令和上下文，可以大大提升CPU的工作效率。

现在各种编程语言对于多线程各有自己的考虑，那些去理解并发现这些语言在多线程并行执行的性能，对于开发者们来说就显得非常有必要。

本文的目的是分析和比较 Java、Go 和 Python 使用它们的并行工具解决几种算法的性能，例如：Java 和 Python 的线程，以及 Go 的 goroutine。为了评估性能，我们编写了经典矩阵乘法算法、快速排序算法和康威生命游戏的并行实现。

背景

Java ：它是一种面向对象的编程语言，通过Thread类、Runnable接口和java.util.concurrent包中包含的其他功能内置支持并发。

Go：它是谷歌在 2012 年发布的一种编程语言。它是一种类似于 C 的过程语言，并且具有垃圾收集器和内置的并发支持。对于并发性和并行性，Go 使用称为goroutines的线程实现。它使用内置的调度程序在后台处理线程，并试图向用户隐藏通常线程管理的大部分复杂性，以支持简单地指定要运行的函数并使用go命令为它们开头。Go 在幕后使用操作系统 (OS) 线程。

Python：标准库线程，这个模块封装了线程，提供了一个干净的接口来处理它们。在这种方法中，操作系统实际上知道每个线程，并且可以随时中断它以开始运行不同的线程。可以使用 Python 的其他标准库（称为multiprocessing ）在 Python 中实现并行性，而多处理Python 会创建新进程。线程模块使用线程，多处理模块使用进程。不同之处之一是线程在相同的内存空间中运行，而进程具有单独的内存。

矩阵乘法：它是线性代数中一个重要而简单的数学运算，经典的矩阵乘法算法（CMMA）可以很容易地用任何编程语言实现。CMMA 在O(N^3)中运行，其中N是矩阵的维度。

快速排序：它是一种分而治之的算法。最初，它将数组拆分为两个子数组：分别是较低的项和较高的项。然后它递归地对这些子数组进行排序。其算法可以描述为：

1. 从数组中选择一个枢轴元素。
2. 对数组进行分区，使得枢轴左侧的所有元素的值都小于枢轴的值，而枢轴右侧的所有元素的值都大于枢轴的值。
3. 对生成的子数组递归执行上述步骤，直到得到完全排序的子数组。

它的平均排序复杂度为O(n log(n))，但在极少数情况下会降级为O(n^2)。

康威的人生游戏：它是由剑桥大学冈维尔和凯斯学院的数学家约翰霍顿康威在 60 年代开发的。规则是：

1. 规则 1 生存：如果一个活细胞有两个或三个活的邻居，它就可以生存。
2. 规则 2 死亡：如果一个活细胞的存活邻居少于两个或多于三个，它就会死亡。
3. 规则 3 出生：如果一个死细胞恰好有三个活着的邻居，它就会出生。

下一张图片显示了康威从时间T到时间T + 2的生活游戏的几个场景。该算法的一个简单实现将检查每一步的每个单元格，其时间复杂度为O(M × N )，其中M表示行数，N表示网格的列数。

解决方案

所有基准测试都在同一台计算机和同一环境中执行。表 I 显示了我们进行实验的硬件规格，表 II 显示了每种语言编程编译器的版本

对于每个基准，我们计算其各自的加速和效率。加速比定义为最佳顺序时间与p个处理器的并行时间之比：S = T1/Tp。那么效率定义为：并行系统中每个处理器的总体利用率：E = S/p。

矩阵乘法：在本实验中，我们使用由C = AB计算的简单矩阵乘法。矩阵的大小为 512 × 512。我们正在运行一个顺序场景，然后是几个线程池大小为：2、4、8、16 和 32 个线程的多线程场景。相同的矩阵A和B用于运行 Java、Go 和 Python 中的代码。这些矩阵将具有从 0 到 1000 的整数值（包括 0 到 1000）。线程池将接收n 个工作，表示矩阵A中的行数，然后每个线程将执行该特定行的乘法，并更新C中的相应行与得到的结果。每次线程完成其工作时，它将从线程池接收新的分配，直到所有工作都完成。下图说明了矩阵C的计算。

快速排序：我们从 0 到 10^7（包括 0 到 10^7）对 10^7 个整数值的数组进行排序。我们使用ForkJoinPool方法来解决这个实验。执行顺序运行，然后多线程测试以 2 的幂从 2 到 32 个线程。这 3 个实现对同一个数组进行排序。在快速排序的并行实现中，分区后新子序列的排序可以并行执行，因为没有冲突。

康威生命游戏：康威生命游戏中有几个初始已知模式会产生预期的结果，有一个会无限增长，下一张图像的左侧显示其初始设置。在这个基准测试中，我们定义了一个 28 × 28 的 2D 网格，其中 4 个先前的模式彼此相邻，并在 20,000 代期间执行游戏，该网格看起来像下图的右侧。

对于这个实验，我们重复线程池方法，它将处理 2、4、8、16 和 32 个线程。此外，我们运行顺序实现。我们并行应用了决定细胞在每一代中是否继续生存、死亡或重生的规则。此外，为了获取单元格的邻居，我们不会将网格视为无限网格，如果单元格的邻居在世界范围之外，则认为它已死。

结果

矩阵乘法：表 III 显示了运行矩阵乘法基准后获得的结果。Java 是顺序执行中最好的，它在 316 毫秒内运行了 512 × 512 矩阵乘法，而 Go 消耗了 453 毫秒，这代表顺序运行的时间增加了 43.35%。性能最差的是 Python，它使用了 93,870 毫秒（93.87 秒），相差约 29,600%。

此外，在表 III 中可以看出，当使用 2 个线程执行基准测试时，Java 性能更好，但是当实验在 4、8 和 16 个线程中运行时，Go 优于 Java 和 Python。我们可以在 32 个线程的阈值处检测到性能下降，这可能是由于创建过多线程的开销超过了 CPU 中的物理内核；即使在这种恶化的情况下，Go 的性能也优于其他两种语言。

下图的左侧反映了对于 Go，从 2 到 4 个线程的性能差异是显着的（大约 92% 的改进），而从 8 到 16 个线程的性能差异是微不足道的，因为图中的曲线几乎保持不变，这说明我们认为 8 个线程对于这个特定场景来说是一个很好的数字。另一方面，Java 的性能从 2 个线程稳步增加到 16 个线程；从这个图中，我们可以选择 16 个线程作为大量线程，以便在 Java 中获得不错的性能。从下图右侧可以确定，资源利用效率最差的是Python，最好的是Go。

快速排序：在表 IV 中，我们可以看到 Go 在测试的顺序运行中获得最佳性能，而 Python 最差。Python 实现的一般行为非常糟糕，在 16 和 32 线程的情况下，应用程序无法完成执行（DNF 代表没有完成）卡住并阻塞计算机。Go 提供了有趣的结果，因为多线程运行从糟糕到最差的性能。对于这个度量，Java 获得了最好的多线程结果，但是在 16 和 32 线程的运行中，我们可以发现性能下降，其中 16 线程的性能最差。

下图左侧的加速表明，当使用 Java 实现时，使用超过 8 个线程运行快速排序算法是没有意义的。此外，我们可以看到 32 线程的运行比 16 线程的运行好一点，但比 8 线程的运行差。该图反映了 Go 多线程实现不如顺序实现。即使 Python 的性能很差，使用 2、4 和 8 个线程的运行也比顺序运行要好。

下图右侧反映的效率证实了我们在表 IV 中看到的最好的，但不是最差的，因为这个图可以让我们认为 Python 比 Go 更好，但是时间的消耗告诉我们一段不同的历史：Go 的表现优于 Python。

康威的人生游戏：Python 再次获得了所有 3 种实现中最差的结果，但是正如我们在表 V 中看到的，它是唯一一个从顺序实现到多线程实现有一些改进的版本；尽管如此，随着线程数量的增加，时间的消耗也会增加。在 Java 和 Go 的情况下，它们的最佳性能来自顺序实现。在 Java 场景中，从顺序版本到具有 32 个线程的版本的时间差异为 11,455%，这代表了当时的巨大差距。在 Java 实现中，每一代之后都会释放线程池并创建一个新的线程池，这会产生相当大的开销。Go 行为不稳定，时间利用率从顺序到 2 线程版本增加，然后在 4、8、

下图的加速图证实了康威生命游戏的多线程实现的一般性能很差。围绕加速曲线的期望是它应该遵循增加的行为，而这并没有发生。报告的效率表明资源没有得到适当的利用。Java 的效率非常接近于零，Go 和 Java 之间只有一点点差异。

总结

创建线程的开销直接影响应用程序的性能。在表 III 中可以看出，在达到某个阈值后继续创建线程是没有意义的，因为性能会下降。

如表 V 所示，使用多线程解决问题并不能保证我们会获得更好的性能，有时顺序实现是最好的选择。

处理并发性和并行性的 Python 标准库不如 Java 和 Go 等其他编程语言中实现的标准库。

很难说 Java 和 Go 之间哪个更好，因为 Java 在矩阵乘法基准测试中优于 Go，但 Go 在快速排序实验中超过了 Java。

未来的工作

这项工作仅限于每个算法的基本实现，下一步将是复制本研究引入的场景，但使用每个基准测试的最知名实现。

在 Python 中实现并行代码有多种选择，例如：MPI for Python、CharmPy、Numba 等。一个好的实验是使用这个库用更有效的实现来替换书面代码。

扩展这项研究的一种方法是考虑其他技术方面，例如编译时间、文件大小和编写的代码行数。

参考资料

[1] S. Majumdar、I. Jain 和 A. Gawade。“使用线程池模式进行并行快速排序。” 在：国际计算机应用杂志136（2016 年 2 月），第 36-41 页。DOI：10.5120/ijca2016908495。

[2] T. Andersson 和 C. Brenden，“Go 和 Java 中的并行性使用矩阵乘法比较性能”，论文，2018 年。

[3] 艾莉. “线程问题”。在：计算机39（2006 年 6 月），第 33-42 页。DOI：10.1109/MC.2006.180。

[4] J. Carl，“Go 和 Scala 中的并行编程：性能比较”，论文，2015 年。

[5] “关键 Java 里程碑的时间线”。甲骨文网站。https://www.oracle。com/java/moved-by-java/（访问日期：2021 年 6 月 19 日）。

[6] “Oracle Java SE 支持路线图”。甲骨文网站。https://www.oracle。com/java/technologies/java-se-support-roadmap.html（访问日期：2021 年 6 月 19 日）。

[7] R. Buyya，“Java 面向对象编程”，第 14 章，第 367-368 页，2009 年。Tata McGraw Hill Education Private Limited。

[8] N. Togashi 和 V. Klyuev，“A new approach for web development: A schedule management system using GAE/Go”，2015 年 IEEE 第 7 届国际意识科学与技术会议 (iCAST)，2015 年，第 55-59 页，doi：10.1109/ICAwST.2015.7314020。

[9] “下载”。Golang.org。https://golang.org/dl/（访问时间：2021 年 5 月 21 日）。

[10] “常见问题解答 (FAQ)”。Golang.org https://golang.org/doc/faq#goroutines（访问时间：2021 年 5 月 21 日）。

[11] “Go 调度程序源代码。” Github.com。https://github.com/golang/go/blob/master/src/runtime/proc.go（访问时间：2021 年 5 月 21 日）。

[12] AAA Donovan 和 BW Kernighan，“共享变量的并发性”，Go 编程语言，第 1 版。美国纽约州纽约市：Addison-Wesley，2015 年，第 280-283 页。

[13] JJ Galvez、K. Senthil 和 L. Kale，“CharmPy: A Python Parallel Programming Model”，2018 年 IEEE 集群计算国际会议 (CLUSTER)，2018 年，第 423–433 页，doi: 10.1109/CLUSTER .2018.00059。

[14] V. Sheromova，“Python 简史”，Exyte.com。https://exyte。com/blog/a-brief-history-of-python（访问日期：2021 年 6 月 19 日）。

[15] “下载 Mac OS X 的最新版本。” Python.org。https://www.python.org/downloads/（访问时间：2021 年 6 月 19 日）。

[16] J. Anderson，“Python 线程简介”。RealPython.com。https://realpython.com/intro-to-python-threading/（访问时间：2021 年 6 月 19 日）。

[17] J. Anderson，“使用并发加速你的 Python 程序”。RealPython.com。https://realpython.com/python-concurrency/（访问时间：2021 年 6 月 19 日）。

[18] K. Khankasikam，“使用康威生命游戏识别印刷兰纳字符”，第七届数字信息管理国际会议（ICDIM 2012），2012 年，第 104-109 页，doi：10.1109/ICDIM.2012.6360138。