Array resizing

General
1

Can it become problematic if an array of 50 000 objects is treated that way (this is for a sort algorithm I’m testing):

  • Add 50 000 unique objects
  • Loop over the 50 000 objects and append them in a different order, then remove the first 50 000 entries
  • Loop over the 50 000 objects and append them in a different order, then remove the first 50 000 entries
  • Loop over the 50 000 objects and append them in a different order, then remove the first 50 000 entries
  • … and so on

Can this lead to memory problems?

2

Wouldn’t it be easier to create a new array and then replace the original all at once?

3

Not that that answers your question.

I think no. But it’s still less efficient.

4

How large are the elements of your array? Have you calculated the sum over the members of the array?

5

I would go and make new arrays
redim they to target size.
And than fill them.

6

One can not make new typed arrays by introspection. This means I would have to create more than one hundred copies of my method, each with one line changed to specify the object type of the new array. I’m dreaming of Generics…

So Tim is right, for the moment I’m not looking for alternative solutions, but for a comment to “Can this lead to memory problems?”.

7

Well, it could lead to memory problems. You want the sort function to be generic? What if instead of 50,000 items you have 50,000,000? You could definitely see memory issues then.

Also, are you certain you need typed arrays? Perhaps you could just sort arrays of objects? Or sort arrays of Comparable interfaces with a Compare function (which, yes, you’d have to add to any class you intend to sort).

Also also, given your scheme, at the very least it would be a bit more efficient to redim the array to twice it’s size, once, then as you loop, fill up the second half the first time through, then fill up the first half the next time through, etc.

8

Perhaps a class interface would help.

9

Thanks for all your suggestions, I appreciate it, but I’m not searching for an alternative solution at the moment - I’m really only interested to learn if this can lead to memory problems.

For example it could be that removing elements at the start of an array doesn’t mean that the memory is freed. It probably is if elements are removed at the end of the array. So it could be like this:

adding 100 objects —> 400 bytes for 100 pointers
removing objects 50 to 99 --> 200 bytes kept for 50 pointers, 200 bytes freed

adding 100 objects —> 400 bytes for 100 pointers
removing objects 0 to 49 --> 400 bytes kept for 50 freed pointers and 50 valid pointers

For speed issues, internally Xojo could keep this gaps and wouldn’t rearrange the elements. That’s my concern with the above, because I don’t know how arrays are implemented in the Xojo framework.

10

Hi.

As far as I can tell the array is re-structured when elements are removed. This is based on my own tests which determined that performance got worse the larger the array. I wouldn’t be surprised if a second temporary copy was made during this time which would also impact memory usage but I have not tried to verify that myself.

Since it looks like you are dealing with a large number of elements I suggest you spend a little time benchmarking your array structure manipulation code. Depending on what you are trying to do you might find a Dictionary is better. In the end we solved our problem by creating a double linked list class that also used a Dictionary so that we could step through the elements in insertion order via the linked list and also find an element by key using the Dictionary.

HTH
Kev.