Open JohannesMP opened 3 years ago
I've made a pull requests that adds a variation of the proposal discussed in this issue.
I opted to just add the proposed functionality as overloads to SimplePriorityQueue.TryFirst
, SimplePriorityQueue.TryRemove
and SimplePriorityQueue.TryDequeue
, consistent with the intent that the Try*
methods are for multithreading.
In each case if the caller wants the priority of the head/head-to-be-removed/node-to-be-removed, they can now get it without an additional (Try)GetPriority
call, making it easier to remain thread-safe while also avoiding an extra _itemToNodesCache
lookup.
Overview
When working with priority queues it's often useful to be able to access the priority of the head node as you dequeue it. This is especially common in many pathfinding and graph traversal algorithms.
When using
GenericPriorityQueue
orFastPriorityQueue
you manipulate the nodes directly and so have access to their respectivePriority
properties.When using
SimplePriorityQueue
the nodes are not publicly exposed and so it is currently necessary to first get the priority of the head element, and only then dequeue it.A naïve user implementation might look like this:
This achieves the desired result using
SimplePriorityQueue.GetPriority
(added as a result of related issue #27), but this implementation is suboptimal (even if for a moment we ignore the fact that it is not thread safe).The Problem
In its current implementation
SimplePriorityQueue.Dequeue()
retrieves an internalSimpleNode
, which contains both theData
as well as thePriority
properties we need, but only returns the data to the caller:So by performing
Dequeue
/TryDequeue
we actually already have access the priority value of the head node that we want! It's just not exposed to the caller.They instead have to make an additional
GetPriority
call, which in the general case means a_itemToNodesCache
lookup since it is intended to work for any node, that could be avoided altogether.The Proposal
It would be trivial to add a
Dequeue
andTryDequeue
overload toSimplePriorityQueue
that each have aout TPriority
parameter, since we get that value for free in both of the existing implementations.For example, the overload for Dequeue could be:
And the overload for TryDequeue could be:
They are identical to the existing implementations, except for assigning the
priority
out parameter. There should be no performance overhead other than one additional assignment, which is trivial (and would still happen with(Try)GetPriority
anyway).This would even have the additional benefit of being thread-safe, unlike the naïve user implementation provided as an example at the start.
If it was deemed necessary to keep the function names unique and not overload them they could be named
DequeueWithPriority
andTryDequeueWithPriority
respectively, or something comparable. 2nd hardest problem in computer science and all that...Keeping things 'Simple'
The argument could be made that if you care enough about optimizing Dequeue with priority you should just use
GenericPriorityQueue
orFastPriorityQueue
, and that the public signature ofSimplePriorityQueue
should be kept, well, 'simple'.That is valid, but given how trivial this implementation would be to add it just seems like such a missed opportunity, especially for saving an additional hash for an operation that as I understand it is very common in some of the main applications of Priority Queues.
More importantly
SimplePriorityQueue
promises to be thread-safe, and requiring the user to make three calls means we can no longer guarantee that the operation is thread-safe - it's now up to the user to ensure that they correctly lock access to the container for the duration of theirFirst
(orTryFirst
),GetPriority
andDequeue
calls. Yuck.It just seems like the equivalent of creating a
SimpleDictionary
implementation that promises to be "thread-safe" , but only hasContains
andGetValue
and does not provide aTryGetValue
:The primary purpose of this library is performance (it's in the name after all), so I'd like to make the argument that even its 'simple' implementation would benefit from this addition, while (especially if we use unique names) remaining backwards compatible.
The proposed addition would make a common access pattern safer (one less place the user has to worry about thread safety) and faster, at no extra cost.
Relevant issues
SimplePriorityQueue.GetPriority
. As outlined here that is sub-optimal in this specific case where we already have the node and so don't need to hash to retrieve it. It also requires the caller to manage their own thread safety which the proposed change also throws in for free.