Opened 7 years ago

Closed 6 years ago

Last modified 6 years ago

#9135 closed optimization (fixed)

wxString::Replace() very slow

Reported by: hildensia Owned by:
Priority: normal Milestone:
Component: base Version:
Keywords: Cc: hildensia, vaclavslavik, kcwu@…
Blocked By: Blocking:
Patch: yes

Description

When you do a global replace on very large Strings with a lot of replacements (>10000 and so on) wxString::Replace() gets really slow. (> 20 s)

The problem is, that the string is copied every time a replacement is done, because of the use of wxStringImpl::replace().

I've rewritten wxString::Replace() to copy the string only once. It results in a ca. five times faster Replace().

Attachments (2)

string.patch download (2.9 KB) - added by hildensia 7 years ago.
diff-wxstring-replace.patch download (3.1 KB) - added by kcwu 6 years ago.

Download all attachments as: .zip

Change History (8)

Changed 7 years ago by hildensia

comment:1 Changed 7 years ago by vaclavslavik

Couple of comments:

  • Your patch doesn't apply on latest SVN sources (and it obviously isn't for 2.8 branch). Also, please follow wx coding guidelines -- in particular, don't use TABs.
  • I think it's more likely the problem is caused by bad Replace() implementation in UTF-8 build. I fixed that, if the problem persists (because you don't use UTF-8 build), please update the patch to work with latest SVN trunk (it would help to attach then benchmark you use, too).
  • The patch's replacing loop unnecessarily calls operator+= for every character in unmodified part, when it could simply do on append() to copy the unmodified block.

comment:2 Changed 6 years ago by sf-robot

This Tracker item was closed automatically by the system. It was
previously set to a Pending status, and the original submitter
did not respond within 14 days (the time period specified by
the administrator of this Tracker).

Changed 6 years ago by kcwu

comment:3 Changed 6 years ago by kcwu

  • Cc kcwu@… added
  • Component set to base
  • Status changed from closed to reopened
  • Type set to optimization

Based on hildensia's patch, I rewrite it for trunk.
And include simple benchmarks.

Before fix:
wxWidgets benchmarking program
Build: 2.9.0 (no debug,UTF-8,compiler with C++ ABI 1002,wx containers,compatible with 2.8)
Benchmarking ReplaceShorter: 16225ms total, 1613.75 avg (min=1543, max=1772)
Benchmarking ReplaceLonger: 31918ms total, 3141.88 avg (min=3129, max=3654)

With the patch:
Benchmarking ReplaceShorter: 3944ms total, 393.50 avg (min=387, max=409)
Benchmarking ReplaceLonger: 8010ms total, 794.25 avg (min=774, max=882)

comment:4 Changed 6 years ago by kcwu

And if the benchmark size change from ASCIISTR_LEN to ASCIISTR_LEN*10.

Before patch:
Benchmarking ReplaceShorter: 1353344ms total, 134538.38 avg (min=117583, max=159454)
Benchmarking ReplaceLonger: 2285396ms total, 224587.25 avg (min=220675, max=268023)

With the patch:
Benchmarking ReplaceShorter: 27603ms total, 2713.12 avg (min=2696, max=3202)
Benchmarking ReplaceLonger: 68371ms total, 6792.62 avg (min=6728, max=7302)

comment:5 Changed 6 years ago by VZ

  • Resolution set to fixed
  • Status changed from reopened to closed

(In [59420]) optimize Replace() to use a linear algorithm (closes #9135)

comment:6 Changed 6 years ago by vadz

Thanks for your patch, applied with minor changes.

Note: See TracTickets for help on using tickets.