It is currently Mon Oct 15, 2018 10:23 pm

All times are UTC + 1 hour




Post new topic Reply to topic  [ 42 posts ]  Go to page Previous  1, 2, 3
Author Message
 Post subject: Re: Fast string
PostPosted: Fri Aug 11, 2017 11:51 am 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Sun Sep 11, 2016 2:17 pm
Posts: 236
+ 1


Top
 Profile  
Reply with quote  
 Post subject: Re: Fast string
PostPosted: Fri Aug 11, 2017 1:12 pm 
Offline
User
User

Joined: Tue Jun 17, 2014 4:49 pm
Posts: 44
+ 1


Top
 Profile  
Reply with quote  
 Post subject: Re: Fast string
PostPosted: Fri Aug 11, 2017 3:37 pm 
Offline
Addict
Addict
User avatar

Joined: Mon Jun 06, 2005 2:35 pm
Posts: 1180
Location: germany
I know that I'm somehow "old fashioned", but I think it is upon the developer to understand, at least in a basic form, how strings are working. And if I find such a scenario, I do it like this since 30 years now:

Code:
DisableDebugger

Str.s
Dummy.s
#Text = "1234567890"

Time = ElapsedMilliseconds()

For i=1 To 100000
  Dummy + #Text
  If Len(Dummy) > 2048
    Str + Dummy
    Dummy = ""
  EndIf
Next i
Str + Dummy

MessageRequester("", StrF((ElapsedMilliseconds()-Time)/1000, 3))


While the initial function in the first thread takes me 48 seconds to complete, the 6 additional lines enhanced the speed to be 0.38 seconds. This is simple to use and really helpful. I do it like this all the time when I concatenate lager strings.

It is definitely not the fastest way possible, but solved it for me cross platform and reliable.

Kukulkan


Top
 Profile  
Reply with quote  
 Post subject: Re: Fast string
PostPosted: Fri Aug 11, 2017 3:56 pm 
Offline
Enthusiast
Enthusiast

Joined: Fri Feb 19, 2010 3:42 am
Posts: 482
Thanks for that example.

I like solutions where things are easy and fast and not only "fastest as possible even hard to implement".

What speed factors do we talk about?
- naive string handling
- Kukulkans less memory mappings method
- fast string builder
(It's about huge strings, isn't it?)

And... I can not see the problem.
Shouldn't it be possible in any situation (CSV, etc.) to guess the max size of the string and use Space() and PokeS?
Another shrink is then one fast memory operation.


Top
 Profile  
Reply with quote  
 Post subject: Re: Fast string
PostPosted: Sun Apr 15, 2018 8:25 am 
Offline
User
User

Joined: Mon Jun 23, 2014 1:18 pm
Posts: 51
Just a little fun code, to remember this is still a thing :D

Code:
EnableExplicit

