redimensioning an array really slow...?

Just starting out? Need help? Post your questions and find answers here.
jassing
Addict
Addict
Posts: 1745
Joined: Wed Feb 17, 2010 12:00 am

redimensioning an array really slow...?

Post by jassing »

Is this to be expected? Are arrays, with structures, just slow by nature? or is the size of the array element?

Code: Select all

; test results are on a cheap old laptop

Structure dbwin_buffer 
  dwProcessID.l
  Data.s{4096-SizeOf(long)} ; can't really use this, need ascii, so just for reference
EndStructure

Debug "List test"
s = ElapsedMilliseconds()
NewList mno.dbwin_buffer()
For x = 1 To 10000
  AddElement( mno() )
Next
Debug ElapsedMilliseconds()-s           ; 40 ms

Debug "Arrays"

Debug "ABC test"
s = ElapsedMilliseconds()
Dim abc(0)
For x = 1 To 10000
  ReDim abc( ArraySize(abc()) + 1 )     ; 2 ms
Next
Debug ElapsedMilliseconds()-s

Debug "Now XYZ"

s=ElapsedMilliseconds()
Dim xyz.dbwin_buffer(0)
For x = 1 To 10000
  ReDim xyz( ArraySize(xyz()) + 1 )
Next
Debug ElapsedMilliseconds()-s           ; 260 seconds
Debug "Done"
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: redimensioning an array really slow...?

Post by Little John »

In order to measure time values that make sense, switch OFF debugging in the PureBasic IDE. Of course, you can't use any "Debug" statement for output then.
jassing
Addict
Addict
Posts: 1745
Joined: Wed Feb 17, 2010 12:00 am

Re: redimensioning an array really slow...?

Post by jassing »

Little John wrote: Wed Jun 07, 2023 12:02 am In order to measure time values that make sense, switch OFF debugging in the PureBasic IDE. Of course, you can't use any "Debug" statement for output then.
Sorry, should have said that up front.
Time w/o debugger aren't much different...
for the list, 40ms
for the plain array, 1ms
for the structure array, 225 seconds

I'm not saying it's a bug, I'm just curious if that's expected performance for an array. I was thinking it'd be on par with a list, or at least close to it.
User avatar
Demivec
Addict
Addict
Posts: 4086
Joined: Mon Jul 25, 2005 3:51 pm
Location: Utah, USA

Re: redimensioning an array really slow...?

Post by Demivec »

jassing wrote: Wed Jun 07, 2023 12:15 am for the list, 40ms
for the plain array, 1ms
for the structure array, 225 seconds

I'm not saying it's a bug, I'm just curious if that's expected performance for an array. I was thinking it'd be on par with a list, or at least close to it.
IMHO, it is due to the memory management overhead and yes it is expected

When an array is ReDim'med to add an element the array memory is reallocated if it can't be expanded, the previous contents are copied over and then the previous memory is freed. If this is done repetitively like in your test code the result is slow just like repetitive small string concatenations.
It is similar to the slowness in string concatenations which the increases the time it takes according to the size of the memory being copied. Because naive PB string concatenation also includes other slowdowns such as traversing the size of the memory to determine its length.

Lists on the other hand are only adding a single element at a time without relocating anything. In addition they have a custom process to manage the memory for new elements. Here is a entry in the PureBasic Blog that details this a bit:
https://www.purebasic.fr/blog/?p=8
jassing
Addict
Addict
Posts: 1745
Joined: Wed Feb 17, 2010 12:00 am

Re: redimensioning an array really slow...?

Post by jassing »

Awesome. Thank you very much for the detailed answer. Makes sense.
AZJIO
Addict
Addict
Posts: 1319
Joined: Sun May 14, 2017 1:48 am

Re: redimensioning an array really slow...?

Post by AZJIO »

At least working in AutoIt3, I found out that Redim should not be greater than 1000. The function is slower when the array is large. Use Redim to add 1000 elements at once, and after filling, cut it with Redim to the actual size, according to the counter that is used at the time of filling with elements. I also saw options when a person checked the size of the array before filling in the next element when searching for files and each time doubled the size of the array 2, 4, 8, 16, 32, etc.
jassing
Addict
Addict
Posts: 1745
Joined: Wed Feb 17, 2010 12:00 am

Re: redimensioning an array really slow...?

Post by jassing »

AZJIO wrote: Wed Jun 07, 2023 1:01 am At least working in AutoIt3, I found out that Redim should not be greater than 1000. The function is slower when the array is large. Use Redim to add 1000 elements at once, and after filling, cut it with Redim to the actual size, according to the counter that is used at the time of filling with elements. I also saw options when a person checked the size of the array before filling in the next element when searching for files and each time doubled the size of the array 2, 4, 8, 16, 32, etc.
I was trying different 'standard' methods for dealing with a data queue, where 'total' is not known, as data is added, the list grows; that's how I noticed it. I actually noticed it with a much smaller value, I just posted the large value to show the extremeness of the variation.

For now; I'm sticking with a list(), will work on a FIFO memory linked-list later to see if that'll be faster.
Post Reply