COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 9 years ago

#309 closed task (done)

Benchmark tests for graphs

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.2 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

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.

Attachments (9)

benchmark_graphs.cpp (5.9 KB) - added by Peter Kovacs 9 years ago.
309-listdigraph-arcit-c6157e490d8c.patch (1.5 KB) - added by Peter Kovacs 9 years ago.
results-main.txt (920 bytes) - added by Peter Kovacs 9 years ago.
results-3fe3c838a89e.txt (922 bytes) - added by Peter Kovacs 9 years ago.
results-c6157e490d8c.txt (925 bytes) - added by Peter Kovacs 9 years ago.
benchmark_graphs.2.cpp (7.5 KB) - added by Peter Kovacs 9 years ago.
A nerw version of the benchmark test file
results-staticdigraph-1-cf360f758f25.txt (313 bytes) - added by Peter Kovacs 9 years ago.
results-staticdigraph-2-a3de05c56e7e.txt (313 bytes) - added by Peter Kovacs 9 years ago.
results-afad5d01ef8e.txt (1.2 KB) - added by Peter Kovacs 9 years ago.

Download all attachments as: .zip

Change History (18)

Changed 9 years ago by Peter Kovacs

Attachment: benchmark_graphs.cpp added

Changed 9 years ago by Peter Kovacs

Changed 9 years ago by Peter Kovacs

Attachment: results-main.txt added

Changed 9 years ago by Peter Kovacs

Attachment: results-3fe3c838a89e.txt added

Changed 9 years ago by Peter Kovacs

Attachment: results-c6157e490d8c.txt added

comment:1 Changed 9 years ago by Peter Kovacs

Status: newassigned

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 9 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 9 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 Changed 9 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 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. :)

comment:5 in reply to:  4 Changed 9 years ago by 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.

Changed 9 years ago by Peter Kovacs

Attachment: benchmark_graphs.2.cpp added

A nerw version of the benchmark test file

Changed 9 years ago by Peter Kovacs

Changed 9 years ago by Peter Kovacs

Changed 9 years ago by Peter Kovacs

Attachment: results-afad5d01ef8e.txt added

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

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

Resolution: done
Status: assignedclosed

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.

Note: See TracTickets for help on using tickets.