You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@trafficserver.apache.org by Phil Sorber <so...@apache.org> on 2014/01/30 19:24:43 UTC
C++ B-tree
https://code.google.com/p/cpp-btree/
I have been thinking about adding this to libts. It's licensed AL2 already.
It currently requires C++11 but there is also a patch to remove that
dependency that is AL2 licensed as well.
I personally need this because it implements an ordered set where all our
hash table implementations are obviously unordered. Since std::map is off
the table, this seems like a good replacement. They even bench it against
std::map for comparison.
Thoughts?
Re: C++ B-tree
Posted by Phil Sorber <so...@apache.org>.
On Thu, Jan 30, 2014 at 11:43 AM, Phil Sorber <so...@apache.org> wrote:
> On Thu, Jan 30, 2014 at 11:39 AM, Alan M. Carroll <
> amc@network-geographics.com> wrote:
>
>> Thursday, January 30, 2014, 12:24:43 PM, you wrote:
>>
>> > https://code.google.com/p/cpp-btree/
>>
>> > I personally need this because it implements an ordered set where all
>> our
>> > hash table implementations are obviously unordered.
>>
>> Have you looked at the red/black tree implementation in lib/ts/IpMap.h?
>>
>
> No, I was not aware of that. I will check it out.
>
> Does this mean you are against including the btree implementation then?
>
>
>
I just took a look. It seems to me like we would need to abstract that out
as it's built into the IpMap class.
Re: C++ B-tree
Posted by "Alan M. Carroll" <am...@network-geographics.com>.
I'm not sure. The IpMap implementation is a simplified version of code I used elsewhere. The original version used a customized RB-tree implementation because it needed callbacks when the tree structure was modified (and it need to be threaded as well). I left that in because it was easier than taking it out but I don't know if IpMap really needs that for ATS. We should try to minimize the number of independent implementations but we might do that by converting IpMap to use the Google B-tree. You could take IpMap as an example of what we would need out of an ordered set.
Thursday, January 30, 2014, 12:43:22 PM, you wrote:
> On Thu, Jan 30, 2014 at 11:39 AM, Alan M. Carroll <
> amc@network-geographics.com> wrote:
>> Thursday, January 30, 2014, 12:24:43 PM, you wrote
>> > https://code.google.com/p/cpp-btree/
>> > I personally need this because it implements an ordered set where all our
>> > hash table implementations are obviously unordered.
>> Have you looked at the red/black tree implementation in lib/ts/IpMap.h?
> No, I was not aware of that. I will check it out.
> Does this mean you are against including the btree implementation then?
Re: C++ B-tree
Posted by Phil Sorber <so...@apache.org>.
On Thu, Jan 30, 2014 at 11:39 AM, Alan M. Carroll <
amc@network-geographics.com> wrote:
> Thursday, January 30, 2014, 12:24:43 PM, you wrote:
>
> > https://code.google.com/p/cpp-btree/
>
> > I personally need this because it implements an ordered set where all our
> > hash table implementations are obviously unordered.
>
> Have you looked at the red/black tree implementation in lib/ts/IpMap.h?
>
No, I was not aware of that. I will check it out.
Does this mean you are against including the btree implementation then?
Re: C++ B-tree
Posted by "Alan M. Carroll" <am...@network-geographics.com>.
Thursday, January 30, 2014, 12:24:43 PM, you wrote:
> https://code.google.com/p/cpp-btree/
> I personally need this because it implements an ordered set where all our
> hash table implementations are obviously unordered.
Have you looked at the red/black tree implementation in lib/ts/IpMap.h?
Re: C++ B-tree
Posted by Phil Sorber <so...@apache.org>.
On Thu, Jan 30, 2014 at 12:03 PM, Leif Hedstrom <zw...@apache.org> wrote:
>
> On Jan 30, 2014, at 11:41 AM, Phil Sorber <so...@apache.org> wrote:
> >
> >> On Thu, Jan 30, 2014 at 11:37 AM, Igor Galić <i....@brainsware.org>
> wrote:
> >>
> >>
> >>
> >> ----- Original Message -----
> >>> https://code.google.com/p/cpp-btree/
> >>>
> >>> I have been thinking about adding this to libts. It's licensed AL2
> >> already.
> >>
> >> You mean to literally drop it in there, or require it as dependencies
> for
> >> people to build externally?
> >
> > Literally drop it in. It's not a library you can build. It's designed to
> > become part of your code base.
>
>
>
> STL is generally ok, as long as it's not on the critical path, or bloats
> things unnecessarily . Any new or external library used on the CP should be
> carefully investigated for heap based memory allocations and lock
> contentions .
>
>From previous conversations I got the impression that STL was not OK. Even
out of the critical path, it set a precedent that one could use std::map
and friends. I'm willing to put forth the patch I have as is for comment
(as soon as legal agrees). I'm not using memory allocating things in the
critical path, but my concern is that someone might by using the class I
created elsewhere.
Also, I agree 100% that we need to make sure that any solution we have is
performant. Especially with regard to memory and lock contention. That's
why I wanted to have this convo here instead of just committing the code.
Here is some performance info from the wiki on cpp-btree:
https://code.google.com/p/cpp-btree/wiki/UsageInstructions#Memory_usage_comparison
https://code.google.com/p/cpp-btree/wiki/UsageInstructions#Performance_comparison
Perhaps we can create a STL/stdlib compliant Allocator that pulls from a
global memory pool like a global Arena? And possibly a per thread pool for
special use cases. Kind of like tcmalloc/jemalloc.
>
> I'd also make sure we avoid code / functionality duplication. If we bring
> in something new that's a superset of existing code, we should eliminate
> the old code. We've messed this up in the past, hence we still suffer with
> the TCL hash for no good reason.
>
Also agree that we don't want to duplicate functionality. I don't think we
have anything currently that covers this functionality. And while it is
true that this could cover instances of hashes, I think the two data
structures are fundamentally different and we don't want to necessarily
change all hashes to btrees. As far as IpMap goes, it does have a data
structure that is congruent, but as it's built into that class, it's not
really usable in it's current form. We could make IpMap more generic and
use a separate container class for it's internal data store, wether it be a
generic RB tree implementation that we derive from IpMap as well, or
something like this btree implementation.
>
> Cheers,
>
> -- Leif
> >
> >
> >>
> >>> It currently requires C++11 but there is also a patch to remove that
> >>> dependency that is AL2 licensed as well.
> >>>
> >>> I personally need this because it implements an ordered set where all
> our
> >>> hash table implementations are obviously unordered. Since std::map is
> off
> >>> the table, this seems like a good replacement. They even bench it
> against
> >>> std::map for comparison.
> >>
> >> Are you considering to replace the current uses of std::map too?
> >
> > Sure, if we have others. I have one use in a patch I am working on, but
> as
> > we have rejected the use of std::map outright, I plan to replace it
> before
> > I commit it.
> >
> >
> >>
> >>> Thoughts?
> >>
> >> --
> >> Igor Galić
> >>
> >> Tel: +43 (0) 664 886 22 883
> >> Mail: i.galic@brainsware.org
> >> URL: http://brainsware.org/
> >> GPG: 8716 7A9F 989B ABD5 100F 4008 F266 55D6 2998 1641
> >>
> >>
>
Re: C++ B-tree
Posted by Leif Hedstrom <zw...@apache.org>.
On Jan 30, 2014, at 11:41 AM, Phil Sorber <so...@apache.org> wrote:
>
>> On Thu, Jan 30, 2014 at 11:37 AM, Igor Galić <i....@brainsware.org> wrote:
>>
>>
>>
>> ----- Original Message -----
>>> https://code.google.com/p/cpp-btree/
>>>
>>> I have been thinking about adding this to libts. It's licensed AL2
>> already.
>>
>> You mean to literally drop it in there, or require it as dependencies for
>> people to build externally?
>
> Literally drop it in. It's not a library you can build. It's designed to
> become part of your code base.
STL is generally ok, as long as it's not on the critical path, or bloats things unnecessarily . Any new or external library used on the CP should be carefully investigated for heap based memory allocations and lock contentions .
I'd also make sure we avoid code / functionality duplication. If we bring in something new that's a superset of existing code, we should eliminate the old code. We've messed this up in the past, hence we still suffer with the TCL hash for no good reason.
Cheers,
-- Leif
>
>
>>
>>> It currently requires C++11 but there is also a patch to remove that
>>> dependency that is AL2 licensed as well.
>>>
>>> I personally need this because it implements an ordered set where all our
>>> hash table implementations are obviously unordered. Since std::map is off
>>> the table, this seems like a good replacement. They even bench it against
>>> std::map for comparison.
>>
>> Are you considering to replace the current uses of std::map too?
>
> Sure, if we have others. I have one use in a patch I am working on, but as
> we have rejected the use of std::map outright, I plan to replace it before
> I commit it.
>
>
>>
>>> Thoughts?
>>
>> --
>> Igor Galić
>>
>> Tel: +43 (0) 664 886 22 883
>> Mail: i.galic@brainsware.org
>> URL: http://brainsware.org/
>> GPG: 8716 7A9F 989B ABD5 100F 4008 F266 55D6 2998 1641
>>
>>
Re: C++ B-tree
Posted by Phil Sorber <so...@apache.org>.
On Thu, Jan 30, 2014 at 11:37 AM, Igor Galić <i....@brainsware.org> wrote:
>
>
> ----- Original Message -----
> > https://code.google.com/p/cpp-btree/
> >
> > I have been thinking about adding this to libts. It's licensed AL2
> already.
>
> You mean to literally drop it in there, or require it as dependencies for
> people to build externally?
>
Literally drop it in. It's not a library you can build. It's designed to
become part of your code base.
>
> > It currently requires C++11 but there is also a patch to remove that
> > dependency that is AL2 licensed as well.
> >
> > I personally need this because it implements an ordered set where all our
> > hash table implementations are obviously unordered. Since std::map is off
> > the table, this seems like a good replacement. They even bench it against
> > std::map for comparison.
>
> Are you considering to replace the current uses of std::map too?
>
Sure, if we have others. I have one use in a patch I am working on, but as
we have rejected the use of std::map outright, I plan to replace it before
I commit it.
>
> > Thoughts?
> >
>
> --
> Igor Galić
>
> Tel: +43 (0) 664 886 22 883
> Mail: i.galic@brainsware.org
> URL: http://brainsware.org/
> GPG: 8716 7A9F 989B ABD5 100F 4008 F266 55D6 2998 1641
>
>
Re: C++ B-tree
Posted by Phil Sorber <ph...@sorber.net>.
On Thu, Jan 30, 2014 at 11:37 AM, Igor Galić <i....@brainsware.org> wrote:
>
>
> ----- Original Message -----
> > https://code.google.com/p/cpp-btree/
> >
> > I have been thinking about adding this to libts. It's licensed AL2
> already.
>
> You mean to literally drop it in there, or require it as dependencies for
> people to build externally?
>
Literally drop it in. It's not a library you can build. It's designed to
become part of your code base.
>
> > It currently requires C++11 but there is also a patch to remove that
> > dependency that is AL2 licensed as well.
> >
> > I personally need this because it implements an ordered set where all our
> > hash table implementations are obviously unordered. Since std::map is off
> > the table, this seems like a good replacement. They even bench it against
> > std::map for comparison.
>
> Are you considering to replace the current uses of std::map too?
>
Sure, if we have others. I have one use in a patch I am working on, but as
we have rejected the use of std::map outright, I plan to replace it before
I commit it.
>
> > Thoughts?
> >
>
> --
> Igor Galić
>
> Tel: +43 (0) 664 886 22 883
> Mail: i.galic@brainsware.org
> URL: http://brainsware.org/
> GPG: 8716 7A9F 989B ABD5 100F 4008 F266 55D6 2998 1641
>
>
Re: C++ B-tree
Posted by Igor Galić <i....@brainsware.org>.
----- Original Message -----
> https://code.google.com/p/cpp-btree/
>
> I have been thinking about adding this to libts. It's licensed AL2 already.
You mean to literally drop it in there, or require it as dependencies for
people to build externally?
> It currently requires C++11 but there is also a patch to remove that
> dependency that is AL2 licensed as well.
>
> I personally need this because it implements an ordered set where all our
> hash table implementations are obviously unordered. Since std::map is off
> the table, this seems like a good replacement. They even bench it against
> std::map for comparison.
Are you considering to replace the current uses of std::map too?
> Thoughts?
>
--
Igor Galić
Tel: +43 (0) 664 886 22 883
Mail: i.galic@brainsware.org
URL: http://brainsware.org/
GPG: 8716 7A9F 989B ABD5 100F 4008 F266 55D6 2998 1641
Re: C++ B-tree
Posted by Phil Sorber <so...@apache.org>.
On Thu, Jan 30, 2014 at 12:30 PM, Jim Jagielski <ji...@jagunet.com> wrote:
> Anything is stdcxx.apache.org usable?
>
I looked at this a little bit, and correct me if I am wrong, but this is
meant as a drop in replacement for the stdcxx that comes with an
OS/Compiler?
Also, it looks like it also uses red/black trees as well.
>
> On Jan 30, 2014, at 1:24 PM, Phil Sorber <so...@apache.org> wrote:
>
> > https://code.google.com/p/cpp-btree/
> >
> > I have been thinking about adding this to libts. It's licensed AL2
> already.
> > It currently requires C++11 but there is also a patch to remove that
> > dependency that is AL2 licensed as well.
> >
> > I personally need this because it implements an ordered set where all our
> > hash table implementations are obviously unordered. Since std::map is off
> > the table, this seems like a good replacement. They even bench it against
> > std::map for comparison.
> >
> > Thoughts?
>
>
Re: C++ B-tree
Posted by Jim Jagielski <ji...@jaguNET.com>.
Anything is stdcxx.apache.org usable?
On Jan 30, 2014, at 1:24 PM, Phil Sorber <so...@apache.org> wrote:
> https://code.google.com/p/cpp-btree/
>
> I have been thinking about adding this to libts. It's licensed AL2 already.
> It currently requires C++11 but there is also a patch to remove that
> dependency that is AL2 licensed as well.
>
> I personally need this because it implements an ordered set where all our
> hash table implementations are obviously unordered. Since std::map is off
> the table, this seems like a good replacement. They even bench it against
> std::map for comparison.
>
> Thoughts?