Re: [boost] [submission] STL-compliant containers with copy-on-write

Subject: Re: [boost] [submission] STL-compliant containers with copy-on-write
From: Alexandr Sterligov (sterligov.ak_at_[hidden])
Date: 2011-03-31 15:19:29

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

> On Thu, Mar 31, 2011 at 8:00 AM, Alexandr Sterligov
> <sterligov.ak_at_[hidden]>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