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

Question

我写了一个冒泡排序的实现,与Groovy一起玩,看看是否--indy对性能有任何明显的影响.

从本质上讲,它对一千个随机整数的列表进行了一千次排序,并测量了对列表进行排序的平均执行时间.

列表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使用情况,编译时的CPU使用率--indy要比非编译时高很多.

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

没有--indy:

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并尝试了同样的事情,但结果是相似的,尽管如果没有JRuby,它就不那么快了invokedynamic:

$ 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形式最初较慢,而峰值性能更好.基本上你要做的是让热点从头开始进行大多数方法调用,防止它一直应用优化.当然这不是你的错,而是因为还没有PIC的Groovy的错.并且只是为了使这个非常清楚...这不是语言的问题,它只是我还没有实现的东西.

另一方面,JRuby具有PIC,因此不必担心始终创建新方法句柄的开销.