Cheap copy of maps (reference counting) PHASE I.

[Alpar Juttner]

The idea is that the copy constructor and operator=() of a ListGraph::NodeMap<> &Co. would not effectively copy the map but instead it would use the container array of the source map. The storage would be deallocated when there are no maps pointing to it.

Moreover, the default maps would have a copy() member function, which would effectively copy the contents, i.e.:

  ListDigraph::NodeMap<int> a(g);
  ListDigraph::NodeMap<int> b(a); /// a and b use the same storage
  a[e]=5   /// this also sets b[e] to 5.
  ...
  b.copy() /// b now have a separate storage
  a[e]=7   /// the value of b[e] does not change

The advantage of this approach is that

• a function could create return a map. Currently it is impossible, the caller must allocate the map and pass it as a reference.
• we could assume that the copy/assignment of a map of the same type are cheap therefore we don't have to differentiate e.g. between the default maps and the map adaptors.

However this approach is not fully compatible with the current implementation, therefore we must follow one of the tree approaches below.

• Declare that this is a basically bad idea and therefore we will never introduce it. I would not be happy with a decision like this.
• We like the idea so much that we implement it right now. Though it is not a trivial task, I guess.
• We postpone this to the next release. If we want to do this, we must forbid temporarily the usage of operator= and the copy constructor of the default maps, for a late introduction of a cheap copy would break the API compatibility.

P.S: It can also be a nice thing to do something similar with the graphs themselves. Fortunately, graph have no copy constructors and assignment operators, therefore in case of graphs the introduction of "cheap copy" is a clear enhancement and does not break the API compatibility.

[Balazs Dezso]

More library contains template reference counted smart pointers. In my point of view, if the user needs such functionality, then he/she can use one of them. I think the current solution is closer to the C++ ideology.

[Alpar Juttner]

Replying to deba:

More library contains template reference counted smart pointers.

This is a different story. You probably missed the point. Maybe because I was not clear enough.

In my point of view, if the user needs such functionality, then he/she can use one of them.

Reference counted pointers are unusable for this purpose. Mainly because then the lemon core tools cannot depend on the "cheap copy" nature of the maps.

I think the current solution is closer to the C++ ideology.

I think the opposite. The "copy on write" approach is very common in C++. It was even used in the original SGI STL implementation: the std::string used to be implemented in this way.

The only difference here is that - for efficiency reasons - we have to need explicit "copy" operation.

[Balazs Dezso]

Replying to alpar:

Reference counted pointers are unusable for this purpose. Mainly because then the lemon core tools cannot depend on the "cheap copy" nature of the maps.

I think the current solution is closer to the C++ ideology.

I think the opposite. The "copy on write" approach is very common in C++. It was even used in the original SGI STL implementation: the std::string used to be implemented in this way.

I could rather look this from the opposite direction. All the stl containers work like regular values. Indeed, in the SGI implementation the std::string is reference counted, but it is the only exception. And it's semantics is completely the same, as if it would be a regular value.

The only difference here is that - for efficiency reasons - we have to need explicit "copy" operation.

It is quite a big difference, in my point of view.

[Alpar Juttner]

Replying to deba:

The only difference here is that - for efficiency reasons - we have to need explicit "copy" operation.

It is quite a big difference, in my point of view.

It is a matter of taste.

However the point is that here is a proposal for a very useful feature with the only drawback that the map copy will be very slightly more complex. Using a separate ref. count. pointer tool cannot replace this feature.

Therefore the question is if we want it (not necessarily now) or not. At least for me, I really want it.

As the implementation is not trivial, we cannot include it into version 1.0. In order to be able to do it later while keeping the backward compatibility we must

temporarily turn of operator= and the copy constructor for the standard maps.

This is not the big deal because nothing uses these features internally in lemon-1.0. Moreover doing this we can still opt for adopting the cheap copy principle or not at a later date.

So the only question now is:

Is there anything against doing this first step?

If not, let's do it.

[Balazs Dezso]

Replying to alpar:

However the point is that here is a proposal for a very useful feature with the only drawback that the map copy will be very slightly more complex. Using a separate ref. count. pointer tool cannot replace this feature.

Therefore the question is if we want it (not necessarily now) or not. At least for me, I really want it.

Yes, the main question is whether we would like to introduce this feature, or not. However some details should be clarified before we decide:

• The alteration observing should work with the proposed feature, will it cause some problems? How could the special maps implemented, like InDegMap?, ...
• Could we implement each non-lightweight map with similar reference counting, for example RangeMap?, SparseMap?, InDegMap?, DescriptorMap? or in the future BoostGraphAdaptor::NodeMap?? Would we like to do that? If we change in the graph map, then we have to use reference counting in each heavy weight maps.
• Should we use it an other elements of the library. For example in Graphs, Paths, ...?
• How the parallelization works with this feature? As I know the std::string had some trouble with the implementation. For me the effects are not so clear.

As the implementation is not trivial, we cannot include it into version 1.0. In order to be able to do it later while keeping the backward compatibility we must

temporarily turn of operator= and the copy constructor for the standard maps.

If we would like to turn off operator=, then the current implementation could be renamed to template <CMap> set(const CMap& cmap);.

This is not the big deal because nothing uses these features internally in lemon-1.0.

In my point of view, sometimes the external users should be considered well.

Moreover doing this we can still opt for adopting the cheap copy principle or not at a later date.

So the only question now is:

Is there anything against doing this first step?

If not, let's do it.

I am against the first step, while the questions regarding the whole feature are not clear. I see some advantages of the feature (simpler map adaptors), but I am not sure about the whole thing is promising.

[Alpar Juttner]

Replying to deba:

Replying to alpar: Yes, the main question is whether we would like to introduce this feature, or not. However some details should be clarified before we decide:

I definitely to not want to start any debate like this before the release 1.0.

I suggested this "first step" modification because I want to make it possible to decide on this later while keeping the backward compatibility.

temporarily turn of operator= and the copy constructor for the standard maps.

If we would like to turn off operator=, then the current implementation could be renamed to template <CMap> set(const CMap& cmap);.

Then we would have to keep it forever, which is probably not exactly what we want.

This is not the big deal because nothing uses these features internally in lemon-1.0.

In my point of view, sometimes the external users should be considered well.

In theory, you are right. In practice, version 1.0 hasn't been released yet, so the number of external code using it is more than limited.

Moreover doing this we can still opt for adopting the cheap copy principle or not at a later date.

So the only question now is:

Is there anything against doing this first step?

If not, let's do it.

I am against the first step, while the questions regarding the whole feature are not clear.

Come on, please read carefully what I wrote before you answer!

This first step is in order to make it possible to decide later. If we do it, we can decide in either way later. If we don't do it, we cannot introduce this feature later.

[Peter Kovacs]

Replying to alpar:

So the only question now is:

Is there anything against doing this first step?

If not, let's do it.

I am not against this first step, although I am unconvinced about the feature and a lot of details are not so clear for me, yet.

[Alpar Juttner]

[6a55577420eb] makes the copy constructor and the operator=() of the default maps private. Could anyone review the patch?

[Peter Kovacs]

As far as I understand [6a55577420eb] disables concept checking for all structures (not only for graph maps), since it disables the following line in checkConcept() function. However it is not necessary.

void (ConceptCheck::*x)() = & ConceptCheck::constraints;

[be8a861d3bb7] contains a fixed variant of the changeset.

[Peter Kovacs]

Is [be8a861d3bb7] correct?

Applying it we could postpone the ticket.

[Balazs Dezso]

Replying to kpeter:

Is [be8a861d3bb7] correct?

Applying it we could postpone the ticket.

In my opinion yes.

[Alpar Juttner]

Replying to deba:

Replying to kpeter:

Is [be8a861d3bb7] correct?

Applying it we could postpone the ticket.

In my opinion yes.

Instead, I close the ticket and create another one. Thus see #146 for the follow-up of this ticket