May 03, 2008
janderson wrote:
> downs wrote:
>> janderson wrote:
>>> Robert Fraser wrote:
>>>> I'd rather ask the GC to expose a canExpand() method and have it
>>>> implemented in the library.
>>> I agree.
>>
>> So do I, actually. That would be best.
>>> BTW, to state the obvious:
>>>
>>> "Linked arrays" have several dis-advantages when compared to arrays.
>>> Namely after a while of lots of insertions deletions they become very
>>> fragmented and performance slows down.
>>
>> I don't see how that could happen, if you're only appending at the end.
>>
>>> The main thing you have to
>>> watch out for is traversal. Often I've seen code slow down because
>>> people write a data structure to speed up insertion, not realizing that
>>> most of the time was spent in traversal.  By using links the work of the
>>> pre-fetcher, code optimizer and cache is increased.
>>
>> It depends on the size of the elements.
>>
>> If it's, say, an int[>], about 1k of them could fit into a single page of memory. At that point, and especially if the next array pointer is stored at the _end_ of the memory range, and considering that linear traversal can easily be enhanced with prefetch instructions, I think the traversal speed difference to flat arrays shrinks considerably.
>>
>> I don't have the benchs to demonstrate that though. Sorry.
>>
>>> One think what would help, is if you could get the next free aligned
>>> block in memory from the previous block.  That way the array would be
>>> slightly more cache friendly.
>>>
>>
>> I don't understand.
>>
>>> I'm not saying this sort of data struct doesn't have it's uses,
>>> sometimes its useful for minimizing Memory Manager fragmentation.  In
>>> fact if you have a huge array, sometimes the only way to get around
>>> fragmentation is to spit it up.
>>
>> That's the idea :) Currently, appending to an array is almost embarassingly slow. This forces the use of preallocating, which is unintuitive.
>>
>> Imnsho :)
>>
>>> -Joel
>>
>>  --downs
> 
> 
> This may help:
> 
> http://video.google.com/videosearch?hl=en&safe=off&pwst=1&resnum=0&q=herb%20sutter&um=1&ie=UTF-8&sa=N&tab=wv 
> 
> 
> Note that smallest cache lines could be as small as 64bit.
> 
> -Joel


Also you should be aware of this trick:

array.length = 100;
array.length = 0;

Will preallocate memory for you.

-Joel
May 03, 2008
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.

> 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).

> 
> -Steve
> 
> 
May 04, 2008
"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


May 07, 2008
downs schrieb:
> Since one of D's weaknesses is bad speed when appending to dynamic arrays, I've been thinking about a way to fix this.
> 
> Linked arrays are a hybrid between flat arrays and linked list: a single linked list of array chunks.

So it would be nice to have a datastructure that is a mixture of a <Vector> and a <LinkedList>.
A list-implementation that
automatically handles allocation of needed space quite efficiently, provides fast index-based access *and* fast insertions and removals.
List.d tries to behave like a <Vector> and thus like a
dynamic array if possible:

if T.sizeof <= (void*).sizeof
  behave like vector
else
behave circular linked list // to solve the head tail problem

I think it is worth to have a look at Uwe Salomons  list implementation.
dsource indigo/tools/list.d

based on :
http://doc.trolltech.com/4.0/qlist.html

Bjoern
1 2
Next ›   Last »