Boost logo

Boost :

Subject: [boost] [heap] A performance test and some questions
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2011-06-05 14:27:39


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




Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk