Java 8 带有流和性能的嵌套循环

Question

我为了练习Java 8 Streams，尝试将以下嵌套循环转换为Java 8 Stream API。它计算a^b的最大数字和（a，b<100），在我的Core i5 760上需要大约0.135秒。

public static int digitSum(BigInteger x)
{
    int sum = 0;
    for(char c: x.toString().toCharArray()) {sum+=Integer.valueOf(c+"");}
    return sum;
}

@Test public void solve()
    {
        int max = 0;
        for(int i=1;i<100;i++)
            for(int j=1;j<100;j++)
                max = Math.max(max,digitSum(BigInteger.valueOf(i).pow(j)));
        System.out.println(max);
    }

我的解决方案本来因为并行处理应该更快，但实际上花了0.25秒（没有parallel()时是0.19秒）：

int max =   IntStream.range(1,100).parallel()
            .map(i -> IntStream.range(1, 100)
            .map(j->digitSum(BigInteger.valueOf(i).pow(j)))
            .max().getAsInt()).max().getAsInt();

我的问题

• 我是否正确地进行了转换，还是有更好的方式将嵌套循环转换为流计算？
• 为什么流变体比旧方法慢得多？
• 为什么parallel()语句实际上会使时间从0.19秒增加到0.25秒？

我知道微基准测试很脆弱，且并行处理只适用于大问题，但对于CPU来说，即使0.1秒也是漫长的，对吗？

更新

我使用Eclipse Kepler中的JUnit 4框架进行测量（它显示执行测试所需的时间）。

a,b<1000而非100时的结果：

• 传统循环186s
• 顺序流193s
• 并行流55s

更新2
用sum+= c - '0';替换sum+=Integer.valueOf(c+"");（感谢Peter！）将并行方法的总时间缩短了10秒，达到了45秒。没想到这样会有如此大的性能影响！

此外，将并行度减少到CPU核心数（我的情况下为4）并没有太大作用，因为它只将时间缩短到了44.8秒（是的，它增加了a和b=0，但我认为这对性能影响不大）。

int max = IntStream.range(0, 3).parallel().
          .map(m -> IntStream.range(0,250)
          .map(i -> IntStream.range(1, 1000)
          .map(j->.digitSum(BigInteger.valueOf(250*m+i).pow(j)))
          .max().getAsInt()).max().getAsInt()).max().getAsInt();

- Konrad Höffner

---

你如何衡量？正如你所指出的，如果没有适当的关注，微基准测试的结果可能会误导人。 - assylias

жҲ‘дјҡе°Ҷsum+=Integer.valueOf(c+"");жӣҝжҚўдёәsum+= c - '0';пјҢеӣ дёәиҝҷж ·йҖҹеәҰжӣҙеҝ«гҖӮ - Peter Lawrey

顺便提一下，您可以使用CharSequence.chars()方法中的流替换digitSum中的循环。这样可以避免分配字符数组。 - Stuart Marks

Answer 1

我已经根据你的代码创建了一个快速而简单的微基准测试。 结果如下：

loop: 3192
lambda: 3140
lambda parallel: 868

因此，循环和lambda表达式是等效的，但并行流显着提高了性能。 我怀疑你的结果不可靠，因为你的基准测试方法可能存在问题。

public static void main(String[] args) {
    int sum = 0;

    //warmup
    for (int i = 0; i < 100; i++) {
        solve();
        solveLambda();
        solveLambdaParallel();
    }

    {
        long start = System.nanoTime();
        for (int i = 0; i < 100; i++) {
            sum += solve();
        }
        long end = System.nanoTime();
        System.out.println("loop: " + (end - start) / 1_000_000);
    }
    {
        long start = System.nanoTime();
        for (int i = 0; i < 100; i++) {
            sum += solveLambda();
        }
        long end = System.nanoTime();
        System.out.println("lambda: " + (end - start) / 1_000_000);
    }
    {
        long start = System.nanoTime();
        for (int i = 0; i < 100; i++) {
            sum += solveLambdaParallel();
        }
        long end = System.nanoTime();
        System.out.println("lambda parallel : " + (end - start) / 1_000_000);
    }
    System.out.println(sum);
}

public static int digitSum(BigInteger x) {
    int sum = 0;
    for (char c : x.toString().toCharArray()) {
        sum += Integer.valueOf(c + "");
    }
    return sum;
}

public static int solve() {
    int max = 0;
    for (int i = 1; i < 100; i++) {
        for (int j = 1; j < 100; j++) {
            max = Math.max(max, digitSum(BigInteger.valueOf(i).pow(j)));
        }
    }
    return max;
}

public static int solveLambda() {
    return  IntStream.range(1, 100)
            .map(i -> IntStream.range(1, 100).map(j -> digitSum(BigInteger.valueOf(i).pow(j))).max().getAsInt())
            .max().getAsInt();
}

public static int solveLambdaParallel() {
    return  IntStream.range(1, 100)
            .parallel()
            .map(i -> IntStream.range(1, 100).map(j -> digitSum(BigInteger.valueOf(i).pow(j))).max().getAsInt())
            .max().getAsInt();
}

---

我也使用了jmh来运行它，这比手动测试更可靠。结果与上面一致（每次调用的微秒数）：

---

Benchmark                                Mode   Mean        Units
c.a.p.SO21968918.solve                   avgt   32367.592   us/op
c.a.p.SO21968918.solveLambda             avgt   31423.123   us/op
c.a.p.SO21968918.solveLambdaParallel     avgt   8125.600    us/op

- assylias

---

如果您按相反的顺序运行测试，我会很感兴趣看到您得到什么结果。 - Peter Lawrey

@PeterLawrey 相同的结果（lambda 并行：836，lambda：3124，循环：3184） - assylias

有趣的结果！也许我的结果也是由于英特尔 Turbo Boost（仅在使用单个核心时自动超频）引起的？但是我不确定 Junit 在时间记录方面是否真的那么不可靠，因为我多次重复测试，每次都获得类似的结果。 - Konrad Höffner

JUnit很可靠，但它不能为你预热代码。预热后的代码比第一次运行时快好多倍。 - Peter Lawrey

@delive no! - 这对于特定的代码来说可能更快，但并不总是如此。 - assylias

https://dev59.com/l2Ag5IYBdhLWcg3wDHU3 - user3402040

Answer 2

你面临的问题是你正在查看次优代码。当你有可能对代码进行大量优化时，你非常依赖于JVM是否足够聪明来优化你的代码。循环已经存在了很长时间并且更容易理解。

你的循环代码中一个重要的区别是你的工作集非常小。你一次只考虑一个最大数字总和。这意味着代码具有缓存友好性并且对象的生命周期很短。在stream()的情况下，你正在构建集合，其中任何时候都有更多的工作集，使用更多的缓存，有更多的开销。我也希望你的GC时间更长和/或更频繁。

为什么流变量比旧的慢那么多？

循环已经相当优化了，在Java开发之前就已经存在了。它们可以被映射到硬件上非常高效。

为什么parallel()语句实际上将时间从0.19秒增加到0.25秒？

最有可能的是你有一个共享资源的瓶颈。你创建了相当多的垃圾，但这通常是相当并发的。使用更多的线程只能保证你会有更多的开销，不能确保你能利用额外的CPU功率。

- Peter Lawrey

---

哦，但是看着我的代码，我没有看到任何共享资源，我只是使用了Java库，或者我有什么疏忽吗？ - Konrad Höffner

@kirdie，你有正在共享的硬件资源。例如你的L3缓存，可能还有L1/L2缓存，你的主内存，以及垃圾回收器可能也会发挥作用。 - Peter Lawrey