Fastest strings concatenation

Share your advanced PureBasic knowledge/code with the community.
User avatar
Lunasole
Addict
Addict
Posts: 1091
Joined: Mon Oct 26, 2015 2:55 am
Location: UA
Contact:

Fastest strings concatenation

Post by Lunasole »

Oh I know it was many times on forum, just I've finally tired to code that bicycle everytime and made generic macro/procedures for it ^^
The following is CLOSER TO perfect :3 (comparing with previous dirty version).
You can easily change that code to be thread-safe, or pack it into module, and so on with what is needed

Code: Select all

EnableExplicit

;{ StrFastConcat } 
	
	; v 1.0.0.5
	;   2017		(c) Luna Sole
	Structure STRFASTOBJ
		*Data
	EndStructure
	
	; Starts new concatenation. Lot of them may exists and be threaded
	; RETURN:		strfast object on success
	Procedure StrFastNew()
		Protected *StrFast.STRFASTOBJ = AllocateStructure(STRFASTOBJ)
		If *StrFast
			*StrFast\Data = AllocateMemory(4 + 10240*SizeOf(Character))
			If *StrFast\Data
				PokeL(*StrFast\Data, 0)      ; bytes 1-4 storing current len (chars)
				ProcedureReturn *StrFast
			Else
				FreeStructure(*StrFast)
			EndIf
		EndIf
	EndProcedure
	
	; Concatenate strings quite optimized way
	; *String		pointer to a string
	; Len			*String len (chars). If set, len is not calculated here, which brings some more speed in some cases
	; RETURN:		none
	Procedure StrFastAddEx (*StrFast.STRFASTOBJ, *String, Len = 0)
		Protected NewLenB, *FastLen.Long
		If *StrFast
			If Len <= 0
				Len = MemoryStringLength(*String)
			EndIf
			If Len
				*FastLen = *StrFast\Data
				NewLenB = (*FastLen\l + Len)*SizeOf(Character)
				If NewLenB > (MemorySize(*StrFast\Data)-4)
					; every time buffer size is set to required size*2. that GREATLY raises both memory overhead and speed, comparing to use of small/medium fixed step
					; idea stolen from @Karig variant ^^
					*StrFast\Data = ReAllocateMemory(*StrFast\Data, 4 + NewLenB*1.28, #PB_Memory_NoClear)
					*FastLen = *StrFast\Data
				EndIf
				CopyMemory(*String, *StrFast\Data+4 + *FastLen\l*SizeOf(Character), Len*SizeOf(Character))
				*FastLen\l + Len
			EndIf
		EndIf
	EndProcedure
	
	; Wrapper for a cases where pointer is not applicable.
	; It is much slower than StrFastAddEx(), but only comparing to it. Itself is still very fast.
	; String$		a string to add
	; Len			String$ len (chars). If set, len is not calculated here, which brings some more speed in some cases
	; RETURN:		none
	Procedure StrFastAdd(*StrFast.STRFASTOBJ, String$, Len = 0)
		StrFastAddEx(*StrFast, @String$, Len)
	EndProcedure
	
	; Returns concatenated string
	; RETURN:		string
	Procedure$ StrFastGet(*StrFast.STRFASTOBJ)
		If *StrFast
			ProcedureReturn PeekS(*StrFast\Data+4, PeekL(*StrFast\Data))
		EndIf
	EndProcedure
	
	; Release specified fast string
	; RETURN:		none
	Procedure StrFastFree(*StrFast.STRFASTOBJ)
		If *StrFast
			FreeMemory(*StrFast\Data)
			FreeStructure(*StrFast)
		EndIf
	EndProcedure
	
;}


;;; Example

; Allocate this fast stuff
Define FS = StrFastNew()

; 1) Typical usage
StrFastAdd(FS, "test ")
; 2) Sometime this is faster, when is reasonable
StrFastAdd(FS, "this ", 5)
; 3) Using pointer + fixed len, fastest option here
StrFastAddEx(FS, @"ssst++", 4)

; Get Result & Release
Debug StrFastGet(FS)
StrFastFree(FS)
Last edited by Lunasole on Sun Oct 22, 2017 1:24 am, edited 7 times in total.
"W̷i̷s̷h̷i̷n̷g o̷n a s̷t̷a̷r"
User avatar
Kwai chang caine
Always Here
Always Here
Posts: 5342
Joined: Sun Nov 05, 2006 11:42 pm
Location: Lyon - France

Re: Faster strings concatenation

Post by Kwai chang caine »

Can be usefull
Thanks for sharing 8)
ImageThe happiness is a road...
Not a destination
User avatar
Lunasole
Addict
Addict
Posts: 1091
Joined: Mon Oct 26, 2015 2:55 am
Location: UA
Contact:

Re: Faster strings concatenation

Post by Lunasole »

Posted updated version based on allocator.
It's universal and much faster comparing to previous crude stuff.

You're welcome with your enhancements to this 4-wheel bicycle ^^
"W̷i̷s̷h̷i̷n̷g o̷n a s̷t̷a̷r"
infratec
Always Here
Always Here
Posts: 6817
Joined: Sun Sep 07, 2008 12:45 pm
Location: Germany

Re: Faster strings concatenation

Post by infratec »

Hi,

only one question:

why not

Code: Select all

Structure STRFASTOBJ
  len.l
  Step.l
  *Data
EndStructure
This would save some math :wink:

Bernd
User avatar
Lunasole
Addict
Addict
Posts: 1091
Joined: Mon Oct 26, 2015 2:55 am
Location: UA
Contact:

Re: Faster strings concatenation

Post by Lunasole »

infratec wrote:Hi,

only one question:
Hi. Mostly just because I don't like to add custom structures when can not add ^^
Generally even that STRFASTOBJ is rudimentary and left only "as decoration", can be nicely replaced with *Pointer.Integer/Integer structure.

Also anyway that math plays no role, should be 2-15ms speed up per million calls.
"W̷i̷s̷h̷i̷n̷g o̷n a s̷t̷a̷r"
User avatar
Lunasole
Addict
Addict
Posts: 1091
Joined: Mon Oct 26, 2015 2:55 am
Location: UA
Contact:

Re: Faster strings concatenation

Post by Lunasole »

@infratec, that pointer math should be avoided not for performance, but because of chances to shoot own legs, etc ^^

Just updated code to 1.0.0.3 with following patch to fix trivial-but-not too obvious bug (as allocated memory size grows, pointers defined previously in procedure may become invalid after reallocation):

Code: Select all

If NewLenB+8 > (MemorySize(*StrFast\Data))
	*StrFast\Data = ReAllocateMemory(*StrFast\Data, 8+NewLenB + *FastStepB\l)
	*FastLen = *StrFast\Data : *FastStepB = *StrFast\Data+4; ++
EndIf
"W̷i̷s̷h̷i̷n̷g o̷n a s̷t̷a̷r"
User avatar
Lunasole
Addict
Addict
Posts: 1091
Joined: Mon Oct 26, 2015 2:55 am
Location: UA
Contact:

Re: Faster strings concatenation

Post by Lunasole »

Updated it once more. Now it's probably fastest variant on forum, except maybe something coded in ASM if any exists.

Though using large fixed step would be anyway faster (or equal), this variant is more usable for most cases, than setting astronomical step values.
"W̷i̷s̷h̷i̷n̷g o̷n a s̷t̷a̷r"
User avatar
Lunasole
Addict
Addict
Posts: 1091
Joined: Mon Oct 26, 2015 2:55 am
Location: UA
Contact:

Re: Fastest strings concatenation

Post by Lunasole »

And again changed a bit:
- added #PB_Memory_NoClear flag (which may bring some more speed, and maybe not)
- slighty balanced realloc coefficient: 1.28 acts better than 2.0, no such a crazy overhead at really large strings, while performance is not much affected

I also though to return option with fixed alloc step, but it really doesn't looks useful comparing with "auto" *1.28.
Generally now it should be realy done and stable, already used it in few programs.
"W̷i̷s̷h̷i̷n̷g o̷n a s̷t̷a̷r"
User avatar
Thunder93
Addict
Addict
Posts: 1788
Joined: Tue Mar 21, 2006 12:31 am
Location: Canada

Re: Fastest strings concatenation

Post by Thunder93 »

Looking very slick Lunasole, thanks for sharing :!:
ʽʽ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 avatar
Lunasole
Addict
Addict
Posts: 1091
Joined: Mon Oct 26, 2015 2:55 am
Location: UA
Contact:

Re: Fastest strings concatenation

Post by Lunasole »

Thunder93 wrote:Looking very slick Lunasole, thanks for sharing :!:
np, but why "slick"? ^^
"W̷i̷s̷h̷i̷n̷g o̷n a s̷t̷a̷r"
User avatar
Thunder93
Addict
Addict
Posts: 1788
Joined: Tue Mar 21, 2006 12:31 am
Location: Canada

Re: Fastest strings concatenation

Post by Thunder93 »

Just thought it was appropriate here, best I felt describes It.

"(of an action or thing) done or operating in an impressively smooth, efficient, and apparently effortless way." :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 avatar
Lunasole
Addict
Addict
Posts: 1091
Joined: Mon Oct 26, 2015 2:55 am
Location: UA
Contact:

Re: Fastest strings concatenation

Post by Lunasole »

Thunder93 wrote:Just thought it was appropriate here, best I felt describes It.

"(of an action or thing) done or operating in an impressively smooth, efficient, and apparently effortless way." :wink:
Incompleteness of my english ^^ Had different association to that word and surprised from it in such context
"W̷i̷s̷h̷i̷n̷g o̷n a s̷t̷a̷r"
User avatar
Lunasole
Addict
Addict
Posts: 1091
Joined: Mon Oct 26, 2015 2:55 am
Location: UA
Contact:

Re: Fastest strings concatenation

Post by Lunasole »

Dam'n lol, I can't read some my old forum comments without facepalm.
My english was really mad (even though it is not perfect for today). Especially when I was replying in english while having some extremely good mood.....
"W̷i̷s̷h̷i̷n̷g o̷n a s̷t̷a̷r"
Post Reply