copy-on-write++

[Peter]

Cannot post a .pdf file here.
See

http://foelsche.files.wordpress.com/2011/04/copy_on_write.pdf

or

http://foelsche.wordpress.com

 

[Jorgen Grahn]

Cannot post a .pdf file here.

You could at least summarize it, if you want us to read it.

/Jorgen

 

[Peter]

You could at least summarize it, if you want us to read it.

being able to give up copy-on-write-ownership without destroying the
object

 

[Öö Tiib]

Cannot post a .pdf file here.
See

http://foelsche.files.wordpress.com/2011/04/copy_on_write.pdf

or

http://foelsche.wordpress.com

You have two pages of plain text and so you post it as link to pdf
containing that text?

 

[Peter]

I hate all these hyperintelligent email tools,
which are using all their intelligence to mess up simple text....


copy-on-write++

My code was very slow. Despite the fact that I was already using some
copy-on-write mechanism to avoid calling the copy constructor. It
involved passing a map to every child of a tree. Every child passed it
on to its children. Every child returned a map, which in turn was then
passed to the next child (its next sibling). And every child stored
the map or some changed version of it. Some elements of the tree
merged the maps returned by their children. I was using the following
classes:

ï‚· CReferenceCounted Essentially containing an integer and a method to
increment this integer (Addref()) and a method to decrement this
integer (Release()). In case of Release() caused the integer to drop
to zero, it called delete this; Of course the destructor was virtual.

ï‚· CSmartPtr Containing a pointer to some class derived from
CReferenceCounted. The constructor called AddRef() on the pointer and
the destructor called Release(). Of course there were copy constructor
and assignment operator.

ï‚· CSmartMap In essence a CSmartPtr to a class derived from
CReferenceCounted containing a std::map. The copy constructor copied
only the pointer. Then there are all the needed methods from std::map
in essence forwarding to the std::map pointed to. Any non-const method
checked the reference count and if it was larger than one, performed a
deep copy before executing the method on the std::map.

ï‚· CTreeElement An element of the tree. Every such object contains a
vector of CTreeElement representing the children. And there is the
method to pass and return the map: CSmartMap
CTreeElement ::setMap(const CSmartMap &); As I said, this method calls
every child and passes some potentially modified map:

for (std::size_t i = 0, iMax = m_sChildren.size(); i < iMax; ++i)
sMap = m_sChildren.setMap(sMap);

I was thinking, that the CSmartMap objects stayed alive too long
causing unnecessary copies to be performed. Consider the case of
passing a map to a child by calling setMap(). It would be nice if the
caller would be able to transfer ownership to the child method
setMap(), if he does not have any use anymore for the object. So this
passing of ownership must be optional. But how do you release an
object without actually destroying it? Here comes the solution:

ï‚· CCopyOnWriteCounter Similar to CReferenceCounted. The only
difference was that Release() did not destroy the object.

ï‚· CCopyOnWritePtr Derived from CSmartPtr. It must point to an object
derived from both, CReferenceCounted and CCopyOnWriteCounter. The
constructor calls the AddRef() of CCopyOnWriteCounter and the
destructor calls the Release() (remember that this Release() does not
call delete). The base class constructor and destructor of CSmartPtr
are calling into CReferenceCounted. There is of course also an
assignment operator (which in turn called the assignment operator of
the base class CSmartPtr). Since the object pointed to has two
reference counts, we can use one reference count for live time
management and one for managing copy-on-write.

I made CSmartMap derived from CCopyOnWritePtr. And I created
CSmartMap::CPointer which was a plain CSmartPtr. CSmartMap has a cast
operator to convert to CSmartMap::CPointer and a constructor with
argument type CSmartMap::CPointer. Thus if one wanted to perform some
operation on the map, one could hold a copy-on-write reference count,
since it required a CSmartMap. CSmartMap::CPointer did not provide any
functionality. The signature of the method CTreeElement::setMap() was
changed:

CSmartMap::CPointer CTreeElement ::setMap(const CSmartMap::CPointer
&);

Now every implementation of setMap() would have to watch, if it needs
some CSmartMap object again or if it does not care about it anymore:

CSmartMap::CPointer CTreeElement ::setMap(const CSmartMap::CPointer
&p)
{ m_sChildren[0].setMap(CSmartMap(p)); // need the map pointed to by p
to stay unchanged
// thus increment the copy-on-write reference count
// before calling setMap() and decrementing it after
return m_sChildren[1].setMap(p);// don’t need the map pointed to byp
after this anymore
}

Is this sufficiently clear?
Peter Foelsche
Milpitas, California, USA
Friday, April 08, 2011

 

[Pavel]

I hate all these hyperintelligent email tools,
which are using all their intelligence to mess up simple text....


copy-on-write++

My code was very slow. Despite the fact that I was already using some
copy-on-write mechanism to avoid calling the copy constructor. It
involved passing a map to every child of a tree. Every child passed it
on to its children. Every child returned a map, which in turn was then
passed to the next child (its next sibling). And every child stored
the map or some changed version of it. Some elements of the tree
merged the maps returned by their children. I was using the following
classes:

ï‚· CReferenceCounted Essentially containing an integer and a method to
increment this integer (Addref()) and a method to decrement this
integer (Release()). In case of Release() caused the integer to drop
to zero, it called delete this; Of course the destructor was virtual.

ï‚· CSmartPtr Containing a pointer to some class derived from
CReferenceCounted. The constructor called AddRef() on the pointer and
the destructor called Release(). Of course there were copy constructor
and assignment operator.

