Static graph maps

[Alpar Juttner]

Sometimes it would be nice to have a map which is not registered in the alteration notifier of the graph.

One reason might be running time efficiency, but the more important is multi-thread applications (see #223). Currently, it is not safe to run say two Dijkstra algorithms on the same graph in parallel, as they would allocate maps and register them into the alteration notifier simultaneously, which is not safe. Changing these map allocations to static one would solve this problem.

My suggestion is to use the standard maps with a special constructor for this purpose, e.g.

ListGraph::NodeMap<int> map1(g,STATIC);
ListGraph::NodeMap<int> map1(g,15,STATIC);

or

ListGraph::NodeMap<int> map1(STATIC,g);
ListGraph::NodeMap<int> map1(STATIC,g,15);

See also #223.

'

[Peter Kovacs]

Replying to alpar:

One reason might be running time efficiency,

I like this concept. An algorithm typically allocates one or more maps for the underlying graph, but it do not modify the graph, since it is usually a const parameter. In these cases we could use static maps.

My suggestion is to use the standard maps with a special constructor for this purpose

What about StaticNodeMap as an alternative?

[Alpar Juttner]

My suggestion is to use the standard maps with a special constructor for this purpose

What about StaticNodeMap as an alternative?

The dynamic and the static maps are the same data structure, the only difference is that in the static case it is not registered in the alteration notifier. So I prefer using the special constructor.

It is also better because many algorithms set their template parameters to the standard NodeMap/EdgeMap by default. Using these algorithms with {StaticNodeMap would be an extra trouble.

[Peter Kovacs]

Replying to alpar:

My suggestion is to use the standard maps with a special constructor for this purpose

What about StaticNodeMap as an alternative?

The dynamic and the static maps are the same data structure, the only difference is that in the static case it is not registered in the alteration notifier. So I prefer using the special constructor.

I see. That's clear.

STATIC would be a global constant, such as INVALID?

[Alpar Juttner]

STATIC would be a global constant, such as INVALID?

Yes.

[Alpar Juttner]

Can we agree in this concept, then?

Could anyone familiar with the map internals estimate how difficult is to implement it?

[Balazs Dezso]

Replying to alpar:

Can we agree in this concept, then?

Could anyone familiar with the map internals estimate how difficult is to implement it?

In my opinion, the extra parameter is a good solution. However, the thread-safe map construction must be solved somehow (not just the static ones). If it was solved, then this concept would become useless (If we do not consider the runtime efficiency improvement, which might be very small).

The implementation is not so difficult, but it needs some refactoring. The most important thing, that the map must hold a pointer to the notifier, however it should not be attached.

I see only one problem with the concept, the detection and the chance of memory leaks could become greater. If there is a registered static array map and the graph is altered during its existence, then some items will not constructed or destructed in the static map. I think, if we make possible to use static maps, then we should provide some tools(for example debug macro) to detect such bugs.

[Alpar Juttner]

Replying to deba:

Could anyone familiar with the map internals estimate how difficult is to implement it?

In my opinion, the extra parameter is a good solution. However, the thread-safe map construction must be solved somehow (not just the static ones).

In theory, yes, it would be a nice feature.

My feeling however, that this simple static map idea covers virtually all practical use-cases.

I see only one problem with the concept, the detection and the chance of memory leaks could become greater. If there is a registered static array map and the graph is altered during its existence, then some items will not constructed or destructed in the static map.

I don't think it increases the risk significantly. If you alter a graph behind any existing map based data structure, the chance is high that it will be ruined without explicitly updating the maps, even if the maps are dynamic.

I think, if we make possible to use static maps, then we should provide some tools(for example debug macro) to detect such bugs.

[Balazs Dezso]

I have one more problem with this algorithm. Currently, most of the algorithm classes are able to run several times, and between the executions you can modify the graph. I feel, with this modification we lost this opportunity.

[Alpar Juttner]

Replying to deba:

I have one more problem with this algorithm. Currently, most of the algorithm classes are able to run several times, and between the executions you can modify the graph. I feel, with this modification we lost this opportunity.

Could you list some concrete tools where this might be a problem?

[Balazs Dezso]

Replying to alpar:

Replying to deba:

I have one more problem with this algorithm. Currently, most of the algorithm classes are able to run several times, and between the executions you can modify the graph. I feel, with this modification we lost this opportunity.

Could you list some concrete tools where this might be a problem?

For example in the price and repair algorithms. They start with a small sparse graph, and if the generated solution is not valid for the whole graph, then it is extended with the violating nodes, arcs or edges.

This idea can be used for shortest path, matching, constrained shortest path algorithms.

[Alpar Juttner]

Replying to deba:

Replying to alpar:

Replying to deba: Could you list some concrete tools where this might be a problem?

For example in the price and repair algorithms.

I mean which current tools of LEMON tool would loose flexibility because of using static maps?

I.e. do we indeed have tools that enable changing the graph between two executions, but rely only on automatic extension of maps with no manual initialization at the beginning of the execution?

[Balazs Dezso]

Replying to alpar:

Replying to deba:

Replying to alpar:

Replying to deba: Could you list some concrete tools where this might be a problem?

For example in the price and repair algorithms.

I mean which current tools of LEMON tool would loose flexibility because of using static maps?

I.e. do we indeed have tools that enable changing the graph between two executions, but rely only on automatic extension of maps with no manual initialization at the beginning of the execution?

The initialization has two steps in most cases, the first step allocates memory(maps and other data) for the algorithm, the second step assigns initial values to the allocated maps. The memory allocations are made once per algorithm class instance, while the initial data setting is made per execution.

The problem is that the proposed issue would change the algorithms to use the static maps (the initial example of the issue).

Let see the following example:

  ListDigraph digraph;
  ListDigraph::ArcMap<double> length(digraph);
  buildInitialDigraph(digraph, length);

  Dijkstra<ListDigraph, ListDigraph::ArcMap<double> > dijkstra(digraph, length);
  while (true) {
    dijkstra.run(s);
    if (checkPricingAndExtendDigraph(digraph, length)) break;
}

This algorithm works now well, because the maps are extended. If the new approach would be introduced, then some workaround have to be find:

• We should use separate dijkstra instances for every phases.
• Every map used by the Dijkstra algorithm have to be specified directly.
• Parameter for the algorithms, that the maps have to be static or not.

[Alpar Juttner]

Replying to deba:

This algorithm works now well, because the maps are extended. If the new approach would be introduced, then some workaround have to be find:

• We should use separate dijkstra instances for every phases.
• Every map used by the Dijkstra algorithm have to be specified directly.
• Parameter for the algorithms, that the maps have to be static or not.

What about the fourth (and most natural) solution?

• Dijkstra<>::run() extends the map manually if need be.

[Balazs Dezso]

Replying to alpar:

Replying to deba:

This algorithm works now well, because the maps are extended. If the new approach would be introduced, then some workaround have to be find:

• We should use separate dijkstra instances for every phases.
• Every map used by the Dijkstra algorithm have to be specified directly.
• Parameter for the algorithms, that the maps have to be static or not.

What about the fourth (and most natural) solution?

• Dijkstra<>::run() extends the map manually if need be.

How does the Dijkstra know which items are added to the graph? It is not trivial question. The current map implementations assume that the maps are not changed without they are notified about it. Because the ArrayMaps constructs the map values as the items added to the graph, and it knows about each graph alteration, it can be kept consistent. But if we do not track which items are changed, then we have to find all the changes. I do not know better solution, than an extra bool flag for each value in the map. But it needs extra space and time. Is it possible to do it better?

[Alpar Juttner]

Replying to deba:

How does the Dijkstra know which items are added to the graph? It is not trivial question. The current map implementations assume that the maps are not changed without they are notified about it. Because the ArrayMaps constructs the map values as the items added to the graph, and it knows about each graph alteration, it can be kept consistent. But if we do not track which items are changed, then we have to find all the changes. I do not know better solution, than an extra bool flag for each value in the map. But it needs extra space and time. Is it possible to do it better?

I think it is. It is enough to extend the storage array of the map to the highest ID and construct the elements of the interval of new values. I.e. a static map would always contain a continuous range of initialized elements. The destructors are only called when the whole map is deallocated. This approach can cause problem if

• the constructor or the destructor of the items have side-effects or
• the algorithm needs a freshly initialized (by the default constructor) objects for the newly added item.

I don't think either of them would be a real problem in case of the standard algorithms.

[Balazs Dezso]

I think it is. It is enough to extend the storage array of the map to the highest ID and construct the elements of the interval of new values. I.e. a static map would always contain a continuous range of initialized elements. The destructors are only called when the whole map is deallocated. This approach can cause problem if

• the constructor or the destructor of the items have side-effects or
• the algorithm needs a freshly initialized (by the default constructor) objects for the newly added item.

I don't think either of them would be a real problem in case of the standard algorithms.

You say that this is not a problem for standard algorithms, but I think the STATIC maps can be used also in user codes. So we cannot check only how they are used in standard algorithms, because the user can use them directly. The different behavior can be misleading.

I think, another approach would solve this problem cleaner and it could be used more generally, because the user should not care about the concurrent modifications.

[Alpar Juttner]

Replying to deba:

I think it is. It is enough to extend the storage array of the map to the highest ID and construct the elements of the interval of new values. I.e. a static map would always contain a continuous range of initialized elements. The destructors are only called when the whole map is deallocated. This approach can cause problem if

• the constructor or the destructor of the items have side-effects or
• the algorithm needs a freshly initialized (by the default constructor) objects for the newly added item.

I don't think either of them would be a real problem in case of the standard algorithms.

You say that this is not a problem for standard algorithms, but I think the STATIC maps can be used also in user codes.

Of course yes, assuming they know the limitations.

So we cannot check only how they are used in standard algorithms, because the user can use them directly.

I don't understand what are you complaining about.

The different behavior can be misleading.

Everything can be misleading.

I think, another approach would solve this problem cleaner and it could be used more generally, because the user should not care about the concurrent modifications.

They are independent. A locking mechanism might be necessary sometimes, but in 99.9% of the cases it is a completely unnecessary extra hassle. Static maps cover this 99.9%, while #223 does so with the remaining 0.01%.

Btw. static maps has an additional benefit - using them in the algorithm can cause significant speedup in graph modifying operations if there are more algorithms preallocated to the graph.

[Balazs Dezso]

Replying to alpar:

They are independent. A locking mechanism might be necessary sometimes, but in 99.9% of the cases it is a completely unnecessary extra hassle. Static maps cover this 99.9%, while #223 does so with the remaining 0.01%.

Btw. static maps has an additional benefit - using them in the algorithm can cause significant speedup in graph modifying operations if there are more algorithms preallocated to the graph.

I think, the performance improvements of the static maps cannot be significant in any real applications. In addition, one solution have to be enough for the concurrent map addition problem, and I suggest to use only the locking mechanism. It has more advantages:

• This works always when the static map concept works.
• The user should not care about which map should be used in a place. In my opinion this is the more important reason to choose the locking approach. I think if a user want to write an algorithm for a singlethreaded program, then he may use normal maps (non static). If he want to reuse the algorithm in a multithreaded program, then he have to intrusively modify his old code.
• I think, the implementation of lock based solution is easier also.

[Alpar Juttner]

Replying to deba:

I think, the performance improvements of the static maps cannot be significant in any real applications.

They really can be. Just think of a graph which is used by some algorithms, say by just one Dfs, one Dijkstra, and one MinCostArborescense?`. This means we already have 11 nodemaps and 2 arcmaps attached to the graph, not counting the input of these algs. It means the same amount of virtual function calls at each node/arc addition/deletion.

In addition, one solution have to be enough for the concurrent map addition problem,

I try to argue that it isn't.

and I suggest to use only the locking mechanism. It has more advantages:

• This works always when the static map concept works.
• The user should not care about which map should be used in a place.

In fact, he should. If Dijsktra used static map, it was thread-safe out-of-box (because e.g. ListGraph?+static maps were thread-safe). With the locking approach, the default tools were not thread-safe by default, but you have to use a specialized version of the tools.

In my opinion this is the more important reason to choose the locking approach. I think if a user want to write an algorithm for a single threaded program, then he may use normal maps (non static). If he want to reuse the algorithm in a multithreaded program, then he have to intrusively modify his old code.

I consider the following use-case: the user wants to run 8 instances of Dijkstra on the same graph. She don't write any shared data thus don't want to care about locking.

• I think, the implementation of lock based solution is easier also.

It depends if you count with the development and maintenance of the various lock implementations. If you do, than implementing the lock model is far more complex.