Re: Boost Digest, Vol 6764, Issue 1

From: Benedict Bede McNamara (benedict_at_[hidden])
Date: 2022-07-29 13:10:26

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_at_[hidden]
Sent: Friday, 29 July 2022 10:00 PM
To: boost_at_[hidden]
Subject: Boost Digest, Vol 6764, Issue 1

Send Boost mailing list submissions to
        boost_at_[hidden]

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_at_[hidden]

You can reach the person managing the list at
        boost-owner_at_[hidden]

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_at_[hidden]>
To: <boost_at_[hidden]>
Subject: Re: [boost] Questions about incorporating my library into a
        new	library within Boost
Message-ID: <1659013070554_at_[hidden]>
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_at_[hidden]>
To: boost_at_[hidden]
Subject: Re: [boost] Questions about incorporating my library into a
        new library within Boost
Message-ID:
        <CAPPJyCuKa8mRMzhKhwaVWXbyuECQDVjXCs_m8kcM_EtDz8dZvg_at_[hidden]>
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_at_[hidden]>
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 &amp; other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

------------------------------

End of Boost Digest, Vol 6764, Issue 1
**************************************