Re: [boost] [MultiIndex] Random Access mental model?

Subject: Re: [boost] [MultiIndex] Random Access mental model?
From: JOAQUIN M. LOPEZ MUÑOZ (joaquin_at_[hidden])
Date: 2008-11-01 11:07:36

________________________________________
De: boost-bounces_at_[hidden] [boost-bounces_at_[hidden]] En nombre de David Abrahams [dave_at_[hidden]]
Enviado el: sábado, 01 de noviembre de 2008 0:47
Para: boost_at_[hidden]
Asunto: Re: [boost] [MultiIndex] Random Access mental model?

on Fri Oct 31 2008, Joaquin M Lopez Munoz <joaquin-AT-tid.es> wrote:
> > Yep, this is done. Only one node per element is allocated. This is
> > true regardless of the indices used, including random
> > access indices. If you want to visualize this, each element node
> > has as many node headers as indices are, each one stacked on top
> > of the next.
>
> I think random access shouldn't need to add a node header unless you
> want to do something like look up a key in the hash index and delete
> that element.  Maybe a feature-model interface would be a more powerful
> way to approach this space, so we don't have to pay for what we don't
> use.

It is very difficult (I suspect impossible) to come up with a satisfactory global
picture without this up-pointer. Consider just the following scenario:

I have a multi_index_container<hashed,random_access> m and an
iterator to the hashed index it. m.erase(it) cannot be implemented
without the up-pointer in the random-access index. (If you don't
immediately realize why, picture yourself the hand-rolled composition
of a hashed_map and a deque<pointer>: you can't erase an element
from the combined structure given only a hash_map::iterator).

There are lots of additional problems, but I think this is sufficiently
serious to justify my decision. Basically, Boost.MultiIndex assumes
O(1) inter-index iterator projection (getting from an iterator in
an index to an iterator in another index pointing to the same element,
in constant time).

[...]
> > The deque-based structure you propose would save, as you
> > say, roughly one pointer per node with respect to sequenced
> > indices and also with respect to random access indices,
> > which have the up-pointer your proposed data structure lacks,
> > while on the other hand it requires an extra pointer as the deque
> > stores pointers while multi_index_containers enjoy the header
> > stacking property referred to above.
> >
> > So, roughly speaking, things are even.
>
> Sorry, I don't see it.  Since I need O(1) pop-front I am using
> sequenced<> which IIUC is a doubly-linked list.  Therefore your nodes
> have this overhead:
>
>   next-in-list, prev-in-list, and next-in-hash-bucket = 3 pointers
>
> and mine have only next-in-hash-bucket.  Add one pointer of overhead in
> the deque and I am storing 2 pointers.

But your deque is a deque of *pointers*, so the (amortized) penalty
of the deque is 2 pointers per element. Please take a look at the attached
figure, where the resulting data structures are depicted for:

  * Boost.MultiIndex (hashed + sequenced),
  * Boost.MultiIndex (hashed + random access),
  * Hand-rolled composition (hash_map + deque).

(The array labeled "deque<pointer>" does not do merit to the actual
chunk-based structure used by most deque implementations, but you get
the idea, there's on average one pointer per element). Do you see you've
got four pointers (black dots) per element in the three structures?

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo