Freesteel Blog » Multi-threading progress object

Multi-threading progress object

Tuesday, January 14th, 2014 at 6:47 pm Written by:

A quick day’s work to make a multi-threading percentage progress handling object in Python that handles residuals.

Let’s start with the test code (which I wrote after the working code — take that TDD!):

class ACProgress:
    def __init__(self):
        self.sumprogress = 0
    def ReportProgress(self, lprogress):
        self.sumprogress += lprogress
        print "The progress is at:", (self.sumprogress *100), "percent"

def addprogress(a, n):
    for i in range(n):
        acprogress.ReportProgress(a/n)
        time.sleep(0.05)

acprogress = ACProgress()
addprogress(1.0, 25)

This prints numbers up to 100% in steps of 4%.

Now we want to do this in threads.

acprogress = ACProgress()
ts = [ ]
for j in range(20):
    t = threading.Thread(target=addprogress, args=(1.0/20, 25))
    t.daemon = True
    t.start()
    ts.append(t)

for t in ts:
    t.join(1)

print "Final progress is", (acprogress.sumprogress *100), "%"

This steps up in increments of 0.2% (a 25th of a 20th) in 20 different threads, but the final result can vary between something like 97.6% and 100% due to the lack of thread safety in ReportProgress(), specifically on the line:

self.sumprogress += lprogress

This is because the code actually evaluates in the following 3 steps:

Step 1:  a = self.sumprogress
Step 2:  b = a + lprogress
Step 3:  self.sumprogress = b

So, if two threads execute these lines in tandem, they’ll both take local copies of sumprogress into a, and return the summed value from each of their b’s which will include the sum from only one, but not both of them. Whichever thread leaves the function last will set the value, and it will therefore be an undercount.

Now, normally, you work round this with a thread lock that blocks other threads from entering and simultaneously executing the same region of code to cause this type of nuisance. This is standard practice, but I didn’t want to do it.

Instead, let’s begin with the list of Python atomic operations, which include array.append() and array.pop() among them.

Suppose we rewrite the object like so:

class ACProgress:
    def __init__(self):
        self.progressstack = [ ]
    def ReportProgress(self, lprogress):
        self.progressstack.append(lprogress)
        print "The progress is at:", (sum(self.progressstack)*100), "percent"

Now it’s always going to sum to 100%, because the progressstack list will faithfully accumulate everything that’s appended into it.

Unfortunately, this is a little inefficient when we start having millions of tiny progress increments. What we need is a combination of the two:

class ACProgress:
    def __init__(self):
        self.sumprogress = 0
        self.progressstack = [ ]
        self.sumprogress = 0
        self.tokenlist = [ 999 ]

    def ReportProgress(self, lprogress):
        try:
            token = self.tokenlist.pop()          # atomic
        except IndexError:
            self.progressstack.append(lprogress)  # will be accumulated later
            return

        # add in the progress
        self.sumprogress += lprogress
        while self.progressstack:      # non-empty false positives not possible
            self.sumprogress += self.progressstack.pop()
        print "The progress is at:", (self.sumprogress*100), "percent"

        self.tokenlist.append(token)   # return the token

Who knows if this is more efficient because I have avoided use of a Lock? Avoiding Locks is good. The magic happens at the pop() where only one thread at a time can get the single value from the array; all others get the exception.

What more do I need?

I need to handle residuals.

What are residuals?

Well, the way the progress works is that I have divided up my operation several large pieces, which I have distributed to the threads, and these threads do their work in thousands of little pieces, but we’re never quite sure how many.

The trick is to think in terms of overall proportion of the work package in relation to the job, not the time for the work.

Focus on creating a progress meter that goes from 0% to 100% sort of evenly.

Let’s say we have 7 fields we need to plough, and 3 farmers with tractors to do the ploughing. Only one farmer can work in a field at a time. We need to rate the progress towards completion through the day on the progress meter.

