何时应该使用parrallelStream

发表于 |

非专业翻译，欢迎指正！

——————————-原文翻译————————————-

原文链接：http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html

辅助翻译工具：DeepL

何时使用并行流？

[草稿，2014年9月1日。目前，最小程度格式规范，刊登位置待定。]

java.util.streams框架支持对集合和其他资源进行数据驱动的操作。大多数流方法对每个数据元素应用相同的操作。当有多个CPU核心可用时，通过使用集合的parallelStream()方法，”数据驱动 “可以变成 “数据并行”。但是，你应该在什么时候这样做呢？

当操作是独立的，并且计算成本很高，或操作是应用于可有效分割的数据结构的大量元素，或者两者兼而有之时，考虑使用S.parallelStream().operation(F)代替S.stream().operation(F)。更详细地讲：

  • F，每个元素的函数（通常是一个lambda）是独立的：每个元素的计算不依赖或影响任何其他元素的计算。（查看stream包摘要获取关于使用无状态非干扰函数的进一步指导）。
  • S，源集合是可有效分割的。除了Collections，还有一些其他容易并行化的流源，例如java.util.SplittableRandom（对于它，你可以使用stream.parallel()方法来并行化）。但是大多数基于IO的源主要是为顺序使用而设计的。
  • 执行顺序版本的总时间超过了一个最低阈值。如今，在大多数平台上，这个阈值大约是100微秒（同一数量级内）。不过你不需要精确地测量这个。在实践中，你可以通过用N（元素的数量）乘以Q（执行F的每个元素的开销）来估计这个数字，反过来把Q估计为操作或代码行的数量，然后检查N*Q至少是10000。（如果不确定，可以再加一两个零）因此，当F是一个很小的函数，如x->x+1，那么它需要N>=10000个元素，并行执行才是值得的。反之，当F是一个大规模的计算，比如在国际象棋游戏中寻找最佳的下一步，Q因子是如此之高，以至于只要集合是完全可分割的，N就不重要了。
  • （个人补充）对于IO操作，数据库操作，则要去估计时间开销了，代码行数已经没有太多的参考价值。

流框架没有（也不能）强制要求满足这些条件。如果计算不是独立的，那么并行运行将没有任何意义，甚至可能导致严重的错误。其他标准源于三个工程问题和权衡：

  • 启动
    随着处理器多年来不断增加内核，大多数处理器也增加了功率控制机制，这会使内核启动缓慢，有时还会有JVM、操作系统和管理程序所带来的额外开销。此启动开销与大量内核处理并行子任务需要的时间相当。一旦启动，并行计算可能比顺序计算更节能（取决于各种处理器和系统细节；例如，见Federova等人的这篇文章）。
  • 颗粒度
    对已经很小的计算进行细分是不值得的。框架通常会将问题分割开来，以便由系统中所有可用的核来处理子问题。如果每个核心在启动后实际上没有什么可做的，那么（大多顺序执行）设置为并行计算的努力就被白费了。考虑到现在内核的实际范围是2到256个，这个阈值也避免了过度任务拆分的影响。
  • 可分割性
    最有效的可分割集合包括ArrayLists和{Concurrent}HashMaps，以及简单的数组（即那些形式为T[]，可使用静态java.util.Arrays方法分割）。效率最低的是LinkedLists、BlockingQueues和大多数基于IO的资源。其他资源则介于两者之间。(如果数据结构内部支持随机访问、高效搜索或两者兼而有之，那么它们往往是可有效分割的。) 如果分割数据的时间比处理数据的时间要长，那么这些努力就白费了。所以，如果计算的Q因子足够高，即使是LinkedList，你也可能获得并行加速，但这并不常见。此外，有些数据源不能被完全分割成单个元素，所以如何很好地分割任务可能存在限制。

收集这些影响的详细测量结果可能是困难的（尽管使用诸如JMH这样的工具时稍加细心就可以做到）。但总体效果是很容易看到的。你可以自己做实验来感受一下。例如，在一台32核的测试机器上，在ArrayList上运行max()或sum()这样的小函数，平衡点非常接近10K大小。更大的尺寸可以看到高达20倍的速度提升。小于10K大小的运行时间并不比10K的运行时间少多少，所以往往比顺序执行要慢。最糟糕的减速发生在少于100个元素的情况下–这激活了一堆线程，而这些线程最终却无事可做，因为计算在它们开始之前就已经完成了。另一方面，当每个元素的计算都很耗时的时候，如果使用ArrayList这样的高效且完全可分割的集合，就能立即看到速度提升效果。

另一种说法是，在没有足够的计算量的情况下，使用parallel()可能会花费你大约100微秒的时间，而在合理的情况下使用它应该至少节省这么多的时间（对于非常大的问题可能是几个小时）。确切的成本和收益随时间和平台的变化而变化，而且在不同的情况下也会有所不同。例如，在一个顺序循环中并行运行一个微小的计算，会很大程度的影响程序运行效果。（这样做的微观基准测试可能无法预测实际的使用情况）。

