Java 8 嵌套循环与流和性能

为了练习 Java 8 流,我尝试将以下嵌套循环转换为 Java 8 流 API。它计算a^b的最大数字总和(a,b<100),并在我的Core i5 760上取~0.135s。

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);
    }

我的解决方案,由于paralellism,我期望更快,实际上需要0.25s(没有0.19s):parallel()

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.1s也是永恒的,对吧?

更新

我使用Eclipse Kepler中的Junit 4框架进行测量(它显示了执行测试所需的时间)。

我对 a,b<1000 而不是 100 的结果:

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

更新 2替换为(感谢彼得!)减少了10整秒的并行方法,使其达到45秒。没想到会有这么大的性能影响!sum+=Integer.valueOf(c+"");sum+= c - '0';

此外,将并行度减少到CPU内核的数量(在我的例子中为4)并没有多大作用,因为它将时间减少到44.8s(是的,它增加了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();

答案 1

我基于您的代码创建了一个快速而肮脏的微基准测试。结果是:

循环: 3192
lambda: 3140
lambda 并行: 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

答案 2

你遇到的问题是你正在查看次优代码。当你的代码可能被高度优化时,你非常依赖于JVM是否足够智能来优化你的代码。循环已经存在了更长的时间,并且得到了更好的理解。

循环代码的一大区别是,你的工作集非常小。您一次只考虑一个最大数字总和。这意味着代码是缓存友好的,并且您有非常短暂的对象。在 stream() 案例中,您正在构建集合,这些集合在任何时候都有更多的工作集中,使用更多的缓存,具有更多的开销。我希望你的GC时间更长和/或更频繁。

为什么流变体比旧变体慢得多?

循环是相当优化的,从Java开发之前就已经存在了。它们可以非常有效地映射到硬件。流是相当新的,没有那么严格优化。

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

最有可能的是,您在共享资源上有瓶颈。你创造了相当多的垃圾,但这通常是相当并发的。使用更多的线程,只能保证您将拥有更多的开销,并不能确保您可以利用您拥有的额外CPU能力。


推荐