]> git.pond.sub.org Git - empserver/commit
Compute distribution paths center by center
authorMarkus Armbruster <armbru@pond.sub.org>
Mon, 21 Feb 2011 22:13:07 +0000 (23:13 +0100)
committerMarkus Armbruster <armbru@pond.sub.org>
Tue, 12 Apr 2011 19:51:31 +0000 (21:51 +0200)
commitbbd6e9182f9b7fd1aeefa71be2f087dee32c2a26
treedf9805775a2613695ae581a7ba6f9fc0cc047fb2
parentbf97fa9c9c822cf007c13f2bc0f2ef8f4dd2d634
Compute distribution paths center by center

This way, we compute all distribution paths from the same center in
one go, and thus fully exploit the fast multiple paths from same
source capability of Dijkstra's algorithm.

Sorting by dist center increases the average length of runs from 4.5
to 73 for my continental test case, and from 3 to 10 for my island
test case.

Compared to the commit before the previous one, distribution path
assembly runs more than 40 times faster for my continental test case,
and more than 5 times faster for my island test case.

The new path finder now runs my continental test case more than 30
times faster than the old A*, and the island test case more than 6
times, in a fraction of the memory.  This makes the continental
updates run 3.5 times faster, and the island updates 6% faster.
Distribution path assembly no longer dominates the continental
update's run time: it takes less than 10% instead of more than 70%.

In a sense, this is the path cache done right.
src/lib/update/finish.c