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"
What is not stored contiguously is child, this is stored in std::vectorstd::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
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::vectorstd::string, so it is not *that* good
(but still better than std::setstd::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
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
Jooseong Lee wrote:
What is not stored contiguously is child, this is stored in std::vectorstd::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 **************************************