I recently wrote a general-purpose STL-like ordered associative B-Tree based container in C++. Its API and usage is very similar to std::set, std::map, std::multiset, std::multimap, and when the number of elements is relatively large, my benchmark shows that it is 2.5~3 times faster than std::set and its friends. Repo link: https://github.com/frozenca/BTree This was better than I thought, so I'd like to contribute to the Boost community by incorporating it within the list of Boost libraries. I'd like to know if it's possible or if you think it's worth it.
Best Regards, Jooseong Lee
Hello, can I ask if Boost is interested in my library and if I can request
a review?
For performance, I saw the following results:
Inserting/retrieving/erasing 1,000,000 random std::int64_t in random order
in gcc 11.2 -O3, averaged 20~200 times:
(https://github.com/frozenca/BTree#performance)
frozenca::BTreeSet : insert 172ms, lookup 199ms, erase 208ms
Google btree::btree_set : insert 248ms, lookup 229ms, erase 243ms
std::set : insert 912ms, lookup 943ms, erase 1002ms
boost::container::flat_set : insert 58527ms, lookup 208ms, erase 59134ms
boost::unordered_set : insert 194ms, lookup 226ms, erase 272ms
If you're interested, I'd appreciate it if you could take a look.
Jooseong
2022년 7월 30일 (토) 오후 2:00, Rainer Deyke via Boost
On 30.07.22 06:38, Jooseong Lee via Boost wrote:
Dear Rainer,
Compared with boost::unordered_map and boost::container::flat_set, I repeated inserting/retrieving/erasing 1,000,000 random std::int64_t in random order, and see the following results in my machine: (gcc 11.2 -O3) (repeated 200 times for each target for B-Tree and unordered_set, repeated 10 times for flat_set)
My B-Tree: insert 196.22 ms, lookup 205.64 ms, erase 233.24 ms boost::container::flat_set : insert 58402.9 ms, lookup 217.73 ms, erase 59075.2 ms boost::unordered_set : insert 189.45 ms, lookup 232.19 ms, erase 268.01 ms
OK, I'm convinced. Your container seems to have competitive lookup times, slightly better even, without the drawbacks of flat_set and unordered_set (i.e. pathological insert/erase times for flat_set, undefined iteration order and the need to provide a hash function for unordered_set).
-- Rainer Deyke (rainerd@eldwood.com)
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost