Ordered queue is a priority queue, which can be implemented using a binary heap. A binary heap can be backed with a simple array, which is more cache friendly than a linked list. The worst case is O(logN) for insert and delete, only O(1) for peek. It's better than the O(N) insertion sort on the linked list.
Worth to mention, ordered queue is also called as priority or heap queue. There's a one builtin implementation in Python's built library, inside the "heapq" module.
one thing that'd be interesting to see benchmarked is the performance of a linked list implementation vs a heap backed by an array allocated with sufficient capacity for expected usage, so it doesn't need to be resized often (or ever).
one downside of linked lists is that each node in the list can reside in an arbitrary part of memory. in the worst case each traversal of a link is a cache miss, so you sit around for 100 or 200 cycles waiting for a main memory read. similarly if all the values in the list that are used to implement comparisons are also stored by reference and scattered throughout memory.
with heaps, another interesting thing to try is switching from a binary heap to e.g. a 4-ary heap (i.e. 4 children per parent). i've been fiddling with heaps recently for a priority queue & see a decent speedup switching to a 4-ary heap -- provided the "heapify down" logic that runs whenever you pop an element is structured to let the cpu do as many pairwise compares as possible in parallel, rather than structuring it as a big chain of dependent computations. during "heapify" operations you're jumping around inside a heap a fair bit, which may also cause cache misses, but each bunch of children will be arranged linearly in memory, so there is a bit more signal to noise of each cache line read.
This reads like a system design interview, and a good one. The author clearly understands the pattern and the technologies they’re working with.
I would perhaps attempt to gather more non functional requirements. How many items on the queue? How quickly are they added? How many threads are consuming from the queue? What’s the size of the message?
Also, how much would all this cost to run, in terms of memory? Is there a way of persisting the in-memory structure in case the server goes down?
> This reads like a system design interview, and a good one.
> The author clearly understands the pattern and the technologies they’re working with.
We must have read a different article.
The one I read put a big lock around the outside of their interface and called that "concurrent". This is not what is normally meant by the term.
This was after a dozen or so pages that described an insertion sort poorly, and followed by some speculation about why their software still didn't work right.
Agree: soothingly well versed tone of voice, but leads to "it works"-level solution at best. Enumerates a bunch of data structures, but skips heap. Puts huge mutex over the interface, then even breaks open the abstraction to expose the lock using Hold()! So much for RAII.
Interesting article, but surprised that the author never mentions heaps... https://en.wikipedia.org/wiki/Heap_(data_structure)
previously: On Modern Hardware the Min-Max Heap beats a Binary Heap
https://probablydance.com/2020/08/31/on-modern-hardware-the-...
heaps of comments in the 2020 HN thread: https://news.ycombinator.com/item?id=24353423
Mind you, the "array" underlying Min-Max binary heaps in this example is actually a linked list!
Heaps are very underappreciated for this and similar use cases.
Ordered queue is a priority queue, which can be implemented using a binary heap. A binary heap can be backed with a simple array, which is more cache friendly than a linked list. The worst case is O(logN) for insert and delete, only O(1) for peek. It's better than the O(N) insertion sort on the linked list.
Worth to mention, ordered queue is also called as priority or heap queue. There's a one builtin implementation in Python's built library, inside the "heapq" module.
one thing that'd be interesting to see benchmarked is the performance of a linked list implementation vs a heap backed by an array allocated with sufficient capacity for expected usage, so it doesn't need to be resized often (or ever).
one downside of linked lists is that each node in the list can reside in an arbitrary part of memory. in the worst case each traversal of a link is a cache miss, so you sit around for 100 or 200 cycles waiting for a main memory read. similarly if all the values in the list that are used to implement comparisons are also stored by reference and scattered throughout memory.
with heaps, another interesting thing to try is switching from a binary heap to e.g. a 4-ary heap (i.e. 4 children per parent). i've been fiddling with heaps recently for a priority queue & see a decent speedup switching to a 4-ary heap -- provided the "heapify down" logic that runs whenever you pop an element is structured to let the cpu do as many pairwise compares as possible in parallel, rather than structuring it as a big chain of dependent computations. during "heapify" operations you're jumping around inside a heap a fair bit, which may also cause cache misses, but each bunch of children will be arranged linearly in memory, so there is a bit more signal to noise of each cache line read.
This is a horrible implementation. To start with, this queue isn't concurrent. It has a lock (and make it easy to leak / stall) with it.
Second, it has a `O(N)` performance on inserts.
This is beyond unexpected for something that is supposed to be a queue.
This reads like a system design interview, and a good one. The author clearly understands the pattern and the technologies they’re working with.
I would perhaps attempt to gather more non functional requirements. How many items on the queue? How quickly are they added? How many threads are consuming from the queue? What’s the size of the message?
Also, how much would all this cost to run, in terms of memory? Is there a way of persisting the in-memory structure in case the server goes down?
> This reads like a system design interview, and a good one.
> The author clearly understands the pattern and the technologies they’re working with.
We must have read a different article.
The one I read put a big lock around the outside of their interface and called that "concurrent". This is not what is normally meant by the term.
This was after a dozen or so pages that described an insertion sort poorly, and followed by some speculation about why their software still didn't work right.
Agree: soothingly well versed tone of voice, but leads to "it works"-level solution at best. Enumerates a bunch of data structures, but skips heap. Puts huge mutex over the interface, then even breaks open the abstraction to expose the lock using Hold()! So much for RAII.
I'm still reading and I am thinking wouldn't this be a "thread safe priority queue"?