Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8065159

AttributedString has quadratic resize algorithm

    Details

    • Type: Bug
    • Status: Closed
    • Priority: P2
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 9
    • Component/s: core-libs
    • Labels:
    • Subcomponent:
    • Resolved In Build:
      b42
    • CPU:
      generic
    • OS:
      generic

      Backports

        Description

        AttributedString has a data structure that grows by a constant amount, not a constant factor, scaling quadratically, not linearly.

        If you run the program below with -Dsize=2*NNN, it is ~4 times as expensive as -Dsize=NNN.

        import java.text.AttributedCharacterIterator;
        import java.text.AttributedString;
        import java.util.Map;
        import java.util.Collections;

        public class AttributedStringBenchmark {
            public static void main(String[] args) {
                class Att extends AttributedCharacterIterator.Attribute {
                    public Att(String name) { super(name); }
                }
                int size = Integer.getInteger("size", 1000);
                AttributedString attributedString =
                    new AttributedString(new String(new char[size]));
                Map<Att, Object> propertyMap =
                    Collections.singletonMap(new Att("foo"), (Object) "foo");
                for (int i = 0; i < size; i++)
                    attributedString.addAttributes(propertyMap, i, i+1);
            }
        }

          Attachments

            Issue Links

              Activity

                People

                • Assignee:
                  martin Martin Buchholz
                  Reporter:
                  martin Martin Buchholz
                • Votes:
                  0 Vote for this issue
                  Watchers:
                  3 Start watching this issue

                  Dates

                  • Created:
                    Updated:
                    Resolved: