Min heap with std::priority_queue is my bottleneck

Question

Alternative title:

Implement min heap with something faster than std::priority_queue.

grpof gave me:

time seconds seconds calls s/call s/call name
84.12 105.54 105.54 320000 0.00 0.00 _ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i

which I believe is my only std::priority_queue used in the project. The 'Division_Euclidean_space' part confuses me, since it's a class/file not used any more in my project.

Here is what I use exactly:

/**
 * Min_heap is actually a std::priority_queue,
 * with std::greater as a parameter.
 */
typedef std::priority_queue<std::tuple<float, int, int>,
    std::vector<std::tuple<float, int, int> >,
    std::greater<std::tuple<float, int, int> > > Min_heap;

I use the first element as the key for comparison.

and as one can see in my repo, I create only one Min_heap and I use it in two parts:

if(...) {
  branch.push(std::make_tuple(new_dist, other_child_i, tree_i));
}

and

while (branch.size()) {
  std::tie(new_mindist, node_i, tree_i) = branch.top();
  branch.pop();
  ...
}

I feel that if I replace this data structure with something else, my project may run a bit faster (super duper great). Any ideas?

I push items in the heap for a while, then I pop one and I will probably push other items do and so on. Most of the times I stop with another condition, not when the heap gets empty.

That gprof function is `RKD >::nn`, where the `priority_queue` is just one of the arguments. The entire name is very long, you can get it by running your mangled string through `c++filt -n`. — Adam, Apr 27 '15 at 20:22
I and other people take a dim view of gprof, because it tells you silly stuff like "library function xyz is my bottleneck". Take a break and [*try this method*](http://stackoverflow.com/a/378024/23771). My suspicion is if you just replace all that fanciness with a simple linked list, *and* if you recycle used objects in free lists, you will see a speedup of an order of magnitude or more. — Mike Dunlavey, Apr 28 '15 at 01:27
@MikeDunlavey you mean replacing the min heap with a single linked list? I am not sure what you mean by recycling and free lists. Moreover, I had seen the link already, thanks! Off topic: Respect for the pilots by the way/ :) — gsamaras, Apr 28 '15 at 07:14
I think this deserves a new question: http://stackoverflow.com/questions/29914485/pushing-in-min-heap-with-stdpriority-queue-is-my-bottleneck — gsamaras, Apr 28 '15 at 08:42
The "respect for pilots" comment went over my head - sorry. Recycling used objects is a basic technique to drastically reduce time spent in new and delete, constructors and destructors. If you're using a heap as a priority queue, I suspect the crossover size where it becomes more efficient than a simple linked list is quite large. — Mike Dunlavey, Apr 28 '15 at 13:36

rici · Accepted Answer · 2015-04-27T20:31:23.800

8

http://demangler.com translated that function into: (indented by me)

RKD<Division_Euclidean_space<float> >::nn(
  unsigned int,
  std::vector<float, std::allocator<float> > const&,
  float const&,
  std::vector<std::pair<float, int>, std::allocator<std::pair<float, int> > >&,
  int&,
  int,
  unsigned int*,
  std::priority_queue<std::tuple<float, int, int>,
                      std::vector<std::tuple<float, int, int>,
                                  std::allocator<std::tuple<float, int, int> > >,
                      std::greater<std::tuple<float, int, int> > >&,
  float const&,
  unsigned int const&,
  std::vector<float, std::allocator<float> > const&,
  std::vector<float, std::allocator<float> > const&,
  int)

I don't know what nn does, but I suppose it does a lot more than priority queue operations.

edited Apr 27 '15 at 20:31

answered Apr 27 '15 at 20:23

rici

234,347
28
237
341

Oh damn. If only I could profile *only* that function with gprof, that would be great. `nn` is the core of my project and what interests me at most. Thanks, especially for the link! – gsamaras Apr 27 '15 at 20:27
I tried this: `gprof -p_ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i geraf gmon.out > analysis.txt`, but it displays ONLY the `nn()`, not its children! – gsamaras Apr 27 '15 at 20:43
1

@G.Samaras: I think you need a call graph to get the info you want (option -q?) – rici Apr 27 '15 at 20:49
In case you have some ideas rici, I would be glad to see them in my new question: http://stackoverflow.com/questions/29914485/pushing-in-min-heap-with-stdpriority-queue-is-my-bottleneck :) – gsamaras Apr 28 '15 at 08:43

Min heap with std::priority_queue is my bottleneck

1 Answers1

Linked