Re: [boost] [heap] A performance test and some questions

Subject: Re: [boost] [heap] A performance test and some questions
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-07 04:15:49

> The other difference is that he stores the returned "handle_type" in a Map,
> while I store it in a separate bulk (which I called m_tBackpointer) of the
> same size as the (arrival time) bulk. (A similar bulk is implicitly also
> present when using TStaticHeap, but it is a part of the heap itself.) So
> Andrew Sutton's approach to use the mutable interface is not too different
> from mine, but will probably lead to even worse performance (because a
> "map" lookup seems to be worse than a "bulk" lookup).

from what i see (taking andrew's example), the problem is the following:

struct Vertex {
  Key k;
  Queue<Vertex*>::handle_type handle;
};

Queue<Vertex*> q;

Vertex v;
v.handle = q.push(&v); 
v.key = new_key; 
q.update(v.handle); 

... this is actually the use case, where intrusive mutable heaps would be very 
handy ...

> On the one hand, your proposed mutable interface seems to be quite
> "natural" for node based heaps. On the other hand, it looks like there is
> one more indirection than for a "straightforward" implementation of a
> "mutable" binary heap, where the heap "knows" the maximum number of
> different items that it has to manage.

true ... but this is mainly the point, where the bgl heaps use a propery map ...

cheers, tim