New issue
Advanced search Search tips
Note: Color blocks (like █ or █) mean that a user may not be available. Tooltip shows the reason.

Issue 760330 link

Starred by 2 users
Status: Fixed
Owner:
█ nick@chromium.org
not working at Google anymore
Closed: Sep 2017
Components:
EstimatedDays: ----
NextAction: ----
OS: ----
Pri: 3
Type: Bug



Sign in to add a comment

[string_util] base::ReplaceChars and base::RemoveChars can be O(n^2)

Project Member Reported by nick@chromium.org, Aug 29 2017 
base::ReplaceChars and base::RemoveChars can be O(n^2) in the worst case.

A loop like the below shows the problem:

std::string value = "*";
for (int i = 0; i < 20; i++) {
  base::ReplaceChars(value, "*", "**", &value);
}
Project Member

Comment 1 by bugdroid1@chromium.org, Sep 26 2017 

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/b1e364df6b2f944f8879737a61e45a991a96f518

commit b1e364df6b2f944f8879737a61e45a991a96f518
Author: Nick Carter <nick@chromium.org>
Date: Tue Sep 26 18:28:45 2017

Fix O(n^2) performance in base::ReplaceChars() and base::RemoveChars()

ReplaceChars and RemoveChars can actually be implemented in terms of
the algorithm used for ReplaceSubstringsAfterOffset(), which is already
finely tuned to do this operation in linear time. The only difference
is to swap out which find function is used, which is accomplished here
by a boolean parameter.

Bug:  756585 
Bug:  760330 
Change-Id: I780dc996e360b75dc8845af90cfc7e2afed2cd6d
Reviewed-on: https://chromium-review.googlesource.com/642357
Commit-Queue: Nick Carter <nick@chromium.org>
Reviewed-by: Daniel Cheng <dcheng@chromium.org>
Cr-Commit-Position: refs/heads/master@{#504430}
[modify] https://crrev.com/b1e364df6b2f944f8879737a61e45a991a96f518/base/strings/string_util.cc
[modify] https://crrev.com/b1e364df6b2f944f8879737a61e45a991a96f518/base/strings/string_util_unittest.cc

Comment 2 by nick@chromium.org, Sep 26 2017

Status: Fixed (was: Assigned)
Fixed by https://chromium-review.googlesource.com/c/chromium/src/+/642357
►

Sign in to add a comment