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);
    }
}