Fast string

Got an idea for enhancing PureBasic? New command(s) you'd like to see?
User_Russian
Addict
Addict
Posts: 1443
Joined: Wed Nov 12, 2008 5:01 pm
Location: Russia

Fast string

Post 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.
User avatar
Thunder93
Addict
Addict
Posts: 1788
Joined: Tue Mar 21, 2006 12:31 am
Location: Canada

Re: Fast string

Post 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:
ʽʽSuccess is almost totally dependent upon drive and persistence. The extra energy required to make another effort or try another approach is the secret of winning.ʾʾ --Dennis Waitley
User_Russian
Addict
Addict
Posts: 1443
Joined: Wed Nov 12, 2008 5:01 pm
Location: Russia

Re: Fast string

Post by User_Russian »

Incidentally, in SpiderBasic, the first code is work fast (20 milliseconds). :shock: In PureBasic a very long time! :?
User avatar
Shield
Addict
Addict
Posts: 1021
Joined: Fri Jan 21, 2011 8:25 am
Location: 'stralia!
Contact:

Re: Fast string

Post 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).
Image
Blog: Why Does It Suck? (http://whydoesitsuck.com/)
"You can disagree with me as much as you want, but during this talk, by definition, anybody who disagrees is stupid and ugly."
- Linus Torvalds
User_Russian
Addict
Addict
Posts: 1443
Joined: Wed Nov 12, 2008 5:01 pm
Location: Russia

Re: Fast string

Post 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!
User avatar
Shield
Addict
Addict
Posts: 1021
Joined: Fri Jan 21, 2011 8:25 am
Location: 'stralia!
Contact:

Re: Fast string

Post 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.
Image
Blog: Why Does It Suck? (http://whydoesitsuck.com/)
"You can disagree with me as much as you want, but during this talk, by definition, anybody who disagrees is stupid and ugly."
- Linus Torvalds
User_Russian
Addict
Addict
Posts: 1443
Joined: Wed Nov 12, 2008 5:01 pm
Location: Russia

Re: Fast string

Post 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().
User avatar
Shield
Addict
Addict
Posts: 1021
Joined: Fri Jan 21, 2011 8:25 am
Location: 'stralia!
Contact:

Re: Fast string

Post by Shield »

Yes, but PureBasic is using HeapAlloc, not HeapReAlloc, while concatenating strings.
Image
Blog: Why Does It Suck? (http://whydoesitsuck.com/)
"You can disagree with me as much as you want, but during this talk, by definition, anybody who disagrees is stupid and ugly."
- Linus Torvalds
User_Russian
Addict
Addict
Posts: 1443
Joined: Wed Nov 12, 2008 5:01 pm
Location: Russia

Re: Fast string

Post 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;
}
User avatar
Shield
Addict
Addict
Posts: 1021
Joined: Fri Jan 21, 2011 8:25 am
Location: 'stralia!
Contact:

Re: Fast string

Post by Shield »

Interesting. How did you produce this? I quickly checked with a disassembler
before posting and I could have sworn it said HeapAlloc. :|
Image
Blog: Why Does It Suck? (http://whydoesitsuck.com/)
"You can disagree with me as much as you want, but during this talk, by definition, anybody who disagrees is stupid and ugly."
- Linus Torvalds
User_Russian
Addict
Addict
Posts: 1443
Joined: Wed Nov 12, 2008 5:01 pm
Location: Russia

Re: Fast string

Post by User_Russian »

User avatar
Shield
Addict
Addict
Posts: 1021
Joined: Fri Jan 21, 2011 8:25 am
Location: 'stralia!
Contact:

Re: Fast string

Post by Shield »

Well, that's a little bit far out of my wallet's league. Thanks for the link, though. :)
Image
Blog: Why Does It Suck? (http://whydoesitsuck.com/)
"You can disagree with me as much as you want, but during this talk, by definition, anybody who disagrees is stupid and ugly."
- Linus Torvalds
User_Russian
Addict
Addict
Posts: 1443
Joined: Wed Nov 12, 2008 5:01 pm
Location: Russia

Re: Fast string

Post by User_Russian »

Then compile this code.

Code: Select all

s.s+" "
And open exe-file in editor.
Find in text, the word HeapReAlloc.
User avatar
STARGÅTE
Addict
Addict
Posts: 2067
Joined: Thu Jan 10, 2008 1:30 pm
Location: Germany, Glienicke
Contact:

Re: Fast string

Post by STARGÅTE »

Fast string is implimented es CopyMemoryString()

Code: Select all

Str + #Text
is converte to:

Code: Select all

Str = Str + #Text
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Lizard - Script language for symbolic calculations and moreTypeface - Sprite-based font include/module
User avatar
skywalk
Addict
Addict
Posts: 3972
Joined: Wed Dec 23, 2009 10:14 pm
Location: Boston, MA

Re: Fast string

Post 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.
The nice thing about standards is there are so many to choose from. ~ Andrew Tanenbaum
Post Reply