使用 --indy 时冒泡排序的执行速度慢了 5 倍

Question

我写了一个冒泡排序的实现来尝试一下 Groovy 看看 --indy 是否对性能有任何显着影响。

本质上，它对一千个运行dom 整数的列表进行一千次排序，并测量对列表进行排序的平均执行时间。

一半时间列表是 Integer[]，另一半时间是 ArrayList<Integer>。

结果让我很困惑：

$ groovyc BubbleSort.groovy
$ time java -cp ~/.gvm/groovy/current/embeddable/groovy-all-2.4.3.jar:. BubbleSort
Average: 22.926ms
Min: 11.202ms
[...] 26.48s user 0.84s system 109% cpu 25.033 total

$ groovyc --indy BubbleSort.groovy
$ time java -cp ~/.gvm/groovy/current/embeddable/groovy-all-2.4.3-indy.jar:. BubbleSort
Average: 119.766ms
Min: 68.251ms
[...] 166.05s user 1.52s system 135% cpu 2:03.82 total

查看基准测试为运行时的 CPU 使用情况，使用 --indy 编译时 CPU 使用率比不使用时高很多。

这引起了我的兴趣，所以我再次运行基准测试 - 但这次启用了 Yourkit 代理和 CPU 跟踪。以下是录制的调用树：

没有--indy：

与--indy：

这里是性能图表 - 请注意时间尺度不同，因为 --indy 代码慢得多。

没有--indy（1s 比例）：

使用 --indy（60 秒比例）：

可以看出，CPU 使用率稳定在一个核心的 100%（图中为 12.5%），当编译时没有 --indy，但在 12.5% 和 ~35% 之间变化很大用 --indy 编译。更令人困惑的是，Yourkit 只报告了一个活动线程（而我的代码只使用主线程），但它仍然设法保持两个半核心被占用。

用 --indy 编译的代码在开始时也使用了大量的内核时间，虽然这会下降并在一段时间后稳定在 0% - 此时代码似乎加快了一点（堆使用增长率增加）和 CPU 使用增加。

任何人都可以向我解释这种行为吗？

版本：

$ groovy -v
Groovy Version: 2.4.3 JVM: 1.8.0_45 Vendor: Oracle Corporation OS: Linux

$ java -version
java version "1.8.0_45"
Java(TM) SE Runtime Environment (build 1.8.0_45-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.45-b02, mixed mode)

BubbleSort.groovy:

class BubbleSort {
    final def array

    BubbleSort(final def array) {
        this.array = array
    }

    private void swap(int a, int b) {
        def tmp = array[a];
        array[a] = array[b]
        array[b] = tmp;
    }

    private void rise(int index) {
        for(int i = index; i > 0; i--) {
            if(array[i] < array[i - 1]) {
                swap(i, i-1)
            } else {
                break
            }
        }
    }

    void sort() {
        for(int i = 1; i < array.size(); i++) {
            rise i
        }
    }

    final static Random random = new Random()

    static void main(String[] args) {
        def n = 1000
        def size = 1000
        // Warm up
        doBenchmark 100, size
        def results = doBenchmark n, size
        printf("Average: %.3fms%n", results.total / 1e6 / n)
        printf("Min: %.3fms%n", results.min / 1e6)
    }

    private static def doBenchmark(int n, int size) {
        long total = 0
        long min = Long.MAX_VALUE
        n.times {
            def array = (1..size).collect { random.nextInt() }
            if(it % 2) {
                array = array as Integer[]
            }
            def start = System.nanoTime()
            new BubbleSort<Integer>(array).sort()
            def end = System.nanoTime()
            def time = end - start
            total += time
            min = Math.min min, time
        }
        return [total: total, min: min]
    }
}

我对我的冒泡排序实现的优化不感兴趣，除非它们与 invokedynamic 行为相关 - 这里的目的不是编写性能最好的冒泡排序，而是要弄清楚为什么--indy 对性能有如此大的负面影响。

更新：

我将我的代码转换为 JRuby 并尝试了同样的事情并且结果相似，尽管没有 invokedynamic:

JRuby 几乎没有那么快

$ JAVA_OPTS="-Djruby.compile.invokedynamic=false" jruby bubblesort.rb
Average: 78.714ms
Min: 35.000ms

$ JAVA_OPTS="-Djruby.compile.invokedynamic=true" jruby bubblesort.rb
Average: 136.287ms
Min: 92.000ms

更新 2：

如果我删除将列表更改为 Integer[] 一半时间的代码，性能会显着提高，尽管在没有 --indy 的情况下它仍然更快：

$ groovyc BubbleSort.groovy
$ java -cp ~/.gvm/groovy/current/embeddable/groovy-all-2.4.3.jar:. BubbleSort
Average: 29.794ms
Min: 26.577ms

$ groovyc --indy BubbleSort.groovy
$ java -cp ~/.gvm/groovy/current/embeddable/groovy-all-2.4.3-indy.jar:. BubbleSort
Average: 37.506ms
Min: 33.555ms

如果我用 JRuby 做同样的事情，invokedynamic 会更快：

$ JAVA_OPTS="-Djruby.compile.invokedynamic=false" jruby bubblesort.rb
Average: 34.388ms
Min: 31.000ms

$ JAVA_OPTS="-Djruby.compile.invokedynamic=true" jruby bubblesort.rb
Average: 20.785ms
Min: 18.000ms

Answer 1

答案很简单其实很简单，Groovy还没有PIC。

... 或者你可以说我们通常有一个大小为 1 的内联缓存。这意味着每次你更改列表数组类型时，它都会使之前存在的所有缓存失效并且缓存版本被丢弃.这对于普通 Groovy 几乎与 Indy 相同，只是普通 Groovy 使用运行时生成的类而 Indy 使用 invokedynamic/lambda 形式。但是 lambda 形式最初较慢，而峰值性能更好。基本上你所做的是让热点从头开始大多数方法调用，防止它一直应用优化。当然这不是你的错，而是 Groovy 还没有 PIC 的错。只是为了说清楚...这不是语言的问题，这只是我还没有实现的东西。

另一方面，JRuby 有一个 PIC，因此不必一直承受创建新方法句柄的开销。

使用 --indy 时冒泡排序的执行速度慢了 5 倍

Execution of bubble sort is 5 times slower with --indy

groovy

jruby

invokedynamic

java-8