Tuesday, October 26, 2004

The FastCode AnsiStringReplace results are in

The results of the FastCode AnsiStringReplace competition are in:

http://dennishomepage.gugs-cats.dk/AnsiStrReplaceChallenge.htm

The fastest entry is some 7-9 times faster than the RTL reference version (depending on the CPU). My own contribution scored less than 3 times faster... ;). Note that real-world speed gain will vary considerably - as always what you benchmark determines the results.

When that is said, Eric Grange's winning entry has some really neat tricks. The most important trick is to search for and store the position of all hits in the source string before allocating the result string and copying over the string data. Another is to use an upper-case character table to avoid pre-upping strings in the case-insensitive mode.

A much faster StringReplace can be nice, but before you jump in, consider if StringReplace really is the right tool for the job at hand. As Martin James put it in the delphi.non-tech newsgroup:

"In anything other than trivial cases with small strings, I always use a char-by-char state machine anyway, certainly with HTML text parsing/tag handling. In such cases, any 'stringReplace' is hugely inefficient."

My response was:

"Yes, you are right. If you want performance, using StringReplace is most probably the wrong solution (no matter how fast it is). Most of the time you don't want to replace a single string, you want to replace a number of strings/patterns. A custom parser using a state-machine is often the best solution, performance wise. However, such optimizations might be prohibitively expensive to develop for simple problems where StringReplace will suffice."

And on the FastStrings comment from my last blog entry, here are the results on one CPU:

P4 1600A Northwood
StringReplace_EG_MMX_1 8 671 1165 1836 // Eric Grange = 1836 ms
...
StringReplace_HV_IA32_1 4 2846 5018 7864 // Mine = 7864 ms
StringReplace_DKC_Pas_1 8 4565 4990 9555
FastAnsiReplace 0 4382 9248 13630 // FastStrings version = 13630 ms
StringReplaceRef 0 5523 9514 15037 // Bug-fixed RTL version = 15037 ms
StringReplaceRTL 8 6848 13336 20184 // RTL version = 20184 ms

So even my version kicked FastStrings ReplaceString... <bg>. And even as we speak, those delphi.language.basm folks are now cooperating to improve the blind-test winners few notches more...

3 comments:

Anonymous said...

Yep, the benefits of a fast StringReplace are:
- allow you to be lazy in more situations
- have Junior developper's code behave decently without expensive refactoring

State-machines are nice, but not that many people can write decent ones in my experience... and I've encountered very awful ones :p

Hallvard Vassbotn said...

Update: the FastCode winner is almost 17 times faster now. See also FastCoder's 2004 New Year's Speech

Anonymous said...
This comment has been removed by a blog administrator.


Copyright © 2004-2007 by Hallvard Vassbotn