On 12/18/18 1:49 PM, Jason Mehrens wrote:
The reason the patched code is faster is because it will avoid an array resize
that is triggered in the benchmark by:
"// once a new ArrayList is created add a new element
al.add(new Integer(900));"
http://cr.openjdk.java.net/~sgroeger/perf/arraylist/ArrayListBenchmark.java
If you look at the patch, it is over provisioning the backing array by using
"elements.length" (elementData = new Object[((ArrayList)c).elementData.length];)
instead of "size". The toArray call uses size and then the benchmark adds one
element to trigger the resize.
Yep, that's the reason. I was arriving at the same conclusion but you beat me to
it. I modified the patch to base the length of elementData on 'size' instead of
the other elementData.length, and also to preserve the EMPTY_ELEMENTDATA sentinel:
@@ -176,6 +176,15 @@
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
+ if (c.getClass() == ArrayList.class) {
+ ArrayList<?> other = (ArrayList<?>)c;
+ int sz = other.size;
+ if ((size = sz) == 0) {
+ elementData = EMPTY_ELEMENTDATA;
+ } else {
+ elementData = Arrays.copyOf(other.elementData, sz);
+ }
+ } else {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// defend against c.toArray (incorrectly) not returning Object[]
and some quick benchmark runs don't show any improvement over the baseline.
Well, there might be a tiny improvement, but it's well within the margin of
error, so I'm not sure.
Not sure if over provisioning the backing array is the right choice. I tend to
lean towards the current paradigm of exact sizing on copy.
I agree, I don't think we want to change this behavior. There may be
applications that rely on the exact size, e.g. to release memory by making a
copy of a list after having removed a lot of elements.
s'marks
