ListGraph should store/update the number of edges and nodes

[Alpar Juttner]

Counting the number of edges and nodes is a frequent graph operation. Now, it takes linear time to get these values. Instead we might store these values and update them at every edge/node addition and deletion.

Of course this change would slow down these operations a bit.

This ticket is a copy of report #8 of the old bug tracking system. It refers to svn trunk -r2460.

[Peter Kovacs]

Replying to alpar:

Counting the number of edges and nodes is a frequent graph operation. Now, it takes linear time to get these values. Instead we might store these values and update them at every edge/node addition and deletion.

It is still relevant in [3fb8ed1322de]. Moreover SmartGraph also needs such improvement, since it doesn't have the needed tags and functions, although I think it would be easy to implement.

[Alpar Juttner]

Replying to kpeter:

It is still relevant in [3fb8ed1322de]. Moreover SmartGraph also needs such improvement, since it doesn't have the needed tags and functions, although I think it would be easy to implement.

For SmartGraph we definitely want O(1) node/edge counting.

For ListGraph it is a question. It increases a bit the memory footprint (well, the increment is negligible), and makes the edge addition/deletion a bit slower. I cannot tell how big this effect would be. I think we can wait with this until we have a reliable benchmarking system.

[Peter Kovacs]

Replying to alpar:

For SmartGraph we definitely want O(1) node/edge counting.

I know, and I thought that it is true for both SmartGraph and SmartDigraph, but for the former one it isn't implemented yet.

For ListGraph it is a question.

I think it would be much better. Item counting operations are used really frequently (even by algorithms). And since alterations are (relatively) slow operations (modify the containers, indices, notifying all observers etc.) compared to a single assignment of type int, so I think this change would worth to make.

For example, when I implemented algorithms I queried the number of nodes and edges/arcs only once and stored it just because I would like to be efficient even for List(Di)Graph. It is not convenient.

[Alpar Juttner]

Replying to kpeter:

For example, when I implemented algorithms I queried the number of nodes and edges/arcs only once and stored it just because I would like to be efficient even for List(Di)Graph. It is not convenient.

Yes, I know this. The question is if we want to require that these queries are O(1) for _all_ graphs?

• If yes, then these query functions could/should be the members of the graph classes.
• If not, then a generic algorithm cannot depend on this property.

[Peter Kovacs]

Replying to alpar:

Yes, I know this. The question is if we want to require that these queries are O(1) for _all_ graphs?

Definitely not. Think of the various adaptors implemented in the 0.x series (and we want to have them in the 1.x series as well). E.g. in the case of sub graph adaptors and ResGraphAdaptor I think it could not be implemented (or would be very difficult and/or inefficient). Although these adaptors are very important.

With this observation I aswered my own question: we should not call count functions many times in a generic algorithm, but not because of List(Di)Graph, even bacause of adaptors. :)

However I think it would be important to have O(1) count functions in all graph implementations that are not adaptors. For example, in STL all containers are expected to have an O(1) size() function, even lists, sets etc., since it is an important and frequent operation.

• If yes, then these query functions could/should be the members of the graph classes.

Think of adaptors again.

• If not, then a generic algorithm cannot depend on this property.

Yes, it is true.

[Alpar Juttner]

Replying to kpeter:

For example, in STL all containers are expected to have an O(1) size() function, even lists, sets etc., since it is an important and frequent operation.

I don't know what do you mean by "expected", but std::list::size() are recommended but not required to be O(1) by the standard.

[Peter Kovacs]

Replying to alpar:

I don't know what do you mean by "expected", but std::list::size() are recommended but not required to be O(1) by the standard.

I didn't know that, I just expected what is recommended.

However it is exactly the same concept that I would like to follow in LEMON: O(1) item counting is not required for all graph types (e.g. adaptors won't support it), but it is strongly recommended for all basic graph implementations. They are much more heavy-weight structures than e.g. a single std::list, thus the relative overhead would be much smaller.

[Peter Kovacs]

Replying to kpeter:

I know, and I thought that it is true for both SmartGraph and SmartDigraph, but for the former one it isn't implemented yet.

[a7e8ad460d66] adds missing tags and functions for item counting in SmartGraph.

[Peter Kovacs]

[3fe3c838a89e] adds support for constant time item counting in ListDigraph and ListGraph.

[Alpar Juttner]

Replying to kpeter:

[3fe3c838a89e] adds support for constant time item counting in ListDigraph and ListGraph.

I would like to see a detailed running time evaluation, before putting this patch into the main branch.

The question is important, but in my opinion, it is not of the highest priority. Therefore I remove it from the 1.1 milestone. (Which does not mean that this change cannot get into the 1.1 release. If a satisfactory running time analyses will have been done before the release, we will include this path into the release.)

[Alpar Juttner]

Additional benchmarking results can be found at #309.

[Peter Kovacs]

Replying to alpar:

I would like to see a detailed running time evaluation, before putting this patch into the main branch.

What kind of "detailed running time evaluation" would you like to see?

Isn't it clear enough (with virtually no tests) that a simple ++ or -- operation for an int variable cannot make a noticeable difference in the running time of such functions that contain 8-10 assignments and 2-3 ifs, each of which performs at least one operator[] for a vector? And keep in mind, that if there were node/arc maps (that's the typical use case), then the relative difference would be even smaller! I think it is clear. However I made some tests that validated this assumption. Of course, many other tests could be performed, but that could be an endless story. Why don't we make tests in which countNodes() and/or countArcs() is also used?

