36776bc03ce03eef27c70a9750513ce6d6d19385 |
|
31-Dec-2014 |
Narayan Kamath <narayan@google.com> |
Extend ArrayList fastpath to Collections.sort(List<T>, Comparator<T>). My original reasons for not extending it were bogus. We can safely cast Object[] to T[] in this case. Also tidy up the benchmark by changing buildList(.. boolean isArrayList) to buildList(.. Class<T extends List<Integer> list. AFTER SortWithComparator_arrayList, arrayListLength=4} 10881.97 ns; σ=64.97 ns @ 3 trials SortWithComparator_arrayList, arrayListLength=16} 33235.73 ns; σ=127.45 ns @ 3 trials SortWithComparator_arrayList, arrayListLength=64} 130317.52 ns; σ=135.31 ns @ 3 trials SortWithComparator_arrayList, arrayListLength=256} 495200.19 ns; σ=1120.86 ns @ 3 trials SortWithComparator_arrayList, arrayListLength=1024} 1990796.02 ns; σ=19151.58 ns @ 6 trials BEFORE SortWithComparator_arrayList, arrayListLength=4} 40030.32 ns; σ=509.60 ns @ 10 trials SortWithComparator_arrayList, arrayListLength=16} 122122.08 ns; σ=182.58 ns @ 3 trials SortWithComparator_arrayList, arrayListLength=64} 457833.87 ns; σ=1311.54 ns @ 3 trials SortWithComparator_arrayList, arrayListLength=256} 1764647.22 ns; σ=35150.74 ns @ 10 trials SortWithComparator_arrayList, arrayListLength=1024} 7127679.90 ns; σ=122546.75 ns @ 10 trials bug: 18821961 Change-Id: I22a18d99598dfacbdc54cf75e38dbc32ab027754
|
fa080b83161fa8f2c538009b312d074dd17016bc |
|
24-Dec-2014 |
Narayan Kamath <narayan@google.com> |
Add a zero-copy path for Collections.sort() on ArrayList. Given that ArrayLists are array backed, we can sort the underlying array in place. A similar optimisation can be applied to Vector and CopyOnWriteArrayList but vector isn't used often enough to slow everything else down with an instanceof check and nobody should be daft enough to try sorting a CopyOnWriteArrayList. Note that it's possible to apply the same optimisation to Collections.sort(List<T>, Comparator<? super T>) but it involves a larger refactoring to allow us to use Object[] instead of T[] and is accompanied by a general loss of readability. ArrayList performance improves for all array sizes : BEFORE Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=4} 39021.26 ns; σ=206.27 ns @ 3 trials Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=16} 120903.59 ns; σ=1188.88 ns @ 5 trials Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=64} 435484.98 ns; σ=19141.88 ns @ 10 trials Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=256} 1772876.81 ns; σ=5542.74 ns @ 3 trials Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=1024} 7289431.83 ns; σ=110869.13 ns @ 10 trials AFTER Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=4} 9161.79 ns; σ=90.04 ns @ 6 trials Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=16} 29988.90 ns; σ=74.05 ns @ 3 trials Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=64} 118142.86 ns; σ=1133.52 ns @ 7 trials Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=256} 456091.11 ns; σ=9110.18 ns @ 10 trials Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=1024} 1851939.39 ns; σ=69542.41 ns @ 10 trials For all other lists, there's no measurable difference for most sizes. length == 4 is harder to be sure about, given the large standard deviations and we'd expect the time spent in instanceof to be larger relative to the rest of what's going on. BEFORE Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=4} 49002.02 ns; σ=1392.58 ns @ 10 trials Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=16} 154967.88 ns; σ=332.29 ns @ 3 trials Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=64} 588207.14 ns; σ=1863.60 ns @ 3 trials Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=256} 2292967.79 ns; σ=4578.14 ns @ 3 trials Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=1024} 9299582.60 ns; σ=179459.24 ns @ 10 trials AFTER Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=4} 49324.98 ns; σ=240.86 ns @ 3 trials Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=16} 155639.91 ns; σ=215.12 ns @ 3 trials Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=64} 581950.81 ns; σ=938.11 ns @ 3 trials Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=256} 2285933.64 ns; σ=13265.42 ns @ 3 trials Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=1024} 8981475.84 ns; σ=431676.48 ns @ 10 trials bug: 18821961 Change-Id: I30a3eaf89ff478663f555c93556167107da10873
|