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
Merge "Add a zero-copy path for Collections.sort() on ArrayList."