8065159: AttributedString has quadratic resize algorithm
Summary: Grow backing arrays geometrically instead of arithmetically
Reviewed-by: naoto, okutsu
--- 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