ï‚· CSmartMap In essence a CSmartPtr to a class derived from
CReferenceCounted containing a std::map. The copy constructor copied
only the pointer. Then there are all the needed methods from std::map
in essence forwarding to the std::map pointed to. Any non-const method
checked the reference count and if it was larger than one, performed a
deep copy before executing the method on the std::map.

ï‚· CTreeElement An element of the tree. Every such object contains a
vector of CTreeElement representing the children. And there is the
method to pass and return the map: CSmartMap
CTreeElement ::setMap(const CSmartMap&); As I said, this method calls
every child and passes some potentially modified map:

for (std::size_t i = 0, iMax = m_sChildren.size(); i< iMax; ++i)
sMap = m_sChildren.setMap(sMap);

I was thinking, that the CSmartMap objects stayed alive too long
causing unnecessary copies to be performed. Consider the case of
passing a map to a child by calling setMap(). It would be nice if the
caller would be able to transfer ownership to the child method
setMap(), if he does not have any use anymore for the object. So this
passing of ownership must be optional. But how do you release an
object without actually destroying it? Here comes the solution:

ï‚· CCopyOnWriteCounter Similar to CReferenceCounted. The only
difference was that Release() did not destroy the object.

ï‚· CCopyOnWritePtr Derived from CSmartPtr. It must point to an object
derived from both, CReferenceCounted and CCopyOnWriteCounter. The
constructor calls the AddRef() of CCopyOnWriteCounter and the
destructor calls the Release() (remember that this Release() does not
call delete). The base class constructor and destructor of CSmartPtr
are calling into CReferenceCounted. There is of course also an
assignment operator (which in turn called the assignment operator of
the base class CSmartPtr). Since the object pointed to has two
reference counts, we can use one reference count for live time
management and one for managing copy-on-write.

I made CSmartMap derived from CCopyOnWritePtr. And I created
CSmartMap::CPointer which was a plain CSmartPtr. CSmartMap has a cast
operator to convert to CSmartMap::CPointer and a constructor with
argument type CSmartMap::CPointer. Thus if one wanted to perform some
operation on the map, one could hold a copy-on-write reference count,
since it required a CSmartMap. CSmartMap::CPointer did not provide any
functionality. The signature of the method CTreeElement::setMap() was
changed:

CSmartMap::CPointer CTreeElement ::setMap(const CSmartMap::CPointer
&);

Now every implementation of setMap() would have to watch, if it needs
some CSmartMap object again or if it does not care about it anymore:

CSmartMap::CPointer CTreeElement ::setMap(const CSmartMap::CPointer
&p)
{ m_sChildren[0].setMap(CSmartMap(p)); // need the map pointed to by p
to stay unchanged
// thus increment the copy-on-write reference count
// before calling setMap() and decrementing it after
return m_sChildren[1].setMap(p);// don’t need the map pointed to by p
after this anymore
}

Is this sufficiently clear?
Peter Foelsche
Milpitas, California, USA
Friday, April 08, 2011

Do you still experience a problem or you just want to solicit feedback on the
design?

If the former, what is the current problem?

If the latter, here is my feedback: The design seems to make sense although to
pass ownership of a CSmartPtr you could probably use out-of-the-box
std::auto_ptr<CSmartPtr> or std::unique_ptr<CMartPtr> if your environment allows
using features from upcoming standards. It is difficult to say for sure without
seeing the code though.

High-performance implementation of the design may hit some small snugs but
should not be too challenging. High-performance thread-safe implementation could
pose a greater challenge; unsure if you need it though.

-Pavel

 

[Peter]

Do you still experience a problem or you just want to solicit feedback onthe
design?

The code is considerable faster than before.
I think the number of copy-constructor calls for std::map is
negligable now.
I wanted the share the idea, as I did not know about it before and I
did not find this approach anywhere.

I'm still wrecking my brain about if the same can be achived in a
simpler way.

If the former, what is the current problem?

If the latter, here is my feedback: The design seems to make sense although to
pass ownership of a CSmartPtr you could probably use out-of-the-box
std::auto_ptr<CSmartPtr> or std::unique_ptr<CMartPtr> if your environmentallows
using features from upcoming standards. It is difficult to say for sure without
seeing the code though.

I don't think my approach can be implemented with auto_ptr
(unique_ptr is similar to auto_ptr was far as I understand).

CSmartPtr calls CReferenceCounted::AddRef()/
CReferenceCounted::Release() in the constructor/destructor/assignment
operator.
CCopyOnWritePtr is derived from CSmartPtr and additionally calls
CCopyOnWriteCounter::AddRef/CCopyOnWriteCounter::Release in the
constructor/destructor/assignment operator.
CSmartPtr keeps the object alive.
CCopyOnWritePtr keeps the object alive and keeps a reference for copy-
on-write.
CSmartMap is derived from CCopyOnWritePtr.

The idea is to pass an object without anybody holding a copy-on-write
reference (optionally).
To perform an operation on the map one needs a CSmartMap.

 

[Peter]

I understand now -- the whole idea is identical to passing a
std::string by pointer (I don't use non-constant references):


std::string CTreeElement ::setMap(std::string *const _p);


So if you don't need your copy anymore, simply pass a pointer to it:


std::string s;

m_sChilren.setMap(&s);


If you still need your copy:

m_sChilren.setMap(&std::string(s));