search

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

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

StablePriorityQueue is not stable. #56

Closed kikaragyozov closed 2 years ago

kikaragyozov commented 2 years ago

I see that there is a _numNodesEverEnqueued field in the class.

When you have a single queue for the lifetime of your application being used, sooner or later the bits for that Int64 will flip, resulting in now incorrect "aging" of future entries.

Imagine the following scenario:

Before the field overflows, we had the following items in the queue:

Priority Value InsertionIndex
1 3 9999..1
1 9 9999..2

Now, if we were to add an element with a priority of 1 and value 5, we get incorrect behavior. The queue is no longer stable, in that 3, 9, 5 will not be dequeued in that order, but rather 5, 3, 9.

As a side effect, this effectively means that 3 and 9 (ALL the items left in the queue when the bit shifts) in applications with extreme throughput will be blocked from ever being dequeued if a priority of 1 is the main player in the queue.

BlueRaja commented 2 years ago

If you enqueue 1 million nodes per second, it will take you 500,000 years to overflow a 64-bit counter. I don't think this is a realistic concern.