| 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
|