Opened 11 years ago

Closed 11 years ago

# Benchmark tests for graphs

Reported by: Owned by: Peter Kovacs Peter Kovacs major LEMON 1.2 release core hg main

### Description

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.

### comment:1 Changed 11 years ago by Peter Kovacs

Status: new → assigned

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.

### comment:2 Changed 11 years ago by 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.

### comment:3 Changed 11 years ago by 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?

### comment:4 follow-up:  5 Changed 11 years ago by 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 `ArcIt`s and `OutArcIt`s referencing the changed arc remain valid. However `InArcIt`s are invalidated. So if we consider this behavior as a part of the interface, then the attached patch is actually a bug fix. :)

### comment:5 in reply to:  4 Changed 11 years ago by Peter Kovacs

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

### Changed 11 years ago by Peter Kovacs

A nerw version of the benchmark test file

### comment:6 Changed 11 years ago by 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.

### comment:7 follow-up:  8 Changed 11 years ago by Alpar Juttner

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

### comment:8 in reply to:  7 ; follow-up:  9 Changed 11 years ago by Peter Kovacs

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.

### comment:9 in reply to:  8 Changed 11 years ago by Alpar Juttner

Resolution: → done assigned → closed