Bug 118282

Summary: plainText() is O(N^2)
Product: WebKit Reporter: Geoffrey Garen <ggaren>
Component: New BugsAssignee: Geoffrey Garen <ggaren>
Status: RESOLVED FIXED    
Severity: Normal CC: ap, benjamin, msaboff
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
Patch
none
Patch ap: review+

Geoffrey Garen
Reported 2013-07-01 23:06:52 PDT
plainText() is O(N^2)
Attachments
Patch (1.40 KB, patch)
2013-07-01 23:08 PDT, Geoffrey Garen 		no flags
DetailsFormatted DiffDiff
Patch (5.28 KB, patch)
2013-07-02 09:40 PDT, Geoffrey Garen 		ap: review+
DetailsFormatted DiffDiff
Show Obsolete (1) View All Add attachment proposed patch, testcase, etc.
Geoffrey Garen
Comment 1 2013-07-01 23:08:23 PDT
Created attachment 205870 [details] Patch
Alexey Proskuryakov
Comment 2 2013-07-01 23:27:12 PDT
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
Comment 3 2013-07-01 23:48:55 PDT
> 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
Comment 4 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.
Geoffrey Garen
Comment 5 2013-07-02 09:30:26 PDT
Eep! How could I miss that?!
Geoffrey Garen
Comment 6 2013-07-02 09:35:51 PDT
Now I have an excuse to fix two O(N^2) bugs in one patch!
Geoffrey Garen
Comment 7 2013-07-02 09:40:50 PDT
Created attachment 205923 [details] Patch
Alexey Proskuryakov
Comment 8 2013-07-02 09:49:59 PDT
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
Comment 9 2013-07-02 12:10:19 PDT
Committed r152306: <http://trac.webkit.org/changeset/152306>
Geoffrey Garen
Comment 10 2013-07-02 12:10:56 PDT
I went with expandedCapacity.
Note You need to log in before you can comment on or make changes to this bug.