Re: The problems arrayed before me...

• Previous message: Jud McCranie: "Re: The problems arrayed before me..."
• In reply to: Christakis John: "The problems arrayed before me..."
• Next in thread: Christakis John: "Re: The problems arrayed before me..."
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: Sat, 06 Dec 2003 00:35:41 -0600

Christakis John wrote:
> When an array is grown, how does Delphi manage this cleanly?

Delphi uses the ReallocMem function to do the grunt work. With the
default memory manager, the first thing it tries to do, when it receives
a request for a larger piece of memory, is to check whether the existing
allocated block is actually already large enough for the new request.
When you ask for a certain amount of memory, the memory manager is free
to allocate more than you ask for, and it keeps track of that. The
reallocation is then as simple as updating the size field and giving you
back the same buffer you started with.

When the existing buffer isn't large enough for the new request, then
the memory manager will try to find a better fit from the other memory
blocks it has at its disposal. When you free something, that memory
isn't immediately returned to the OS; Delphi will keep it to reuse
later. If the memory manager still doesn't have any blocks large enough
for the new request, it asks for another chunk of memory from the OS. If
that _still_ doesn't work, then you're out of memory.

Once the memory manager has the new lareg block, it copies the contents
of the old block into the new one and marks the old buffer as freed.

Dynamic arrays are stored as pointers to the element data. If you have a
two-dimensional dynamic array, 6x10, the master array will only be 24
bytes long -- long enough to hold six four-byte pointers. It doesn't
matter how long any of the 10 subarrays are. When you resize the master
array, the subarrays are not duplicated. Only their pointers are copied
from the old array to the new one.

> and that code is repeated an unknown amount of times. But, where is Delphi
> putting all this data? It cannot be contiguous, can it - does that matter?
> Could this cause the 'Out of Memory' errors I am getting on large array
> sizes? Would this cause the equivalent of disk fragmentation in memory?

Fragmentation is exactly what happens. With the memory manager
allocating progressively larger buffers each time, it abandons a
slightly smaller one. It won't always be able to use that discarded
space for anything else, but it can't return it to the OS, either, since
other parts of the large block from the OS are still being used. So even
if you have lots of unused memory, it may still report that you're out
of memory since it's all in small portions. (Like Monty Python have
122,000 miles of string in three-inch lengths.)

> I can't just set the length to a figure larger than I think it
> will be as there is no way to tell how big it could get. I could end up
> allocating more memory than the machine has.

A common technique for dynamic memory allocation is to only increase the
array's size occasionally. Not for every iteration, but not just once at
the beginning, either. Allocate a reasonable size at the start, and when
you exhaust that, grab another group. You can see this in action in the
implementations of TList and TStringList. And that leads me to my next
suggestion. Instead of using the master array by itself, wrap access to
it into a class. Then the class can manage the storage and allocation
details.

Since your subarrays aren't stored contiguously, your master array might
not need to be contiguous, either. You could keep the master array in
segments. Have an array of fixed-size segments. When you have enough
subarrays to fill a segment, add another.

-- 
Rob

• Previous message: Jud McCranie: "Re: The problems arrayed before me..."
• In reply to: Christakis John: "The problems arrayed before me..."
• Next in thread: Christakis John: "Re: The problems arrayed before me..."
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]