74904 - ReplaceSubstring is O(n^2) (SLOW SLOW SLOW)

Status: RESOLVED DUPLICATE of bug 82456

(Core :: XPCOM, defect)

Description

[David Hyatt]

The ReplaceSubstring implementation is O(n^2), when it should be O(n).  40% of
mailnews reply performance on large messages is in this method.

Comment 1

[Scott Collins]

|ns[C]String::ReplaceSubstring| doesn't even work in all cases; rickg left a
warning there

  //WARNING: This is not working yet!!!!!

I was just about to provide a new implementation that works on all strings, not
just |ns[C]String|s.  See bug #74896.

Comment 2

[Scott Collins]

These are the 0.9 bugs that didn't make it, and that I intend to fix in 0.9.1

Comment 3

[Scott Collins]

re-targeting milestones, starting from a clean slate

Comment 4

[Scott Collins]

marking the functionality blockers for immediate attention in mozilla0.9.1

Comment 5

[Scott Collins]

What is being replaced in the mail/news case?  If |ReplaceSubstring| is being
used for CRLF conversion, then a more specific solution may be appropriate.  David?

Comment 6

[Chris Waterson]

If you're going to work on ReplaceSubstring(), how about moving the real
implementation into a global function that works on an nsAWritableString, and
then re-implement the ns[C]String::ReplaceSubstring() method in terms of that?
(That's probably already your plan, but I thought I'd make it explicit.)

There are some places in my own code where I could use this.

Comment 7

[chris hofmann]

let's land this in 0.9.2. let drivers know if this creates problems. thanks.

Comment 8

[Scott Collins]

The fix to this bug is that we're going to replace the entire implementation of
|ReplaceSubstring| with the new |nsSubstituteC?String| generator.  See bug
#82456.  There's no perfect way to mark this bug for this resolution (it's not
FIXED yet, it's not INVALID, it's not WONTFIX).  We'll settle for making it a
dup of the new bug.

*** This bug has been marked as a duplicate of 82456 ***