Re: [boost] [Intrusive]

Subject: Re: [boost] [Intrusive]
From: degski (degski_at_[hidden])
Date: 2017-08-27 04:24:49

Just posting my own experience with intrusive slists.

I've (re-)implemented a Rooted Directed Graph (Adjacency-lists, in- and
out-arcs, using the same arcs in both in and out slists). Underlying memory
is provided by 2 memory pools (nodes-, arcs-value-types), the nodes and
arcs are themselves intrusive as well, as the data is carried directly in
the nodes and arcs. Eventually, I'll also need a map, to cater for
Transpositions, which will also be intrusive, just need to add that to the
nodes.

Once I got my head around how to use Boost.Intrusive, its use simplified
the design (so less error-prone) a lot.

The previous implementation was, what is best described as a flat-graph,
linked lists over vector(s), using indexes for linking up the various
components.

Depending on the fan-out, the new implementation is 40% (low fan-out) to
10% (high fan-out) faster than the old one. In testing, I've made sure no
re-allocation of the vectors (in the flat-graph) is ever done, while the
memory pools allocate sufficiently large chuncks not to make any difference
as well. In my use case fan-out will (normally) decrease as the RDG gets
deeper, this is not reflected in the testing, so the speed-up is
under-estimated.

So, all-in-all, I'm very happy with Boost.Intrusive (no need for
multi-indexing, or duplication of data) and it also gives good performance.
In the old design, iterators had to be implemented (to deal with the
internal logic of the graph). In the new design, I just forward the
standard ones provided by the linked intrusive lists, how easy is that.

degski
-- 
"*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend,
Schmerzen aus Schwäche stillend.*" - Novalis 1798