First, allocate percentages of the overall job per field so that they add up to 100%. Suppose there are 3 big fields and 4 small fields. Then we can assign 20% to each of the big fields, and 10% to each of the small fields.

Now each farmer goes to a field and starts work, knowing the percentage of the allocation for that field. Suppose he picks a small field and starts ploughing. Every time he completes a furrow line he’s going to phone back to the Controller with a number until the work is completed. His numbers should all add up to 10%, which is the allocation for this field.

In the beginning he looks at the field and thinks he can do it in about 5 furrow lines. So after each furrow he calls back with the number 2%. If he guessed correctly, then his numbers will all add up to 10%, which is the allocation.

All the farmers across the other fields are doing the same concurrently, and the Controller is adding up a progress value that advances to 100% relatively evenly throughout the day until the whole job is done.

But wait, the farmer in the small field estimated the furrows wrongly. When he gets to 4th furrow he can see there are actually 2 more furrows to do to make a total of 6. He can’t give 2% to each one of them, because that would add up to 12%, which is beyond his allocation. Instead he cuts down on his reporting, so the last 2 rows are given only 1% each.

This is not a big problem, because the overall progress meter will still look okay as it advances through the day.

Chances are he will have seen that his estimation was out a little earlier on and could spread the numbers more evenly.

But what happens if he over-estimates and there are only 3 furrows needed. Does he apply 2% on the first 2 furrows and lump 6% onto the last one? That would be uneven. The progress meter would suddenly jump forward. It’s usually a mess because towards the end of the work you’re never sure how many scraps are left. You could potentially be left with a very large unallocated amount.

So instead of creating an unnecessary bump, what he does when he completes a field is phone back with a residual — the part of his allocation that he did not use.

The residuals get cumulatively subtracted from a limitprogress value that starts at 100%. After the first farmer has returned his residual of 4%, the Controller knows that when everything is completed at the end of the day the sumprogress will only add up to 96%. This limitprogress will gradually decrease throughout the day as more residuals come in. And instead of setting the progress meter tracking the sumprogress value, it should be set to sumprogress/limitprogress, so that at the end of the day when the total job is done it will have reached 100%.

But still, when the residuals get added in, there would be a bump because, say, when the sumprogress is at 70%, and the limitprogress is reduced from 100% to 90%, the progress meter will jump from 70% to 77%.

What we need to do is spread that bump between the remaining 30% of the progress meter’s progress.

I do this by also providing a lowerprogress value, which starts at 0.0. For a given sumprogress, the progress meter is calculated to be:

  (sumprogress - lowerprogress) / (limitprogress - lowerprogress)

And when you add in a new residual, the values of the two ends change like this:

  lowerprogress += residual * (sumprogress - lowerprogress) / (limitprogress - sumprogress)
  limitprogress -= residual

This means that there isn’t a bump on the progress meter when we introduce the residual, because:

(sum - lower -  res * (sum - lower) / (limit - sum)) / 
                        (limit - res - lower -  res * (sum - lower) / (limit - sum))
    = ((sum - lower)*(limit - sum) -  res * (sum - lower)) / 
                        ((limit - res - lower)*(limit - sum) -  res * (sum - lower))
    = ((sum - lower)*(limit - sum - res)) / 
                        ((limit - res - lower)*(limit - sum) -  res * (sum - lower))
    = ((sum - lower)*(limit - sum - res)) / 
                        ((limit - lower)*(limit - sum) -  res * (limit - sum + sum - lower))
    = ((sum - lower)*(limit - sum - res)) / 
                        ((limit - lower)*(limit - sum - res))
    = (sum - lower) / (limit - lower)

In practice, to avoid a division by zero, it’s better to put, say, 90% of the residual into the limitprogress, and the remaining 10% sumprogress, because when each field is done it’s okay to have at least a small step forward.

Leave a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <blockquote cite=""> <code> <em> <strong>