From: ggaren@apple.com Date: Tue, 2 Jul 2013 19:09:44 +0000 (+0000) Subject: plainText() is O(N^2) X-Git-Url: http://git.webkit.org/?p=WebKit-https.git;a=commitdiff_plain;h=a13b1ec28d7f6e65b6fc092d890817bb12a78431 plainText() is O(N^2) https://bugs.webkit.org/show_bug.cgi?id=118282 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 --- a/Source/WTF/ChangeLog +++ b/Source/WTF/ChangeLog @@ -1,3 +1,22 @@ +2013-07-02 Geoffrey Garen + + plainText() is O(N^2) + https://bugs.webkit.org/show_bug.cgi?id=118282 + + + 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 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 --- 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(std::max(requiredLength, std::max(minimumCapacity, m_buffer->length() * 2))); + reallocateBuffer(expandedCapacity(capacity(), requiredLength)); } else { ASSERT(m_string.length() == m_length); - allocateBuffer(m_length ? m_string.getCharacters() : 0, std::max(requiredLength, std::max(minimumCapacity, m_length * 2))); + allocateBuffer(m_length ? m_string.getCharacters() : 0, expandedCapacity(capacity(), requiredLength)); } CharType* result = getBufferCharacters() + 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(length) * sizeof(UChar)); diff --git a/Source/WebCore/ChangeLog b/Source/WebCore/ChangeLog index 64855d0..3b4972e 100644 --- a/Source/WebCore/ChangeLog +++ b/Source/WebCore/ChangeLog @@ -1,3 +1,16 @@ +2013-07-02 Geoffrey Garen + + plainText() is O(N^2) + https://bugs.webkit.org/show_bug.cgi?id=118282 + + + 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 constrainScrollPositionForOverhang needs to handle scrollOrigin correctly diff --git a/Source/WebCore/editing/TextIterator.cpp b/Source/WebCore/editing/TextIterator.cpp index ddf5d07..36953f7 100644 --- 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(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(); }