Re: [boost] Boost Digest, Vol 6764, Issue 1
I++ Binary Serialization I++ binary serialization just got twice as fast by using linked lists rather than binary trees as before. Sent from Mail for Windows From: boost-request@lists.boost.org Sent: Friday, 29 July 2022 10:00 PM To: boost@lists.boost.org Subject: Boost Digest, Vol 6764, Issue 1 Send Boost mailing list submissions to boost@lists.boost.org To subscribe or unsubscribe via the World Wide Web, visit https://lists.boost.org/mailman/listinfo.cgi/boost or, via email, send a message with subject or body 'help' to boost-request@lists.boost.org You can reach the person managing the list at boost-owner@lists.boost.org When replying, please edit your Subject line so it is more specific than "Re: Contents of Boost digest..." The boost archives may be found at: http://lists.boost.org/Archives/boost/ Today's Topics: 1. Re: Questions about incorporating my library into a new library within Boost (Phil Endecott) 2. Re: Questions about incorporating my library into a new library within Boost (Jooseong Lee) ---------------------------------------------------------------------- Message: 1 Date: Thu, 28 Jul 2022 13:57:50 +0100 From: "Phil Endecott" <spam_from_boost_dev@chezphil.org> To: <boost@lists.boost.org> Subject: Re: [boost] Questions about incorporating my library into a new library within Boost Message-ID: <1659013070554@dmwebmail.dmwebmail.chezphil.org> Content-Type: text/plain; format="flowed"; charset="UTF-8" Jooseong Lee wrote:
What is not stored contiguously is child, this is stored in std::vector<std::unique_ptr>. But when N keys are erased, the number of children erased is not O(N), because a node can have #(fanout) keys.
I have to correct this sentence, the number of children erased is O(N). But the coefficient is small, because practically B-Trees use large fanouts.
Most technically, a call for erase_range(a, b) would be O(log N) + O(K) where N is the number of whole keys and K is the number of keys being erased. I've updated the repo description, thanks for the catch.
Good, I'm glad I don't have to give the CS101 complexity lecture :-) One other comment - how do you deal with strings? To get the locality benefits of the B-Tree you can't store variable-size data totally out-of-band. Regarding the general "how do I get this in Boost?" question, I encourage you to look back through the mailing list archive at the last few "Is Boost interested in my XYZ libary?" threads. Some people post useful replies about what to do next which. Cynically, what happens most often is that there are one or two emails and then the library author and any replies disappear. Some persistence is required to make anything happen. One hint: put something more descriptive (i.e. "B-Tree") in your subject line! Regards, Phil. ------------------------------ Message: 2 Date: Thu, 28 Jul 2022 22:18:33 +0900 From: Jooseong Lee <frozenca91@gmail.com> To: boost@lists.boost.org Subject: Re: [boost] Questions about incorporating my library into a new library within Boost Message-ID: <CAPPJyCuKa8mRMzhKhwaVWXbyuECQDVjXCs_m8kcM_EtDz8dZvg@mail.gmail.com> Content-Type: text/plain; charset="UTF-8"
One other comment - how do you deal with strings? To get the locality benefits of the B-Tree you can't store variable-size data totally out-of-band.
For std::string and its friends (i.e. not trivially copyable types) it is stored as something like std::vector<std::string>, so it is not *that* good (but still better than std::set<std::string>). Google Abseil's B-Tree implementation use similar approach. When I personally use my B-Tree for strings, I use raw char arrays like std::array<char, 16>
Regarding the general "how do I get this in Boost?" question, I encourage you to look back through the mailing list archive at the last few "Is Boost interested in my XYZ libary?" threads.
Thanks, I'll have a look. Best, Jooseong On Thu, Jul 28, 2022, 9:58 PM Phil Endecott via Boost <boost@lists.boost.org> wrote:
Jooseong Lee wrote:
What is not stored contiguously is child, this is stored in std::vector<std::unique_ptr>. But when N keys are erased, the number of children erased is not O(N), because a node can have #(fanout) keys.
I have to correct this sentence, the number of children erased is O(N). But the coefficient is small, because practically B-Trees use large fanouts.
Most technically, a call for erase_range(a, b) would be O(log N) + O(K) where N is the number of whole keys and K is the number of keys being erased. I've updated the repo description, thanks for the catch.
Good, I'm glad I don't have to give the CS101 complexity lecture :-)
One other comment - how do you deal with strings? To get the locality benefits of the B-Tree you can't store variable-size data totally out-of-band.
Regarding the general "how do I get this in Boost?" question, I encourage you to look back through the mailing list archive at the last few "Is Boost interested in my XYZ libary?" threads. Some people post useful replies about what to do next which. Cynically, what happens most often is that there are one or two emails and then the library author and any replies disappear. Some persistence is required to make anything happen. One hint: put something more descriptive (i.e. "B-Tree") in your subject line!
Regards, Phil.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
------------------------------ Subject: Digest Footer _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost ------------------------------ End of Boost Digest, Vol 6764, Issue 1 **************************************
participants (1)
-
Benedict Bede McNamara