If constant time item counting is expected for simple data structures like std::list, then it seems to be more than natural to expect this for List(Di)graph as well, since the relative overhead must be much smaller.

I suggest to focus on the huge advantage of this modification rather than this captious discussion about its negligible overhead.

[Alpar Juttner]

Replying to kpeter:

[Peter Kovacs]

I made some tests again and I cannot detect measureable overhead of this proposal (which is quite obvious indeed). Therefore, I see no reason to refuse or postpone it again. I can only repeat my previous reasoning.

[Alpar Juttner]

Replying to kpeter:

I made some tests again and I cannot detect measureable overhead of this proposal (which is quite obvious indeed). Therefore, I see no reason to refuse or postpone it again. I can only repeat my previous reasoning.

This, and all other tickets possibly affecting the performance of the core tools of LEMON are awaiting to a satisfactory solution to #33.

[Peter Kovacs]

Replying to alpar:

This, and all other tickets possibly affecting the performance of the core tools of LEMON are awaiting to a satisfactory solution to #33.

That's what I would like to confirm: this modification does not cause a measurable overhead. It is so obvious, but I validated it in various tests. So it is not performance issue! It is much more about natural requirements/expectations.

I see your reasons about pushing #33, but to tell the truth, I don't think that a comprehensive and satisfactory benchmark system will be realized in a reasonable time (e.g. a few years). I do find it a cumbersome policy to strictly bound this simple but important decision to such a vague task.

[Alpar Juttner]

Replying to kpeter:

I see your reasons about pushing #33, but to tell the truth, I don't think that a comprehensive and satisfactory benchmark system will be realized in a reasonable time (e.g. a few years). I do find it a cumbersome policy to strictly bound this simple but important decision to such a vague task.

Short answer:

Then, we must wait a few years to have this change accepted.

Long answer:

Firstly, it requires no more than a week of work of a single person to develop the core of an appropriate benchmarking tool. Forecasting that it won't be done within a few years is not only stupid, but also counterproductive, demoralizing and gives an overall bad reputation to the project.

Secondly, this kind of decision should not be based on personal trust, but on well documented, reproducible and reliable tests. None of the tests I can see here in the ticket are either well documented or reproducible, therefore none of them are reliable.

I admit in case of this ticket the situation might be pretty clear, therefore the question is matter of principle in some sense. BUT the question is whether or not we want opt for high standards in our developing process. If yes, it means we must insist on them in all cases and can't make random exceptions.

[Peter Kovacs]

Replying to alpar:

Short answer:

Then, we must wait a few years to have this change accepted.

Long answer:

Firstly, it requires no more than a week of work of a single person to develop the core of an appropriate benchmarking tool. Forecasting that it won't be done within a few years is not only stupid, but also counterproductive, demoralizing and gives an overall bad reputation to the project.

I must refuse your rude words (stupid, etc.).

1. In the last 2-3 years, it was me who made tha majority of benchmark test around LEMON (see e.g. ​http://lime.cs.elte.hu/~kpeter/hg/hgwebdir.cgi/lemon-benchmark/) So I have some experiances about it. And I must say that it is not an easy and agreeable work. The only sure thing is that however hard you try to make correct benchmarks, they can still be criticized.
2. Therefore, I find it extremely difficult to build a benchmark system you are talking about in #33, which could be accepted by the LEMON developers as comprehensive and correct in _all_ aspect to rely on about design decisions. Not to mention the actual testing on various computers using different compilers. It is much more than a week.
3. We have plenty of tasks that are much more important (e.g. porting, multi-thread support, etc.).
4. LEMON currently has only a few stable developers. That is why all releases were delayed. Unfortunatelly, I'm sure that I won't be able to realize #33, and I will have much less time for core development in the future. Unless you find a student directly for this task, I'm uncertain about who will do this.

Secondly, this kind of decision should not be based on personal trust, but on well documented, reproducible and reliable tests. None of the tests I can see here in the ticket are either well documented or reproducible, therefore none of them are reliable.

The tests are reproductible, they can be found in this repository:
​http://lime.cs.elte.hu/~kpeter/hg/hgwebdir.cgi/lemon-benchmark/

However, I regard this ticket as a proposal of fixing a bad design decision. If it is widely expected for a simple linked list structure that it knows its length, then it is more than a natural requirement for Lis(Di)graph. As I mentioned several times, it is NOT a perforamnce issue!

I admit in case of this ticket the situation might be pretty clear, therefore the question is matter of principle in some sense.

That's what I say...

BUT the question is whether or not we want opt for high standards in our developing process. If yes, it means we must insist on them in all cases and can't make random exceptions.

BUT we mustn't make such an inexplicably huge argument about the imaginary performance overhead of a single increment or decrement opertaion vs several vector access operations and a few if statements (not to mention the typical case of also maintaining maps) and totally forgeting the conceptual reasons and the dominant advantage and of this proposal. It's nonsense. I give it up.

[Peter Kovacs]

I'm sorry for my vehement comments. I hope I was wrong, and a "satisfactory solution to #33" will be realized and the necessary experiments will be conducted in the near future. Especially, if they are not required to be comprehensive. I just thought that they are.