search

BlueRaja / High-Speed-Priority-Queue-for-C-Sharp

A C# priority queue optimized for pathfinding applications
MIT License
1.16k stars 169 forks source link

FastPriorityQueue or SimplePriorityQueue with value types? #3

Closed mrakgr closed 8 years ago

mrakgr commented 8 years ago

Would you recommend I make a wrapper for FastPriorityQueue for use with value types or to use the SimplePriorityQueue for maximum performance? As long as there not too many of them, 2D grid points could be hashed to an integer, but with a wrapper, there will definitely be some overhead. I saw some discussion of this in the closed issue, but I am guessing that was before the SimplePriorityQueue was implemented.

BlueRaja commented 8 years ago

For maximum performance, you'd want to use FastPriorityQueue. SimplePriorityQueue is not much slower though, it is just a wrapper around FastPriorityQueue to make it more convenient.

mrakgr commented 8 years ago

I am not sure I understand your comment. By wrapper, I really meant a class that extends the FastPriorityQueueNode. If I only wanted a priority queue of ints that would mean having to enclose a value type within a reference type which comes with some overhead.

BlueRaja commented 8 years ago

Yep, I know what you meant. Note that

If I only wanted a priority queue of ints that would mean having to enclose a value type within a reference type which comes with some overhead.

is always going to be true, in any priority queue, but normally that overhead is hidden from you. Using FastPriorityQueue you can manage that overhead yourself (eg. do all the node allocations at a point that's convenient for you, reuse old nodes to avoid allocations, etc)

mrakgr commented 8 years ago

I just wanted to ask this, thanks.

cesarsouza commented 8 years ago

Regarding the overhead of having to enclose a value type within a reference type, has anyone considered making FastPriorityQueueNode a struct? This would avoid this overhead, plus might improve cache locality of some algorithms as arrays of value types are allocated contiguously in memory. I am considering doing this myself, but was just wondering if any of you have attempted this before.

BlueRaja commented 8 years ago

You cannot derive structs from other structs in C# (doing so would require adding a lot of the unnecessary complexity that C++ has: object slicing, copy constructors, etc) so you'd need to rearchitect the queue completely.

I made FastPriorityQueueNode a class because I figured the extra copies necessary when using a struct would slow it down too much, but you have a good point about cache coherence. I think I'll give this a shot and see how it performs in my benchmarks. I've opened https://github.com/BlueRaja/High-Speed-Priority-Queue-for-C-Sharp/issues/8 for it. Thanks!

BlueRaja commented 8 years ago

Actually I should have put more thought into this. There is no way to use a struct and keep the O(1) Contains() method, which is a major selling-point of this library (it's by far the most called method in most pathfinding implementations).

It's possible the cache-coherence would still make up for this, but it seems extremely unlikely.