plainText() is O(N^2)
Created attachment 205870 [details] Patch
Comment on attachment 205870 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=205870&action=review > Source/WebCore/editing/TextIterator.cpp:2514 > if (builder.capacity() < builder.length() + it.length()) > - builder.reserveCapacity(builder.capacity() + cMaxSegmentSize); > + builder.reserveCapacity(builder.capacity() * 2); StringBuilder is supposed to do this internally. Would simply removing these lines fix the issue?
> StringBuilder is supposed to do this internally. Would simply removing these lines fix the issue? No. Prior to 10/13/10 <http://trac.webkit.org/changeset/69683>, StringBuilder used the Vector grow algorithm. Since then, it has used a "grow to fit the requested length exactly" algorithm. It seems like the change in r69683 was inadvertent. Perhaps we should revisit the project-wide behavior in future.
What about all that code saying "std::max(requiredLength, std::max(minimumCapacity, m_length * 2))" in StringBuilder.cpp? I didn't inspect all code paths, but it appears that it's there to implement capacity doubling.
Eep! How could I miss that?!
Now I have an excuse to fix two O(N^2) bugs in one patch!
Created attachment 205923 [details] Patch
Comment on attachment 205923 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=205923&action=review > Source/WTF/wtf/text/StringBuilder.cpp:35 > +static size_t expandCapacity(size_t capacity, size_t newLength) I'm very much not sure about this function name. The function doesn't expand any capacity, it only calculates one. Perhaps something like bestCapacity? suggestedCapacity? expandedCapacity?
Committed r152306: <http://trac.webkit.org/changeset/152306>
I went with expandedCapacity.