Re: C++ B-tree
- 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.ga...@brainsware.org URL: http://brainsware.org/ GPG: 8716 7A9F 989B ABD5 100F 4008 F266 55D6 2998 1641
Re: C++ B-tree
On Thu, Jan 30, 2014 at 11:37 AM, Igor Galić i.ga...@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.ga...@brainsware.org URL: http://brainsware.org/ GPG: 8716 7A9F 989B ABD5 100F 4008 F266 55D6 2998 1641
Re: C++ B-tree
On Thu, Jan 30, 2014 at 11:37 AM, Igor Galić i.ga...@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.ga...@brainsware.org URL: http://brainsware.org/ GPG: 8716 7A9F 989B ABD5 100F 4008 F266 55D6 2998 1641
Re: C++ B-tree
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
On Thu, Jan 30, 2014 at 11:39 AM, Alan M. Carroll a...@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
On Thu, Jan 30, 2014 at 11:43 AM, Phil Sorber sor...@apache.org wrote: On Thu, Jan 30, 2014 at 11:39 AM, Alan M. Carroll a...@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
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 a...@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
On Jan 30, 2014, at 11:41 AM, Phil Sorber sor...@apache.org wrote: On Thu, Jan 30, 2014 at 11:37 AM, Igor Galić i.ga...@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.ga...@brainsware.org URL: http://brainsware.org/ GPG: 8716 7A9F 989B ABD5 100F 4008 F266 55D6 2998 1641
Re: C++ B-tree
Anything is stdcxx.apache.org usable? On Jan 30, 2014, at 1:24 PM, Phil Sorber sor...@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
On Thu, Jan 30, 2014 at 12:30 PM, Jim Jagielski j...@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 sor...@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
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 sor...@apache.org wrote: On Thu, Jan 30, 2014 at 11:37 AM, Igor Galić i.ga...@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.ga...@brainsware.org URL: http://brainsware.org/ GPG: 8716 7A9F 989B ABD5 100F 4008 F266 55D6 2998 1641
