| Summary: | plainText() is O(N^2) | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Product: | WebKit | Reporter: | Geoffrey Garen <ggaren> | ||||||
| Component: | New Bugs | Assignee: | Geoffrey Garen <ggaren> | ||||||
| Status: | RESOLVED FIXED | ||||||||
| Severity: | Normal | CC: | ap, benjamin, msaboff | ||||||
| Priority: | P2 | ||||||||
| Version: | 528+ (Nightly build) | ||||||||
| Hardware: | Unspecified | ||||||||
| OS: | Unspecified | ||||||||
| Attachments: |
|
||||||||
|
Description
Geoffrey Garen
2013-07-01 23:06:52 PDT
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. |