[heap] A performance test and some questions
Hi Tim, Attached is a performance test that tries to immitate the priority_queue usage a fast marching algorithm. I actually wrote this performance test in 2005 while tuning a heap implementation (TSequentialHeap, not attached) used by a "real" fast marching algorithm. I tried to adapt this test for Boost.Heap now, but it looks like I haven't yet found out how to use the mutable heap interface optimally for this task. The most obvious symptom of this are the performance numbers I get when executing the performance test: $ g++ heaptest.cpp -O2 -DNDEBUG -Iboost_heap-449f378 -I/cygdrive/c/nobackup/boost_release -DHAVE_SEQ_HEAP $ ./a.exe Sanity Check Small TStaticHeap Test : passed Linear TStaticHeap Test : passed March TStaticHeap Test : passed Small TUglyHeap Test : passed Linear TUglyHeap Test : passed Small TSequentialHeap Test : passed Linear TSequentialHeap Test : passed March TSequentialHeap Test : passed Small b_heap Test : passed Linear b_heap Test : passed March b_heap Test : passed Small binomial_heap Test : passed Linear binomial_heap Test : passed March binomial_heap Test : passed Small d_ary_heap Test : passed Linear d_ary_heap Test : passed March d_ary_heap Test : passed Small fibonacci_heap Test : passed Linear fibonacci_heap Test : passed March fibonacci_heap Test : passed Performance Check for Linear Forward 297 ticks and 15952569 compares for TStaticHeap 296 ticks and 15952569 compares for TStaticHeap 95 ticks and 5495826 compares for TSequentialHeap 78 ticks and 5495826 compares for TSequentialHeap 999 ticks and 20929621 compares for b_heap 1032 ticks and 20929621 compares for b_heap 875 ticks and 7012461 compares for binomial_heap 906 ticks and 7012461 compares for binomial_heap 797 ticks and 16164008 compares for d_ary_heap 812 ticks and 16164008 compares for d_ary_heap 688 ticks and 5637046 compares for fibonacci_heap 688 ticks and 5637046 compares for fibonacci_heap Performance Check for Linear Backward 297 ticks and 22976046 compares for TStaticHeap 328 ticks and 22976046 compares for TStaticHeap 94 ticks and 5225203 compares for TSequentialHeap 93 ticks and 5225203 compares for TSequentialHeap 1125 ticks and 31971032 compares for b_heap 1125 ticks and 31971032 compares for b_heap 688 ticks and 5636875 compares for binomial_heap 718 ticks and 5636875 compares for binomial_heap 813 ticks and 19465560 compares for d_ary_heap 828 ticks and 19465560 compares for d_ary_heap 703 ticks and 5866500 compares for fibonacci_heap 703 ticks and 5866500 compares for fibonacci_heap Performance Check for March 1672 ticks and 93489201 compares for TStaticHeap 1734 ticks and 93489201 compares for TStaticHeap 921 ticks and 53507489 compares for TSequentialHeap 907 ticks and 53507489 compares for TSequentialHeap 5625 ticks and 121120384 compares for b_heap 5563 ticks and 121120384 compares for b_heap 6312 ticks and 73639894 compares for binomial_heap 6265 ticks and 73639894 compares for binomial_heap 4391 ticks and 92667621 compares for d_ary_heap 4375 ticks and 92667621 compares for d_ary_heap 4000 ticks and 39902719 compares for fibonacci_heap 4078 ticks and 39902719 compares for fibonacci_heap $ We can see that "fibonacci_heap" has always more than a factor two fewer comparisons than TStaticHeap (a simple text book binary heap implementation used as reference), but is always more than a factor two slower than TStaticHeap. And "fibonacci_heap" seems to be the fastest heap from Boost.Heap in this performance test, while TStaticHeap is still a factor two slower than the tuned TSequentialHeap. I guess the problem here is that I found no way around using "std::pair<value_type, value_type*>" as value_type for the heap, because I need to know the position in the bulk of the point with the smallest arrival time. But Dijkstra algorithm should be no different, I have to know the vertex in the graph with the shortest path. Independent of this, I also have a totally different question. There is a FIXME in line 233 of the test program, and if the following line is commented out, fibonacci_heap shows undefined behavior, ranging from segmentation fault to failing the Sanity Check. Here is the code surrounding the FIXME: std::size_t Set_Size ( std::size_t lSize_p) { if (!m_tHeap.empty()) { exit(1); } // FIXME: I don't understand why the fibonacci_heap shows undefined behavior if clear() is not called. m_tHeap.clear(); m_tBackpointer.clear(); m_tBackpointer.resize(lSize_p); return lSize_p; } You can see that the heap is actually empty, so why is calling clear() on the empty heap important in case of a fibonacci_heap? Regards, Thomas
hi thomas,
We can see that "fibonacci_heap" has always more than a factor two fewer comparisons than TStaticHeap (a simple text book binary heap implementation used as reference), but is always more than a factor two slower than TStaticHeap. And "fibonacci_heap" seems to be the fastest heap from Boost.Heap in this performance test, while TStaticHeap is still a factor two slower than the tuned TSequentialHeap.
i breefly looked into your heap implementation and it seems to follow a different design than boost.heap ... actually more similar to the implementation of the heaps that are currently used in bgl. this probably explains the performance difference.
I guess the problem here is that I found no way around using "std::pair<value_type, value_type*>" as value_type for the heap, because I need to know the position in the bulk of the point with the smallest arrival time. But Dijkstra algorithm should be no different, I have to know the vertex in the graph with the shortest path.
you mean std::pair<value_type, handle_type> in order to store the handle inside? this may be a hole in the API. at the moment it is possible to convert an iterator to a handle (s_handle_from_iterator), so possibly i should add an handle_type s_handle_from_reference(reference); to all mutable heaps ...
Independent of this, I also have a totally different question. There is a FIXME in line 233 of the test program, and if the following line is commented out, fibonacci_heap shows undefined behavior, ranging from segmentation fault to failing the Sanity Check. Here is the code surrounding the FIXME:
will have a look, what is going wrong here ... tim
Tim Blechmann wrote:
Thomas Klimpel wrote:
I guess the problem here is that I found no way around using "std::pair<value_type, value_type*>" as value_type for the heap, because I need to know the position in the bulk of the point with the smallest arrival time. But Dijkstra algorithm should be no different, I have to know the vertex in the graph with the shortest path.
you mean std::pair<value_type, handle_type> in order to store the handle inside? this may be a hole in the API. at the moment it is possible to convert an iterator to a handle (s_handle_from_iterator), so possibly i should add an handle_type s_handle_from_reference(reference); to all mutable heaps ...
Oh, you probably assume too much ingenuity from my part. Perhaps it becomes clearer when I use typedefs: typedef value_type* bulk_ptr_type; typedef std::pair<value_type, bulk_ptr_type> heap_value_type; If I store the index into the (arrival time) bulk instead of the pointer, it would read typedef std::size_t bulk_index_type; typedef std::pair<value_type, bulk_index_type> heap_value_type; I have now read (and tried to understand) the similar question from Andrew Sutton with respect to Dijkstra's SP: <http://lists.boost.org/Archives/boost/2011/06/182381.php> (On a slightly unrelated note, I first also used his way to call "update", but that totally killed the performance (and compare count) of fibonacci_heap. I would suggest to remove this form of "update" at least from fibonacci_heap, and require calling "increase" or "decrease" when you have modified the priority "manually".) If I write his approach with typedefs, it would read for my case typedef value_type* bulk_ptr_type; typedef bulk_ptr_type heap_value_type; The other difference is that he stores the returned "handle_type" in a Map, while I store it in a separate bulk (which I called m_tBackpointer) of the same size as the (arrival time) bulk. (A similar bulk is implicitly also present when using TStaticHeap, but it is a part of the heap itself.) So Andrew Sutton's approach to use the mutable interface is not too different from mine, but will probably lead to even worse performance (because a "map" lookup seems to be worse than a "bulk" lookup). On the one hand, your proposed mutable interface seems to be quite "natural" for node based heaps. On the other hand, it looks like there is one more indirection than for a "straightforward" implementation of a "mutable" binary heap, where the heap "knows" the maximum number of different items that it has to manage.
reproduced and fixed the issue with the fibonacci heap ...
Nice. Regards, Thomas
I have now read (and tried to understand) the similar question from Andrew Sutton with respect to Dijkstra's SP: <http://lists.boost.org/Archives/boost/2011/06/182381.php>
(On a slightly unrelated note, I first also used his way to call "update", but that totally killed the performance (and compare count) of fibonacci_heap. I would suggest to remove this form of "update" at least from fibonacci_heap, and require calling "increase" or "decrease" when you have modified the priority "manually".)
That's only a viable solution if you have some a priori knowledge about which "direction" the value has changed with respect to the comparison operator. If you have an expression like this: x' = x + y; where x is the previous key and x' the new key--a possible implementation of edge relaxation. You still have to compare x and x' to determine which direction the change was in. Minimally, you'd have to check y to determine if it was less than 0, assuming the types of x, x', and y are numeric. Removing the update() method makes the user work harder. Increase and decrease are nice when you know that you can optimize. Andrew
That's only a viable solution if you have some a priori knowledge about which "direction" the value has changed with respect to the comparison operator. If you have an expression like this:
x' = x + y;
where x is the previous key and x' the new key--a possible implementation of edge relaxation. You still have to compare x and x' to determine which direction the change was in. Minimally, you'd have to check y to determine if it was less than 0, assuming the types of x, x', and y are numeric.
Indeed, I have to check this, if I want to use the interface where I can change the priority "manually". The issue here is that fibonacci_heap itself can no longer do this check, since the previous value is already gone when "update" is called. And it seems that this missing piece of information totally ruins the performance of fibonacci_heap. So if you want the convenience of "update" and don't care about performance, just use std::pair<priority_type, Vertex*> as value_type for the heap, and use the "normal" update function. This is still an order of magnitude faster than the performance that results from modifying the priority "manually" and just calling "update".
Removing the update() method makes the user work harder. Increase and decrease are nice when you know that you can optimize.
It's not that I want to optimize something here, I want to avoid a totally unnecessary pessimization. Because the normal user won't be aware of the consequences of this tiny bit of missing information for the performance of fibonacci_heap. Regards, Thomas
I have now read (and tried to understand) the similar question from Andrew Sutton with respect to Dijkstra's SP: <http://lists.boost.org/Archives/boost/2011/06/182381.php>
(On a slightly unrelated note, I first also used his way to call "update", but that totally killed the performance (and compare count) of fibonacci_heap. I would suggest to remove this form of "update" at least from fibonacci_heap, and require calling "increase" or "decrease" when you have modified the priority "manually".)
That's only a viable solution if you have some a priori knowledge about which "direction" the value has changed with respect to the comparison operator. If you have an expression like this:
x' = x + y;
where x is the previous key and x' the new key--a possible implementation of edge relaxation. You still have to compare x and x' to determine which direction the change was in. Minimally, you'd have to check y to determine if it was less than 0, assuming the types of x, x', and y are numeric.
Removing the update() method makes the user work harder. Increase and decrease are nice when you know that you can optimize.
btw, the fibonacci heap also provides an update_lazy with slightly different performance characteristics than update(), since it does not run a consolidation phase ... it mainly gives a better throughput at the costs of a worse worst-case performance ... tim
The other difference is that he stores the returned "handle_type" in a Map, while I store it in a separate bulk (which I called m_tBackpointer) of the same size as the (arrival time) bulk. (A similar bulk is implicitly also present when using TStaticHeap, but it is a part of the heap itself.) So Andrew Sutton's approach to use the mutable interface is not too different from mine, but will probably lead to even worse performance (because a "map" lookup seems to be worse than a "bulk" lookup).
from what i see (taking andrew's example), the problem is the following: struct Vertex { Key k; Queue<Vertex*>::handle_type handle; }; Queue<Vertex*> q; Vertex v; v.handle = q.push(&v); v.key = new_key; q.update(v.handle); ... this is actually the use case, where intrusive mutable heaps would be very handy ...
On the one hand, your proposed mutable interface seems to be quite "natural" for node based heaps. On the other hand, it looks like there is one more indirection than for a "straightforward" implementation of a "mutable" binary heap, where the heap "knows" the maximum number of different items that it has to manage.
true ... but this is mainly the point, where the bgl heaps use a propery map ... cheers, tim
hi thomas, reproduced and fixed the issue with the fibonacci heap ... tim
Tim Blechmann wrote:
hi thomas,
reproduced and fixed the issue with the fibonacci heap ...
tim
I now also included pairing_heap and skew_heap in the performance test. However, I get a segfault for pairing_heap when running the "Linear Forward" performance test. That's the place with "// if (0)" in the attached file. When I uncomment that line, I get the following results (linux32): Performance Check for Linear Forward 270 ticks and 15952569 compares for TStaticHeap 280 ticks and 15952569 compares for TStaticHeap 100 ticks and 5495826 compares for TSequentialHeap 80 ticks and 5495826 compares for TSequentialHeap 470 ticks and 20929621 compares for b_heap 470 ticks and 20929621 compares for b_heap 400 ticks and 7012461 compares for binomial_heap 420 ticks and 7012461 compares for binomial_heap 300 ticks and 16164008 compares for d_ary_heap 290 ticks and 16164008 compares for d_ary_heap 210 ticks and 5637046 compares for fibonacci_heap 220 ticks and 5637046 compares for fibonacci_heap 850 ticks and 17013833 compares for skew_heap 850 ticks and 17013833 compares for skew_heap Performance Check for Linear Backward 280 ticks and 22976046 compares for TStaticHeap 260 ticks and 22976046 compares for TStaticHeap 100 ticks and 5225203 compares for TSequentialHeap 90 ticks and 5225203 compares for TSequentialHeap 620 ticks and 31971032 compares for b_heap 630 ticks and 31971032 compares for b_heap 260 ticks and 5636875 compares for binomial_heap 270 ticks and 5636875 compares for binomial_heap 350 ticks and 19465560 compares for d_ary_heap 350 ticks and 19465560 compares for d_ary_heap 220 ticks and 5866500 compares for fibonacci_heap 230 ticks and 5866500 compares for fibonacci_heap 140 ticks and 458856 compares for pairing_heap 150 ticks and 458856 compares for pairing_heap 100 ticks and 458856 compares for skew_heap 110 ticks and 458856 compares for skew_heap Performance Check for March 1590 ticks and 93489201 compares for TStaticHeap 1560 ticks and 93489201 compares for TStaticHeap 710 ticks and 53507489 compares for TSequentialHeap 730 ticks and 53507489 compares for TSequentialHeap 2550 ticks and 121120384 compares for b_heap 2530 ticks and 121120384 compares for b_heap 3400 ticks and 73639894 compares for binomial_heap 3410 ticks and 73639894 compares for binomial_heap 1620 ticks and 92667621 compares for d_ary_heap 1590 ticks and 92667621 compares for d_ary_heap 1250 ticks and 39902719 compares for fibonacci_heap 1260 ticks and 39902719 compares for fibonacci_heap 1910 ticks and 38838757 compares for pairing_heap 1900 ticks and 38838757 compares for pairing_heap 6380 ticks and 100758422 compares for skew_heap 6380 ticks and 100758422 compares for skew_heap What's impressive here is that pairing_heap and skew_heap have a compare count a factor 10 smaller than any other heap for the "Linear Backward" performance test. Regards, Thomas
hi thomas,
I now also included pairing_heap and skew_heap in the performance test. However, I get a segfault for pairing_heap when running the "Linear Forward" performance test. That's the place with "// if (0)" in the attached file. When I uncomment that line, I get the following results (linux32):
... the pairing heap is a self adjusting data structure ... and it is recursively implemented. there are some use cases, where the heap degenerates into a linear list ... the bigger problem is the fact that the heap is implemented recursively ... that means that in some cases you can run into a recursion of O(n) ... in your example, your simply run into a stack overflow ... (there is a warning in the class reference about this issue)
What's impressive here is that pairing_heap and skew_heap have a compare count a factor 10 smaller than any other heap for the "Linear Backward" performance test.
skep heaps have an amortized complexity for all operations. pairing heaps are difficult to analyze but give pretty good real-world results ... cheers, tim
Thomas Klimpel wrote:
I now also included pairing_heap and skew_heap in the performance test. However, I get a segfault for pairing_heap when running the "Linear Forward" performance test. That's the place with "// if (0)" in the attached file. When I uncomment that line, I get the following results (linux32):
I now also tried to compile the extended benchmark with MSVC-9 and MSVC-10. I get a compile error at skew_heap.hpp in line 682: 678: class skew_heap_mutable: 679: public detail::skew_heap<T, store_parent_pointer<true>, A0, A1, A2, A3> 680: { 681: private: 682: typedef detail::skew_heap<T, store_parent_pointer<true>, A0, A1, A2, A3> super_t; It strikes me as odd that line 679 doesn't generate a compile error, even so it looks nearly identical to me. Perhaps the problem is caused by the fact that detail::skew_heap has a member variable with the name store_parent_pointer? Anyway, I replaced "store_parent_pointer<true>" with "boost::heap::store_parent_pointer<true>" and then everything compiles fine. Before I did that, I tried my luck with the "address_review" branch/head from the boost_heap git repository (instead of the "master" branch/head). I got a compile error for detail/ordered_adaptor_iterator.hpp for line 51 then (error C2529: 'abstract declarator' : reference to reference is illegal). I looked up in boost::iterator_facade that "class Value" was expected at that position, so I replaced "ValueType const &," with "ValueType," and it compiled fine. However, this fix seems to change the semantics, so I also checked that not just ValueType, boost::forward_traversal_tag >, but also ValueType const&, boost::forward_traversal_tag, ValueType const& >, would compile fine. Regards, Thomas
hi thomas,
I now also included pairing_heap and skew_heap in the performance test. However, I get a segfault for pairing_heap when running the "Linear Forward" performance test. That's the place with "// if (0)" in the attached file.
When I uncomment that line, I get the following results (linux32): I now also tried to compile the extended benchmark with MSVC-9 and MSVC-10.
I get a compile error at skew_heap.hpp in line 682:
678: class skew_heap_mutable: 679: public detail::skew_heap<T, store_parent_pointer<true>, A0, A1, A2, A3> 680: { 681: private: 682: typedef detail::skew_heap<T, store_parent_pointer<true>, A0, A1, A2, A3> super_t;
It strikes me as odd that line 679 doesn't generate a compile error, even so it looks nearly identical to me. Perhaps the problem is caused by the fact that detail::skew_heap has a member variable with the name store_parent_pointer? Anyway, I replaced "store_parent_pointer<true>" with "boost::heap::store_parent_pointer<true>" and then everything compiles fine.
thanks! i cannot test with msvc, but only with gcc, clang++ and icc ... will commit this fix ...
Before I did that, I tried my luck with the "address_review" branch/head from the boost_heap git repository (instead of the "master" branch/head). I got a compile error for detail/ordered_adaptor_iterator.hpp for line 51 then (error C2529: 'abstract declarator' : reference to reference is illegal). I looked up in boost::iterator_facade that "class Value" was expected at that position, so I replaced "ValueType const &," with "ValueType," and it compiled fine. However, this fix seems to change the semantics, so I also checked that not just
will have a look at this ... thanks, tim
Thomas Klimpel wrote:
We can see that "fibonacci_heap" has always more than a factor two fewer comparisons than TStaticHeap (a simple text book binary heap implementation used as reference), but is always more than a factor two slower than TStaticHeap.
Actually, it looks like I had the most unfortunate compiler/platform combination possible (gcc-4.3.4 on cygwin). I have now tested on the same machine, but with different compilers and different platforms (linux32/cygwin/win32/). On linux, "fibonacci_heap" is actually faster than TStaticHeap. (I have compiled with -march_native, and -DSLOPPY_COMPARE, for better performance: g++ -o linux heaptest.cpp -O2 -DNDEBUG -march=native -Iboost_heap-449f378 -I/media/sda1/nobackup/boost_release/ -DHAVE_SEQ_HEAP -DSLOPPY_COMPARE). Looks like the performance of a each specific heap implementation heavily depends on the compiler, but in a pretty unpredictable way. Regards, Thomas -------- gcc-4.4.3 (linux32): Performance Check for Linear Forward 220 ticks and 0 compares for TStaticHeap 230 ticks and 0 compares for TStaticHeap 80 ticks and 0 compares for TSequentialHeap 70 ticks and 0 compares for TSequentialHeap 470 ticks and 0 compares for b_heap 460 ticks and 0 compares for b_heap 410 ticks and 0 compares for binomial_heap 430 ticks and 0 compares for binomial_heap 340 ticks and 0 compares for d_ary_heap 360 ticks and 0 compares for d_ary_heap 200 ticks and 0 compares for fibonacci_heap 210 ticks and 0 compares for fibonacci_heap Performance Check for Linear Backward 240 ticks and 0 compares for TStaticHeap 230 ticks and 0 compares for TStaticHeap 90 ticks and 0 compares for TSequentialHeap 80 ticks and 0 compares for TSequentialHeap 590 ticks and 0 compares for b_heap 600 ticks and 0 compares for b_heap 280 ticks and 0 compares for binomial_heap 300 ticks and 0 compares for binomial_heap 380 ticks and 0 compares for d_ary_heap 400 ticks and 0 compares for d_ary_heap 220 ticks and 0 compares for fibonacci_heap 230 ticks and 0 compares for fibonacci_heap Performance Check for March 1320 ticks and 0 compares for TStaticHeap 1290 ticks and 0 compares for TStaticHeap 620 ticks and 0 compares for TSequentialHeap 600 ticks and 0 compares for TSequentialHeap 2530 ticks and 0 compares for b_heap 2520 ticks and 0 compares for b_heap 3480 ticks and 0 compares for binomial_heap 3540 ticks and 0 compares for binomial_heap 1880 ticks and 0 compares for d_ary_heap 1870 ticks and 0 compares for d_ary_heap 1130 ticks and 0 compares for fibonacci_heap 1170 ticks and 0 compares for fibonacci_heap gcc-4.3.4 (cygwin): Performance Check for Linear Forward 265 ticks and 0 compares for TStaticHeap 234 ticks and 0 compares for TStaticHeap 79 ticks and 0 compares for TSequentialHeap 62 ticks and 0 compares for TSequentialHeap 875 ticks and 0 compares for b_heap 875 ticks and 0 compares for b_heap 844 ticks and 0 compares for binomial_heap 844 ticks and 0 compares for binomial_heap 781 ticks and 0 compares for d_ary_heap 797 ticks and 0 compares for d_ary_heap 609 ticks and 0 compares for fibonacci_heap 594 ticks and 0 compares for fibonacci_heap Performance Check for Linear Backward 266 ticks and 0 compares for TStaticHeap 234 ticks and 0 compares for TStaticHeap 94 ticks and 0 compares for TSequentialHeap 78 ticks and 0 compares for TSequentialHeap 1015 ticks and 0 compares for b_heap 1016 ticks and 0 compares for b_heap 703 ticks and 0 compares for binomial_heap 687 ticks and 0 compares for binomial_heap 798 ticks and 0 compares for d_ary_heap 812 ticks and 0 compares for d_ary_heap 610 ticks and 0 compares for fibonacci_heap 625 ticks and 0 compares for fibonacci_heap Performance Check for March 1499 ticks and 0 compares for TStaticHeap 1469 ticks and 0 compares for TStaticHeap 781 ticks and 0 compares for TSequentialHeap 782 ticks and 0 compares for TSequentialHeap 5155 ticks and 0 compares for b_heap 5125 ticks and 0 compares for b_heap 5922 ticks and 0 compares for binomial_heap 5890 ticks and 0 compares for binomial_heap 4407 ticks and 0 compares for d_ary_heap 4375 ticks and 0 compares for d_ary_heap 3703 ticks and 0 compares for fibonacci_heap 3703 ticks and 0 compares for fibonacci_heap gcc-4.3.3 (win32): Performance Check for Linear Forward 266 ticks and 0 compares for TStaticHeap 234 ticks and 0 compares for TStaticHeap 94 ticks and 0 compares for TSequentialHeap 62 ticks and 0 compares for TSequentialHeap 813 ticks and 0 compares for b_heap 875 ticks and 0 compares for b_heap 765 ticks and 0 compares for binomial_heap 735 ticks and 0 compares for binomial_heap 719 ticks and 0 compares for d_ary_heap 813 ticks and 0 compares for d_ary_heap 547 ticks and 0 compares for fibonacci_heap 562 ticks and 0 compares for fibonacci_heap Performance Check for Linear Backward 250 ticks and 0 compares for TStaticHeap 250 ticks and 0 compares for TStaticHeap 94 ticks and 0 compares for TSequentialHeap 94 ticks and 0 compares for TSequentialHeap 984 ticks and 0 compares for b_heap 984 ticks and 0 compares for b_heap 625 ticks and 0 compares for binomial_heap 641 ticks and 0 compares for binomial_heap 765 ticks and 0 compares for d_ary_heap 766 ticks and 0 compares for d_ary_heap 578 ticks and 0 compares for fibonacci_heap 562 ticks and 0 compares for fibonacci_heap Performance Check for March 1500 ticks and 0 compares for TStaticHeap 1453 ticks and 0 compares for TStaticHeap 875 ticks and 0 compares for TSequentialHeap 860 ticks and 0 compares for TSequentialHeap 3781 ticks and 0 compares for b_heap 3797 ticks and 0 compares for b_heap 4484 ticks and 0 compares for binomial_heap 4469 ticks and 0 compares for binomial_heap 2953 ticks and 0 compares for d_ary_heap 3016 ticks and 0 compares for d_ary_heap 2218 ticks and 0 compares for fibonacci_heap 2219 ticks and 0 compares for fibonacci_heap gcc-4.5.2 (win32): Performance Check for Linear Forward 235 ticks and 0 compares for TStaticHeap 234 ticks and 0 compares for TStaticHeap 94 ticks and 0 compares for TSequentialHeap 78 ticks and 0 compares for TSequentialHeap 797 ticks and 0 compares for b_heap 875 ticks and 0 compares for b_heap 750 ticks and 0 compares for binomial_heap 750 ticks and 0 compares for binomial_heap 703 ticks and 0 compares for d_ary_heap 828 ticks and 0 compares for d_ary_heap 563 ticks and 0 compares for fibonacci_heap 562 ticks and 0 compares for fibonacci_heap Performance Check for Linear Backward 250 ticks and 0 compares for TStaticHeap 235 ticks and 0 compares for TStaticHeap 109 ticks and 0 compares for TSequentialHeap 109 ticks and 0 compares for TSequentialHeap 922 ticks and 0 compares for b_heap 922 ticks and 0 compares for b_heap 625 ticks and 0 compares for binomial_heap 609 ticks and 0 compares for binomial_heap 750 ticks and 0 compares for d_ary_heap 735 ticks and 0 compares for d_ary_heap 594 ticks and 0 compares for fibonacci_heap 578 ticks and 0 compares for fibonacci_heap Performance Check for March 1281 ticks and 0 compares for TStaticHeap 1250 ticks and 0 compares for TStaticHeap 937 ticks and 0 compares for TSequentialHeap 938 ticks and 0 compares for TSequentialHeap 3422 ticks and 0 compares for b_heap 3437 ticks and 0 compares for b_heap 4188 ticks and 0 compares for binomial_heap 4234 ticks and 0 compares for binomial_heap 2750 ticks and 0 compares for d_ary_heap 2797 ticks and 0 compares for d_ary_heap 2031 ticks and 0 compares for fibonacci_heap 2032 ticks and 0 compares for fibonacci_heap MSVC9: Performance Check for Linear Forward 250 ticks and 0 compares for TStaticHeap 265 ticks and 0 compares for TStaticHeap 78 ticks and 0 compares for TSequentialHeap 63 ticks and 0 compares for TSequentialHeap 1062 ticks and 0 compares for b_heap 1141 ticks and 0 compares for b_heap 781 ticks and 0 compares for binomial_heap 782 ticks and 0 compares for binomial_heap 687 ticks and 0 compares for d_ary_heap 766 ticks and 0 compares for d_ary_heap 562 ticks and 0 compares for fibonacci_heap 563 ticks and 0 compares for fibonacci_heap Performance Check for Linear Backward 250 ticks and 0 compares for TStaticHeap 250 ticks and 0 compares for TStaticHeap 94 ticks and 0 compares for TSequentialHeap 94 ticks and 0 compares for TSequentialHeap 1312 ticks and 0 compares for b_heap 1250 ticks and 0 compares for b_heap 625 ticks and 0 compares for binomial_heap 625 ticks and 0 compares for binomial_heap 719 ticks and 0 compares for d_ary_heap 688 ticks and 0 compares for d_ary_heap 609 ticks and 0 compares for fibonacci_heap 562 ticks and 0 compares for fibonacci_heap Performance Check for March 1344 ticks and 0 compares for TStaticHeap 1297 ticks and 0 compares for TStaticHeap 781 ticks and 0 compares for TSequentialHeap 766 ticks and 0 compares for TSequentialHeap 5031 ticks and 0 compares for b_heap 5047 ticks and 0 compares for b_heap 4375 ticks and 0 compares for binomial_heap 4360 ticks and 0 compares for binomial_heap 2562 ticks and 0 compares for d_ary_heap 2594 ticks and 0 compares for d_ary_heap 2031 ticks and 0 compares for fibonacci_heap 2016 ticks and 0 compares for fibonacci_heap MSVC10: Performance Check for Linear Forward 250 ticks and 0 compares for TStaticHeap 250 ticks and 0 compares for TStaticHeap 63 ticks and 0 compares for TSequentialHeap 63 ticks and 0 compares for TSequentialHeap 875 ticks and 0 compares for b_heap 969 ticks and 0 compares for b_heap 750 ticks and 0 compares for binomial_heap 766 ticks and 0 compares for binomial_heap 656 ticks and 0 compares for d_ary_heap 750 ticks and 0 compares for d_ary_heap 594 ticks and 0 compares for fibonacci_heap 562 ticks and 0 compares for fibonacci_heap Performance Check for Linear Backward 266 ticks and 0 compares for TStaticHeap 250 ticks and 0 compares for TStaticHeap 94 ticks and 0 compares for TSequentialHeap 78 ticks and 0 compares for TSequentialHeap 1078 ticks and 0 compares for b_heap 1062 ticks and 0 compares for b_heap 594 ticks and 0 compares for binomial_heap 609 ticks and 0 compares for binomial_heap 672 ticks and 0 compares for d_ary_heap 672 ticks and 0 compares for d_ary_heap 578 ticks and 0 compares for fibonacci_heap 562 ticks and 0 compares for fibonacci_heap Performance Check for March 1328 ticks and 0 compares for TStaticHeap 1313 ticks and 0 compares for TStaticHeap 765 ticks and 0 compares for TSequentialHeap 750 ticks and 0 compares for TSequentialHeap 4000 ticks and 0 compares for b_heap 4000 ticks and 0 compares for b_heap 4359 ticks and 0 compares for binomial_heap 4344 ticks and 0 compares for binomial_heap 2390 ticks and 0 compares for d_ary_heap 2438 ticks and 0 compares for d_ary_heap 2062 ticks and 0 compares for fibonacci_heap 2063 ticks and 0 compares for fibonacci_heap
participants (3)
-
Andrew Sutton -
Thomas Klimpel -
Tim Blechmann