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 https://github.com/SFTtech/openage/commit/4ab602a6242448bb82eac5db9eafa96d758c7199

Tasks:

• [ ] Implement the pairing heap without using shared_ptr or enable_shared_from_this. You can use the implemenation in https://github.com/SFTtech/openage/commit/4ab602a6242448bb82eac5db9eafa96d758c7199 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 https://github.com/SFTtech/openage/pull/1713