PDA

View Full Version : SetLength() out of memory :(



cronodragon
20-08-2007, 06:22 PM
Hello!

I have a routine to add elements to a dynamic array using SetLength. The array is made of records, which have 2 pointer fields only (should be about 8 bytes per element). But I get an out of memory exception when inserting about 23000 elements, one by one in separate calls. I have 4GB of RAM and few apps loaded, so it shouldn't be a problem. I supposed it's a problem with memory fragmentation, so I added FastMM to "uses". That solved the problem, but does it mean Delphi 7's default memory manager is sucky?

Regards!
-Marco

dmantione
20-08-2007, 06:32 PM
No, your approach is wrong. You should prevent resizing heap blocks repeatedly, or, if you have to, you should resize them exponentially.

Delphi's memory manager isn't worlds best one, but reckless resizing will bring down any memory manager.

cronodragon
20-08-2007, 06:55 PM
That sounds good, and might speed up the application. By exponentially you mean in powers of 2, or doubling the latest size? Wouldn't it be better in blocks of fixed size?

Thanks!
-Marco

dmantione
20-08-2007, 07:02 PM
Yes, powers of 2 used most often. You get an average of 75% fill with powers of 2. If a higher fill is desired you can use a lower exponent, like multiplying the size with 1,5 each time.

Resizing exponentially works better than with fixed blocks in many cases, because with fixed blocks, you can run out of memory again simply by increasing the amount of items. To prevent this you need to make the block size very large, which means you get a very low efficiency if the count is low. However, if the amount of items can be estimated well, fixed blocks can be better.

cronodragon
20-08-2007, 07:10 PM
Excellent, I'll try that! :D

User137
21-08-2007, 09:30 AM
I have also run into problems with such large arrays with my 3D modeller. Thx for pointing out the resizing of pow 2, it may optimize speed great deal but won't solve the array size prob. This is where calls like AllocMem, ReAllocMem and FreeMem step in, as they have only limitation of your system memory unlike setlength.
Oh, they are also much faster than setlength :wink: Only problem is you'd be using pointers which make it slightly more complicated.

cronodragon
21-08-2007, 08:00 PM
I made the changes to increase the dynamic arrays in powers of 2, and that increased the speed a lot! Now Delphi's memory manager works 70% faster than FastMM, maybe because FMM is debugging the processes, and I can add 1 million elements without getting an exception error.

Now I want to speed up the deletion of elements. I supposed it would be a good idea to release the memory in the same way, and modified my algorithm to half the reserved block when the last used element is lower than half of the length.

Also, my algorithm allows batching processes, and I'm thinking on making a deletion list, so I can mark the removed elements and dispose them later... but there are several options I could use, some of them:

1. Creating a linked list of pointers or indexes to elements for deletion. This would waste a lot of memory, and would be too slow to use with my algorithm.

2. Adding a field to the element's "record" type that allows marking it as deleted, but that would waste 1 byte per element.

3. Making an array of bits (or using Delphi's bit array class) to map deleted elements. Maybe this is the option that requires less resources.


This is where calls like AllocMem, ReAllocMem and FreeMem step in, as they have only limitation of your system memory unlike setlength.
Oh, they are also much faster than setlength Wink Only problem is you'd be using pointers which make it slightly more complicated.

Yes, it's not as handy as SetLentgh, but it would be possible to mask the memory block with an array. I'll try those functions too, thanks for sharing the idea.

:D

dmantione
21-08-2007, 08:09 PM
A technique I'm using in FPC's register allocator is to move the last item to the deleted item:

I.e. say you have:

1 2 3 4 5 6

... and you would want to remove "3", you move "6" to the positition of 3:

1 2 6 4 5

Now that destroys any ordering, but often, deletion occurs in batches, so you can sort it again after all the deletes have happened.



Yes, it's not as handy as SetLentgh, but it would be possible to mask the memory block with an array. I'll try those functions too, thanks for sharing the idea.


I consider dynamic arrays (and therefore setlength on them) a bad Delphi feature, as it has very odd semantcs and it suggests you can recklessly use setlength for each mutation without consequences. The reality is that it is almost never a good idea to resize the memory block for each mutation.

Huehnerschaender
21-08-2007, 08:29 PM
One question...

I always use dynamic arrays for my game elements and in my update and render routines I do things like:


for i := 0 to high(enemys) do
enemys[i].update(time_);

Using SetLength like you are discussing here would force me to do it like:


for i := 0 to high(enemys) do
if assigned(enemys[i]) then
enemys[i].update(time_);

Am I right? And is this really faster than having an array of exact the size I need?

Or does this advance you are talking about only make sense when the arrays size changes over and over again.... hundreds of times a second?

In my case the arrays size would only change e.g. if an enemy is destroyed.

cronodragon
21-08-2007, 08:36 PM
A technique I'm using in FPC's register allocator is to move the last item to the deleted item

That's such a simple and excellent idea, why didn't I think about it before? Thanks! :D

cronodragon
21-08-2007, 08:41 PM
for i := 0 to high(enemys) do
if assigned(enemys[i]) then
enemys[i].update(time_);

Instead I would do something like:


for i := 0 to lastIndex do
enemys[i].update(time_);

Where lastIndex is not necessarily equal to high(enemys), just points to the last assigned element and the array can have any given size.

dmantione
22-08-2007, 06:38 AM
One question...
Or does this advance you are talking about only make sense when the arrays size changes over and over again.... hundreds of times a second?

In my case the arrays size would only change e.g. if an enemy is destroyed.

Only when the array size changes over and over again. Using setlength once to initialize an array is not harmfull, since that compares to a simple "getmem".

However, changing the array size when an enemy is destroyed can be harmfull and cause heap fragmentation, be it slowly.