Fastest way to append to array (large arrays)

[pneumatic]

Hello

Just wondering if there any difference in performance between the following methods of appending values to an array:

Code: Select all

loop 
{
Array[A_Index] := value
}

Code: Select all

loop 
{
Array.Push(value)
}

In theory it seems like the Push method would be faster since it shouldn't need to iterate through anything to do with array indices.

Thanks

[jeeswg]

Could try some benchmark tests:

Code: Select all

;Push seems to be slower:
;62 234
;62 171
;63 187

q:: ;benchmark tests: 'obj[k] := v' v. 'obj.Push(v)'
vNum := 100000

oArray := []
vTickCount1 := A_TickCount
Loop, % vNum
	oArray[A_Index] := "abcdefghijklmnopqrstuvwxyz"
vTickCount2 := A_TickCount
;MsgBox, % oArray.Length()
oArray := ""

oArray := []
vTickCount3 := A_TickCount
Loop, % vNum
	oArray.Push("abcdefghijklmnopqrstuvwxyz")
vTickCount4 := A_TickCount
;MsgBox, % oArray.Length()
oArray := ""

vOutput := (vTickCount2-vTickCount1) " " (vTickCount4-vTickCount3)
Clipboard := vOutput
MsgBox, % vOutput
return

Btw if adding string keys, I found it's faster to add them in alphabetical order:

objects: AHK array is slow to add keys cf. Scripting.Dictionary object - AutoHotkey Community
https://autohotkey.com/boards/viewtopic.php?f=5&t=31663

[Helgef]

A general tip for improving performance for arrays is to use SetCapacity when possible. If you really just want to fill an array with a single value, you can try these (narrow niche ) functions,

Code: Select all

fillArrChar(char,n){
	; Returns an array of length n whose elements consist of one single symbol: char, such that
	; 0<=asc(char)<=255
	VarSetCapacity(str,n,asc(char))
	return StrSplit(StrGet(&str,n,""))
}
fillArrStr(str,n,del:="`n"){
	; Allows for an arbitrary string instead of just one character.
	; Returns an array of length n whose elements consist of the string str.
	; Input:
	;	str, string to fill array with.
	;	n, integer, length of the array.
	;	del, delimiter for strsplit. Must not be substr of str.
	; Con:
	;	Need (to specify) a delimiter.
	VarSetCapacity(var,n*strlen(n+strlen(del))*(A_IsUnicode?2:1),1)
	s:=StrSplit(StrReplace(StrGet(&var,n,""),chr(1),str . del,,n),del), s.pop()	
	return s 
}

Cheers.

[jeeswg]

For 500000 keys using the code above, I'm getting benchmark test results:
'obj[k] := v' 'obj.Push(v)'
344 4196
234 4258
219 4227

Assuming the tests are correct, why is Push so much slower, the only reason I would use Push is with the expectation that it would be faster.

I changed the code to retrieve the array count each time, to make it a fairer test, but with similar results:
374 4150
297 4180
312 4181

Code: Select all

q:: ;benchmark tests: 'obj[k] := v' v. 'obj.Push(v)'
vNum := 500000

oArray := []
vTickCount1 := A_TickCount
oArray.1 := "abcdefghijklmnopqrstuvwxyz"
Loop, % vNum - 1
	;oArray[A_Index] := "abcdefghijklmnopqrstuvwxyz"
	oArray[oArray.Length()+1] := "abcdefghijklmnopqrstuvwxyz"
vTickCount2 := A_TickCount
;MsgBox, % oArray.Length()
oArray := ""

oArray := []
vTickCount3 := A_TickCount
Loop, % vNum
	oArray.Push("abcdefghijklmnopqrstuvwxyz")
vTickCount4 := A_TickCount
;MsgBox, % oArray.Length()
oArray := ""

vOutput := (vTickCount2-vTickCount1) " " (vTickCount4-vTickCount3)
Clipboard := vOutput
MsgBox, % vOutput
return

[Helgef]

Try oArray.SetCapacity(vNum), and you should use SetBatchlines for benchmarkings, unless you run it in v2.

[jeeswg]

Indeed Push is faster if you use SetCapacity.

Code: Select all

;with oArray.SetCapacity(vNum): Push faster
;297 203
;265 188
;312 187

;without oArray.SetCapacity(vNum): Push slower
;358 4196
;296 4321
;265 4322

q:: ;benchmark tests: 'obj[k] := v' v. 'obj.Push(v)'
vNum := 500000

ListLines, Off

oArray := []
oArray.SetCapacity(vNum)
vTickCount1 := A_TickCount
oArray.1 := "abcdefghijklmnopqrstuvwxyz"
Loop, % vNum - 1
	;oArray[A_Index] := "abcdefghijklmnopqrstuvwxyz"
	oArray[oArray.Length()+1] := "abcdefghijklmnopqrstuvwxyz"
vTickCount2 := A_TickCount
;MsgBox, % oArray.Length()
oArray := ""

oArray := []
oArray.SetCapacity(vNum)
vTickCount3 := A_TickCount
Loop, % vNum
	oArray.Push("abcdefghijklmnopqrstuvwxyz")
vTickCount4 := A_TickCount
;MsgBox, % oArray.Length()
oArray := ""

vOutput := (vTickCount2-vTickCount1) " " (vTickCount4-vTickCount3)
Clipboard := vOutput
MsgBox, % vOutput
return

@Helgef: Have SetBatchlines set to what? Are there any other things that should be set? Should these be used?

Code: Select all

ListLines, Off
#KeyHistory 0
#NoEnv
AutoTrim, Off

[Helgef]

SetBatchLines,-1 for most accurate measurements, and also, you have to spend less of your time waiting for the test to finish.
About accuracy and SetBatchLines. Consider the case where one function takes 9 ms to finish, and another takes 11 ms, when the first function has finished, it still has one ms until the next batch sleep, so it is called two times for each sleep. However, when the second function finishes its call it is already time to sleep, so it will sleep after each call. Each sleep is 10 ms long, so for a test of, say 1000 calls, the scripts sleeps 5 seconds more for the second function than it does for the first function.