java - 消失的可扩展性

Question

我做了一个玩具程序来测试Java的并发性能。我把它放在这里: https://docs.google.com/open?id=0B4e6u_s5iHT6MTNkZGM5ODQtNjZmYi00NTMwLWJlMjUtYzViOWZlMDM5NGVi

它接受一个整数作为参数，指示要使用的线程数。该程序只是计算出一个范围内的质数。通过注释第44~53行获得通用版本，它产生近乎完美的可扩展性。

但是，当我取消注释第 44~53 行(该行在本地进行简单计算)并将变量 s 调整为足够大的值时，可扩展性可能会消失。

我的问题是我的玩具程序是否使用共享数据，这可能会导致并发性能下降。如何解释消失的可扩展性(我认为低级开销，如垃圾收集，导致了这一点)？有什么办法可以解决像这样的问题吗？

Answer 1

有问题的代码是:

int s = 32343;
ArrayList<Integer> al = new ArrayList<Integer>(s);
for (int c = 0; c < s; c++) {
    al.add(c);
}
Iterator<Integer> it = al.iterator();
if (it.hasNext()) {
    int c = it.next();
    c = c++;
}

当然，如果您增加 s 的值，这会降低性能，因为 s 控制您放入列表中的内容数量。但这与并发性或可扩展性关系不大。如果您编写代码告诉计算机浪费时间进行数千或数百万次废弃计算，那么您的性能当然会下降。

用更专业的术语来说，这部分代码的时间复杂度为 O(2n)(需要 n 次操作来构建列表，然后n 操作来迭代它并递增每个值)，其中 n 等于 s。因此，s 越大，执行此代码所需的时间就越长。

就为什么这似乎会使并发的好处变小，您是否考虑过 s 变大时对内存的影响？例如，您确定 Java 堆足够大，可以容纳内存中的所有内容，而无需将任何内容交换到磁盘吗？即使没有任何内容被交换，通过增大 ArrayList 的长度，您也会在运行时为垃圾收集器提供更多工作要做(并且可能会增加其运行频率)。请注意，根据实现情况，垃圾收集器可能会在每次运行时暂停所有线程。

我想知道，是否在创建线程时为每个线程分配一个 ArrayList 实例，然后在调用 isPrime() 时重用该实例每次创建一个新列表，这会改善情况吗？

编辑:这是一个修复版本:http://pastebin.com/6vR7Uhez

它在我的机器上提供以下输出:

------------------start------------------
1 threads' runtimes:
1       3766.0
maximum:    3766.0
main time:  3766.0
------------------end------------------
------------------start------------------
2 threads' runtimes:
1       897.0
2       2483.0
maximum:    2483.0
main time:  2483.0
------------------end------------------
------------------start------------------
4 threads' runtimes:
1       576.0
2       1473.0
3       568.0
4       1569.0
maximum:    1569.0
main time:  1569.0
------------------end------------------
------------------start------------------
8 threads' runtimes:
1       389.0
2       965.0
3       396.0
4       956.0
5       398.0
6       976.0
7       386.0
8       933.0
maximum:    976.0
main time:  978.0
------------------end------------------

...随着线程数量的增加，它显示出几乎线性的缩放。我修复的问题是上面提出的问题和 John Vint(现已删除)的答案中提出的问题的组合，以及 ConcurrentLinkedQueue 结构的不正确/不必要的使用和一些有问题的计时逻辑。

如果我们启用 GC 日志记录并分析两个版本，我们可以看到原始版本运行垃圾收集的时间是修改版本的大约 10 倍:

Original:  [ParNew: 17401K->750K(19136K), 0.0040010 secs] 38915K->22264K(172188K), 0.0040227 secs]
Modified:  [ParNew: 17024K->0K(19136K),   0.0002879 secs] 28180K->11156K(83008K),  0.0003094 secs]

这对我来说意味着，在常量列表分配和Integer自动装箱之间，最初的实现只是简单地搅动了太多的对象，这给GC带来了太多的负载，从而降低了你的性能线程数量达到了创建更多线程没有任何好处(甚至是负面好处)的程度。

所以这一切对我来说是，如果你想在 Java 中很好地扩展并发性，无论你的任务是大还是小，你都必须注意如何使用内存，意识到潜在的隐藏陷阱和低效率，并优化掉低效部分。