8065159: AttributedString has quadratic resize algorithm
authormartin
Fri, 21 Nov 2014 16:30:02 -0800
changeset 27751 e81623e39d23
parent 27750 fe4052cc2c89
child 27752 3f181f406145
8065159: AttributedString has quadratic resize algorithm Summary: Grow backing arrays geometrically instead of arithmetically Reviewed-by: naoto, okutsu
jdk/src/java.base/share/classes/java/text/AttributedString.java
--- a/jdk/src/java.base/share/classes/java/text/AttributedString.java	Fri Nov 21 13:32:17 2014 -0800
+++ b/jdk/src/java.base/share/classes/java/text/AttributedString.java	Fri Nov 21 16:30:02 2014 -0800
@@ -48,21 +48,18 @@
  */
 
 public class AttributedString {
-
-    // since there are no vectors of int, we have to use arrays.
-    // We allocate them in chunks of 10 elements so we don't have to allocate all the time.
-    private static final int ARRAY_SIZE_INCREMENT = 10;
-
     // field holding the text
     String text;
 
-    // fields holding run attribute information
-    // run attributes are organized by run
-    int runArraySize;               // current size of the arrays
-    int runCount;                   // actual number of runs, <= runArraySize
-    int runStarts[];                // start index for each run
-    Vector<Attribute> runAttributes[];         // vector of attribute keys for each run
-    Vector<Object> runAttributeValues[];    // parallel vector of attribute values for each run
+    // Fields holding run attribute information.
+    // Run attributes are organized by run.
+    // Arrays are always of equal lengths (the current capacity).
+    // Since there are no vectors of int, we have to use arrays.
+    private static final int INITIAL_CAPACITY = 10;
+    int runCount;                   // actual number of runs, <= current capacity
+    int[] runStarts;                // start index for each run
+    Vector<Attribute>[] runAttributes;   // vector of attribute keys for each run
+    Vector<Object>[] runAttributeValues; // parallel vector of attribute values for each run
 
     /**
      * Constructs an AttributedString instance with the given
@@ -416,18 +413,17 @@
 
     private final void createRunAttributeDataVectors() {
         // use temporary variables so things remain consistent in case of an exception
-        int newRunStarts[] = new int[ARRAY_SIZE_INCREMENT];
+        int[] newRunStarts = new int[INITIAL_CAPACITY];
 
         @SuppressWarnings("unchecked")
-        Vector<Attribute> newRunAttributes[] = (Vector<Attribute>[]) new Vector<?>[ARRAY_SIZE_INCREMENT];
+        Vector<Attribute>[] newRunAttributes = (Vector<Attribute>[]) new Vector<?>[INITIAL_CAPACITY];
 
         @SuppressWarnings("unchecked")
-        Vector<Object> newRunAttributeValues[] = (Vector<Object>[]) new Vector<?>[ARRAY_SIZE_INCREMENT];
+        Vector<Object>[] newRunAttributeValues = (Vector<Object>[]) new Vector<?>[INITIAL_CAPACITY];
 
         runStarts = newRunStarts;
         runAttributes = newRunAttributes;
         runAttributeValues = newRunAttributeValues;
-        runArraySize = ARRAY_SIZE_INCREMENT;
         runCount = 1; // assume initial run starting at index 0
     }
 
@@ -465,25 +461,22 @@
 
         // we'll have to break up a run
         // first, make sure we have enough space in our arrays
-        if (runCount == runArraySize) {
-            int newArraySize = runArraySize + ARRAY_SIZE_INCREMENT;
-            int newRunStarts[] = new int[newArraySize];
-
-            @SuppressWarnings("unchecked")
-            Vector<Attribute> newRunAttributes[] = (Vector<Attribute>[]) new Vector<?>[newArraySize];
+        int currentCapacity = runStarts.length;
+        if (runCount == currentCapacity) {
+            // We need to resize - we grow capacity by 25%.
+            int newCapacity = currentCapacity + (currentCapacity >> 2);
 
-            @SuppressWarnings("unchecked")
-            Vector<Object> newRunAttributeValues[] = (Vector<Object>[]) new Vector<?>[newArraySize];
+            // use temporary variables so things remain consistent in case of an exception
+            int[] newRunStarts =
+                Arrays.copyOf(runStarts, newCapacity);
+            Vector<Attribute>[] newRunAttributes =
+                Arrays.copyOf(runAttributes, newCapacity);
+            Vector<Object>[] newRunAttributeValues =
+                Arrays.copyOf(runAttributeValues, newCapacity);
 
-            for (int i = 0; i < runArraySize; i++) {
-                newRunStarts[i] = runStarts[i];
-                newRunAttributes[i] = runAttributes[i];
-                newRunAttributeValues[i] = runAttributeValues[i];
-            }
             runStarts = newRunStarts;
             runAttributes = newRunAttributes;
             runAttributeValues = newRunAttributeValues;
-            runArraySize = newArraySize;
         }
 
         // make copies of the attribute information of the old run that the new one used to be part of