>> I don't know the internals of the GPC New procedure, but in various
>> environments where I have worked in the past there was no guarantee that successive
>> calls to New would allocate adjacent blocks of storage, hence no guarantee that
>> there would be no gaps or wasted space.  It all depended on what sequence of
>> calls to New and Dispose had occurred earlier.
>
> You can never rely on successive `New' calls to return adjacent
> blocks of storage. That's not a reliable way to enlarge an array.
> And I don't know of any compiler for Pascal, or any other language
> for that matter, where such a thing would work. Sometimes there are
> special routines for that (in GPC the non-standard ReAllocMem, use
> with caution), otherwise you have to allocate a new array and copy
> the existing elements, or use another data structure that doesn't
> require contiguous memory, such as lists or trees.

I think we have lost the trail here.

 

Peter's original posting on this subject asked if there was a way to store character strings of different lengths without wasting space for the short strings.  Frank Heckenbach suggested that Peter store each string using the New procedure, so each string would get a space its own size.  I said that the Pascal Macro Compiler could store the strings without any gaps or wasted space.  However, this works only if the strings are known at compile time. 

 

I also pointed out that using New does not assure that there would be no gaps because New does not always allocate consecutive adjacent blocks of storage.  In the storage-allocation system that I use most often, storage is allocated in units of 16 bytes, because free storage is kept in a tree structure with each element containing a length, an up pointer and two down pointers.  So if you allocated a separate block for each character string there could be a lot of wasted space.

 

Conclusion:  If the strings are known at compile time, the most efficient way to store them without gaps is to use the Pascal Macro Compiler.  If the strings are not known until run time, the most efficient way is to allocate a large block of storage, and move the strings in end-to-end, using a separate array to hold either pointers or indices into the large block. 

 

When the block is full, allocate another large block using New.  There are two ways to manage the storage.  (1) Extension block method:  Use a second array to point to the set of large blocks.  Each string will be accessed using two pointers or two indices.  The first will point to the particular block, and the second will point to the string within the block.  (2) Single block method:  Make the new block twice as large as the previous block, move the existing strings into the new block and then Dispose the old block.

Frank Rubin