Boost logo

Boost :

From: Jooseong Lee (frozenca91_at_[hidden])
Date: 2022-08-11 08:33:33


> 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 <boost_at_[hidden]>님이
작성:

> 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_at_[hidden])
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk