Feature Request: Linked Arrays

[Steven Schveighoffer]

"downs" wrote
> Steven Schveighoffer wrote:
>> If each array chunk is the same size, you could store the array in an 
>> array
>> of arrays.  Then lookup time becomes O(1), and appending data is not 
>> going
>> to cause a copy of the other array chunks that you already have 
>> allocated.
>>
>
> Yeah but that just reduces the appending problem, not removes it.
> Admittedly, this might be sufficient in many cases.

It basically reduces the copy of all the data to just the copy of the array 
headers.  If each array chunk is a page, 4096 bytes, then a page of array 
headers (on a 32-bit arch) is 4096 / 8 = 512 chunks * 4096 bytes = 2MB 
before you have to reallocate the array header array.  And then each time 
you reallocate, you get another 2MB.  If you size your array chunk size 
appropriately, or pre-allocate the pages for your array of arrays, then you 
get even better performance.  Change the array headers to pointers, and you 
get double the performance.  I'd think it would be very comparable to a 
link-list of arrays.

>
>> If you add a huge piece that is bigger than one chunk, just allocate that
>> piece, then slice the piece up into chunks.
>>
>> It could actually be an array of pointers, assuming all your chunks are 
>> the
>> same size.
>>
>> I'd prefer that to a linked list of arrays, where traversal is O(n) (with 
>> a
>> small constant)
>
> Um, excuse me but isn't traversal always O(n)?
> Perhaps you meant lookup - keep in mind that my original proposal was not 
> intended for situations where random lookup is important (queues, buffers 
> and stacks).

When someone mentioned that traversal would be a problem, I assumed that was 
when you want to do random lookup.  Random lookup is O(n) with a LL of 
arrays, with a very small constant (because you skip n elements at a time 
per link).  The point of my suggestion was to reduce the lookup time.

You could have queue/buffer behavior, but all you need to reallocate is the 
headers.  I admit, the link-list version might be better memory-wise than my 
solution in that regard.

-Steve