Priority queue

[bartoszmodelski]

Priority queues are ubiquitous. I think it would make sense to have one here as it would be useful for scheduling, be it at an actual scheduler level or much higher, e.g. in event loop, which should prioritise user input over some compute.

There is a lot of literature. Probably a good place to start is the chapter on priority queues in The Art of Multiprocessor Programming.

[jake-87]

https://engineering.lehigh.edu/sites/engineering.lehigh.edu/files/_DEPARTMENTS/cse/research/tech-reports/2011/lu-cse-11-004.pdf
"A Lock-Free, Array-Based Priority Queue"

The above seems appealing - if its benchmarks are accurate, it seems to be more efficient then the lock-free skiplist-based prioqueue described in "The Art Of Multiprocessor Programming".

[lyrm]

This implementation appears quite interesting but relies on double compare-and-set operations, which are not available in OCaml. While it would be possible to use kcas, in that case, the implementation would be more appropriately placed in kcas_data rather than here.

[lyrm]

Work is currently in progress to implement a priority queue based on the skip-list implementation available in Saturn and the algorithm described in The Art Of Multiprocessor programming.