Changeset 152306 in webkit


Ignore:
Timestamp:
Jul 2, 2013 12:09:44 PM (11 years ago)
Author:
ggaren@apple.com
Message:

plainText() is O(N2)
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(N2).
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(N2).

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.

Location:
trunk/Source
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/WTF/ChangeLog

    r152289 r152306  
     12013-07-02  Geoffrey Garen  <ggaren@apple.com>
     2
     3        plainText() is O(N^2)
     4        https://bugs.webkit.org/show_bug.cgi?id=118282
     5        <rdar://problem/14284360>
     6
     7        Reviewed by Alexey Proskuryakov.
     8
     9        * wtf/text/StringBuilder.cpp:
     10        (WTF::expandCapacity): Factored out this helper function to simplify
     11        some code that was duplicated in four places.
     12
     13        (WTF::StringBuilder::appendUninitializedSlow):
     14        (WTF::StringBuilder::append): Use expandCapacity(). One of the cases
     15        was not doing anything special, and so was O(N^2).
     16
     17        Also, always call expandCapacity() it in a standard way, calling
     18        capacity() first, so it's easy to tell at a glance that you got it right.
     19
    1202013-07-02  Mikhail Pozdnyakov  <mikhail.pozdnyakov@intel.com>
    221
  • trunk/Source/WTF/wtf/text/StringBuilder.cpp

    r134514 r152306  
    11/*
    2  * Copyright (C) 2010 Apple Inc. All rights reserved.
     2 * Copyright (C) 2010, 2013 Apple Inc. All rights reserved.
    33 * Copyright (C) 2012 Google Inc. All rights reserved.
    44 *
     
    3333namespace WTF {
    3434
    35 static const unsigned minimumCapacity = 16;
     35static size_t expandedCapacity(size_t capacity, size_t newLength)
     36{
     37    static const size_t minimumCapacity = 16;
     38    return std::max(capacity, std::max(minimumCapacity, newLength * 2));
     39}
    3640
    3741void StringBuilder::reifyString() const
     
    225229        ASSERT(m_buffer->length() >= m_length);
    226230       
    227         reallocateBuffer<CharType>(std::max(requiredLength, std::max(minimumCapacity, m_buffer->length() * 2)));
     231        reallocateBuffer<CharType>(expandedCapacity(capacity(), requiredLength));
    228232    } else {
    229233        ASSERT(m_string.length() == m_length);
    230         allocateBuffer(m_length ? m_string.getCharacters<CharType>() : 0, std::max(requiredLength, std::max(minimumCapacity, m_length * 2)));
     234        allocateBuffer(m_length ? m_string.getCharacters<CharType>() : 0, expandedCapacity(capacity(), requiredLength));
    231235    }
    232236   
     
    260264            ASSERT(m_buffer->length() >= m_length);
    261265           
    262             allocateBufferUpConvert(m_buffer->characters8(), requiredLength);
     266            allocateBufferUpConvert(m_buffer->characters8(), expandedCapacity(capacity(), requiredLength));
    263267        } else {
    264268            ASSERT(m_string.length() == m_length);
    265             allocateBufferUpConvert(m_string.isNull() ? 0 : m_string.characters8(), std::max(requiredLength, std::max(minimumCapacity, m_length * 2)));
     269            allocateBufferUpConvert(m_string.isNull() ? 0 : m_string.characters8(), expandedCapacity(capacity(), requiredLength));
    266270        }
    267271
  • trunk/Source/WebCore/ChangeLog

    r152303 r152306  
     12013-07-02  Geoffrey Garen  <ggaren@apple.com>
     2
     3        plainText() is O(N^2)
     4        https://bugs.webkit.org/show_bug.cgi?id=118282
     5        <rdar://problem/14284360>
     6
     7        Reviewed by Alexey Proskuryakov.
     8
     9        * editing/TextIterator.cpp:
     10        (WebCore::plainText): Linear growth for a vector data type is O(N^2).
     11        Don't do that. Luckily, StringBuilder does the right thing automatically,
     12        so we can just delete code.
     13
    1142013-07-02  Tim Horton  <timothy_horton@apple.com>
    215
  • trunk/Source/WebCore/editing/TextIterator.cpp

    r151505 r152306  
    25012501{
    25022502    // The initial buffer size can be critical for performance: https://bugs.webkit.org/show_bug.cgi?id=81192
    2503     static const unsigned cMaxSegmentSize = 1 << 15;
     2503    static const unsigned initialCapacity = 1 << 15;
    25042504
    25052505    unsigned bufferLength = 0;
    25062506    StringBuilder builder;
    2507     builder.reserveCapacity(cMaxSegmentSize);
     2507    builder.reserveCapacity(initialCapacity);
    25082508    TextIteratorBehavior behavior = defaultBehavior;
    25092509    if (!isDisplayString)
     
    25112511   
    25122512    for (TextIterator it(r, behavior); !it.atEnd(); it.advance()) {
    2513         if (builder.capacity() < builder.length() + it.length())
    2514             builder.reserveCapacity(builder.capacity() + cMaxSegmentSize);
    2515 
    25162513        it.appendTextToStringBuilder(builder);
    25172514        bufferLength += it.length();
Note: See TracChangeset for help on using the changeset viewer.