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: |
Attachments (9)
Change History (18)
Changed 9 years ago by
Attachment: | benchmark_graphs.cpp added |
---|
Changed 9 years ago by
Attachment: | 309-listdigraph-arcit-c6157e490d8c.patch added |
---|
Changed 9 years ago by
Attachment: | results-main.txt added |
---|
Changed 9 years ago by
Attachment: | results-3fe3c838a89e.txt added |
---|
Changed 9 years ago by
Attachment: | results-c6157e490d8c.txt added |
---|
comment:1 Changed 9 years ago by
Status: | new → assigned |
---|
comment:2 Changed 9 years ago by
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
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 9 years ago by
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 Changed 9 years ago by
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: TheArcIt
s andOutArcIt
s referencing the changed arc remain valid. HoweverInArcIt
s 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
Attachment: | benchmark_graphs.2.cpp added |
---|
A nerw version of the benchmark test file
Changed 9 years ago by
Attachment: | results-staticdigraph-1-cf360f758f25.txt added |
---|
Changed 9 years ago by
Attachment: | results-staticdigraph-2-a3de05c56e7e.txt added |
---|
Changed 9 years ago by
Attachment: | results-afad5d01ef8e.txt added |
---|
comment:6 Changed 9 years ago by
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 9 years ago by
Let's take a deep breath and collect all the existing benchmarks into a dedicated repository.
comment:8 follow-up: 9 Changed 9 years ago by
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 Changed 9 years ago by
Resolution: | → done |
---|---|
Status: | assigned → closed |
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.
The first attachment is the benchmark file. It builds two instances of
ListDigraph
andSmartDigraph
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, whileListGraph::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. TheArcIt
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
onlime.cs.elte.hu
withgcc 4.1.0
,-O2
optimization.-O3
was also tested and it showed similar relations.