Bug 118282 – plainText() is O(N^2)

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Geoffrey Garen]

plainText() is O(N^2)

[Geoffrey Garen]

Created attachment 205870 [details]
Patch

[Alexey Proskuryakov]

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?

[Geoffrey Garen]

> 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.

[Alexey Proskuryakov]

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.

[Geoffrey Garen]

Eep! How could I miss that?!

[Geoffrey Garen]

Now I have an excuse to fix two O(N^2) bugs in one patch!

[Geoffrey Garen]

Created attachment 205923 [details]
Patch

[Alexey Proskuryakov]

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?

[Geoffrey Garen]

Committed r152306: <http://trac.webkit.org/changeset/152306>

[Geoffrey Garen]

I went with expandedCapacity.