Preallocate memory for Strings

[Josh]

I know, often discussed but that does not change the fact that PureBasic has a huge drawback in string operations. Using many string extensions in small steps, PureBasic is getting slower and slower.

Code: Select all

Define i
Define x$

time = ElapsedMilliseconds()
For i = 1 To 1000
  x$ = x$ + " "
Next
time = ElapsedMilliseconds () - time

MessageRequester ("", "" + time)

Expanding the loop to factor 10, factor time is about 100 times larger
Expanding the loop to factor 100, factor time is about 10'000 times larger


I'm not sure if this could optimize the performance and not sure if possible, but stll my suggestion:

Code: Select all

Define x$ <1000>

In this case, compiler would internally allocate (free) memory for the string x$ in steps of 1000 characters.
So no need to allocate new memory and to copy string for each string-modification.

[User_Russian]

http://www.purebasic.fr/english/viewtop ... =3&t=58892

[walbus]

Here other samples

Mostly it is not a globale problem in a application

http://www.purebasic.fr/english/viewtop ... 12&t=66419

[STARGÅTE]

Expanding the loop to factor 10, factor time is about 100 times larger
Expanding the loop to factor 100, factor time is about 10'000 times larger

This behavior is clearly explanable:

• If you increase your Loop iterations by fator 10, you have also 10 times more operations (*10)
• By an increase of the iterations, also the string lengths increases by a factor of 10 and the creation of the string needs more time (*10)

For an Extension of strings it is not useful to use X$ = Y$, but CopyMemoryString in combination with fixed strings like this:

Code: Select all

Define i
Define x${1000000}
Define *Buffer = @x$

time = ElapsedMilliseconds()
For i = 1 To 10000
  CopyMemoryString(@"Hello World!", @*Buffer)
Next
time = ElapsedMilliseconds () - time

Debug x$

MessageRequester ("", "" + time)

[Kukulkan]

The first post example is not really a real-life issue but it happens every now and then to concatenate a lot of strings into one long string. Since 20 years now I always use this small trick to concatenate very fast without any tricks. Works on all platforms:

Code: Select all

; test with no trick
; ===============================================

start.i = ElapsedMilliseconds()
result.s = ""
For x.i = 1 To 30000
  result.s + "abcdefghijklmnopqrstuvwxyz";
Next

Debug "Standard concat needed: " + Str(ElapsedMilliseconds() - start.i) + "ms"


; test again with simple hack
; ===============================================

start.i = ElapsedMilliseconds()
result.s = ""
intermediate.s = ""
For x.i = 1 To 30000
  intermediate.s + "abcdefghijklmnopqrstuvwxyz";
  If Len(intermediate.s) > 4096
    result.s + intermediate.s
    intermediate.s = ""
  EndIf
Next
result.s + intermediate.s ; get the rest intermediate

Debug "Enhanced concat needed: " + Str(ElapsedMilliseconds() - start.i) + "ms"

Result (Intel Core i5 / PB 5.44 / 64 Bit / Debugger On):

Standard concat needed: 11794ms
Enhanced concat needed: 173ms

This works not only with PB but with every dev language. It is only 5 lines more code...

Background:
If you concat a string, the OS behaves like this:

1) Reserve new string memory [oldStringLength]+[stringLengthToAdd]
2) Copy old string memory to new string memory
3) Copy new string to new string memory
4) release old string memory

The longer the string gets, the more time is needed for steps 1 and 2. Thus, working with smaller strings and concatenating the long ones not that often increases the speed!

[normeus]

@Kukulkan, Thanks for the great example. I added MessageRequester() to turn off debug and also decreased loop to 1000 because my computer is too slow.

Tried it on an i7 windows 10 PB 5.42LST.
My computer is 3 times slower than yours
to run this test with a loop at 1000 it took 40ms and 10ms

Code: Select all

; test with no trick
; ===============================================

start.i = ElapsedMilliseconds()
result.s = ""
For x.i = 1 To 1000
  result.s + "abcdefghijklmnopqrstuvwxyz";
Next

MessageRequester("Standard concat needed: " , Str(ElapsedMilliseconds() - start.i)+ "ms" )

; test again with simple hack
; ===============================================

start.i = ElapsedMilliseconds()
result.s = ""
intermediate.s = ""
For x.i = 1 To 1000
  intermediate.s + "abcdefghijklmnopqrstuvwxyz";
  If Len(intermediate.s) > 4096
    result.s + intermediate.s
    intermediate.s = ""
  EndIf
Next
result.s + intermediate.s ; get the rest intermediate


MessageRequester("Enhanced concat needed: " , Str(ElapsedMilliseconds() - start.i)+"ms")

[Kukulkan]

Hello normeus,

the bigger the resulting string, the bigger is the effect. Try it with 10'000 and take a coffee break and you will see how big the difference will become...