Benchmark tests for graphs

[Peter Kovacs]

I made some basic benchmark tests for ListDigraph and SmartDigraph to help on investigating some changes in their implementation and to compare the StaticDigraph structure to them when it is ported (see #68).

This could be a small step in a general benchmarking, see #33.

[Peter Kovacs]

The first attachment​ is the benchmark file. It builds two instances of ListDigraph and SmartDigraph representing the same random digraph and tests iterations on them. The first graph instances are built using random arc order, while the second instances are built using lexicographical arc order.

results-main.txt​ contains the results for the main repository, namely [9f529abcaebf]. It shows such results that could be expected. Note that using lexicographical arc order both the building and the iterations are faster for both graph structures, especially for the OutArcIt iterations.

results-3fe3c838a89e.txt​ contains the results for the changeset [3fe3c838a89e], see #3. It shows that storing the node and arc number in ListDigraph results in a negligible difference in the time of graph building. Actually the differences are under 1 percent, which is about the measuring error. Moreover if there were node/arc maps, then the relative difference would be even smaller. Thus I suggest applying this changeset. (Note that it allows O(1) item counting instead of O(n).)

Another old idea is to modify the implementation of ListDigraph::ArcIt. Currently it is based on in-arc iteration, while ListGraph::ArcIt is based on out-arc iteration. I see now reason for keeping this difference, moreover out-arc iteration could be typically faster, since graphs are typically built in a way that the outgoing arcs of a certain node are near to each other. At least, it seems to be more typical then for incoming arcs. The attached patch​ [c6157e490d8c] modifies the implementation and results-c6157e490d8c.txt​ shows the results of this modification. The ArcIt iteration for the sorted case became much faster, while all other results are the same.

All the test results were obtained using parameters n = 100000, m = 1000000 on lime.cs.elte.hu with gcc 4.1.0, -O2 optimization. -O3 was also tested and it showed similar relations.

[Peter Kovacs]

Another old question is to use separate vectors instead of vectors of structs in these graph classes, but I think, more extensive tests would be needed for arguing this question.

[Peter Kovacs]

An alternative implementation for NodeIt and ArcIt in List(Di)graph could be the following: instead of using the links between the nodes and arcs, just go along all the items stored in the corresponding vector and leave out the items that are not valid (that were deleted before). It could be much faster for the cases when there are relatively few slots in the vectors that are not used. On the other hand it would be slower if the graph is much smaller than it was once before. What do you think? Would it worth to try this solution? Or should we accept the huge difference between the efficiency of ListDigraph::NodeIt/ArcIt and SmartDigraph::NodeIt/ArcIt as a natural result of the flexible implementation?

[Peter Kovacs]

modify the implementation of ListDigraph::ArcIt.

Note that the current version of the doc describes this modified implementation. In the doc of changeTarget() there is a note saying: The ArcIts and OutArcIts referencing the changed arc remain valid. However InArcIts are invalidated. So if we consider this behavior as a part of the interface, then the attached patch is actually a bug fix. :)

[Peter Kovacs]

Replying to kpeter:

Note that the current version of the doc describes this modified implementation. In the doc of changeTarget() there is a note saying: The ArcIts and OutArcIts referencing the changed arc remain valid. However InArcIts are invalidated. So if we consider this behavior as a part of the interface, then the attached patch is actually a bug fix. :)

See also: #311.

[Peter Kovacs]

A nerw version of the benchmark test file

[Peter Kovacs]

I attached a new version of the benchmark test file. It also tests StaticDigraph (see #68). The first column shows the results for the iterator interfaces and the second column shows the results for the basic interfaces.

I also attached benchmark results for StaticDigraph. The first file​ is for changeset [cf360f758f25] (the port of the structure) and the second file​ is for changeset [a3de05c56e7e]. The difference shows that [a3de05c56e7e] made the basic iteration about 15 percent slower, but it did not modify anything other (since this structure has a special OutArcIt implementation).

The third file​ contains results for all structures using changeset [afad5d01ef8e] (the last changeset in #68). It shows that iteration using InArcIt and especially OutArcIt of StaticDigraph is really much faster than both SmartDigraph and ListDigraph, thus it seems to be important to have such implementation.

[Alpar Juttner]

Let's take a deep breath and collect all the existing benchmarks into a dedicated repository.

[Peter Kovacs]

Replying to alpar:

Let's take a deep breath and collect all the existing benchmarks into a dedicated repository.

I did it, at least for my own test programs (except for min cost flow tests, that haven't been ported yet). See Contribution Projects.

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

Let's take a deep breath and collect all the existing benchmarks into a dedicated repository.

I did it, at least for my own test programs (except for min cost flow tests, that haven't been ported yet). See Contribution Projects.

That's great!

Let me move the discussion about the benchmark repo in general to #33, while the questions of the results of these specific tests to #3, thus close this ticket.