Page 1 of 5

Fast string

Posted: Fri Mar 28, 2014 12:56 pm
by User_Russian
In my opinion, working with strings in PB, very slow (snail crawls faster than operations are performed with strings).
The example is very slow work with a string.

Code: Select all

DisableDebugger

Str.s
#Text = "1234567890"

Time = ElapsedMilliseconds()

For i=1 To 100000
  Str + #Text
Next i

MessageRequester("", StrF((ElapsedMilliseconds()-Time)/1000, 3))
Similar code with the string in memory is performed in a split second.

Code: Select all

DisableDebugger

*Str = AllocateMemory(10)
Len = 10
Pos = 0
#Text = "1234567890"

Time = ElapsedMilliseconds()

For i=1 To 100000
  Size = StringByteLength(#Text)
  If Pos+Size+4>Len
    Len+Size+4
    *Str = ReAllocateMemory(*Str, Len)
  EndIf
  Pos+PokeS(*Str+Pos, #Text, Size)
Next i

EnableDebugger

Result.f = (ElapsedMilliseconds()-Time)/1000
ShowMemoryViewer(*Str, Len)
MessageRequester("", StrF(Result, 3))
I assume that the reason for the slow work with strings in the string length is calculated for each access to string.
If the in beginning of the string to keep it length and not be calculated for each access to the string, it should increase performance.

Re: Fast string

Posted: Fri Mar 28, 2014 1:13 pm
by Thunder93
What snail species you in reference too? :P

The speed of land snail is 12.2 meters per hour. The fastest specie of landsnail is the common garden snail (Helix aspersa) moving at 20 meters per hour. The fastest recorded was by the Helix aspersa moving at 48.3 meters per hour. :wink:

Re: Fast string

Posted: Fri Mar 28, 2014 2:18 pm
by User_Russian
Incidentally, in SpiderBasic, the first code is work fast (20 milliseconds). :shock: In PureBasic a very long time! :?

Re: Fast string

Posted: Fri Mar 28, 2014 2:48 pm
by Shield
It's not a Problem in JavaScript (at least on some implementations) because there exist optimizations.
The problem that it is so slow in PB is because of the continuous allocation and deallocation of memory.

Search for StringBuilder on the forum to find a fast way. :wink:
(This is not generally a PureBasic "problem". Firstly because it's not a problem at all but what is to be expected,
and secondly because it is the same case in most programming languages).

Re: Fast string

Posted: Fri Mar 28, 2014 3:10 pm
by User_Russian
Shield wrote:The problem that it is so slow in PB is because of the continuous allocation and deallocation of memory.
I think that problem not in it.
In the second code is also allocated and deallocation memory

Code: Select all

*Str = ReAllocateMemory(*Str, Len)
but the program works fast.
In my opinion, the problem is that every access string, measured its length. And this is done by iterating through all characters and search for zero bytes. It's a slow process.
Need to store the string length (for example, as stored, the size of the array) and not recalculate it every time.

This confirms the experiment.
If the second code to add a function MemoryStringLength(), then it will work just as slowly as the first code.

Code: Select all

DisableDebugger

*Str = AllocateMemory(10)
Len = 10
Pos = 0
#Text = "1234567890"

Time = ElapsedMilliseconds()

For i=1 To 100000
  Size = StringByteLength(#Text)
  If Pos+Size+4>Len
    Len+Size+4
    *Str = ReAllocateMemory(*Str, Len)
  EndIf
  Pos+PokeS(*Str+Pos, #Text, Size)
  MemoryStringLength(*Str) ; This is the main reason the slow work With strings!
Next i

EnableDebugger

Result.f = (ElapsedMilliseconds()-Time)/1000
ShowMemoryViewer(*Str, Len)
MessageRequester("", StrF(Result, 3))
Measuring the length of string each time you access the main reason for the slow work of all string functions!

Re: Fast string

Posted: Fri Mar 28, 2014 3:17 pm
by Shield
I don't think that PB uses ReAllocateMemory to create a new string buffer.
ReAllocateMemory can reuse the same buffer if there is more space available at the end
whereas AllocateMemory will always create a new buffer (so everything has to be copied).

I can't comment on the speed of MemoryStringLength(*Str) though,
but it seems to be rather slow as your experiment confirms.

Re: Fast string

Posted: Fri Mar 28, 2014 4:03 pm
by User_Russian
When added in string, use function HeapReAlloc(), the same as in ReAllocateMemory().
The memory is not deallocation and allocated.
Works similarly ReAllocateMemory().
In my opinion, slow work, due to of the function strlen().

Re: Fast string

Posted: Fri Mar 28, 2014 4:35 pm
by Shield
Yes, but PureBasic is using HeapAlloc, not HeapReAlloc, while concatenating strings.

Re: Fast string

Posted: Fri Mar 28, 2014 6:05 pm
by User_Russian
Function string concatenation.

Code: Select all

int __stdcall sub_100021B0(LPVOID *a1, int a2)
{
  int result; // eax@4
  int v3; // [sp+0h] [bp-4h]@1

  v3 = dword_10004150 - a2;
  if ( *a1 )
    *a1 = HeapReAlloc(dword_10004158, 0, *a1, v3 + 5);     // < ----- HeapReAlloc.
  else
    *a1 = HeapAlloc(dword_10004158, 0, v3 + 5);
  sub_100022B0(*a1, (char *)lpMem + a2, v3);
  result = a2;
  dword_10004150 = a2;
  return result;
}

Re: Fast string

Posted: Fri Mar 28, 2014 6:25 pm
by Shield
Interesting. How did you produce this? I quickly checked with a disassembler
before posting and I could have sworn it said HeapAlloc. :|

Re: Fast string

Posted: Fri Mar 28, 2014 6:49 pm
by User_Russian

Re: Fast string

Posted: Fri Mar 28, 2014 7:40 pm
by Shield
Well, that's a little bit far out of my wallet's league. Thanks for the link, though. :)

Re: Fast string

Posted: Fri Mar 28, 2014 8:02 pm
by User_Russian
Then compile this code.

Code: Select all

s.s+" "
And open exe-file in editor.
Find in text, the word HeapReAlloc.

Re: Fast string

Posted: Sat Mar 29, 2014 1:03 am
by STARGÅTE
Fast string is implimented es CopyMemoryString()

Code: Select all

Str + #Text
is converte to:

Code: Select all

Str = Str + #Text

Re: Fast string

Posted: Sat Mar 29, 2014 2:14 am
by skywalk
STARGÅTE wrote:Fast string is implemented as CopyMemoryString()
Yes, without it, string concatenation is unusable for large writes. I use Join() when speed is required.