Re: [boost] [ boost ] [ Trie ]

Subject: Re: [boost] [ boost ] [ Trie ]
From: Antony Polukhin (antoshkka_at_[hidden])
Date: 2015-03-12 15:15:14

2015-03-12 20:12 GMT+03:00 Cosmin Boaca <boost.cosmin.boaca_at_[hidden]>:

> 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).
>

O2 and O3 are the main cases. Good performance on O1 and O0 is not
essential.

I've took a look into std::map implementation in GCC 4.8. Helper data in
node of a map consumes same or bigger amount of memory, as
intrusive::set_base_hook. std::map holds first node by value (it removes
memory allocation for maps with size 1, which is a common case in our
performance tests), that's why we did not get the x2 speedup when moved
from std::map to intrusive.

Let's apply Ion's recommendations:

set_base_hook <optimize_size<true>, link_mode<normal_link> > as hook
set<node_type, constant_time_size<false> > as children_type.

and measure the speed at O2.

-- 
Best regards,
Antony Polukhin