Re: [boost] [Intrusive]

Subject: Re: [boost] [Intrusive]
From: degski (degski_at_[hidden])
Date: 2017-08-28 05:16:27

On 28 August 2017 at 01:15, Soul Studios via Boost <boost_at_[hidden]>
wrote:

> By contrast a vector of pointers/indexes will be faster to iterate due to
> the CPU being able to cache the jump locations/offsets, whereas it can't
> with a linked list of any type. That's what my graphs show.

So, I implemented that. The design now as simple as it gets. A
RootedDiGraph with Adjacency vectors (and pointers obtained from the
memory-pool to nodes and arcs). Instead of std::vector, I use the
pt::pector from https://github.com/aguinet/pector, which has (can have) a
smaller footprint, allows for std::uint32_t's as indices and has a
growth-policy option (possibly with the use of realloc).

Results:

fan-out 32:

 RootedDiGraphAdjIntrLists: 1810 milliseconds.
 RootedDiGraphAdjVectors: 1302 milliseconds.
 RootedDiGraphFlat: 2486 milliseconds.

fan-out 512:

 RootedDiGraphAdjIntrLists: 28841 milliseconds.
 RootedDiGraphAdjVectors: 14698 milliseconds.
 RootedDiGraphFlat: 33168 milliseconds.

That's a significant improvement.

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