Re: [boost] [ boost ] [ Trie ]

Subject: Re: [boost] [ boost ] [ Trie ]
From: Antony Polukhin (antoshkka_at_[hidden])
Date: 2015-03-11 15:30:42

2015-03-11 15:14 GMT+03:00 Cosmin Boaca <boost.cosmin.boaca_at_[hidden]>:

> Hello,
>
> I have replaced std::map with intrusive set and I have run the benchmarks.
> The peformance dropped versus the std::map implementation quite a lot. For
> instance, inserting time is about 1.5x worse. I have pushed the changes
> into a branch of the project [0].
>

No need to worry. We've just started with that intrusive things. Let's try
to tune our implementation:
* we do not need constant time size(), so let's provide
`optimize_size<true>` option for sets
* turn link mode into `link_mode<normal_link>` for sets at least when
measuring performance (turn back to safe_mode for debug purposes after
measure)
* the sweetest thing: trie_node does not need `pred_node` and `next_node`
pointers any more. Just use `--children_type::s_iterator_to(*this)` and
`++children_type::s_iterator_to(*this)`

> I think one potential improvement would be to use node refferences instead
> of node_pointers wherever possible in the whole trie implementation
>

This will give you nothing. On Assembler level there's no difference
between reference and pointer.

-- 
Best regards,
Antony Polukhin