search

ocaml-multicore / saturn

Lock-free data structures for multicore OCaml
ISC License
202 stars 30 forks source link

Priority queue #31

Open bartoszmodelski opened 2 years ago

bartoszmodelski commented 2 years ago

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 commented 5 months ago

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".