Really strange performance problem with string map vs regsub
skuh...@web.de
I have a very strange performance behaviour here, which I can't
explain. If
someone could enlighten me, it would be a great help:
I have a data string with about 128k length, containing 16k "words"
where I need
to replace parts of as fast as possible. I used [string map] first,
because I
thought, this must be very fast. But then I checked [regsub] and it
was even
faster, which I found a little bit strange, since there is the whole
regexp-machinery behind it. Then I thought, [regsub {***=...}] should
be even
faster, since it uses a fixed string, but it wasn't... This really
made me
wonder, so I wrote some tests and it seems to be, that the performance
is very
dependend on length and format (!) of the data. Especially the last
thing is
what puzzles me, since not only EIAS but also a string is a string, is
it?
Here is a test, which I tried with 8.4.13 and 8.5a6:
######################################################################
proc timeTest {} {
set s0 [string repeat "qwertzu " 16384]
puts "Character string: [string length $s0]"
puts "string map"
puts [time {string map {rt RT} $s0} 1000]
puts "regsub -all"
puts [time {regsub {rt} $s0 RT} 1000]
puts "regsub -all ***="
puts [time {regsub {***=rt} $s0 RT} 1000]
#-----------------------------------------------------------------------------
set s1 [string repeat "Qdd%Xdd " 16384]
puts "Placeholder String: [string length $s1]"
puts "string map"
puts [time {string map {%X **} $s1} 1000]
puts "regsub -all"
puts [time {regsub -all {%X} $s1 **} 1000]
puts "regsub -all ***="
puts [time {regsub -all {***=%X} $s1 **} 1000]
puts [string range $s0 0 100]
puts [string range $s1 0 100]
}
timeTest
######################################################################
The results are nearly identical for the two Tcl-versions (8.5 is a
little bit
faster), but very strange:
Character string: 131072
string map
5415.17 microseconds per iteration
regsub -all
1091.12 microseconds per iteration
regsub -all ***=
1084.06 microseconds per iteration
Placeholder String: 131072
string map
5437.74 microseconds per iteration
regsub -all
5347.31 microseconds per iteration
regsub -all ***=
43599.2 microseconds per iteration
qwertzu qwertzu qwertzu qwertzu qwertzu qwertzu qwertzu qwertzu
qwertzu qwertzu qwertzu qwertzu qwert
Qdd%Xdd Qdd%Xdd Qdd%Xdd Qdd%Xdd Qdd%Xdd Qdd%Xdd Qdd%Xdd Qdd%Xdd Qdd
%Xdd Qdd%Xdd Qdd%Xdd Qdd%Xdd Qdd%X
As you can see, [regsub] in both flavours is nearly as five times as
fast as
[string map] with the first data string. With the second data string,
[string
map] and the normal [regsub] are equally fast (or slow...), but the
[regsub
***=], which should be at least faster compared to the normal version,
is nearly
ten times SLOWER now!!! Looking at the strings, I can't find any
explanation for
this, since there no such huge differences in it.
Can someone explain that to me?
TIA, regards
Stephan
Bryan Oakley
> Here is a test, which I tried with 8.4.13 and 8.5a6:
>
> ######################################################################
> proc timeTest {} {
> set s0 [string repeat "qwertzu " 16384]
> puts "Character string: [string length $s0]"
> puts "string map"
> puts [time {string map {rt RT} $s0} 1000]
> puts "regsub -all"
> puts [time {regsub {rt} $s0 RT} 1000]
> puts "regsub -all ***="
> puts [time {regsub {***=rt} $s0 RT} 1000]
In the above statements you say you are doing "regsub -all" in the puts
statement, but do not include the -all argument in the actual call. Was
that on purpose?
That would certainly account for some of the time differences you are
seeing.
skuh...@web.de
Bryan Oakley wrote:
> In the above statements you say you are doing "regsub -all" in the puts
> statement, but do not include the -all argument in the actual call. Was
> that on purpose?
>
> That would certainly account for some of the time differences you are
> seeing.
Yes, that was really stupid, of course it should be -all. But also
with -all normal [regsub] is a little bit faster than [string map],
but [regsub ***=] is about ten times slower. I don't understand that.
Maybe there is another such stupid thing I do not see in my own
code...?
Thanks, regards
Stephan
Jeff Hobbs
> I have a data string with about 128k length, containing 16k "words"
> where I need to replace parts of as fast as possible. I used [string
> map] first, because I thought, this must be very fast. But then I
> checked [regsub] and it was even faster, which I found a little bit
> strange, since there is the whole regexp-machinery behind it. Then I
> thought, [regsub {***=...}] should be even faster, since it uses a
> fixed string, but it wasn't... This really made me wonder, so I wrote
> some tests and it seems to be, that the performance is very dependend
> on length and format (!) of the data. Especially the last thing is
> what puzzles me, since not only EIAS but also a string is a string,
> is it?
I believe your benchmark tests are flawed. I have rewritten them to
recreate a new s0/s1 string each time, and find the more consistent
timings of:
Character string: 131072
string map
9722.719 microseconds per iteration
regsub -all
10419.861 microseconds per iteration
regsub -all ***=
78603.581 microseconds per iteration
with the other timings similar. This is also correcting your test to
use -all for the regsub. This is also logically consistent. I modified
the regsub -all case specifically to turn it into a string map of the
prior variant because it was much faster. You will find this transition
between 8.3 and 8.4 in the "MAP ..." benchmarks at http://wiki.tcl.tk/1611.
In short, stick with string map.
Jeff
skuh...@web.de
Jeff Hobbs wrote:
> skuh...@web.de wrote:
> I believe your benchmark tests are flawed. I have rewritten them to
> recreate a new s0/s1 string each time,
Okay, I should have done that also. I used always the same string,
because I copied the test from my source code. In the real scenario
the data string is always the same, but the insertions change every
time.
> and find the more consistent
> timings of:
This is right, the tests were stupid, as I replied before. But when I
recreate the string every time, I get similar results: regsub is a
little bit faster than string map, and regsub ***= is really slow,
what I find strange, it should be faster than normal regexp, I think.
Below is my changed code, maybe, I made another stupid error like the
one yesterday.
Regards
Stephan
-------------------------------------------------------------------
proc timeTest {} {
set s0 [string repeat "qwertzu " 16384]
puts "Character string: [string length $s0]\n"
set s0 [string repeat "qwertzu " 16384]
puts "string map"
puts [time {string map {rt RT} $s0} 1000]\n
set s0 [string repeat "qwertzu " 16384]
puts "regsub -all"
puts [time {regsub -all {rt} $s0 RT} 1000]\n
set s0 [string repeat "qwertzu " 16384]
puts "regsub -all ***="
puts [time {regsub -all {***=rt} $s0 RT} 1000]\n\n
#-----------------------------------------------------------------------------
set s1 [string repeat "Qdd%Xdd " 16384]
puts "Placeholder String: [string length $s1]\n"
set s1 [string repeat "Qdd%Xdd " 16384]
puts "string map"
puts [time {string map {%X **} $s1} 1000]\n
set s1 [string repeat "Qdd%Xdd " 16384]
puts "regsub -all"
puts [time {regsub -all {%X} $s1 **} 1000]\n
set s1 [string repeat "Qdd%Xdd " 16384]
puts "regsub -all ***="
puts [time {regsub -all {***=%X} $s1 **} 1000]\n
puts [string range $s0 0 100]
puts [string range $s1 0 100]
}
timeTest
---
Results are:
Character string: 131072
string map
5561.65 microseconds per iteration
regsub -all
5398.025 microseconds per iteration
regsub -all ***=
49511.28 microseconds per iteration
Placeholder String: 131072
string map
5616.791 microseconds per iteration
regsub -all
5425.566 microseconds per iteration
regsub -all ***=
49834.215 microseconds per iteration
Gerald W. Lester
On 8.4.13 from ActiveState I get similar results.
--
+--------------------------------+---------------------------------------+
| Gerald W. Lester |
|"The man who fights for his ideals is the man who is alive." - Cervantes|
+------------------------------------------------------------------------+
Jeff Hobbs
> Jeff Hobbs wrote:
>> skuh...@web.de wrote:
>> and find the more consistent timings of:
>
> This is right, the tests were stupid, as I replied before. But when I
> recreate the string every time, I get similar results: regsub is a
> little bit faster than string map, and regsub ***= is really slow,
> what I find strange, it should be faster than normal regexp, I think.
> Below is my changed code, maybe, I made another stupid error like the
> one yesterday.
OK, I can confirm seeing slightly faster timings for regsub -all than
string map on my x64 machine, but using the same bits, it's a smidge
slower consistently on my x86 machine. You'll have to go down to the
assembly to explain that, but in general, they should be about the same.
There is no specific bytecode for either operation, and they
essentially use the same algorithm to achieve their task (though not the
same code, so cache locality and other bits come into play).
The ***= case is simply one that has not been optimized with my special
check, and that is the numbers you would get from the RE without the
special case. I suppose I could extend the code to check for that, but
people should just rely on 'string map'. In addition, you can better
verify the effects of this special case by choosing something that will
foil it. This is meant to find 1:1 simple mappings being passed through
regsub. Simply make either the search or replace "non-simple" (ie, add
an escaped char), and you will lose all speed gains.
Jeff
proc timeTest {} {
set s0 [string repeat "qwertzu " 16384]
puts "Character string: [string length $s0]"
puts "string map R\\T"
set s0 [string repeat "qwertzu " 16384]
puts [time {string map "rt R\\T" $s0} 100]
puts "regsub -all R\\T"
set s0 [string repeat "qwertzu " 16384]
puts [time {regsub -all {rt} $s0 "R\\T"} 100]
puts "regsub -all ***= R\\T"
set s0 [string repeat "qwertzu " 16384]
puts [time {regsub -all {***=rt} $s0 "R\\T"} 100]
puts "string map RT"
set s0 [string repeat "qwertzu " 16384]
puts [time {string map "rt RT" $s0} 100]
puts "regsub -all RT"
set s0 [string repeat "qwertzu " 16384]
puts [time {regsub -all {rt} $s0 "RT"} 100]
puts "regsub -all ***= RT"
set s0 [string repeat "qwertzu " 16384]
puts [time {regsub -all {***=rt} $s0 "RT"} 100]
}
puts "tcl [info patch]"
timeTest
RETURNS:
tcl 8.4.15
Character string: 131072
string map R\T
9961.91 microseconds per iteration
regsub -all R\T
79553.1 microseconds per iteration
regsub -all ***= R\T
79644.28 microseconds per iteration
string map RT
9860.75 microseconds per iteration
regsub -all RT
10476.81 microseconds per iteration
regsub -all ***= RT
78899.83 microseconds per iteration
Stephan Kuhagen
> The ***= case is simply one that has not been optimized with my special
> check, and that is the numbers you would get from the RE without the
> special case. I suppose I could extend the code to check for that, but
> people should just rely on 'string map'. In addition, you can better
> verify the effects of this special case by choosing something that will
> foil it. This is meant to find 1:1 simple mappings being passed through
> regsub. Simply make either the search or replace "non-simple" (ie, add
> an escaped char), and you will lose all speed gains.
Thanks for explaining that. I think, string map will be it. But just out of
curiosity I made some more Tests on different CPU, all running Linux and
the mentioned version of Tcl. I tested:
1 AMD Athlon(tm) 64 X2 Dual Core Processor 3800+
2 Intel(R) Pentium(R) 4 CPU 3.00GHz
3 Intel(R) Pentium(R) 4 CPU 3.40GHz
4 Intel(R) Core(TM)2 CPU T7400 @ 2.16GHz
5 PowerPC 750FX @ 800Mhz
"string map" is only faster on 1 and 3, the others are faster with regexp.
I'm wondering what magic the assembler does there...
Regards
Stephan