Greetings, I've recently implemented a new collection type for a project of mine. It works identically to std::map, with the same algorithmic guarantees, but additionally can be 'copied' in constant time. That is: shared_map<int, int> a; for(i = 0; i < 100; i++) a[i] = i*i; // Each insert in log(n) of the map size shared_map<int, int> b = a; // This is constant time (not linear as in a std::map) b[1] = 7; // Still log(n) of course b[2] = 3; assert(a[2] == 4 && b[2] == 3 && a[6] == 36 && b[6] == 36); The trick is simple: the map is a red-black tree, but we get rid of the explicit parent pointer for each red-black node. This complicates the code, but is algorithmically uninteresting since we always descend from the root anyway and just need to track the parent as we go, either in an explicit stack or through recursion (my current implementation). The key point however is that the lack of an explicit parent allows us to use reference counting, and share children. Thus the copy from a to b simply copies the root node, and adds an additional reference count. All future changes do copy on write for shared nodes (any with a ref count of 2 or more). The does lower the overall performance for all operations somewhat, but for cases like mine where there is a need to copy large maps a lot, and each map remains quite similar to the other maps, there is a huge savings in computation and memory usage. Another nice use is: copy a map (since it's free) and iterate over it while modifying the original with no worries. One caveat, obviously multiple threads require a single global lock since even apparently different collections share internal state (or I could add a per node lock, which has the nice effect of general fine grained tree locking, but is tons of overhead, perhaps a compile time choice?). My current implementation is sufficient for my purposes, but with a little cleanup (making stronger iterator validity guarantees, better support for erasing ranges, explicit parent stack instead of recursion perhaps), it could be perhaps useful to everyone. Also, it's a little work but straightforward to generalize to shared_set, shared_multimap, etc. I was wondering if there would be any interest from people in such a library? If so, I would be willing to do the needed cleanup, if not, it suits me reasonably well as is (I don't even use erase). Also curious if anyone has seen such a thing anywhere before. It seems obvious enough to me, but perhaps it's actually new, I couldn't find anything like it when I went searching. Thanks for your time -Jeremy
"Jeremy Bruestle" <jeremy.bruestle@gmail.com> writes:
I've recently implemented a new collection type for a project of mine. It works identically to std::map, with the same algorithmic guarantees, but additionally can be 'copied' in constant time. That is:
shared_map<int, int> a; for(i = 0; i < 100; i++) a[i] = i*i; // Each insert in log(n) of the map size shared_map<int, int> b = a; // This is constant time (not linear as in a std::map) b[1] = 7; // Still log(n) of course b[2] = 3;
assert(a[2] == 4 && b[2] == 3 && a[6] == 36 && b[6] == 36);
The trick is simple: the map is a red-black tree, but we get rid of the explicit parent pointer for each red-black node. This complicates the code, but is algorithmically uninteresting since we always descend from the root anyway and just need to track the parent as we go, either in an explicit stack or through recursion (my current implementation). The key point however is that the lack of an explicit parent allows us to use reference counting, and share children. Thus the copy from a to b simply copies the root node, and adds an additional reference count. All future changes do copy on write for shared nodes (any with a ref count of 2 or more).
How does this work with iterators? On a normal map you can get an iterator to an entry and it remains valid until that entry is deleted. Can you do this with your shared map? I'm inclined to think that any modification to the map would have to result in all iterators being invalidated, as they may now potentially refer to the wrong copy of a node. Anthony -- Anthony Williams Just Software Solutions Ltd - http://www.justsoftwaresolutions.co.uk Registered in England, Company Number 5478976. Registered Office: 15 Carrallack Mews, St Just, Cornwall, TR19 7UL
On Tue, 7 Aug 2007, Anthony Williams wrote:
"Jeremy Bruestle" <jeremy.bruestle@gmail.com> writes:
I've recently implemented a new collection type for a project of mine. It works identically to std::map, with the same algorithmic guarantees, but additionally can be 'copied' in constant time. [snip] The trick is simple: the map is a red-black tree, but we get rid of the explicit parent pointer for each red-black node. This complicates the code, but is algorithmically uninteresting since we always descend from the root anyway and just need to track the parent as we go, either in an explicit stack or through recursion (my current implementation). The key point however is that the lack of an explicit parent allows us to use reference counting, and share children. Thus the copy from a to b simply copies the root node, and adds an additional reference count. All future changes do copy on write for shared nodes (any with a ref count of 2 or more).
How does this work with iterators? On a normal map you can get an iterator to an entry and it remains valid until that entry is deleted. Can you do this with your shared map? I'm inclined to think that any modification to the map would have to result in all iterators being invalidated, as they may now potentially refer to the wrong copy of a node.
I also wonder how he implements iterators without a pointer to the parent. AFAIK, that is one way to allow stepping from one element to the next (or the previous) from any node, with no knowledge of how we accessed that node. Without a parent pointer, aside from using threaded trees (which would created cycles of shared pointers), I don't know how to do it efficiently (keeping a stack inside the iterator would make them costly to copy, and would require O(log N) memory). Another thing, could this shared_map be implemented in terms of Boost.Intrusive (IIRC, it has been accepted, though I didn't follow the review process very much)? -- François Duranleau LIGUM, Université de Montréal
On 8/7/07, François Duranleau <duranlef@iro.umontreal.ca> wrote:
On Tue, 7 Aug 2007, Anthony Williams wrote:
How does this work with iterators? On a normal map you can get an iterator to an entry and it remains valid until that entry is deleted. Can you do this with your shared map? I'm inclined to think that any modification to the map would have to result in all iterators being invalidated, as they may now potentially refer to the wrong copy of a node.
I also wonder how he implements iterators without a pointer to the parent. AFAIK, that is one way to allow stepping from one element to the next (or the previous) from any node, with no knowledge of how we accessed that node. Without a parent pointer, aside from using threaded trees (which would created cycles of shared pointers), I don't know how to do it efficiently (keeping a stack inside the iterator would make them costly to copy, and would require O(log N) memory).
First, in reference to François, you are correct that the iterators contain log(n) components, and thus copy of an iterator is log(n). In reply to Anthony, given the current implementation, you are correct, as my project only needs const_iterators. However there is a solution as follows: First note that the iterators are not a single pointer as mentioned, but a stack of pointers,since they must maintain parent data in some way. The iterator also maintainsa pointer to the collection it was generated from. The stack of pointers allows amortized constant time access to previous and next elements without starting over from root. Now to deal with modification of the underlying collection, we put a 'version number' on each red black tree node, and when we generate the iterator, place the version number alongside the pointers as we do our find(), etc. When we copy red-black node, we inc the version number on the source node (the copy starts at 0). Now our iterators check the pointer's versions as they traverse them to make sure the cached and current numbers are identical. If this check ever fails, the iterator resets itself by looking up the key in the collection anew, which is transparent to the user (although it incurs another log(n) bit of work, breaking the constant time requirement on transversal, but only for the cases where a collection is under heavy modification during transversal). This makes the shared_map have the same iterator stability guarantees as std::map. Additionally, I need to cache the 'begin' iterator, since begin should be constant time, this is also a mild pain but doable. Note the pointers cached by the iterator can't become invalid since an iterator hold reference counts. Also note: the dereference operator for non const iterators may need to do a log(n) copy down the tree if the node in question has a ref-count > 1, otherwise changes to the mapped_type would be visible to others. To avoid needless work when the user isn't going to modify the mapped_type during a dereference, we could return a proxy object with a cast and operator=, etc, but that's probably more hassle than it's worth. Another tricky question is const_iterators. The general semantics for const_iterators in std::map are that they have visibility to changes to the map, but do not allow changes to the map. I can make my const_iterators simpler (not check version number, etc), if I make them see a 'frozen' version of the collection (effectively they iterate over a copy of the collection, since copies are free). This is actually very convenient in many cases, but causes the shared_map to have slightly different semantics from std::map, and I'm not sure if it's a good design decision. On the other hand, there is a high cost to tracking changes which could be avoided for const_iteators, and isn't scanning the collection with a const_iterator while modifying it a fairly cracked thing to do anyway? I can't think of any std::algorithm for example that does any such thing. -Jeremy
Jeremy: You might be interested in this paper which basically describes (albeit from a different design point of view) your data structure: James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, Robert Endre Tarjan: Making Data Structures Persistent. J. Comput. Syst. Sci. 38 (1): 86-124 (1989) As far as the lock goes, why not a shared_ptr per node? (those use atomic ref counters) As long as you do not maintain the size of the map, that should be all good. You can maintain the size in every node, and get the size of a collection from the root. I've heard of shared DAG structures to represent hierarchical shared collections, along the same principles. They work well, if a bit slow. --Herve Bronnimann On Aug 7, 2007, at 12:59 AM, Jeremy Bruestle wrote:
Greetings,
I've recently implemented a new collection type for a project of mine. It works identically to std::map, with the same algorithmic guarantees, but additionally can be 'copied' in constant time. That is:
shared_map<int, int> a; for(i = 0; i < 100; i++) a[i] = i*i; // Each insert in log(n) of the map size shared_map<int, int> b = a; // This is constant time (not linear as in a std::map) b[1] = 7; // Still log(n) of course b[2] = 3;
assert(a[2] == 4 && b[2] == 3 && a[6] == 36 && b[6] == 36);
The trick is simple: the map is a red-black tree, but we get rid of the explicit parent pointer for each red-black node. This complicates the code, but is algorithmically uninteresting since we always descend from the root anyway and just need to track the parent as we go, either in an explicit stack or through recursion (my current implementation). The key point however is that the lack of an explicit parent allows us to use reference counting, and share children. Thus the copy from a to b simply copies the root node, and adds an additional reference count. All future changes do copy on write for shared nodes (any with a ref count of 2 or more).
The does lower the overall performance for all operations somewhat, but for cases like mine where there is a need to copy large maps a lot, and each map remains quite similar to the other maps, there is a huge savings in computation and memory usage. Another nice use is: copy a map (since it's free) and iterate over it while modifying the original with no worries.
One caveat, obviously multiple threads require a single global lock since even apparently different collections share internal state (or I could add a per node lock, which has the nice effect of general fine grained tree locking, but is tons of overhead, perhaps a compile time choice?).
My current implementation is sufficient for my purposes, but with a little cleanup (making stronger iterator validity guarantees, better support for erasing ranges, explicit parent stack instead of recursion perhaps), it could be perhaps useful to everyone. Also, it's a little work but straightforward to generalize to shared_set, shared_multimap, etc.
I was wondering if there would be any interest from people in such a library? If so, I would be willing to do the needed cleanup, if not, it suits me reasonably well as is (I don't even use erase). Also curious if anyone has seen such a thing anywhere before. It seems obvious enough to me, but perhaps it's actually new, I couldn't find anything like it when I went searching.
Thanks for your time
-Jeremy _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost
Thanks for the reference, the paper is very interesting. I'm still reading it, but it's very applicable, and I might get some good algorithmic improvements out of it. Also, for concurrency, the use of shared_ptr makes good sense in terms of code reuse. All of this discussion has gotten me thinking about the details of my structure more (for example, with the basic design as it is, no matter what I do, begin is always going to be log(n) since of course the returning of the iterator requires a copy, which is log(n)). I think I will churn on it for a while, and once I've cleaned it up come back with an explict list of the algorithmic properties to reduce any confusion (my statement about the bounds being the same as map for example is true of insert, find, and delete, but not of many of the iterator uses). If anyone has more question though, or has ideas, or just wants to express interest, please do so. At this point I think I'm going to keep working on the project even if no one is interested, because I see of lot of fun problems to attack, but I'm still curious if anyone else has use for such a structure. Thanks to all so far for the good feedback. -Jeremy On 8/7/07, Hervé Brönnimann <hervebronnimann@mac.com> wrote:
Jeremy: You might be interested in this paper which basically describes (albeit from a different design point of view) your data structure:
James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, Robert Endre Tarjan: Making Data Structures Persistent. J. Comput. Syst. Sci. 38 (1): 86-124 (1989)
As far as the lock goes, why not a shared_ptr per node? (those use atomic ref counters) As long as you do not maintain the size of the map, that should be all good. You can maintain the size in every node, and get the size of a collection from the root.
I've heard of shared DAG structures to represent hierarchical shared collections, along the same principles. They work well, if a bit slow.
--Herve Bronnimann
On Aug 7, 2007, at 12:59 AM, Jeremy Bruestle wrote:
Greetings,
I've recently implemented a new collection type for a project of mine. It works identically to std::map, with the same algorithmic guarantees, but additionally can be 'copied' in constant time. That is:
shared_map<int, int> a; for(i = 0; i < 100; i++) a[i] = i*i; // Each insert in log(n) of the map size shared_map<int, int> b = a; // This is constant time (not linear as in a std::map) b[1] = 7; // Still log(n) of course b[2] = 3;
assert(a[2] == 4 && b[2] == 3 && a[6] == 36 && b[6] == 36);
The trick is simple: the map is a red-black tree, but we get rid of the explicit parent pointer for each red-black node. This complicates the code, but is algorithmically uninteresting since we always descend from the root anyway and just need to track the parent as we go, either in an explicit stack or through recursion (my current implementation). The key point however is that the lack of an explicit parent allows us to use reference counting, and share children. Thus the copy from a to b simply copies the root node, and adds an additional reference count. All future changes do copy on write for shared nodes (any with a ref count of 2 or more).
The does lower the overall performance for all operations somewhat, but for cases like mine where there is a need to copy large maps a lot, and each map remains quite similar to the other maps, there is a huge savings in computation and memory usage. Another nice use is: copy a map (since it's free) and iterate over it while modifying the original with no worries.
One caveat, obviously multiple threads require a single global lock since even apparently different collections share internal state (or I could add a per node lock, which has the nice effect of general fine grained tree locking, but is tons of overhead, perhaps a compile time choice?).
My current implementation is sufficient for my purposes, but with a little cleanup (making stronger iterator validity guarantees, better support for erasing ranges, explicit parent stack instead of recursion perhaps), it could be perhaps useful to everyone. Also, it's a little work but straightforward to generalize to shared_set, shared_multimap, etc.
I was wondering if there would be any interest from people in such a library? If so, I would be willing to do the needed cleanup, if not, it suits me reasonably well as is (I don't even use erase). Also curious if anyone has seen such a thing anywhere before. It seems obvious enough to me, but perhaps it's actually new, I couldn't find anything like it when I went searching.
Thanks for your time
-Jeremy _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
If anyone has more question though, or has ideas, or just wants to express interest, please do so.
I hereby express an interest. In fact I'd love to see a complete set of standard-library-like copy-on-write containers, though I haven't thought through what this would require for lists and vectors. Regards, Phil.
A shared string would be *extremely* useful. Most of the projects I'm working on these days spend a non-negligible time copying strings... FWIW, HB On Aug 8, 2007, at 3:03 PM, Phil Endecott wrote:
If anyone has more question though, or has ideas, or just wants to express interest, please do so.
I hereby express an interest.
In fact I'd love to see a complete set of standard-library-like copy-on-write containers, though I haven't thought through what this would require for lists and vectors.
Regards,
Phil.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost
Hervé Brönnimann wrote:
A shared string would be *extremely* useful. Most of the projects I'm working on these days spend a non-negligible time copying strings... FWIW, HB
A special data structure was designed for that, it's called a rope. It allows various substrings to be shared by different strings. However, it is not much used because: - A lot of existing code wants efficient ways to have contiguous strings, - A lot of people consider sharing to be evil (and sometimes rightly so. I don't see the point of sharing only at the whole string level. Libraries that produce needless copies are simply ill-designed, and thus it is true great parts of the standard library are), - Sharing, if used, works way better with immutable objects.
loufoque wrote:
Hervé Brönnimann wrote:
A shared string would be *extremely* useful. Most of the projects I'm working on these days spend a non-negligible time copying strings... FWIW, HB
Libraries that produce needless copies are simply ill-designed, The obvious case is return by value. I know that there are some compiler optimizations that can help here, but we have to work with the compilers we have.
The other case is standard containers (and yes, I know I snipped your comment that the standard library is badly designed). Until we have a C++09 compiler that supports move, maps etc involve a lot of copying.
- Sharing, if used, works way better with immutable objects. Well yes. I don't know about Hervé, but I would have thought a shared string class would indeed be immutable
-- Martin Bonner Project Leader PI SHURLOK LTD Telephone: +44 1223 441434 / 203894 (direct) Fax: +44 1223 203999 Email: martin.bonner@pi-shurlok.com www.pi-shurlok.com disclaimer
Martin Bonner wrote:
loufoque wrote:
Libraries that produce needless copies are simply ill-designed, The obvious case is return by value. I know that there are some compiler optimizations that can help here, but we have to work with the compilers we have.
No exisiting decent C++ compiler doesn't perform NRVO. The only compiler I know that performs RVO and not NRVO is MSVC6, and it certainly isn't decent. NRVO is such an obvious optimization that a C++ compiler that doesn't do it is no good in my opinion. Returning by copy still implies copying (or moving) when it is not the initialization of a variable, but nothing can really be done about that unless the function is nothrow (in that case, we could destruct then re-initialize the variable, but the C++ standard doesn't allow that anyway).
The other case is standard containers (and yes, I know I snipped your comment that the standard library is badly designed). Until we have a C++09 compiler that supports move, maps etc involve a lot of copying.
Move is NOT the solution at all. Move only reduces the cost of copying in a few cases. While useful for std::vector is the case of resizing, the problem is not here. The problem is that it is not possible to construct objects in place in the container. It would be trivial to do so by generalizing use of something similar to boost in-place, but it's only used by boost optional AFAIK.
- Sharing, if used, works way better with immutable objects. Well yes. I don't know about Hervé, but I would have thought a shared string class would indeed be immutable
Actually I was more replying to "why std::string does not use sharing" here.
Mathias Gaunard wrote:
Martin Bonner wrote:
loufoque wrote:
Libraries that produce needless copies are simply ill-designed, The obvious case is return by value. I know that there are some compiler optimizations that can help here, but we have to work with the compilers we have.
No exisiting decent C++ compiler doesn't perform NRVO. The only compiler I know that performs RVO and not NRVO is MSVC6, and it certainly isn't decent.
What about MSVC 7.1? IIRC it does unnamed RVO but not NRVO (which was added in MSVC8). Overall its still a decent compiler... it does a better job than VC8 in some cases. - Michael Marcin
Hi,
Libraries that produce needless copies are simply ill-designed, and thus it is true great parts of the standard library are),
Well... Having had to recent pleasure to find code like this: bool foo::check(T *obj) const { std::string name = obj->name(); bool value = (name == "foo"); value = value || (name == "bar"); value = value || (name == "foobar"); value = value || (name == "zoinc"); value = value || (name == "barfy"); value = value || (name == "zoobie"); value = value || (name == "ayeyei"); return value; } That was one of the contributors to ~800'000 memory allocation calls per second. It was called... often. I'd say there's something a bit more fundamental going on here than _just_ a library design issue :-) No class can be all things to all users. Lassi
Lassi Tuura wrote:
Hi,
Libraries that produce needless copies are simply ill-designed, and thus it is true great parts of the standard library are),
Well... Having had to recent pleasure to find code like this:
bool foo::check(T *obj) const { std::string name = obj->name(); bool value = (name == "foo"); value = value || (name == "bar"); value = value || (name == "foobar"); value = value || (name == "zoinc"); value = value || (name == "barfy"); value = value || (name == "zoobie"); value = value || (name == "ayeyei"); return value; }
That was one of the contributors to ~800'000 memory allocation calls per second. It was called... often.
I'd say there's something a bit more fundamental going on here than _just_ a library design issue :-) No class can be all things to all users.
This isn't even a design issue. Your standard library is just being stupid (or overly pedantic) in its handling of operator==(string const&, char const*). Let them know how you feel.
Hi,
Libraries that produce needless copies are simply ill-designed, and thus it is true great parts of the standard library are),
[...] I'd say there's something a bit more fundamental going on here than _just_ a library design issue :-) No class can be all things to all users.
This isn't even a design issue. Your standard library is just being stupid (or overly pedantic) in its handling of operator==(string const&, char const*). Let them know how you feel.
Sure, that's certainly a very important factor. But I was going in a bit different direction. I'm of course delighted when people have sat down and produced an elegant and robust class design. I've had the pleasure to use a number of libraries with an excellent design. But each library has a purpose and it may differ from that of the developer. Of the libraries I have come across, the ones that tried to cover the whims of every turkey that walked by often had the most incomprehensible and bug-ridden interfaces and implementations. It's healthy when developers know the purpose of their classes and know when to resist requests for significant deviations. No class can nor needs to be all things to all users. In a way of an example, I happen to find std::string a decent general string class. It has some odd behaviours and maybe flaws, but overall it does a fine job and life is too short to sweat every detail. If I have a huge pool of arbitrary-size read-only strings that I want to treat as highly efficient interned atom database, is std::string a good choice? Nah. If 75% of my strings are dynamically built but read-only after creation, and I want to pass them a lot between threads, is std::string optimal? Naah. If I need to efficiently shuffle a lot of string data over networks, is std::string optimal? Nope. But to pursue any of these into std::string interface? Surely madness lies that way? How about a very general string-like concept which would be able to cover all these bases with suitably clever parametrisation? Why, when each can be satisfied by 50-500 lines of very straightforward code every dabbling developer will understand in hours? On the other hand, there _are_ areas where suitable abstraction pays off _big_ time. Lassi PS. In my earlier example the best choice would have been to drop strings altogether.
On 8/8/07, Phil Endecott <spam_from_boost_dev@chezphil.org> wrote:
In fact I'd love to see a complete set of standard-library-like copy-on-write containers, though I haven't thought through what this would require for lists and vectors.
Regards,
Phil.
opensource.adobe.com has a generic cow<> template, but I'm not sure how it works with containers. Tony
On 8/8/07, Jeremy Bruestle <jeremy.bruestle@gmail.com> wrote:
If anyone has more question though, or has ideas, or just wants to express interest, please do so. At this point I think I'm going to keep working on the project even if no one is interested, because I see of lot of fun problems to attack, but I'm still curious if anyone else has use for such a structure. Thanks to all so far for the good feedback.
-Jeremy
Your original reason for the shared map seems to be the cost of copying. If the map was based on a vector instead of a tree (and didn't share nodes at all) do you think that might solve your slow copy problems? I worked on a project where we found that copying of maps was one of the major bottle-necks, so we converted most of them to sorted vectors, and that fixed it. We didn't need the sorted vectors to have all the same behaviour as maps, but I've had a plan for vector-based maps sitting on the back-burner for a while now. Might be something to consider. Tony
On 8/10/07, Gottlob Frege <gottlobfrege@gmail.com> wrote:
I worked on a project where we found that copying of maps was one of the major bottle-necks, so we converted most of them to sorted vectors, and that fixed it.
We didn't need the sorted vectors to have all the same behaviour as maps, but I've had a plan for vector-based maps sitting on the back-burner for a while now. Might be something to consider.
It is true the vector copies are more efficient, but they are still linear time to copy. The bigger problem though is that each copy typically needs a few inserts done, so it's A.insert, A.insert, A.insert, B = A, B.insert, B.insert, B.insert, C = B, C.insert, C.insert, C.insert, so sorted vectors wouldn't work since they are bad at dealing with insertions. Also, I think I've figured out a better way to do iterators. I'll post again once I've gotten it all worked out. -Jeremy
participants (12)
-
Anthony Williams -
François Duranleau -
Gottlob Frege -
Hervé Brönnimann -
Jeremy Bruestle -
Lassi Tuura -
loufoque -
Martin Bonner -
Mathias Gaunard
-
Michael Marcin -
Peter Dimov -
Phil Endecott