3 ms·

I'm just curious, what are some of the disadvantages to priority queue?

lostcolony 10y ago
Okay. Let's start with a perfectly naive priority queue. We have a default data structure (nevermind the implementation for now), and a thread that pulls items off the queue, and executes them. Works perfectly in test. But we notice something; our executions take a non-zero amount of time, and so if we have two events happening simultaneously, they don't both get fired off in time. So now we have to switch to a thread pool, that gets handed events from the priority queue. Task runners, in effect. So, great. Everything works now. But then we have to start accepting updates to tasks. That is, we are able to move a task forwards or backwards in time. Now, suddenly, we care about the underlying data structure of the queue; can we both be updating the order of events -and- be pulling from it? Does it require locking to do that? Maybe it does require locking, in which case are we certain that we got ~that~ implemented right? Not just the queue library, but, in the event of an exception in our code, we correctly free the lock? And how long does it take to rebalance the queue? Is that acceptable, since we can't be pulling from the queue during that time? Maybe it doesn't require locking, such as when using immutable data structures where we build a copy and swap it out, but then we might have a chance of executing a task twice (i.e., our task launcher thread reads copyA, while we're modifying copyB, and so the head of the queue in both gets executed), so now we have to keep tabs on what we launched last. But that assumes a stable priority queue in the event of two items having the same time; -that's- a fun edge case to miss. But maybe we get all that working, by getting a lock-free priority queue in place. We have one thread reading from a priority queue, and handing tasks off to a thread pool. What size is the thread pool? What happens if a task is long running? Can we exhaust the thread pool? What happens if we need to scale out a bit, because we're exhausting our thread pool? We only have one thing reading off the queue; can it hand those off to another machine in a timely enough fashion? Probably not, especially if we're getting GC pauses; how do we solve that? Maybe we change it so that we launch things a little early, either locally or remotely, and the thread sleeps until it's time to start the task. That will work, but what happens when we want to update the task? Now the logic exists in two places; the task could still be on the priority queue in which case we have to modify the queue, or the task could be sitting in its own thread, and we have to modify it there (arguably this existed before; if a task had started you modified it in the thread it was executing in, if the task hadn't started you had to modify the priority queue, but this makes it far less determinate). Etc. In Erlang, you skip past all of these issues, and implement the end solution as your first, rather more easily. There's still a data structure somewhere saying what tasks have to execute, and when (probably just in your database, though, nothing needed in memory), but you don't have to worry about managing it beyond "hey, make sure the items for the next (time period) are running in a thread (Erlang process)". You can do that with one process launching the others, and (naive) distribution across machines is incredibly easy (the same complexities of handling partitions apply to both solutions). Individual tasks are built from the beginning to handle sleeping until start time, and updates are trivial, being just a message to them that they respond to, and a modification of your data structure (database). There's no tight coupling between the two. You end up with just "whenever a change in events happens (creation or update), send a message to that process if it exists, and update the DB". And the process scheduler in Erlang handles all the concurrency. There's no locking you have to worry about, and latency will be spread equally, rather than running the risk of choking out a single task. And this is the -naive- Erlang implementation. That's the benefit. For this particular use case, with priority queues you start running into issues, and as you solve them, your implementation looks more and more like the naive Erlang implementation.
- rubatuga 10y ago
  Thank you so much for the write up, I'm just getting into programming at school and this was a fantastic and interesting read! I've always been interested in how data structures work in real-life applications and I'm thankful for the explanation.

Okay. Let's start with a perfectly naive priority queue. We have a default data structure (nevermind the implementation for now), and a thread that pulls items off the queue, and executes them. Works perfectly in test. But we notice something; our executions take a non-zero amount of time, and so if we have two events happening simultaneously, they don't both get fired off in time. So now we have to switch to a thread pool, that gets handed events from the priority queue. Task runners, in effect. So, great. Everything works now. But then we have to start accepting updates to tasks. That is, we are able to move a task forwards or backwards in time. Now, suddenly, we care about the underlying data structure of the queue; can we both be updating the order of events -and- be pulling from it? Does it require locking to do that? Maybe it does require locking, in which case are we certain that we got ~that~ implemented right? Not just the queue library, but, in the event of an exception in our code, we correctly free the lock? And how long does it take to rebalance the queue? Is that acceptable, since we can't be pulling from the queue during that time? Maybe it doesn't require locking, such as when using immutable data structures where we build a copy and swap it out, but then we might have a chance of executing a task twice (i.e., our task launcher thread reads copyA, while we're modifying copyB, and so the head of the queue in both gets executed), so now we have to keep tabs on what we launched last. But that assumes a stable priority queue in the event of two items having the same time; -that's- a fun edge case to miss. But maybe we get all that working, by getting a lock-free priority queue in place. We have one thread reading from a priority queue, and handing tasks off to a thread pool. What size is the thread pool? What happens if a task is long running? Can we exhaust the thread pool? What happens if we need to scale out a bit, because we're exhausting our thread pool? We only have one thing reading off the queue; can it hand those off to another machine in a timely enough fashion? Probably not, especially if we're getting GC pauses; how do we solve that? Maybe we change it so that we launch things a little early, either locally or remotely, and the thread sleeps until it's time to start the task. That will work, but what happens when we want to update the task? Now the logic exists in two places; the task could still be on the priority queue in which case we have to modify the queue, or the task could be sitting in its own thread, and we have to modify it there (arguably this existed before; if a task had started you modified it in the thread it was executing in, if the task hadn't started you had to modify the priority queue, but this makes it far less determinate). Etc. In Erlang, you skip past all of these issues, and implement the end solution as your first, rather more easily. There's still a data structure somewhere saying what tasks have to execute, and when (probably just in your database, though, nothing needed in memory), but you don't have to worry about managing it beyond "hey, make sure the items for the next (time period) are running in a thread (Erlang process)". You can do that with one process launching the others, and (naive) distribution across machines is incredibly easy (the same complexities of handling partitions apply to both solutions). Individual tasks are built from the beginning to handle sleeping until start time, and updates are trivial, being just a message to them that they respond to, and a modification of your data structure (database). There's no tight coupling between the two. You end up with just "whenever a change in events happens (creation or update), send a message to that process if it exists, and update the DB". And the process scheduler in Erlang handles all the concurrency. There's no locking you have to worry about, and latency will be spread equally, rather than running the risk of choking out a single task. And this is the -naive- Erlang implementation. That's the benefit. For this particular use case, with priority queues you start running into issues, and as you solve them, your implementation looks more and more like the naive Erlang implementation.

rubatuga 10y ago
Thank you so much for the write up, I'm just getting into programming at school and this was a fantastic and interesting read! I've always been interested in how data structures work in real-life applications and I'm thankful for the explanation.