plainText() is O(N^2)

https://bugs.webkit.org/show_bug.cgi?id=118282
<rdar://problem/14284360>

Reviewed by Alexey Proskuryakov.

Source/WebCore:

* editing/TextIterator.cpp:
(WebCore::plainText): Linear growth for a vector data type is O(N^2).
Don't do that. Luckily, StringBuilder does the right thing automatically,
so we can just delete code.

Source/WTF:

* wtf/text/StringBuilder.cpp:
(WTF::expandCapacity): Factored out this helper function to simplify
some code that was duplicated in four places.

(WTF::StringBuilder::appendUninitializedSlow):
(WTF::StringBuilder::append): Use expandCapacity(). One of the cases
was not doing anything special, and so was O(N^2).

Also, always call expandCapacity() it in a standard way, calling
capacity() first, so it's easy to tell at a glance that you got it right.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@152306 268f45cc-cd09-0410-ab3c-d52691b4dbfc

diff --git a/Source/WTF/ChangeLog b/Source/WTF/ChangeLog
index 61ce9f9..104acdc 100644 (file)
--- a/Source/WTF/ChangeLog
+++ b/Source/WTF/ChangeLog
@@ -1,3 +1,22 @@
+2013-07-02  Geoffrey Garen  <ggaren@apple.com>
+
+        plainText() is O(N^2)
+        https://bugs.webkit.org/show_bug.cgi?id=118282
+        <rdar://problem/14284360>
+
+        Reviewed by Alexey Proskuryakov.
+
+        * wtf/text/StringBuilder.cpp:
+        (WTF::expandCapacity): Factored out this helper function to simplify
+        some code that was duplicated in four places.
+
+        (WTF::StringBuilder::appendUninitializedSlow):
+        (WTF::StringBuilder::append): Use expandCapacity(). One of the cases
+        was not doing anything special, and so was O(N^2).
+
+        Also, always call expandCapacity() it in a standard way, calling
+        capacity() first, so it's easy to tell at a glance that you got it right.
+
 2013-07-02  Mikhail Pozdnyakov  <mikhail.pozdnyakov@intel.com>
 
         Avoid code duplication inside String::append()

diff --git a/Source/WTF/wtf/text/StringBuilder.cpp b/Source/WTF/wtf/text/StringBuilder.cpp
index a143d0a..81e5d27 100644 (file)
--- a/Source/WTF/wtf/text/StringBuilder.cpp
+++ b/Source/WTF/wtf/text/StringBuilder.cpp
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2010 Apple Inc. All rights reserved.
+ * Copyright (C) 2010, 2013 Apple Inc. All rights reserved.
  * Copyright (C) 2012 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -32,7 +32,11 @@
 
 namespace WTF {
 
-static const unsigned minimumCapacity = 16;
+static size_t expandedCapacity(size_t capacity, size_t newLength)
+{
+    static const size_t minimumCapacity = 16;
+    return std::max(capacity, std::max(minimumCapacity, newLength * 2));
+}
 
 void StringBuilder::reifyString() const
 {
@@ -224,10 +228,10 @@ CharType* StringBuilder::appendUninitializedSlow(unsigned requiredLength)
         // If the buffer is valid it must be at least as long as the current builder contents!
         ASSERT(m_buffer->length() >= m_length);
         
-        reallocateBuffer<CharType>(std::max(requiredLength, std::max(minimumCapacity, m_buffer->length() * 2)));
+        reallocateBuffer<CharType>(expandedCapacity(capacity(), requiredLength));
     } else {
         ASSERT(m_string.length() == m_length);
-        allocateBuffer(m_length ? m_string.getCharacters<CharType>() : 0, std::max(requiredLength, std::max(minimumCapacity, m_length * 2)));
+        allocateBuffer(m_length ? m_string.getCharacters<CharType>() : 0, expandedCapacity(capacity(), requiredLength));
     }
     
     CharType* result = getBufferCharacters<CharType>() + m_length;
@@ -259,10 +263,10 @@ void StringBuilder::append(const UChar* characters, unsigned length)
             // If the buffer is valid it must be at least as long as the current builder contents!
             ASSERT(m_buffer->length() >= m_length);
             
-            allocateBufferUpConvert(m_buffer->characters8(), requiredLength);
+            allocateBufferUpConvert(m_buffer->characters8(), expandedCapacity(capacity(), requiredLength));
         } else {
             ASSERT(m_string.length() == m_length);
-            allocateBufferUpConvert(m_string.isNull() ? 0 : m_string.characters8(), std::max(requiredLength, std::max(minimumCapacity, m_length * 2)));
+            allocateBufferUpConvert(m_string.isNull() ? 0 : m_string.characters8(), expandedCapacity(capacity(), requiredLength));
         }
 
         memcpy(m_bufferCharacters16 + m_length, characters, static_cast<size_t>(length) * sizeof(UChar));        

diff --git a/Source/WebCore/ChangeLog b/Source/WebCore/ChangeLog
index 64855d0..3b4972e 100644 (file)
--- a/Source/WebCore/ChangeLog
+++ b/Source/WebCore/ChangeLog
@@ -1,3 +1,16 @@
+2013-07-02  Geoffrey Garen  <ggaren@apple.com>
+
+        plainText() is O(N^2)
+        https://bugs.webkit.org/show_bug.cgi?id=118282
+        <rdar://problem/14284360>
+
+        Reviewed by Alexey Proskuryakov.
+
+        * editing/TextIterator.cpp:
+        (WebCore::plainText): Linear growth for a vector data type is O(N^2).
+        Don't do that. Luckily, StringBuilder does the right thing automatically,
+        so we can just delete code.
+
 2013-07-02  Tim Horton  <timothy_horton@apple.com>
 
         constrainScrollPositionForOverhang needs to handle scrollOrigin correctly

diff --git a/Source/WebCore/editing/TextIterator.cpp b/Source/WebCore/editing/TextIterator.cpp
index ddf5d07..36953f7 100644 (file)
--- a/Source/WebCore/editing/TextIterator.cpp
+++ b/Source/WebCore/editing/TextIterator.cpp
@@ -2500,19 +2500,16 @@ bool TextIterator::getLocationAndLengthFromRange(Node* scope, const Range* range
 String plainText(const Range* r, TextIteratorBehavior defaultBehavior, bool isDisplayString)
 {
     // The initial buffer size can be critical for performance: https://bugs.webkit.org/show_bug.cgi?id=81192
-    static const unsigned cMaxSegmentSize = 1 << 15;
+    static const unsigned initialCapacity = 1 << 15;
 
     unsigned bufferLength = 0;
     StringBuilder builder;
-    builder.reserveCapacity(cMaxSegmentSize);
+    builder.reserveCapacity(initialCapacity);
     TextIteratorBehavior behavior = defaultBehavior;
     if (!isDisplayString)
         behavior = static_cast<TextIteratorBehavior>(behavior | TextIteratorEmitsTextsWithoutTranscoding);
     
     for (TextIterator it(r, behavior); !it.atEnd(); it.advance()) {
-        if (builder.capacity() < builder.length() + it.length())
-            builder.reserveCapacity(builder.capacity() + cMaxSegmentSize);
-
         it.appendTextToStringBuilder(builder);
         bufferLength += it.length();
     }