queue container?

[Gor Gyolchanyan]

I see. makes sense. :-)
Although you could just as well have a pre-allocated and cached links
in doubly-linked list, but i think this one has a greater potential
for optimization.
D needs a few of those ultra-fast container types. Like the Judy array.
Oh, Judy array is by far the sexiest container i ever saw.
http://en.wikipedia.org/wiki/Judy_array

On Wed, Oct 26, 2011 at 2:25 PM, bearophile <bearophileHUGS at lycos.com> wrote:
> Gor Gyolchanyan:
>
>> I don't understand the advantage of having a dynamic array of static arrays.
>> How is that gonna increase add/remove performance to the ends?
>
> You also keep a length that tells you how many items you are using in the last fixed size array. Removing on item means just decreasing this length. Appending an item often just means writing the item and then increasing this length. Once in a while you add or remove a chunk (keeping one fully empty one at the end avoids you to do busywork when the queue item that gets added and removed many times is the first one of a chunk).
>
> In a linked list you have to do something with the memory used by the added/removed item every time you add and remove an item (like removing and putting it into a freelist).
>
> Working on the chunk array gives more CPU cache locality and probably requires less management code.
>
> With a small change the dynamic array of chunk pointers is usable to implement a deque too: you have to manage the dynamic array as a growable circular queue. Like a hash, when this array is full you allocate a new one twice larger, and copy the chunk pointers into it.
>
> ----------------
>
> Timon Gehr:
>
>> A dynamic array of pointers to fixed size arrays is this:
>> T[N]*[] arr;
>> What would you wrap exactly?
>
> How do you allocate those T[N] in D?
>
>
>> Do you know how this implementation compares to a circular buffer
>> implementation? I'd have expected that to be faster.
>
> A circular buffer is faster in some situations, when you on average need a constant number of items in your data structure. But a circular buffer needs lot of time to change its size a lot, because you have to halve or double it once in a while. Generally, if you don't know much about how your queue will be used, a dynamic array of chunks is better (some people use a linked list of chunks, but this makes it worse to access items randomly, and the time saved not managing a growable circular queue of the chunk pointers is not much, because the chunks usually contain hundreds of items or more).
>
> Bye,
> bearophile
>