Two Workers Are Quadratically Better Than One(hillelwayne.com)
hillelwayne.com
Two Workers Are Quadratically Better Than One
https://www.hillelwayne.com/post/queueing-prism/
11 comments
"If jobs are randomly coming in at the same speed that a worker can work, you will get a line. The lines can grow without bound, and the average length of the line is linear in the amount of time this has been going on. Therefore the amount of time spend waiting in line grows quadratically with how long this has been going on."
I don't think this is true, unless I'm misunderstanding your description. Do you mean if the work comes in faster than the worker can process it?
If work arrives at the same rate the worker can process it, the depth of the queue is a random walk starting at zero, with the restriction that it can never go below zero. I'm not sure how that behaves, but it definitely grows much less than linearly.
Python simulation code below:
I don't think this is true, unless I'm misunderstanding your description. Do you mean if the work comes in faster than the worker can process it?
If work arrives at the same rate the worker can process it, the depth of the queue is a random walk starting at zero, with the restriction that it can never go below zero. I'm not sure how that behaves, but it definitely grows much less than linearly.
Python simulation code below:
import random
def random_walk(steps):
count = 0
max_count = 0
for step in range(steps):
if count > 0:
count -= 1
if random.random() > .5:
count += 2
max_count = max(count, max_count)
if step in [2 ** i for i in range(14)]:
print(f"step={step}, count={count}, max_count={max_count}")
for i in range(10):
random_walk(2**13 + 1)Sorry, I dashed that off, and then have been driving kids around.
That is wrong. It is proportional to sqrt(n). And the fact that in the blog post it looked quadratic rather than n^(3/2) suggests that the tool was producing misleading results.
That is wrong. It is proportional to sqrt(n). And the fact that in the blog post it looked quadratic rather than n^(3/2) suggests that the tool was producing misleading results.
Along with the probability distribution on arrivals, there’s a probability distribution on work times. There’s a chance that a job takes longer than average, which would cause the queue to grow longer. You might say, “Yeah, but they could also be shorter than average.” And you’d be right. But consider: If the average job takes 5 steps, then “shorter” means 1-4. Longer means 6-infinite. A single job taking 25 steps (5x average) would require either a lull in arrivals (statistically possible but unlikely) or a series of short jobs to balance it out. And while waiting for the queue to die down, yet another job could take longer than average setting you back again. You can only improve the queue in small increments, but you can increase it arbitrarily with one bad job.
What distribution are you thinking of?
Usually arrival is a Poisson distribution and work time is an exponential distribution, IIRC. But I’ll admit I’m rusty on the stats since it’s been nearly 15 years since I was in college, and professionally I haven’t had to use it much.
I tried an exponential distribution with its mean equal to the rate work is processed and got the same result.
Edit: same qualitative result (substantially sublinear). Didn’t try to fit it to a distribution.
Edit: same qualitative result (substantially sublinear). Didn’t try to fit it to a distribution.
To be more precise, the mathematical models usually assume that people arrive at one rate regardless of how recently someone arrived, and work finishes at another rate regardless of how long you have been working.
This makes the time between arrivals, and the time to complete a job both exponential distributions. It also makes the number of arrivals while a job is being worked on into a Poisson distribution.
For a computer simulation you can simplify this even further by forgetting about time and focusing on events. If the worker is busy, the next event is either a new arrival or a job completion with a probability based on the rates.
This makes the time between arrivals, and the time to complete a job both exponential distributions. It also makes the number of arrivals while a job is being worked on into a Poisson distribution.
For a computer simulation you can simplify this even further by forgetting about time and focusing on events. If the worker is busy, the next event is either a new arrival or a job completion with a probability based on the rates.
One of the simplest and most common approximations is to assume a Poisson process for arrivals, which corresponds to exponential distribution of the inter-arrival times.
It's tempting to model work time with an exponential distribution too, and there's a lot of theory for this case. Unfortunately, exponential distribution has a mode = 0, so it's not a good choice for real life process times. It's more common to see distributions like lognormal, gamma, Weibull, loglogistic, beta, or others with a mode > 0.
It's tempting to model work time with an exponential distribution too, and there's a lot of theory for this case. Unfortunately, exponential distribution has a mode = 0, so it's not a good choice for real life process times. It's more common to see distributions like lognormal, gamma, Weibull, loglogistic, beta, or others with a mode > 0.
[deleted]
A pet peeve of mine is demonstrating things through programming than can much more easily and clearly be shown with math.
Funny, mine is the exact opposite of yours.
The exact opposite would be:
> A pet peeve of mine is showing things much more easily and clearly with math than demonstrating them through programming.
You probably meant something like
> A pet peeve of mine is demonstrating things through math that can much more easily and clearly be shown with programming.
I don't think andrepd would disagree with the latter. Basically, pick the clearest way to show things.
> A pet peeve of mine is showing things much more easily and clearly with math than demonstrating them through programming.
You probably meant something like
> A pet peeve of mine is demonstrating things through math that can much more easily and clearly be shown with programming.
I don't think andrepd would disagree with the latter. Basically, pick the clearest way to show things.
Not sure about this. The opposite of a pet peeve would necessarily be a undomesticated, wild, or feral peeve.
In this case, by simple inversion that'd be demonstrating things through programming, that would be more challenging to prove with mathematics.
By such a standard, the four-colour theorem would be an example of a feral peeve. However, the work of Agner Krarup Erlang would not.
In this case, by simple inversion that'd be demonstrating things through programming, that would be more challenging to prove with mathematics.
By such a standard, the four-colour theorem would be an example of a feral peeve. However, the work of Agner Krarup Erlang would not.
Spot on, I think if the author spent 30min watching an introductory queuing theory video they'd realize that there's so many factors:
* Workload distribution (heavy tailed, exponential, uniform etc.)
* Scheduling policies (FirstComeFirstServe, ShortestRemainingProcessingTime etc.)
* Arrival rate of the jobs (poisson, uniform etc.) in comparison to their "service" rate
* Workload distribution (heavy tailed, exponential, uniform etc.)
* Scheduling policies (FirstComeFirstServe, ShortestRemainingProcessingTime etc.)
* Arrival rate of the jobs (poisson, uniform etc.) in comparison to their "service" rate
any recommendations in particular? would love to dip a toe into this
(not the author)
(not the author)
Thank you, your comment was more enlightening than that entire article!
This is nitpicking a little but “randomly” requires a very specific definition of the distribution function. Uniform? Poisson? Gaussian? Geometric?...
I’m not sure what the parent was referring to, but the simplest and most common queue model uses a poisson process[0] for both queue entries and exits, which means inter arrival and processing times are both exponentially distributed. This is called an M/M/1 queue,[1] and waiting times can be analyzed with Little’s law, though that breaks down at the inflection point where service times are identical to waiting times.
[0]: https://en.m.wikipedia.org/wiki/Poisson_point_process [1]: https://en.m.wikipedia.org/wiki/M/M/1_queue
[0]: https://en.m.wikipedia.org/wiki/Poisson_point_process [1]: https://en.m.wikipedia.org/wiki/M/M/1_queue
John Cook wrote a very succinct analysis of the problem [1][2]. It uses an analytical model instead of a simulation, which I personally found easier to understand.
[1] https://www.johndcook.com/blog/2009/01/30/server-utilization...
[2] https://www.johndcook.com/blog/2008/10/21/what-happens-when-...
[1] https://www.johndcook.com/blog/2009/01/30/server-utilization...
[2] https://www.johndcook.com/blog/2008/10/21/what-happens-when-...
Its certainly unintuitive. Same issue with single-person bathrooms.
Reminds me of the of the old business problem - the kiosk coffee drive-up has line 6 cars long during morning rush. Then they stop coming when commute time is over. What could/should the business planner do?
Could put in another window, hire double the employees, get the line down to 2 or 3 cars during rush. But that costs a bunch (almost double the run rate).
OR, could raise prices. The line will get shorter. Revenue goes up with no investment, and you'll serve about the same number of cars each commute time (there's always a line, so it doesn't matter how long when calculating cars served during rush, its the same total). Which is a better answer.
See the demand is pretty inflexible, and only lasts say 7-9AM. Meaning your customer count is pretty much fixed. Two windows doesn't actually serve any more people, but costs about double, losing you money.
Reminds me of the of the old business problem - the kiosk coffee drive-up has line 6 cars long during morning rush. Then they stop coming when commute time is over. What could/should the business planner do?
Could put in another window, hire double the employees, get the line down to 2 or 3 cars during rush. But that costs a bunch (almost double the run rate).
OR, could raise prices. The line will get shorter. Revenue goes up with no investment, and you'll serve about the same number of cars each commute time (there's always a line, so it doesn't matter how long when calculating cars served during rush, its the same total). Which is a better answer.
See the demand is pretty inflexible, and only lasts say 7-9AM. Meaning your customer count is pretty much fixed. Two windows doesn't actually serve any more people, but costs about double, losing you money.
Or pull a Chick-fil-a and send someone out with a tablet to take all orders and possibly payments. Takes one extra person (or no extra people if you have a McDonald’s style pay window and food window), and the line moves faster because nearly all orders are ready as soon as the driver reaches the window, or shortly after. No need to raise prices (and thus risk losing customers) if you can increase the throughput with minimal cost.
One of the biggest issues with drive thru lines is that often very few people have actually placed their order at a time, so the kitchen isn’t actually running at the pace needed to handle all the orders that are about to come in. Get the orders earlier and increase the pace in the kitchen, everything else can keep up because the kitchen is the bottleneck in a place like that.
One of the biggest issues with drive thru lines is that often very few people have actually placed their order at a time, so the kitchen isn’t actually running at the pace needed to handle all the orders that are about to come in. Get the orders earlier and increase the pace in the kitchen, everything else can keep up because the kitchen is the bottleneck in a place like that.
Many coffee shops are limited to the rate they can build drinks. A backlog of orders wouldn't speed those up.
But I get the point. There may be some processes that are order-rate-limited. Witness the technology put in place at Fry's Electronics, with their signaling paddles like a ramp agent at an airport. How nice if your biggest problem is, taking the customers' money fast enough!
But I get the point. There may be some processes that are order-rate-limited. Witness the technology put in place at Fry's Electronics, with their signaling paddles like a ramp agent at an airport. How nice if your biggest problem is, taking the customers' money fast enough!
Around here that is the Dutch Bros or general coffee drive up process already. It also lets the people in the shop just make drinks instead of stopping to use the cash register or back (including any hand sanitation in between). Though Dutch is usually well staffed and rarely not busy.
> See the demand is pretty inflexible, and only lasts say 7-9AM
This is the base hypothesis that doesn’t match semi-realistic situations.
As long as the demand exceeds your lining capacity (let’s say no more than 20 cars because of sheer space constraints, or when the last in queue would be served past 9AM, which is an actually inflexible limit), consuming the queue twice or three times as fast would bring more revenue.
It stops being interesting expanding mostly when your processing ability match the demand or it the cost/benefit balance changes (e.g. you have to buy the surrounding buildings)
This is the base hypothesis that doesn’t match semi-realistic situations.
As long as the demand exceeds your lining capacity (let’s say no more than 20 cars because of sheer space constraints, or when the last in queue would be served past 9AM, which is an actually inflexible limit), consuming the queue twice or three times as fast would bring more revenue.
It stops being interesting expanding mostly when your processing ability match the demand or it the cost/benefit balance changes (e.g. you have to buy the surrounding buildings)
I don't think so. Its not a line limit, its a mean length issue. If you spend more and empty the line, then you haven't made a dime more. In fact if you spent money doing that, you lost money.
That's the issue - if the customer pool is inflexible, the rational thing is to raise prices until you hit that limit.
Now if the line is self-limiting (folks wont queue if it 'looks too long') then there's something to that.
That's the issue - if the customer pool is inflexible, the rational thing is to raise prices until you hit that limit.
Now if the line is self-limiting (folks wont queue if it 'looks too long') then there's something to that.
There's a fastfood chain in Poland named North Fish, which serves relatively expensive fish burgers etc., but at the same time offers a 50% discount on everything during the last 30 minutes of their business day.
The lines are indeed short there, but I only discovered this discount scheme by accident - they don't advertise it too heavily.
The food is average for the price and they're always right next to other options which leads me to believe that it's the short lines that are their product.
The lines are indeed short there, but I only discovered this discount scheme by accident - they don't advertise it too heavily.
The food is average for the price and they're always right next to other options which leads me to believe that it's the short lines that are their product.
Isn't there the assumption in this article that tasks will come in faster than one person can deal with them, which of course leads to an exponential/snowball effect.
To then add a second person, keeping the same input, isn't it obvious that the task latency will drop more than linearly? (Because two ppl working on tasks coming in will be able to respond in the minimal time, rather than them banking up)
Task management, nor stats, are part of my wheelhouse, so I assume I missed some glaring detail about this article?
To then add a second person, keeping the same input, isn't it obvious that the task latency will drop more than linearly? (Because two ppl working on tasks coming in will be able to respond in the minimal time, rather than them banking up)
Task management, nor stats, are part of my wheelhouse, so I assume I missed some glaring detail about this article?
> Isn't there the assumption in this article that tasks will come in faster than one person can deal with them
Yes this is an assumption. This isn't important though - you use a queue when you think tasks will have some level of build-up anyway i.e. the chance of the task being above your processing speed is non-zero.
> Because two ppl working on tasks coming in will be able to respond in the minimal time, rather than them banking up
No - that's not what the article is suggesting at all. It's saying that when you have two workers, the relative probability that both workers are queued up at the same time, causes the loss of the quadratic relationship between latency and N (see formula at the end).
EDIT:
Clarification on the first part. It is not that they will come in faster than the processing speed, but they that they can.
Yes this is an assumption. This isn't important though - you use a queue when you think tasks will have some level of build-up anyway i.e. the chance of the task being above your processing speed is non-zero.
> Because two ppl working on tasks coming in will be able to respond in the minimal time, rather than them banking up
No - that's not what the article is suggesting at all. It's saying that when you have two workers, the relative probability that both workers are queued up at the same time, causes the loss of the quadratic relationship between latency and N (see formula at the end).
EDIT:
Clarification on the first part. It is not that they will come in faster than the processing speed, but they that they can.
Isn't there the assumption in this article that tasks will come in faster than one person can deal with them, which of course leads to an exponential/snowball effect.
They are coming in at exactly the speed that one person can deal with them. Which means that in the long run the worker is always working, and lines can get arbitrarily long. That is what causes his "quadratic".
A second worker makes the odds of a long line drop dramatically.
They are coming in at exactly the speed that one person can deal with them. Which means that in the long run the worker is always working, and lines can get arbitrarily long. That is what causes his "quadratic".
A second worker makes the odds of a long line drop dramatically.
I may be reading it wrong, but if there is a 50% chance that a worker can finish a task in one turn, two workers would help keep the backlog down to linear time. But I learned it from Alvin Drake in 6.041.
Is adding a second worker just equivalent to halving the amount of work?
I don't think this article answered that question.
Since the problem is really that the first worker is overburdened, by being asked to work at maximum capacity plus randomness.
I don't think this article answered that question.
Since the problem is really that the first worker is overburdened, by being asked to work at maximum capacity plus randomness.
> Isn't there the assumption in this article that tasks will come in faster than one person can deal with them, which of course leads to an exponential/snowball effect.
Not everything that grows, not ever everything that grows fast, grows exponentially.
Not everything that grows, not ever everything that grows fast, grows exponentially.
I grepped the article for "Amdahl" before reading, didn't see it and stopped reading.
It's my version of not reading specifications for perpetual motion machines.
It's my version of not reading specifications for perpetual motion machines.
Wow this title is really confusing. If "Workers" are read as "employees", then the conclusion is false and depends on the use-case, especially as organizational/communication overhead scales quadratically (N choose 2) and reduces marginal value of every additional worker. It appears the author is talking about background workers processing task queues. This title should be changed to avoid confusing people who don't read articles and only read titles.
I actually thought that was what this was about when I clicked the link. And I actually agree with that result - while the lines of communication grow by n(n - 1) as you add more people, and in general this leads to diminishing returns in productivity when you add more and more people to a project, from personal experience I can say that the communication added by the jump from 1 -> 2 actually helps you clarify your thoughts and goals, and the companionship and social accountability helps you stay motivated and avoid procrastination, leading to a net gain in productivity.
The title kinda funny as it could be understood as 1*1 or pow(1,2) which is still 1
I'm guessing we assume that the second worker doesn't steal the machine resources of the first worker in this case?
Has anyone here actually observed this? Seems very optimistic.
No lie one of the big inspirations for this post came from a time I was stuck waiting in a bank teller line where both tellers were blocked by long tasks, and noticing how much faster things moved when one of them freed up.
[deleted]
Pretty much every call center every day. It's a numbers game between having enough agents to handle every call without the queue getting backed up, and having few enough agents that they aren't sitting around with nothing to do. This is called the Erlang C formula and there are a variety of calculators on the net if you want to play with it.
I currently work at a place that prioritizes employee utilization over process speed, so my team has a foreverqueue to ensure that time on task (TOT on my metrics dashboard) is maximized to its fullest. I'm just glad it is tickets and not phone calls.
I currently work at a place that prioritizes employee utilization over process speed, so my team has a foreverqueue to ensure that time on task (TOT on my metrics dashboard) is maximized to its fullest. I'm just glad it is tickets and not phone calls.
I only skimmed this, but it seems like they're not measuring latency at all. They're measuring the time for each item in the queue to be worked on, and then summing all of those times, which is quadratic if latency increases linearly.
Now, I only skimmed this, but I do feel comfortable condemning it based on what I gleaned from skimming.
Now, I only skimmed this, but I do feel comfortable condemning it based on what I gleaned from skimming.
“Logic, n. The art of thinking and reasoning in strict accordance with the limitations and incapacities of the human misunderstanding. The basic of logic is the syllogism, consisting of a major and a minor premise and a conclusion - thus:
Major Premise: Sixty men can do a piece of work sixty times as quickly as one man. Minor Premise: One man can dig a post-hole in sixty seconds; Therefore- Conclusion: Sixty men can dig a post-hole in one second.
This may be called syllogism arithmetical, in which, by combining logic and mathematics, we obtain a double certainty and are twice blessed.” --Ambrose Bierce, The Devil's Dictionary
Major Premise: Sixty men can do a piece of work sixty times as quickly as one man. Minor Premise: One man can dig a post-hole in sixty seconds; Therefore- Conclusion: Sixty men can dig a post-hole in one second.
This may be called syllogism arithmetical, in which, by combining logic and mathematics, we obtain a double certainty and are twice blessed.” --Ambrose Bierce, The Devil's Dictionary
It starts with a simple subject, and a mildly interesting result. Then obfuscates it with an unenlightening and confusing model. Then shows how to do lots of exploratory programming with that model and create apparently surprising results. Then uses it to sell the modeling tool so that you too can come to surprising results about things in a way that does not enlighten.
Here is the simple subject. If jobs are randomly coming in at the same speed that a worker can work, you will get a line. The lines can grow without bound, and the average length of the line is linear in the amount of time this has been going on. Therefore the amount of time spend waiting in line grows quadratically with how long this has been going on.
Add a second worker and the average length of line becomes a fixed, small number. Time waiting is now linear.
Add jobs as fast as both workers can work and voila, lines start growing again!
There are a lot of interesting results in queuing theory. But the stated style of experiment doesn't seem like a good way to figure it out.