[Lemon-devel] Cheap copy concept

[Alpár Jüttner]

Hi,

> 1) If we use cheap copy then in each algorithm we should use value data 
> members and value parameters.

Not exactly. This should only be an option.

> Therefore, if we would like to make a heavy 
> weight map, then we have to make this class reference counted.

More exactly, if we want to use it in conjunction with an algorithm
which uses this feature and we want to avoid copying the full data of
the map, then yes, it must be reference counted.

>  It is not 
> enough to just modify graph maps.

Could you list those heavy weight maps that may need reference counting?

> 2) If we use multi-threaded program, then the reference counting can cause 
> problems.

In a multi-thread code everything can cause problems.

>  For example, we use a unmodified map in two different thread. If the 
> two instances are destructed at the same time, then it can happen segmentation 
> fault or memory leak. Because we do not force any threading library, therefore 
> we cannot defend the maps from such problems.

This single problems can be solved with a mutex, but I do not worry
about too much, because currently LEMON is not thread safe at several
places. For example even creating new maps for the same graph in
parallel thread can cause problems. Therefore, for example you cannot
run two dijkstra algorithms or two flow algorithms safely in parallel.

Well, actually I worry about it quite a lot, this is a crucial question,
but it is somehow more general than the cheap copy concept.

> 3) How could be implemented the special maps? I think the special maps, 
> InDegMap/OutDegMap/IterableMaps/Snapshots could be implemented more complex 
> way.

Not really. Peope will rarely copy these maps, thus simplest approach -
when the datastructure is copied - will probably be sufficient. In fact,
this is the current implementations.
If there is a high demands, one can modify it so that it will use a
shares datastructure. It is not completely trivial, bit it can be done.
But probably nobody needs this feature.

> 4) Our solution would not be seamless. If we would like to do seamless 
> reference counting,

The reference counting will be really seamless. You are talking about
the "copy-on-write" feature here, aren't you?

>  then each map write access should contain also a check, 
> and the operator[] could not be used efficiently. 

Not. The write access will simply modify the same underlying data
structure. I agree, it might be strange in the first five minutes, but
this is how the things are going at several places in the world,
especially when reference counting (or other garbage collection) is
used, e.g. in Python or Lisp.

> However, the not-seamless 
> solution is not a quite nice solution in C++. 

It won't be worse than the whole C++ in general. :)

> I would like to speak about the advantages too.
> 
> 1) We can return map by value, we should not give the return value maps as 
> parameters to the function.

sed -e 's/should not/we don\'t have to/g'

Regards,
Alpar