Changeset 152306 in webkit
- Timestamp:
- Jul 2, 2013 12:09:44 PM (11 years ago)
- Location:
- trunk/Source
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/WTF/ChangeLog
r152289 r152306 1 2013-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 1 20 2013-07-02 Mikhail Pozdnyakov <mikhail.pozdnyakov@intel.com> 2 21 -
trunk/Source/WTF/wtf/text/StringBuilder.cpp
r134514 r152306 1 1 /* 2 * Copyright (C) 2010 Apple Inc. All rights reserved.2 * Copyright (C) 2010, 2013 Apple Inc. All rights reserved. 3 3 * Copyright (C) 2012 Google Inc. All rights reserved. 4 4 * … … 33 33 namespace WTF { 34 34 35 static const unsigned minimumCapacity = 16; 35 static 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 } 36 40 37 41 void StringBuilder::reifyString() const … … 225 229 ASSERT(m_buffer->length() >= m_length); 226 230 227 reallocateBuffer<CharType>( std::max(requiredLength, std::max(minimumCapacity, m_buffer->length() * 2)));231 reallocateBuffer<CharType>(expandedCapacity(capacity(), requiredLength)); 228 232 } else { 229 233 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)); 231 235 } 232 236 … … 260 264 ASSERT(m_buffer->length() >= m_length); 261 265 262 allocateBufferUpConvert(m_buffer->characters8(), requiredLength);266 allocateBufferUpConvert(m_buffer->characters8(), expandedCapacity(capacity(), requiredLength)); 263 267 } else { 264 268 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)); 266 270 } 267 271 -
trunk/Source/WebCore/ChangeLog
r152303 r152306 1 2013-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 1 14 2013-07-02 Tim Horton <timothy_horton@apple.com> 2 15 -
trunk/Source/WebCore/editing/TextIterator.cpp
r151505 r152306 2501 2501 { 2502 2502 // 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; 2504 2504 2505 2505 unsigned bufferLength = 0; 2506 2506 StringBuilder builder; 2507 builder.reserveCapacity( cMaxSegmentSize);2507 builder.reserveCapacity(initialCapacity); 2508 2508 TextIteratorBehavior behavior = defaultBehavior; 2509 2509 if (!isDisplayString) … … 2511 2511 2512 2512 for (TextIterator it(r, behavior); !it.atEnd(); it.advance()) { 2513 if (builder.capacity() < builder.length() + it.length())2514 builder.reserveCapacity(builder.capacity() + cMaxSegmentSize);2515 2516 2513 it.appendTextToStringBuilder(builder); 2517 2514 bufferLength += it.length();
Note: See TracChangeset
for help on using the changeset viewer.