[Lemon-devel] Cheap copy concept

[Balazs Dezso]

Dear Developers,

I would like to add some important questions regarding this problem. Some of 
them are repeated from the ticket #146, but I did not get good answers for 
them.

1) If we use cheap copy then in each algorithm we should use value data 
members and value parameters. Therefore, if we would like to make a heavy 
weight map, then we have to make this class reference counted. It is not 
enough to just modify graph maps.

2) If we use multi-threaded program, then the reference counting 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.

Just a note, the gnu std::string uses __gnu_cxx::__atomic_add_dispatch and 
similar functions to avoid such problems, so we should compiler dependent 
code. The Visual C++ 6.0 crashed because of this problem, from 7.0 they 
written thread safe code.

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

4) Our solution would not be seamless. If we would like to do seamless 
reference counting, then each map write access should contain also a check, 
and the operator[] could not be used efficiently. However, the not-seamless 
solution is not a quite nice solution in C++. 

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.

2) Easier usage of class like algorithm interfaces and graph IO. Currently, if 
we would like to give an addMap(nm1, nm2) to a class like algorithm, we should 
create the AddMap object explicitly. 

3) The algorithm objects could be used similarly as maps. However it is not 
surely true, because some other data structures should follow similar copy 
semantics(for example heaps, elevators, unionfinds).

If you have more important use-cases, when the cheap copy is quite usable, 
please share it on the mail-list. I would like to see also a plan about the 
modifications and the necessary effort.

I'm now against the cheap copy. I do not feel that the cheap copy could 
substantially increase the usability of LEMON, and it cause similar number of 
difficulties, as it is currently in LEMON.

Best, Balazs

On Tuesday 28 October 2008 18:37:08 Alpár Jüttner wrote:
> Dear all,
>
> We must urgently start discussing that "cheap copy" concept of maps
> either here, or in the issue tracker (where, in fact, most of the
> development related discussions take place) under the related ticket:
>
> http://lemon.cs.elte.hu/trac/lemon/ticket/146
>
> This issue is probably the most important general question now, as it
> blocks porting other important tools.
>
> Best regards,
> Alpar
>
>
> _______________________________________________
> Lemon-devel mailing list
> Lemon-devel at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-devel