Procedure StringAppend(*sb,string.s)
   Protected size,*Offset
   If *sb
      size=MemorySize(*sb)
      *Offset=size
   EndIf
   size+StringByteLength(string)
   *sb=ReAllocateMemory(*sb,size,#PB_Memory_NoClear)
   PokeS(*sb+*offset,string,-1,#PB_String_NoZero)
   ProcedureReturn *sb
EndProcedure

Procedure.s SBToString(*sb)
   ProcedureReturn PeekS(*sb,MemorySize(*sb)/SizeOf(Character))
EndProcedure

OpenConsole()

Define i
Define s.s="Lalala"
Define *sb=StringAppend(*sb,"Lalala")
#max=100000


Define start=ElapsedMilliseconds()
For i=1 To #max
   s+"La"
Next
Define ende=ElapsedMilliseconds()

PrintN(Str(ende-start)+" - "+Len(s))

start=ElapsedMilliseconds()
For i=1 To #max
   *sb=StringAppend(*sb,"La")
Next
ende=ElapsedMilliseconds()

PrintN(Str(ende-start)+" - "+Len(SBToString(*sb)))

Input()
CloseConsole()


Result
Code:
40733 - 200006
23 - 200006


Top
 Profile  
Reply with quote  
 Post subject: Re: Fast string
PostPosted: Sun Apr 15, 2018 8:52 am 
Offline
Addict
Addict

Joined: Mon Feb 16, 2015 2:49 pm
Posts: 1564
Cyllceaux wrote:
Just a little fun code, to remember this is still a thing :D

I have an issue with extremely slow strings, that I posted about here:

viewtopic.php?f=13&t=70568

I'd love to see strings being fast natively, to avoid POKES and memory buffers and mucking around like that.

Shield wrote:
This is not generally a PureBasic "problem"

Technically, no. But if we can write long blocks of code as a "workaround", then such workarounds need to become native.


Top
 Profile  
Reply with quote  
 Post subject: Re: Fast string
PostPosted: Tue May 01, 2018 2:16 pm 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Sun Mar 10, 2013 3:01 pm
Posts: 561
Location: Portugal
+1


Top
 Profile  
Reply with quote  
 Post subject: Re: Fast string
PostPosted: Tue May 29, 2018 12:35 pm 
Offline
Addict
Addict

Joined: Mon Feb 16, 2015 2:49 pm
Posts: 1564
To build a 505 KB string, it's literally faster to use a ListIconGadget and a disk write/read, than to build it the traditional way :!: :shock: :|

Code:
Debug "Please wait, speed testing..."

DisableDebugger

OpenWindow(0,200,200,200,100,"test",#PB_Window_Invisible)
ListIconGadget(0,10,10,180,80,"test",180)

; Prep the ListIconGadget with 505 KB of text:

items=5000
For a=1 To items
  AddGadgetItem(0,-1,Str(a)+Space(100))
Next

; Build a 505 KB string directly from the gadget:

start.q=ElapsedMilliseconds()
For a=1 To items
  one$+GetGadgetItemText(0,a)
Next
one.q=ElapsedMilliseconds()-start

; Build another 505 KB string using disk access:

start.q=ElapsedMilliseconds()
f$=GetTemporaryDirectory()+"string-speed-test"
If CreateFile(0,f$)
  For a=1 To items
    WriteString(0,GetGadgetItemText(0,a))
  Next
  CloseFile(0)
  If ReadFile(0,f$)
    two$=ReadString(0,#PB_File_IgnoreEOL)
    CloseFile(0)
  EndIf
  DeleteFile(f$)
EndIf
two.q=ElapsedMilliseconds()-start

; The results:

EnableDebugger

Debug "Len(one$)="+Str(Len(one$))+" and took "+Str(one)+" ms" ; 8216 ms (8 seconds!)
Debug "Len(two$)="+Str(Len(two$))+" and took "+Str(two)+" ms" ; 22 ms (not even a quarter of a second!)


Top
 Profile  
Reply with quote  
 Post subject: Re: Fast string
PostPosted: Tue May 29, 2018 12:46 pm 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Sat Feb 13, 2010 3:45 pm
Posts: 712
Dude wrote:
22 ms (not even a quarter of a second!)

:mrgreen:

_________________
sorry for my bad english


Top
 Profile  
Reply with quote  
 Post subject: Re: Fast string
PostPosted: Tue May 29, 2018 9:55 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jul 03, 2003 6:53 pm
Posts: 1216
Location: England
Dude's test made me wonder how fast it would be to add strings you want to concatenate to a list and then iterate over that list and copy each item into a memory block and then PeekS() at the outcome.

I've finessed that idea slightly and here's the result:
Code:
DisableDebugger

Structure StringBuilderItem
  item.s
  size.i
EndStructure

Structure StringBuilder
  size.i
  count.i
  List item.StringBuilderItem()
EndStructure

Procedure StringBuilder_Add(*sb.StringBuilder,itm$)
  nSize = StringByteLength(itm$)
  *sb\size = *sb\size + nSize
  *sb\count = *sb\count + 1
  AddElement(*sb\item())
  *sb\item()\item = itm$
  *sb\item()\size = nSize
EndProcedure

Procedure StringBuilder_Clear(*sb.StringBuilder)
  ClearList(*sb\item())
  *sb\count = 0
  *sb\size = 0
EndProcedure

Procedure StringBuilder_Free(*sb.StringBuilder)
  ClearList(*sb\item())
  FreeStructure(*sb)
EndProcedure

Procedure.s StringBuilder_Get(*sb.StringBuilder,idx.i)
  If idx > *sb\count - 1
    ProcedureReturn ""
  EndIf
  SelectElement(*sb\item(),idx)
  ProcedureReturn *sb\item()\item
EndProcedure

Procedure.s StringBuilder_GetChunk(*source,nSize)
  *bfr = AllocateMemory(nSize + 4)
  CopyMemory(*source,*bfr,nSize)
  out$ = PeekS(*bfr)
  FreeMemory(*bfr)
  ProcedureReturn out$
EndProcedure

Procedure.i StringBuilder_GetLongest(*sb.StringBuilder)
  nLongest = 0
  ResetList(*sb\item())
  While NextElement(*sb\item())
    If *sb\item()\size > nLongest
      nLongest = *sb\item()\size
    EndIf
  Wend
  ProcedureReturn nLongest
EndProcedure

Procedure StringBuilder_Insert(*sb.StringBuilder,idx,val$)
  If idx > *sb\count - 1 : ProcedureReturn : EndIf
  SelectElement(*sb\item(),idx)
  InsertElement(*sb\item())
  nSize = StringByteLength(val$)
  *sb\count = *sb\count + 1
  *sb\size = *sb\size + nSize
  *sb\item()\item = val$
  *sb\item()\size = nSize
EndProcedure

Procedure.s StringBuilder_Join(*sb.StringBuilder,delim$="")
  nSizeDelim = StringByteLength(delim$)
  nAdder = ListSize(*sb\item()) * nSizeDelim
  *bfr = AllocateMemory(*sb\size + nAdder + 4)
  nLoops = 0
  ResetList(*sb\item())
  While NextElement(*sb\item())
    PokeS(*bfr+nPos,*sb\item()\item,*sb\item()\size)
    nPos = nPos + *sb\item()\size
    nLoops = nLoops + 1
    If nSizeDelim > 0 And nLoops < *sb\count
      PokeS(*bfr+nPos,delim$,nSizeDelim)
      nPos = nPos + nSizeDelim
    EndIf
  Wend
  out$ = PeekS(*bfr,*sb\size)
  FreeMemory(*bfr)
  ProcedureReturn out$
EndProcedure

Procedure.i StringBuilder_New()
  *s.StringBuilder = AllocateStructure(StringBuilder)
  *s\count = 0
  *s\size = 0
  ProcedureReturn *s
EndProcedure

Procedure StringBuilder_Remove(*sb.StringBuilder,idx.i)
  If idx > *sb\count - 1 : ProcedureReturn : EndIf
  SelectElement(*sb\item(),idx)
  *sb\count = *sb\count - 1
  *sb\size = *sb\size - *sb\item()\size
  DeleteElement(*sb\item())
EndProcedure

Procedure StringBuilder_Replace(*sb.StringBuilder,idx.i,val$)
  If idx > *sb\count - 1 : ProcedureReturn : EndIf
  SelectElement(*sb\item(),idx)
  *sb\size = *sb\size - *sb\item()\size
  nSize = StringByteLength(val$)
  *sb\size = *sb\size + nSize
  *sb\item()\item = val$
  *sb\item()\size = nSize
EndProcedure

Procedure.i StringBuilder_Split(val$,delim$)
  *sb = StringBuilder_New()
  nSizeDel = StringByteLength(delim$)
  nSizeVal = StringByteLength(val$)
  If nSizeDel = 0 Or nSizeVal = 0
    ProcedureReturn *sb
  EndIf
  nEnd = 0 : nLen = 0 : nStart = 0
  While nEnd <= nSizeVal
    If CompareMemory(@val$+nEnd,@delim$,nSizeDel)
      StringBuilder_Add(*sb,StringBuilder_GetChunk(@val$+nStart,nLen))
      nEnd = nEnd + nSizeDel
      nStart = nEnd
      nLen = 0
    Else
      nEnd = nEnd + 1
      nLen = nLen + 1
    EndIf
  Wend
  If nLen > 0
    StringBuilder_Add(*sb,StringBuilder_GetChunk(@val$+nStart,nLen))
  EndIf
  ProcedureReturn *sb
EndProcedure

items=5000
joinstart.q=ElapsedMilliseconds()
*s.StringBuilder = StringBuilder_New()
For a=1 To items
  StringBuilder_Add(*s,Str(a)+Space(100))
Next
s$=StringBuilder_Join(*s,"|")
joinend.q=ElapsedMilliseconds()-joinstart

splitstart.q=ElapsedMilliseconds()
*s1.StringBuilder = StringBuilder_Split(s$,"|")
splitend.q=ElapsedMilliseconds()-splitstart

EnableDebugger

Debug "Join: Len(s$)= "+Str(Len(s$))+" and took "+Str(joinend)+" ms"
Debug "Split: Elements(s$)= "+Str(*s1\count)+" and took "+Str(splitend)+" ms"

StringBuilder_Free(*s)
StringBuilder_Free(*s1)

s$ = "Probably the best sparkling wine in the world"
*s.StringBuilder = StringBuilder_Split(s$," ")
StringBuilder_Replace(*s,3,"malt")
StringBuilder_Remove(*s,4)
StringBuilder_Insert(*s,4,"vinegar")
Debug StringBuilder_Join(*s," ")


Copying Dude's test (but with a delimiter so I can split the string again) I get:
Join 8ms
Split 31ms

Edit: Tweaked to add procedures to insert, remove, replace and get longest in order to handle this.


Top
 Profile  
Reply with quote  
 Post subject: Re: Fast string
PostPosted: Sat Jun 09, 2018 12:58 pm 
Offline
Addict
Addict

Joined: Mon Feb 16, 2015 2:49 pm
Posts: 1564
@Kukulkan: your code below is magic! I have no idea how it works, but it lets me build a 386 KB string (a list of 9895 filenames in a folder, with 40 characters per name) in just 390 ms! Thank you! :)

So, what's with the 2048 size test? Can you explain how that works? When I halved it to 1024, the routine was slower; and when I doubled it to 4096, my app crashed with an illegal memory access error. So 2048 seems to be the sweet-spot.

Code:
For i=1 To 100000
  Dummy + #Text
  If Len(Dummy) > 2048
    Str + Dummy
    Dummy = ""
  EndIf
Next i
Str + Dummy


Top
 Profile  
Reply with quote  
 Post subject: Re: Fast string
PostPosted: Sat Jun 09, 2018 2:14 pm 
Offline
Enthusiast
Enthusiast

Joined: Mon Feb 04, 2013 5:28 pm
Posts: 327
Yes, stringbuilders in PB and strings prepended with the actual length would be useful language additions.
So ...


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 42 posts ]  Go to page Previous  1, 2, 3

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye