plainText() is O(N^2)
Created attachment 205870 [details]
Comment on attachment 205870 [details]
View in context: https://bugs.webkit.org/attachment.cgi?id=205870&action=review
> 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?
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]
Comment on attachment 205923 [details]
View in context: https://bugs.webkit.org/attachment.cgi?id=205923&action=review
> +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.