13 ms·
Two Workers Are Quadratically Better Than One
- antiquark 6y agoFrederick Brooks would disagree.
- Jtsummers 6y agoLikely he wouldn’t. The premise here is of a task that can be done in parallel here by multiple workers. Brooks’ comment (9 women can’t make a baby in 1 month) is about a task that cannot be divided among workers.
- cmroanirgo 6y agoIsn'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?
- ywei3410 6y ago> 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.
- rmrfstar 6y agoI 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.
- btilly 6y agoIsn'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.
- baking 6y agoI 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.
- learnstats2 6y agoIs 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.
- eru 6y ago> 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.
- nobody9999 6y ago“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
- Jtsummers 6y agoBut sixty men could make sixty post-holes in sixty seconds.
- ouid 6y agoI 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.
- FpUser 6y agoThe title kinda funny as it could be understood as 1*1 or pow(1,2) which is still 1
- btilly 6y agoThis article epitomizes a phenomena that I don't like. 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.
- hyperpape 6y ago"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: 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)
- deleted 6y ago[deleted]
- vladTheInhaler 6y agoJohn 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-joel-on-queuing/ https://www.johndcook.com/blog/2009/01/30/server-utilization... [2] https://www.johndcook.com/blog/2008/10/21/what-happens-when-you-add-a-new-teller/ https://www.johndcook.com/blog/2008/10/21/what-happens-when-...
- ravenstine 6y agoHas anyone here actually observed this? Seems very optimistic.
- hwayne 6y agoNo 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 6y ago[deleted]
- jabroni_salad 6y agoPretty 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.
- JoeAltmaier 6y agoIts 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.
- Jtsummers 6y agoOr 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.
- JoeAltmaier 6y agoMany 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!
- 6y ago
- anonytrary 6y agoWow 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.
- m12k 6y agoI 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.
- didibus 6y agoI'm guessing we assume that the second worker doesn't steal the machine resources of the first worker in this case?