Proposal: ArrayList constructor perforrmance improvement

[Stuart Marks]

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