一些问题和回答：

  1. 为什么JVM不能自己找出是否使用并行模式？
    它可以尝试，但它会经常给出错误的答案。在过去的三十年里，对完全无指导的自动多核并行化的追求并没有获得一致的成功，所以流框架采用了更安全的方法，即只要求用户做出是/否的决定。这些决定依赖于不太可能完全消失的工程权衡，而且与顺序编程中一直在做的决定相似。例如，当你在一个只容纳一个元素的集合中寻找最大的元素时，你可能会遇到一百倍的开销（减速），而不是直接使用该元素（不在一个集合内）。有时JVM可以为你优化这种开销。但这在顺序的情况下不常发生，而在并行的情况下从不发生。另一方面，我们确实期待工具的发展能够帮助用户做出更好的决定。

  2. 如果我对参数（F、N、Q、S）的了解太少，无法做出一个好的决定怎么办？
    这也类似于常见的顺序编程问题。例如调用Collection方法S.contains(x)，如果S是HashSet，通常会很快，如果是LinkedList，则会很慢，否则就在两者之间。通常，处理这个问题的最好方法是，使用集合的组件的作者不要直接导出它，而是导出基于它的操作。这样用户就不会受到这些决定的影响。这同样适用于并行操作。例如，一个有内部集合 “价格 “的组件可以使用一个大小阈值来定义一个方法，除非每个元素的计算很昂贵。比如说：

1
2
3
4
5
6
public long getMaxPrice() { return priceStream().max(); }

 private Stream priceStream() {
   return (price.size() < MIN_PAR) ? 
      prices.stream() : prices.parallelStream()。
 }

​ 你可以用各种方式扩展这个想法，以处理关于何时和如何使用并行的各种考虑。

  1. 如果我的函数可能会做IO或同步，怎么办？
    一个极端是那些不能通过独立标准的函数，包括内在的顺序性IO，对锁定的同步资源的访问，以及一个执行IO的并行子任务的失败对其他子任务产生副作用的情况。将这些并行化不会有太大意义。在另一个极端，是执行偶尔的瞬时IO或同步的计算，很少有块（例如大多数形式的日志和大多数并发集合的使用，如ConcurrentHashMap）。这些都是无害的。介于两者之间的情况需要最多判断。如果每个子任务都可能在相当长的时间内被阻塞，等待IO或访问，那么CPU资源可能会被闲置，而程序或JVM没有办法使用它们。每个人都不会乐意见到这种情况。在这种情况下，并行流通常不是一个好的选择，但是有很好的替代方案，例如async-IO和CompletableFuture设计。

  2. 如果我的源是基于IO的呢？
    目前，基于JDK IO的流源（例如BufferedReader.lines()）主要用于顺序使用，在元素到达时逐一处理。支持高效地批量处理缓冲IO的机会是存在的，但目前这需要定制开发流源、Spliterators和/或Collectors。一些常见的形式可能会在未来的JDK版本中得到支持。

  3. 如果我的程序在一台繁忙的计算机上运行，而且所有的内核都被使用了，怎么办？
    机器一般只有一套固定的内核，当你执行并行操作时，不可能神奇地创造更多的内核。然而，只要明确满足选择并行执行的标准，通常就没有任何理由担心。你的并行任务将与其他任务竞争CPU时间，所以你会看到较少的速度提升。在大多数情况下，这仍然比其他方法更有效。底层机制的设计是这样的：如果没有其他核心可用，那么与顺序性能相比，你只会看到一个小的减速，除非系统已经过载，以至于它把所有的时间都花在上下文切换上而不是做任何真正的工作，或者被调整为假设所有的处理都是顺序的。如果你在这样的系统上，管理员可能已经禁用了多线程/cores的使用，作为JVM配置的一部分。如果你是这样一个系统的管理员，你可以考虑这样做。

  4. 所有的操作都是在并行模式下并行的吗？
    是的，至少在某种程度上是这样的，尽管Stream框架在选择如何做到这一点时服从于源和方法的约束。一般来说，较少的约束条件可以实现更多的潜在并行化。另一方面，不能保证框架会提取并应用所有可能的并行化机会。在某些情况下，如果你有时间和专业知识，你可能能够手工制作一个明显更好的并行解决方案。

  5. 我将得到多少并行速度的提升？
    如果你遵循这些准则，通常是值得的。可预测性不是现代硬件和系统的强项，所以通常的答案是不可能的。缓存定位、垃圾收集率、JIT编译、内存争用、数据布局、操作系统调度策略以及管理程序的存在，都是可以产生重大影响的因素。这些因素在顺序性能中也起作用，但在并行环境中往往被放大。一个在顺序执行中造成10%差异的问题可能会在并行中造成10倍的差异。

    流框架包括一些设施，可以帮助你提高加速的机会。例如，对IntStream这样的基元使用特殊化，在并行中的效果往往比顺序的大，因为它不仅减少了开销（和足迹），还增强了缓存的定位性。而使用ConcurrentHashMap而不是HashMap作为并行 “收集 “操作的目标，可以减少内部开销。随着人们对该框架的经验积累，会有更多的提示和指导出现。

  6. 这一切都太可怕了! 我们是不是应该制定一个政策，使用JVM属性来禁用并行？
    我们不想告诉你该怎么做。为程序员引入新的出错方式可能是很可怕的。编码、设计和判断方面的错误肯定会发生。但有些人几十年来一直在语言，启用应用程序级的并行性会导致重大灾难，但至今这些灾难并没有发生。

由 Doug Lea 书写, 感谢 Brian Goetz, Paul Sandoz, Aleksey Shipilev, Heinz Kabutz, Joe Bowbeer等人的帮助

感谢您的支持，予人玫瑰，手有余香