2015-03-12 20:12 GMT+03:00 Cosmin Boaca
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