Implement pairing heap without shared_ptr

[heinezen]

Required Skills: C++

Difficulty: Hard

openage provides a pairing heap implementation that is mostly used in the A* algorithm of our pathfinder. Currently, nodes on the heap are connected using shared_ptr. However, we have noticed that the creation of shared_ptr objects when using the heap is very slow. A variant with raw pointers and without shared_ptr may offer better performance benefits.

A previous implementation already used raw pointers. You can see it in commit 4ab602a

Tasks:

• Implement the pairing heap without using shared_ptr or enable_shared_from_this. You can use the implemenation in 4ab602a as a reference but be aware that other parts of the code may have changed since then.
• Use callgrind to compare the speed of the old implementation with your solution that uses precomputed graphs:

valgrind --tool=callgrind ./run test -d pathfinding.tests.path_demo 1

Further Reading

• pairing heap code

[vijayabhaskar78]

Can I work on this issue

[heinezen]

@vijayabhaskar78 Yes, you can. Do you have knowledge of C++? It's not the easiest beginner task for someone new to C++.

[jere8184]

@heinezen I would like to pick this up if its still available

[heinezen]

@jere8184 it is available and it would be a nice addition :)

[jere8184]

Great, should I keep the shared pointer implementation or replace it?

[heinezen]

I think we can just replace it.

[TheJJ]

you can replace it, so that one can add shared pointers as the contained element type - then we have both available!

[heinezen]

Resolved in #1713