Freesteel Blog » Washing the progress bar

Washing the progress bar

Wednesday, February 26th, 2014 at 1:41 pm Written by:

Last year we got a chance to see SolidCAM’s iMachining and laughed at the way its progress bar jumped all over the place, from -14% to 200% and back again.

Then we looked at our own Adaptive Clearing strategy which we had just spent the past year making multicore — and noticed it did the same stupid thing!

How embarrassing.

You never notice yourself picking your own nose, but when someone else does it in your face, you realize it’s ugly.

Progress bars don’t get as much love and attention from the programmers as they ought to, given how much time the users have to stare at them. The users think it’s so normal for the progress bar to be absolutely wrong that it’s considered a sign of extreme naivety to think about complaining. They probably believe that we’d going to laugh at them if they raised the issue.

It turns out that the progress bar on multiple CPU processing is not hard to get right, but you do it differently to how you do it on a single-threaded process.

Let’s first think about what a progress bar is for. There are two different options. It could report the time remaining for the process to complete, or it could report the percentage of the process job that has been completed.

The time remaining might be the most useful information for organizing your life (is there enough time to grab lunch while this completes?), but there’s no way you’re going to get that information — even though it’s what everyone wants to know.

You will hear: “How many days till it’s done?” more often than “Are we at the 75% complete stage yet?” for a project — and that’s even before it’s over-run by a factor of two.

In fact, the only practical implementation for the time remaining is to run the whole job first, time it, and then set a count-down timer from that value when you run it again. It’ll make everything run twice as slow, but what’s the big deal?

And just suppose we implemented a percentage-complete progress bar that was accurate according to the definition that it moved at a constant rate from 0 to 100%. This would be a scale-free number that didn’t depend on the speed of your processor, or the fact that you have decided to watch a video while you waited, or created all kinds of other factors it is impossible to predict.

If this percentage-complete value was accurate enough in time, you could measure how long it took for the first 5% to pass, and multiplied the number by 19 to estimate the time to completion. Good enough?

Washing dishes

There are 8 plates and 2 oven pans in the sink.

Single-threaded version 1: Take each item from the sink, wash it, dry it, put it in the cupboard, and set the progress bar to the value (number of items done)/(total number of items) = n/10.

nitems = 10; 
for (i = 0; i < nitems; i++) {
    washitem(i); 
    setpercentprogress(100*(i+1)/nitems); 
}

The item number i steps from item 0 to item 9, and you need to add 1 to this value to state the number of items that are complete after you have washed each one.

Progress is going to be a bit juddery and uneven, because the oven pans take longer than the plates to wash, and 10% is a big increment.

Single-threaded version 2: Oven pans are harder to wash than plates. Count 6 points for each pan, and 1 point for each plate. This adds up to 20 points. Do the pans first. Set the progress bar to the sum of the points for the items already done divided by 20.

npans = 2; nplates = 8 
pantoplateworkratio = 6; 
totalpoints = pantoplateworkratio*npans + nplates;
for (i = 0; i < npans; i++) {
    washpan(i); 
    setpercentprogress(100*(i+1)*pantoplateworkratio/totalpoints); 
}
for (j = 0; j < nplates; j++) {
    washplate(j); 
    setpercentprogress(100*(npans*pantoplateworkratio + (j+1))/totalpoints); 
}

This implementation is getting a bit complicated, but it’s all based on in-line linear equations, and you can see how it evolves as part of the natural process of software development. The first loop moves us from 0% to 60%, and the second loop goes from 60% to 100%.

Suppose we wanted to break down each operation into proportions of 2/5 for washing, 2/5 for drying and 1/5 for putting in the cupboard components, then we’d expand the first loop to read:

    scrubplate(i); 
    setpercentprogress(100*(i+0.4)*pantoplateworkratio/totalpoints); 
    dryplate(i); 
    setpercentprogress(100*(i+0.8)*pantoplateworkratio/totalpoints); 
    plateintocupboard(i); 
    setpercentprogress(100*(i+1.0)*pantoplateworkratio/totalpoints); 

The code evolves and spreads out line this. You simply keep inserting new terms into your setpercentprogress() function calls. It’s not how you would design it if you were starting fresh, but programming is a process of constantly repairing an old machine and patching up its pipe-work to handle new chemicals.

Multi-threaded version 1: How about we set one person to do the plates, and the other to do the pans? Now you’re going to see the progress bar jumping back and forth between a number in the 0 to 60 range and a number in the 60 to 100 range. If, furthermore, each person doesn’t know how many items are in the other person’s sink, like they’ve randomly picked 2 pans and 3 plates for one of the sinks, the conflicts are going to be greater and may even account for the jumpy -14% and +200% ranges.

Single-threaded version 3: Create a special progress object that keeps count of how much progress has been made. Using the points system we have allocated 5% to each plate and 30% to each pan. Also, subdivide these incremental progress percentages into the individual components, like so:

Pick a plate out of the sink, wash it (+2%), dry it (+2%), into the cupboard (+1%). Take a pan out of the sink, wash it (+12%), dry it (+12%), into the cupboard (+6%).

This is getting smoother. But you could break down the drying part into smaller operations of, say, each of three wipes of the tea towel. Also, it doesn’t take that much longer to put an oven pan into the cupboard than a plate, so you should reserve a larger proportion of the pan time for the scrubbing and less for the putting away. Take a pan out of the sink, wash it (+25%), dry it (+3%), into the cupboard (+2%).

Now you have a system where it doesn’t matter what order you do the items, how many people are doing it concurrently, or what jobs they do. You could have a stack of plates on the draining board and two people drying them. If one of the plate-washers finishes first, they could join in the job of putting them away.

Multi-threaded version 2: These percentages may look pretty simple, but there’s the minor issue of how to get the numbers allocated to each component of each item in a sensible way. Those messy calculations of the form setpercentprogress(100*(i+0.4)*pantoplateworkratio/totalpoints) have to happen somewhere, they don’t just go away.

We got into a tangle with this, until we stopped trying to do the calculations in-line, and instead allocated all the percentages at the very start of the operation. We stuck three numbers onto each item while they were still in the sink, one for the washing, another for the drying, and one for the putting away. This can be done in one thread that has the big picture and all the available information. Now, as each job gets done (a pan gets dried), the process peels the stamp displaying the incremental progress allocated to it for the work and sends it to the progress object. Easy.

One of the challenges is that the sink water is dirty so you can’t see exactly how many plates there are left to do. To handle this, we work with an estimate and keep allocating an absolute percentage for each item that comes out of the sink from a remaining stock of allocations. When we run out of plates to wash, we report a residual allocation to the progress object, and it tries to spread out this error across the remaining space on the progress bar, as I outlined in this post about the progress object.

In the Adaptive Clearing algorithm we have 7 stages in the process, instead of just 3 for washing up, and some of the components depend on adjacent pairs (like relinking) so cannot be isolated. There are also two independent hierarchies of allocations and residuals, for the layers and for the toolpaths within each layer.

Here is a diagram of the process with the progress bar value super-imposed. It’s not a very good result, as you can see, but we’ve been working on it.

progressgraph1
progressgraph2

We should put some effort into balancing the proportions between the operations, but we don’t have time for that work right now. Maybe we’d do it if the users started complaining more about it. We can now see some problems with the strategy by the way the progress bar stalls. As a rule, if you can’t see a problem, you can’t fix it.

The original outline for this story involved harvesting potatoes from a valley with a number of farms, each farm with a number of fields, each field harvested by a number tractor runs along its length producing truckloads of potatoes that were taken back to the barn to be individually washed, sorted and bagged into sacks all overseen by an impatient manager who just wanted to know how much longer it was all going to take to get done.

Washing dishes is so much simpler. I don’t know why I didn’t think of it until now.

1 Comment

Leave a comment

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