Bug 118282 - plainText() is O(N^2)
Summary: plainText() is O(N^2)
Alias: None
Product: WebKit
Classification: Unclassified
Component: New Bugs (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Geoffrey Garen
Depends on:
Reported: 2013-07-01 23:06 PDT by Geoffrey Garen
Modified: 2013-07-02 12:10 PDT (History)
3 users (show)

See Also:

Patch (1.40 KB, patch)
2013-07-01 23:08 PDT, Geoffrey Garen
no flags Details | Formatted Diff | Diff
Patch (5.28 KB, patch)
2013-07-02 09:40 PDT, Geoffrey Garen
ap: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Geoffrey Garen 2013-07-01 23:06:52 PDT
plainText() is O(N^2)
Comment 1 Geoffrey Garen 2013-07-01 23:08:23 PDT
Created attachment 205870 [details]
Comment 2 Alexey Proskuryakov 2013-07-01 23:27:12 PDT
Comment on attachment 205870 [details]

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?
Comment 3 Geoffrey Garen 2013-07-01 23:48:55 PDT
> 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.
Comment 4 Alexey Proskuryakov 2013-07-02 08:42:08 PDT
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.
Comment 5 Geoffrey Garen 2013-07-02 09:30:26 PDT
Eep! How could I miss that?!
Comment 6 Geoffrey Garen 2013-07-02 09:35:51 PDT
Now I have an excuse to fix two O(N^2) bugs in one patch!
Comment 7 Geoffrey Garen 2013-07-02 09:40:50 PDT
Created attachment 205923 [details]
Comment 8 Alexey Proskuryakov 2013-07-02 09:49:59 PDT
Comment on attachment 205923 [details]

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?
Comment 9 Geoffrey Garen 2013-07-02 12:10:19 PDT
Committed r152306: <http://trac.webkit.org/changeset/152306>
Comment 10 Geoffrey Garen 2013-07-02 12:10:56 PDT
I went with expandedCapacity.