Proposal: ArrayList constructor perforrmance improvement

Stuart Marks stuart.marks at
Wed Dec 19 00:03:07 UTC 2018

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));"
> 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.


More information about the core-libs-dev mailing list