Two Workers Are Quadratically Better Than One

Re:Two Workers Are Quadratically Better Than One by hyperpape on Thursday November 05, 2020 @07:22PM (#25003605)

"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)

[ Parent | on HN ]

Re:Two Workers Are Quadratically Better Than One by btilly on Thursday November 05, 2020 @09:11PM (#25004208)

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.

[ Parent | on HN ]

Re:Two Workers Are Quadratically Better Than One by Jtsummers on Thursday November 05, 2020 @07:57PM (#25003799)

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.

[ Parent | on HN ]

Re:Two Workers Are Quadratically Better Than One by hyperpape on Thursday November 05, 2020 @08:44PM (#25004052)

What distribution are you thinking of?

[ Parent | on HN ]

Re:Two Workers Are Quadratically Better Than One by Jtsummers on Thursday November 05, 2020 @08:55PM (#25004118)

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.

[ Parent | on HN ]

Re:Two Workers Are Quadratically Better Than One by btilly on Thursday November 05, 2020 @09:28PM (#25004297)

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.

[ Parent | on HN ]

Re:Two Workers Are Quadratically Better Than One by srg0 on Friday November 06, 2020 @05:57AM (#25006691)

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.

[ Parent | on HN ]

Re:Two Workers Are Quadratically Better Than One by hyperpape on Thursday November 05, 2020 @09:12PM (#25004214)

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.

[ Parent | on HN ]