Re: [boost] [ boost ] [ Trie ]

Subject: Re: [boost] [ boost ] [ Trie ]
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2015-03-12 14:42:14

El 12/03/2015 a las 18:12, Cosmin Boaca escribió:
> Hello,
>
> Iteration works faster indeed but all the other operations perform worse.
> It is also true that the current implementation is not tuned for memory
> locality. It's basically the same implementation used by the map having
> changed only the container. However the difference in performance are quite
> big.
> Also, I have performed some benchmarking myself on std::set vs intrusive
> set using variables that are declared in contigous memory zones and
> intrusive_set is performing better when compiled with -O2, -O3 but it
> performs worse when compiled without any optimization flag. Also, for a
> small number of elements (that is the case in our trie too) std::set
> performs better any time.
> I have tested insert / find / erase operations. (Those are the most common
> operations involved in std::trie to).

We can't compare without optimizations. It disables inlining and that 
changes the whole thing as Intrusive has many policy layers. In any 
case, if Intrusive performs worse with optimizations, then there is a 
problem in Boost.Intrusive we need to solve.

Maybe we need to see what's happening with few elements (and define what 
is "a few"). Also, as mentioned before use

set_base_hook <optimize_size<true>, link_mode<normal_link> > as hook

and

set<node_type, constant_time_size<false> > as children_type.

Best,

Ion