|
|
Boost Testing : |
From: Vladimir Prus (ghost_at_[hidden])
Date: 2005-09-28 07:56:16
Douglas Gregor wrote:
>
> On Sep 23, 2005, at 6:54 AM, Martin Wille wrote:
>> For the records, the .run file contains:
>>
>> Generating graph...10000 vertices, 100000 edges.
>> Running Dijkstra's with binary heap...4.14 seconds.
>> Running Dijkstra's with relaxed heap...0.81 seconds.
>> Speedup = 5.11111.
>
> Holy moly! I never expected to see the relaxed heap outperform the
> binary heap by 5x . Maybe it was worth the effort after all :)
Looks cool. However, I'd suggest trying the test several times, and probably
in reverse order. Who knows, maybe all of cache misses on this huge graph
are inside first call of the algorithm?
Ehm... on my system the speedup is never larger then 1.4. And it appears to
be smaller if the order of calls in reversed. Guess the only way to know
for sure is to find completely unloaded machine somewhere ;-)
- Volodya