Page 1 of 1
Another way to speed up concatenation
Posted: Sat May 07, 2016 3:44 am
by Lunasole
I'm not sure will it be useful for someone on practice, just worked this night on some code processing strings and raised following idea as side-effect. The typical way to speed up string merging is to use pre-allocated buffer and writing to it by using kind of direct memory access [and any other trick to avoid iteration of whole 0-terminated string everytime], and I wondered that following code is fast enough too while not doing so
Seems to be about 10x faster than regular concatenation.
Code: Select all
EnableExplicit
DisableDebugger
OpenConsole("Testing facility")
Define.i Time
Define.i Counter, Count
Count = 500000
Define A$
Define B$, C$, D
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; case A, regular
Time = ElapsedMilliseconds()
For Counter = 1 To Count
A$ + "a"
Next Counter
Time = ElapsedMilliseconds() - Time
PrintN("Cycle 1: " + Str(Time) + "ms")
;---------------------------------------------;
; case B. C$ variable used as buffer which is added to B$ and flushed with some interval
Time = ElapsedMilliseconds()
For Counter = 1 To Count
C$ + "a" ; instead of adding directly to B$
D + 1
If D % 50000 = 0 ; clear every N chars
B$ + C$
C$ = ""
EndIf
Next Counter
Time = ElapsedMilliseconds() - Time
PrintN("Cycle 2: " + Str(Time) + "ms")
; print here len of A and B to check if all ok
PrintN(Str(Len(A$)))
PrintN(Str(Len(B$)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Input()
Re: Another way to speed up concatenation
Posted: Sat May 07, 2016 4:00 am
by Keya
interesting! so you are getting a speed gain by working on a temporary smaller string, and copying that over to the final main string only a few times, instead of with every byte. So my guess is the speed gain is from the internal Len function being able to work on the shorter string most of the time instead of the full target string
but like you say still not as fast as directly writing to preallocated buffer
Re: Another way to speed up concatenation
Posted: Sat May 07, 2016 4:28 am
by Lunasole
Keya wrote:interesting! so you are getting a speed gain by working on a temporary smaller string, and copying that over to the final main string only a few times, instead of with every byte. So my guess is the speed gain is from the internal Len function being able to work on the shorter string most of the time instead of the full target string
Like that
For case A internal len() is called 500000 times, for B: 500000 + 10 with large buffers, but B is much faster, some paradox at first sight
Re: Another way to speed up concatenation
Posted: Sat May 07, 2016 5:58 am
by wilbert
It's not strange this happens.
When you combine two strings, both are copied into newly allocated memory and the previous data is freed.
So when you work with small temporary strings, there's less data to process.
Actually, if you take these two lines
what happens with the second line is that both s and "1" are copied to a string buffer and the result is copied back into a newly allocated string which is assigned to s.
So for adding this one character, 2000 characters (2x 1000) are copied.
Re: Another way to speed up concatenation
Posted: Sat May 07, 2016 2:24 pm
by #NULL
with my old thinkpad t410 and PB.542, windows 7 the second version is always a tiny bit slower.
(i had to reduce to 50000
)
Code: Select all
Cycle 1: 4221ms
Cycle 2: 4227ms
50000
50000