Re: [boost] [submission] STL-compliant containers with copy-on-write
I'm working with embedded software and we have to use COW containers pretty often. I haven't found any COW container implementation which may replace STL containers and had to implemented it. It is not possible to make STL containers with COW keeping all semantics of the STL containers. For example, almost any member-function may throw, because copy ctor may throw. It is not always safe to replace std::vector with mine cow_vector, but in most cases it is safe. For example, it is not safe if you have saved constant pointer or constant reference from constant cow_vector. But with std::vector saving addresses is not a good idea as well, because resize, push_back and others may cause address change. In my implementation iterators are safe, for example: cow_vector<int> a; a.push_back( 1 ); cow_vector<int> b; b.push_back( 2 ); cow_vector<int>::const_iterator itA = a.begin(); assert( *itA == 1 ); cow_vector<int>::const_iterator itB = b.begin(); assert( *itB == 2 ); b = a; assert( itA == a.begin() ); assert( itB == b.begin() ); assert( *itA == 1 ); assert( *itB == 1 ); a[0] = 3; // or *a.begin() = 3 assert( itA == a.begin() ); assert( itB == b.begin() ); assert( *itA == 3 ); assert( *itB == 1 ); You example: int* p = &v[1]; // copying is done here v[0] = 1; assert( p == &v[1] ); // still valid as copying was done before. But in following case it won't work now: void test( const cow_vector<int>& a ) { const int *a = &v[1]; v[0] = 1; assert( p != &v[1] ); // sorry, another pointer if internal buffer was shared. } Please note, that it's possible to do copying if any reference or pointer is taken from iterator or container itself, but my current implementation doesn't do it. That's easy to change.
IMO it isn't possible to really make that work anyway since STL containers expose references to their elements *and* make guarantees about iterator stability and element layout. For example, if v is a vector and I do
v[0] = 1;
it's not allowed to change the address of v[1] -- Dave Abrahams BoostPro Computing http://www.boostpro.com
---- Best regards, Alexander Sterligov
On Thu, Mar 31, 2011 at 8:00 AM, Alexandr Sterligov <sterligov.ak@gmail.com>wrote:
I'm working with embedded software and we have to use COW containers pretty often.
[...] Can you describe a typical or example use case, from your experience, where COW is necessary? My own perspective: I've generally thought that, for typical container usage, COW is unnecessary, in the sense that it gives no performance benefit (and, if anything, a performance hit) given disciplined coding practices; COW is complicated to implement correctly and constrains your design; and, simply put, COW is a pessimism. It might be useful in exceptional circumstances, but certainly, I would think, far less frequently than "pretty often". But I'm open and curious to hear others' experiences. - Jeff
That's the point - it is hard to implement COW and test it. So there should be some library... Several years ago I participated in UPnP device/control point framework (lots of string processing). We did performance measurements with COW and without and had about 5 times difference, profiling showed memcpy to be a bottleneck. Also without COW we had memory heap fragmentation after long execution. Also memory consumptions were higher without COW. But in this project we had special circumstances - multithreading application with async string-based interface between subsystems, lots of strings passing from one object to anoter. Strings were modified rather seldom. Current project has less special circumstances. We have thread-safe cache. Objects are containers of messages with binary attachements (images). There are following options: 1. Cache returns cached objects "by value" - this means that objects are copied. -: Cache is read 100-1000 times more often then written. That's usual. We can avoid 100-1000 copies. +: almost no synchronization is needed. 2. Cache returns pointer or reference. No copying. +: no copying, no memcpy... -: very hard synchronization in case if cache is written. Pointer from cache is finally put to another thread (GUI even loop), so only const pointer or reference may be returned from cache and it makes code in the GUI more complex - we need to copy data before we'd like to change anything. It starts to look like "external" COW. If there would be no multithreaded access to cached data then pointers are ok. Such situation may be avoided, but it was legacy project with no cache initially. In case of COW we concentrate all logic of copy-on-write in container implementation and get pluses from both options - no copying and simple synchronization. Also much simplier to test. By the way, synchronization is pretty fast as no mutexes are used - only atomic operations. After buffer is marked "copy on write" it must not be changed - so we don't need to lock it while copying. Implementation has internal std::vector with reference count. All iterators of mine container is wrappers around std::vector interators. On any dereference operation, iterator checks if buffer of the parent container has been changed since last dereference operation. If it was changes - internal native-iterator is constacted again from internal std::vector iterator. Such approach allows to wrap almost any container into COW container. Another situation is inside high-performance streaming library (TVoIP conference) - there are chain of filters which process media packets in conveyor manner. Filters are developed separately and may work inplace, or defer packets to process them later. If there is no COW, filters should always copy packets for deferring or inplace modification. Chain of filters is build during execution and is not known on compile time. Packet has size up to 2000Bytes, frequence is up to 40 packets per second. Number of filters is about 10. At least 3 of fillter types may defer packet and at least 2 would like to work inplace. In this example actually COW containers aren't really needed, but COW itself works good. I agree that in most cases in PC software COW gives no benefit (Aleksandrescu). 2011/3/31 Jeffrey Lee Hellrung, Jr. <jeffrey.hellrung@gmail.com>
On Thu, Mar 31, 2011 at 8:00 AM, Alexandr Sterligov <sterligov.ak@gmail.com>wrote:
I'm working with embedded software and we have to use COW containers pretty often.
[...]
Can you describe a typical or example use case, from your experience, where COW is necessary?
My own perspective: I've generally thought that, for typical container usage, COW is unnecessary, in the sense that it gives no performance benefit (and, if anything, a performance hit) given disciplined coding practices; COW is complicated to implement correctly and constrains your design; and, simply put, COW is a pessimism. It might be useful in exceptional circumstances, but certainly, I would think, far less frequently than "pretty often". But I'm open and curious to hear others' experiences.
- Jeff _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Best regards, Alexander Sterligov
On 31/03/2011 21:19, Alexandr Sterligov wrote:
1. Cache returns cached objects "by value" - this means that objects are copied.
Returning by value does not necessarily mean copying. It can mean "nothing" (if the returned object is local to the function and is used to initialize another object) or "move" (if the returned object is local to the function or is moved from elsewhere).
-: Cache is read 100-1000 times more often then written. That's usual. We can avoid 100-1000 copies. +: almost no synchronization is needed.
2. Cache returns pointer or reference. No copying. +: no copying, no memcpy... -: very hard synchronization in case if cache is written. Pointer from cache is finally put to another thread (GUI even loop), so only const pointer or reference may be returned from cache and it makes code in the GUI more complex - we need to copy data before we'd like to change anything. It starts to look like "external" COW.
Which is probably really what you want. A COW layer built on top. Actually, your whole cache idea really looks like Boost.Flyweight, except the latter purposely disallows mutability.
Another situation is inside high-performance streaming library (TVoIP conference) - there are chain of filters which process media packets in conveyor manner. Filters are developed separately and may work inplace, or defer packets to process them later. If there is no COW, filters should always copy packets for deferring or inplace modification.
Or you could simply move them.
2011/3/31 Mathias Gaunard <mathias.gaunard@ens-lyon.org>
On 31/03/2011 21:19, Alexandr Sterligov wrote:
1. Cache returns cached objects "by value" - this means that objects are
copied.
Returning by value does not necessarily mean copying. It can mean "nothing" (if the returned object is local to the function and is used to initialize another object) or "move" (if the returned object is local to the function or is moved from elsewhere).
-: Cache is read 100-1000 times more often then written. That's usual. We
can avoid 100-1000 copies. +: almost no synchronization is needed.
2. Cache returns pointer or reference. No copying. +: no copying, no memcpy... -: very hard synchronization in case if cache is written. Pointer from cache is finally put to another thread (GUI even loop), so only const pointer or reference may be returned from cache and it makes code in the GUI more complex - we need to copy data before we'd like to change anything. It starts to look like "external" COW.
Which is probably really what you want. A COW layer built on top. Actually, your whole cache idea really looks like Boost.Flyweight, except the latter purposely disallows mutability.
Immutability of stored object is reason why it cannot be used as cache. And flyweight pattern is not for such cases. Scenario: We have list of appointments. Each appointment consist of several fields: creator, subject, time, notes, list of attachements and some other stuff. Creator may change some of the fields, these changes are delivered to all participants of the appointment through network communication. User goes to the list of appointment. GUI requests business-logic for it. There is no object in the cache, server communication is done and appointment list is received and stored to the cache. User goes somewhere form the list of appointments and then goes back. GUI requests business logic again and cached value is received again. But before it is fully displayed on the screen, bottom layer thread which polls server invalidates appointment list, as some of the values has been changed by creator. It happens very seldom. In following scenario it is nice to use move semantics, and when cache is invalidated just remove value from the cache, shared_ptr will delete data which is now in the GUI thread. But here comes the problem, GUI sometimes would like to change data as well - for example apply filter, or sort it, or change binary attachement. Full list of appointments and attachements may be pretty large and both GUI and server side change is really seldom. Good solution is to move, but then if there is any need to change - copy it. That's exactly copy-on-write. It may be implemented in the container itself or on the top like you've noticed. If it is implemented on the top there will be a lot of logic duplicates all over the code. In my case: appointments, messages, call history, medical measurements and other medical data. With COW inside container I've implemented and tested it once and don't need to take care about move semantics (values inside cache depends from what's happening in the GUI - not nice...)
Another situation is inside high-performance streaming library (TVoIP
conference) - there are chain of filters which process media packets in conveyor manner. Filters are developed separately and may work inplace, or defer packets to process them later. If there is no COW, filters should always copy packets for deferring or inplace modification.
Or you could simply move them.
Let's assume following scenario. We have 2 filters. FilterA would may deffer packet to process it later and FilterB may process packet inplace (destroys internal data). Packet is received and put to the chain of filters. First filter in chain FilterA decides to deffer packet. Filter saves packet internally and will process it later together with next packet. Second filter FilterB decides to process it inplace, so it will destroy internal data of the packet. But this data would be needed later by FilterA... Nither FilterA nor FilterB doesn't know about each other. They cannot decide should they move or copy. Without any additional information passing from one to another one of filters should always copy, but this copy may be avoided in some cases. Next packet is received. FilterA decides to process it together with the previous one and it doesn't need to save it in internal state. Second FilterB still decides to process it inplace. FilterB can safely destroy internal data as no one needs it. Move semantics cannot handle it. On first packet it should be copyed somewhere. On second packet it might not be copyed (move semantics). But as FilterA doesn't know about FilterB and vice versa, there is no chance to determine when to copy and when to move. There should be some additional data passing between filters. It may be "COW on the top" or COW internally in packet. -- Best regards, Alexander Sterligov
At Thu, 31 Mar 2011 19:00:16 +0400, Alexandr Sterligov wrote:
It is not possible to make STL containers with COW keeping all semantics of the STL containers.
Then I think you'd better define "STL-compliant" more carefully. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
At Thu, 31 Mar 2011 19:00:16 +0400, Alexandr Sterligov wrote:
It is not possible to make STL containers with COW keeping all semantics of the STL containers.
Then I think you'd better define "STL-compliant" more carefully. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Yes, sorry... I will be more careful with calling anything STL-compliant. It is only STL-like. 2011/3/31 Dave Abrahams <dave@boostpro.com>
At Thu, 31 Mar 2011 19:00:16 +0400, Alexandr Sterligov wrote:
It is not possible to make STL containers with COW keeping all semantics of the STL containers.
Then I think you'd better define "STL-compliant" more carefully.
-- Dave Abrahams BoostPro Computing http://www.boostpro.com
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Best regards, Alexander Sterligov
On 03/31/2011 01:48 PM, Alexandr Sterligov wrote:
Yes, sorry... I will be more careful with calling anything STL-compliant. It is only STL-like.
It seems that using a generic COW wrapper might be more suitable. Internally it would maintain a pointer to a reference-counted instance of the base type. It would provide a method for getting a const reference to the type (e.g. get(), operator*() and operator->()), and also a method for obtaining a non-const reference to a unique copy of the type (e.g. get_unique()), which would take care of copying if the reference count is greater than 1. I believe this interface is better than a specialized type that tries to mimic the interface of a particular container because generally if there is a need to mutate the type, it will be done by a series of possibly many mutating operations on the type/iterations, and it is inefficient to check if there is a need to copy e.g. on each iterator dereference or on each invocation of operator[]. It also avoids the need to create the specialized types in the first place; a single quite simple wrapper type will solve the problem for all types.
I thought about it too, that's very easy to do. Something like: cow_wrapper<std::vector<Big> > a( new std::vector<Big>() ); a->push_back( Big() ); // compilation error, as operator-> returns non-const. a.get_unique().push_back( Big() ); // OK. Just yet another smart pointer. May be added to Boost.SmartPtr. 2011/4/1 Jeremy Maitin-Shepard <jeremy@jeremyms.com>
On 03/31/2011 01:48 PM, Alexandr Sterligov wrote:
Yes, sorry... I will be more careful with calling anything STL-compliant. It is only STL-like.
It seems that using a generic COW wrapper might be more suitable. Internally it would maintain a pointer to a reference-counted instance of the base type. It would provide a method for getting a const reference to the type (e.g. get(), operator*() and operator->()), and also a method for obtaining a non-const reference to a unique copy of the type (e.g. get_unique()), which would take care of copying if the reference count is greater than 1.
I believe this interface is better than a specialized type that tries to mimic the interface of a particular container because generally if there is a need to mutate the type, it will be done by a series of possibly many mutating operations on the type/iterations, and it is inefficient to check if there is a need to copy e.g. on each iterator dereference or on each invocation of operator[].
It also avoids the need to create the specialized types in the first place; a single quite simple wrapper type will solve the problem for all types.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Best regards, Alexander Sterligov
On Thu, Mar 31, 2011 at 2:07 PM, Jeremy Maitin-Shepard <jeremy@jeremyms.com>wrote:
On 03/31/2011 01:48 PM, Alexandr Sterligov wrote:
Yes, sorry... I will be more careful with calling anything STL-compliant. It is only STL-like.
It seems that using a generic COW wrapper might be more suitable. Internally it would maintain a pointer to a reference-counted instance of the base type. It would provide a method for getting a const reference to the type (e.g. get(), operator*() and operator->()), and also a method for obtaining a non-const reference to a unique copy of the type (e.g. get_unique()), which would take care of copying if the reference count is greater than 1.
I believe this interface is better than a specialized type that tries to mimic the interface of a particular container because generally if there is a need to mutate the type, it will be done by a series of possibly many mutating operations on the type/iterations, and it is inefficient to check if there is a need to copy e.g. on each iterator dereference or on each invocation of operator[].
It also avoids the need to create the specialized types in the first place; a single quite simple wrapper type will solve the problem for all types.
+1; I believe this had been mentioned before by someone during the XInt review, but I appreciate being reminded of this technique. - Jeff
On Fri, 01 Apr 2011 03:07:23 +0600, Jeremy Maitin-Shepard <jeremy@jeremyms.com> wrote:
On 03/31/2011 01:48 PM, Alexandr Sterligov wrote:
Yes, sorry... I will be more careful with calling anything STL-compliant. It is only STL-like.
It seems that using a generic COW wrapper might be more suitable. Internally it would maintain a pointer to a reference-counted instance of the base type. It would provide a method for getting a const reference to the type (e.g. get(), operator*() and operator->()), and also a method for obtaining a non-const reference to a unique copy of the type (e.g. get_unique()), which would take care of copying if the reference count is greater than 1.
I believe this interface is better than a specialized type that tries to mimic the interface of a particular container because generally if there is a need to mutate the type, it will be done by a series of possibly many mutating operations on the type/iterations, and it is inefficient to check if there is a need to copy e.g. on each iterator dereference or on each invocation of operator[].
It also avoids the need to create the specialized types in the first place; a single quite simple wrapper type will solve the problem for all types.
See http://stlab.adobe.com/classadobe_1_1version__1_1_1copy__on__write.html
participants (6)
-
Alexandr Sterligov -
Dave Abrahams -
Ilya Sokolov -
Jeffrey Lee Hellrung, Jr. -
Jeremy Maitin-Shepard -
Mathias Gaunard