5 ms·
Instead of picking the fastest lane, it would in principle be faster to distribute all your items across all the lanes. That way, you minimize the time from you
by ssp 16y ago
Instead of picking the fastest lane, it would in principle be faster to distribute all your items across all the lanes. That way, you minimize the time from you are first in line until you are checked out.
Consider the problem of optimizing the response time of a set of servers. Load balancing - keeping the hardware busy - will keep the request queues at roughly equal and therefore minimize the maximum queue length. That ensures that the hardware is as busy as possible, but you can improve on that.
When a new request arrives, you can either add all of that request to one queue, or you can split it into pieces and distribute those across all the queues. Distributing the request, assuming perfect load balancing, means the latency for that request will be k + 1/n instead of k + 1, where k is the length of the queue.
In other words: Parallelizing gets you a substantial improvement in response time without additional hardware, and without making the code run any faster. I didn't realize the implications of this until recently.
- jamn 16y agoI don't think so, The task you are splitting has to be sizeable enough that the setup costs of parallelization (in this case, going to every cashier to put your stuff and then going and picking it up) don't outweigh the potential benefits from parallelization.In this case, unless you are buying the whole store, it just doesn't make sense to bother splitting your shopping cart like this. Further, if all the cashiers are busy at all the times being useful (ringing customers), you cannot possibly get a gain from splitting any further. There's no way you could improve the throughput of this system when every processing unit (cashier) is at the top of its utilization.
- blaines 16y agoIn the case of groceries wouldn't you only be as fast as the slowest line? Your comment only applies if all lines are equal, which they almost never are. So you can't assume perfect load balancing under this circumstance. I think the best store queueing system is to have one main queue that distributes customers to the first available cashier. People with larger loads take longer, but this has little effect on the main queue.
- silentbicycle 16y ago> In the case of groceries wouldn't you only be as fast as the slowest line? That's a pretty good summary of Amdahl's law. Even a computer with an infinite number of processors can't run a program faster than it takes to run the slowest sequential part.