Array Design Idea
Sean Kelly
sean at f4.ca
Mon Dec 10 12:40:34 PST 2007
Jb wrote:
> "Sean Kelly" <sean at f4.ca> wrote in message
> news:fjk706$134g$1 at digitalmars.com...
>> Craig Black wrote:
>>> "Jb" <jb at nowhere.com> wrote in message
>>> news:fjk5g9$10lb$1 at digitalmars.com...
>>>> "Craig Black" <cblack at ara.com> wrote in message
>>>> news:fjk2k6$pfl$1 at digitalmars.com...
>>>>
>>>>> There are three things that need to be stored for a resizable array:
>>>>> the pointer to the array, the size, and the capacity. My array
>>>>> implementation, both the size and the capacity are stored on the heap
>>>>> with the array. There is only one heap allocation, and the first 8
>>>>> bytes are reserved for the size and capacity values. Further, there is
>>>>> no heap allocation if the array is empty. If the array is empty, then
>>>>> the pointer is null, and the array is assumed to have a size and
>>>>> capacity of zero, so there is no need to store the size or capacity of
>>>>> an empty array.
>>>> Thats how Delphi does dynamic arrays and strings. Well except that it
>>>> has length & refcount rather than length & capacity. Wouldnt it break
>>>> slicing though? You cant point halfway into an existing array and still
>>>> have the length & capacity at -4,-8 bytes?
>>> I still haven't wrapped my head around the slicing issue. Obviously it's
>>> not an issue for C++ arrays. Doesn't D already allocate the capacity of
>>> the array on the heap? If this is so why doesn't this break slicing?
>> D relies on the GC to tell it what the capacity for a block is. However,
>> because operations on slices should always reallocate, it is enough for
>> the GC to simply return 0 for the capacity if the supplied pointer is not
>> at the head of a memory block.
>
> Except that a slice can somtimes point at the begining of a block. So slices
> dont always reallocate, although perhaps they should?
Steven Schveighoffer's proposal entitled "Proposal: alternative GC idea
that negates the need for T[new]" would address issue, though it has yet
to receive any responses.
Sean
More information about the Digitalmars-d
mailing list