2015-03-12 20:12 GMT+03:00 Cosmin Boaca <boost.cosmin.boaca@gmail.com>:
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