Two Workers Are Quadratically Better Than One
hillelwayne.com
hillelwayne.com
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.
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)Edit: same qualitative result (substantially sublinear). Didn’t try to fit it to a distribution.
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.
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.
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.
> 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.
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.
* 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
(not the author)
[0]: https://en.m.wikipedia.org/wiki/Poisson_point_process [1]: https://en.m.wikipedia.org/wiki/M/M/1_queue
[1] https://www.johndcook.com/blog/2009/01/30/server-utilization...
[2] https://www.johndcook.com/blog/2008/10/21/what-happens-when-...
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.
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.
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!
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)
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.
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.
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?
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.
It's my version of not reading specifications for perpetual motion machines.
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 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.
Not everything that grows, not ever everything that grows fast, grows exponentially.
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.
Now, I only skimmed this, but I do feel comfortable condemning it based on what I gleaned from skimming.
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
And if they have a standup meeting beforehand to give status updates and "identify blockers," it's going to take even longer.