Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Discussion / Dynamic Arrays

Author
Message
Robert The Robot
13
Years of Service
User Offline
Joined: 8th Jan 2007
Location: Fireball XL5
Posted: 27th Jan 2011 15:28
I was playing around in DBC, and I've found a way to dynamically change the size of an array. The method is actually quite simple - Clone the existing array, UnDim the original array, ReDim the original array with an increased size, and copy the data back.


Array Insert at Bottom:


Example



Array Insert at Top:


Example:



Array Insert at Element:


Example:


It seems to work quite well, although there seems to be a slight slow down with large array sizes - at 10000 entries it takes 3ms to add the next one!

We spend our lives chasing dreams. Dark Basic lets us catch some of them.
Libervurto
14
Years of Service
User Offline
Joined: 30th Jun 2006
Location: On Toast
Posted: 27th Jan 2011 23:03 Edited at: 27th Jan 2011 23:13
Quote: "rem Faster way to do this?..."



It's not pretty but it removes a condition.

You might know the answer to this question: if you give an expression as one of the bounds of the for loop (e.g. ArrayCounter-1), does DB calculate the value every loop or just at the start?
If so I have saved adding another condition by using T instead of element+1, which are equal because after the first for loop ends we know T must be greater than element (otherwise it wouldn't have ended) and the step of the for loop is one by default, so we can conclude that T=element+1.
Maybe try storing ArrayCounter-1 and see if that speeds it up further.

This would be a great thing to have in the DBC armory, but I wonder if it can be made fast enough to be used practically. If it can, I doubt the answer can be found using DB's arrays, but feel free to prove me wrong!


Everything worthwhile requires effort.
Latch
14
Years of Service
User Offline
Joined: 23rd Jul 2006
Location:
Posted: 28th Jan 2011 01:19
Quote: "...Obese87: You might know the answer to this question: if you give an expression as one of the bounds of the for loop (e.g. ArrayCounter-1), does DB calculate the value every loop or just at the start?"

I would think that it evaluates the expression every time. The values in an expression can change as the loop progresses therefore, DBC needs to evaluate the expression each iteration:



If you know that the value of the expression won't change then you can assign a variable to the value of the expression to save a little processing time:



Quote: "...Robert The Robot: It seems to work quite well, although there seems to be a slight slow down with large array sizes - at 10000 entries it takes 3ms to add the next one!"

It's very effective and the lag, if any, isn't noticed in an application environment - like a level builder where you are adding and removing images and objects all the time.

In fact, the only way to resize arrays in ANY language is to reallocate the memory and copy them to the reallocated memory. Some languages do this behind the scenes for you so you don't see the process. Since memory is changeable and a shared resource, you can't just add or subtract bytes to a memory location because those bytes might be used by something else. You have to create a new block of memory of a specific size (dim array) and then copy the old data to it.

Enjoy your day.
Robert The Robot
13
Years of Service
User Offline
Joined: 8th Jan 2007
Location: Fireball XL5
Posted: 28th Jan 2011 15:44
That's fascinating!

I know DBC evaluates the conditions every time the for-loop loops round, as I've sometimes used this as a handy "Exit" condition to break out of a for-loop early:


I've a feeling I've used this with variables as well!


I suspect the time lag may not matter at all as long as you only use a few hundred elements in each array. And it might be more effective if you (say) double the size of your array when you need to extend it, enlarging it beyond its required size - that way you could perhaps speed up the addition of later elements.

Quote: "...Maybe try storing ArrayCounter-1 and see if that speeds it up further"

Another thing to do is correct the way "CloneArray" exists the whole time, not just when you need to resize the main array.

I'll try and include some of these optimisations (not to mention write a "Delete Array Element" command -there's no point extending a list if you can't shrink it!)

We spend our lives chasing dreams. Dark Basic lets us catch some of them.
Kevin Picone
17
Years of Service
User Offline
Joined: 27th Aug 2002
Location: Australia
Posted: 29th Jan 2011 04:18
It's best not to dimension arrays constantly, so using them as fixed pre-sized caches and expanding them only when there is demand is a better way of going. This reduces the impact of allocation & deallocations and lowers the risk of serious memory fragmentation as the app is running over time.

So something like this (which is where you're heading anyway) is a more rubust solution.

Note: (This is PB code written to look like DB code)




Depending upon the size of the arrays, such brute force approaches well enough, but can be improved further. For example deletion and insertion both could be batched. Which would minimized the data movement.

Imagine a situation where you have a particle emitter and spawns 50 fragements each update. Then we don't rally want to be inserting those fragements indivually. If we know we're going to adding more than one, then the insert could make space for the required amount. Same with deletion, this can single passed, by caching what's to be removed then, culling them together.


However if the order of items is not important, then something like the Array Allocation Management Examples would be preferable solution.

The idea being the we have our arrays to hold the information about the game characters. Then use a management array to keep track of the active objective within the list.

Libervurto
14
Years of Service
User Offline
Joined: 30th Jun 2006
Location: On Toast
Posted: 29th Jan 2011 14:41
When you add an entity to the array you could dimension the new array with 10 more slots instead of one, then you have a bit of space before you need to extend the array again.

This is either a clever or dumb idea:
Make a temporary array, which stores 10 entities the same way as the main array. Then at appropriate intervals - or when you have filled the temp array - clone the main array and include the temp entities.


Everything worthwhile requires effort.

Login to post a reply

Server time is: 2020-08-06 08:42:07
Your offset time is: 2020-08-06 08:42:07