19 deleted 16938 characters in body
source | link

Are there completely different techniques of reporting progress that I've overlooked?

All my answers tend to be a bit long-winded, but bear with me. I've designed progress bars multiple times over the years for applications (games, audio, VFX -- typically with proprietary GUIs) that do some hefty operations over very large input data. My latest design has made me the happiest, by far. I'll try to cover the main alternative strategy I was exploring before I settled on this design though. Maybe sharing this experience will help in some way.

Pushing

All but my latest incarnation of the progress bar used a push-based design, and all but my latest incarnation had the UI front-end processing (including event processing) and the back-end doing the work in the same thread. They also all had the same needs:

  1. Modality: Operations were synchronous and modal in nature. For example, a progress bar would display to the user when first loading a video game or going to the next stage while the data was being loaded from a floppy disk. More modern examples would be like a progress bar showing up and blocking the user while loading a hefty file after choosing to open a file from a menu. Some tweaks could be made to this design to make it work for asynchronous cases where multiple operations are going on simultaneously (the Progress object would turn into a collection).
  2. Nested Operations: Operations could be nested without explicit knowledge about how much total work was required. An outer operation might know it has 3 iterations of work, for example, but the inner operation it invokes for all 3 iterations might each require 100 iterations of work. The total amount of work is 300 iterations, but the outer operation doesn't know that -- it only knows it has 3 iterations of work.
  3. User Abort: The user can abort at any time (ex: by pressing escape key or clicking a button).
  4. Granular Iterations: Some of the iterations of work could be very, very granular in nature (ex: incrementing progress a million times in a tight loop along side of light iterations of work).

Push Design

The fundamental design for my push-based progress designs haven't changed much even since the days I was writing DOS applications. At the heart of it was a Progress bar object (originally globally-accessible, later passed through the call stack and threads), which was basically a signal with some simple state.

Stack

The state consisted of a simple stack with two integers for each entry (step and num_steps). This allowed for those nested operations described above in #2 so that the total progress could be calculated without the outer operation knowing how many iterations of work would be performed by the inner one, like so:

enter image description here

Beginning a new operation would push to the stack, ending it would pop from it. The UI observer side of the progress bar would not show up if the stack is empty.

Signal

In addition to the stack making up the Progress object's state was also a collection of function pointers that could be called on modifying the progress (effectively a list of observers as people call it nowadays).

The GUI code can hook into that and get notifications of when the progress bar was implemented.

Interface

The interface for the progress object consisted of these functions:

// Returns true when in the middle of an existing operation.
bool active();

// Begins a new/nested operation.
void begin(num_steps);

// Ends the current operation.
void end();

// Increments the current operation by a single step.
// This does nothing if the user aborted already.
void inc();

// Requests to abort the operation.
void abort();

// Returns true if the user requested to abort the operation.
bool aborted();

// Returns the total amount of progress as a percentage in
// the range, [0, 1].
float total();

// Adds an observer that's notified about progress events.
void attach_observer(observer);

// Removes an observer so that it will no longer be notified.
void detach_observer(observer);

... something to this effect. There was some temporal coupling here between begin/inc/end but this was back in C when it wasn't so easy to avoid (no closures, e.g.).

The GUI code would start off adding an observer that would be notified whenever a new operation has begun, when an existing one has ended, and when progress has been made.

Client Code

The client code then looked like this (pseudocode):

void outer_operation(progress):
{
    progress.begin(3);
    for (j=0; j < 3; ++j)
    {
       inner_operation(progress);
       progress.inc();
       if (progress.aborted()) // If user aborted:
       {
          // Roll back any side effects/release resources.
          break;
       }
    }
    progress.end();
}

void inner_operation(progress)
{
    progress.begin(100);
    for (j=0; j < 100; ++j)
    {
       // Do some work.
       progress.inc();
       if (progress.aborted()) // If user aborted:
       {
          // Roll back any side effects/release resources.
          break;
       }
    }
    progress.end();
}

Exception-Handling

One of the pains with this design was just checking to see if the user aborted, as with manual error-handling/propagation in general. Later I got into C++ and that allowed the design to eliminate this aborted query, making it so I could simply throw an exception indicating that the user aborted if inc was called on a progress object which was already in an aborted state. The code then started taking on this shape:

void outer_operation(progress):
{
    Monitor mon(progress, 3);
    try
    {
        for (j=0; j < 3; ++j)
        {
           inner_operation(progress);
           ++mon; // this will throw if user aborted
        }
    }
    catch (exception& ex)
    {
        // Report error if error message is not empty.
    }
}

void inner_operation(progress)
{
    Monitor mon(progress, 100);
    for (j=0; j < 100; ++j)
    {
        // Do some work.
        ++mon; // this will throw if user aborted
    }
}

For user-abort exceptions, I'd just throw an exception with an empty message to avoid showing anything in the UI (since doing so would be kind of redundant when the user explicitly interrupted the operation himself/herself). Might be a questionable practice (and could vary by needs), but I preferred the idea of more catch-all clauses instead of trying to catch each and every different exception type (since I couldn't always anticipate every possible exception that could occur, and most of the time I'd just end up reporting a message).

Smooth, Responsive Progress

The above kind of design worked at a basic level. It was fairly easy to use and the notion of Progress was decoupled from GUI code, making it easy to swap out GUI front-ends in the future without touching the logical aspects of the codebase.

But there existed a latency vs. throughput problem, and it had to do with the interaction of #3 (user abort) and #4 (granular iterations). Since the UI would simply refresh whenever it was notified of a progress change, incrementing the progress bar at a very granular level would yield a very smooth and responsive progress bar, but slow down the whole operation. There was an embarrassing case once where I noticed that I was incrementing the progress bar at such a granular level that a file loading operation took three times longer with the progress updates because I was calling inc so frequently.

To compromise, I captured the system time on the GUI observer side so that it would only refresh the UI every 50 milliseconds or so from the observer, ignoring notifications in between those time intervals (but with some adjustments to always refresh when a progress bar began, e.g.). That made it so these granular calls to inc only increased the time of operations by 35% or so, not more than doubling the time they took. Yet it was still fiddly and kind of ugly that a smooth progress bar would still increase the times by that much.

In some cases I compromised and made it so I don't call inc as often, but that made the progress bar more chunky (not so smooth). For example, I might only increment the progress once per entire scanline of a large image being processed instead of every few pixels. That made it so you'd have to mash the escape key and wait a second or two to abort because inc was being called less frequently. When I started having an abort button inside the GUI itself that users could click on, the responsiveness of clicking the button would drop and feel horrible if inc wasn't called very often to pump UI events.

So there was this ugly juggling act of keeping the progress bar smooth and responsive vs. not slowing down the operation too much as a result of the UI event processing and refreshes.

Thread-Safety

Another problem was that multiprocessor (and later multi-core) hardware was starting to become popular. This design was inherently not thread-safe, as none of the operations involved like incrementing the progress were thread-safe. That was fairly easy to address though by simply implementing a concurrent stack with atomic CAS and making the inc function use atomic increments of the step counter and atomic operations to set the aborted state. The observers would get notified using a deferred mechanism with inc acting as an event pump in the UI thread but as a deferral mechanism in other threads.

Multi-Threaded GUI

Yet it still took a number of years for me to explore a multithreaded GUI application. I often opted in to multithreading with the main thread, by default, processing UI events and also doing some of the heavy-lifting logic. If I needed it, I would simply opt in to distribute work for the operations involved in a separate thread as an optimization detail. The main thread still wanted to, by default, lump processing of UI events together with the UI-independent logic of the operations.

Finally, after some peer pressure, I designed a multithreaded UI kit where the entire UI design was asynchronous in nature. It took a number of iterations to test and get right on all the platforms we were targeting, but after that, it was a piece of cake to run an operation in the main thread which was no longer the UI thread.

... and that finally lead to the pull design.

Pull Design

It might seem backwards to go from a push design (often encouraged) to pull (often discouraged). Yet with the UI processing always residing in a separate thread from the logic, the need to push in every single little call to inc was starting to get incredibly awkward/expensive.

So I actually inverted the paradigm in favor of a pull design. The UI thread would actually sort of poll the progress bar for the current state. To avoid burning up CPU cycles needlessly, however, condition variables were used to put the UI thread to sleep when there was nothing to do (woken up, for example, when begin was called on a progress object or any sort of event was pushed to the GUI event queue).

This made it so calls to inc did nothing more than atomic increment a counter and a check to see if it should throw (if the progress had been aborted). It made it ultra cheap (well, atomic increments are a tad expensive, but vastly cheaper than what I was doing before). The UI thread would then pull that state periodically (not all the time) and update the progress bar as needed.

I found this design to be the most attractive so far, even though it's pull-based. It allowed me to call inc in the most granular iterations of work being done, sometimes even millions of times in an operation with very, very smooth progress and aborts that respond immediately to the touch. It also let me do things like animate a spinning gear while the operation was going without the operation having to pump UI events indirectly through calls to inc.

So I really like this design so far, and it is pull-based, but it gave the most silky-smooth progress bars that instantly abort the operation to the touch (with a little animation that begins the moment you touch the abort key or click the button). Calls to inc became so cheap that I could call them it quite very frequently without a care in the world.

Questions

After sharing that little experience, on to the questions:

Obviously, there has to be some call-back somewhere to make this work.

In my latest case with the pull-based design from another thread, actually no. I would actually recommend exploring a pull design if you end up tackling this multithreaded as I eventually did with similar goals for silky smooth progress and ultra-responsiveness to abort. There are techniques like condition variables/monitors to mitigate burning CPU cycles needlessly querying the state of the progress object.

Pass a mutable object to the back-end, and have the back-end make changes to it on progress. The object notifies the front-end when a change occurs.

This wasIt's difficult to balance efficiency if the way I was originally doing itbackend notifies in this respect. It worked out reasonably well except forWithout care you might find that incrementing your progress ends up doubling or tripling the problems noted where I was having a hard time balancing the throughput ofit takes to complete the operation with the latency of theif you're aiming for a very smooth progress barupdate.

Having a hard time wrapping my head around this approach where you're kind of passing, say, a GUI callback into the operation. This kind of approach would make the notion of who gets notified when progress has been made very flexible, but I can't imagine a scenario where that kind of flexibility is needed. I think easier is to pass along the progress object which already has a list of observers if you explore the push-style design, since I think most scenarios would have you initializing the list of observers infrequently (very possibly, just once when the UI starts). So I'd personally lean, between these two choices, towards the first and have the GUI-independent progress object encapsulate a list of observers which conform to an abstract interface (possibly just a function signature for function pointers, e.g.).

Maybe this kind of design could be helpful for asynchronous cases where you're firing off a bunch of operations asynchronously and want a bunch of progress bars in various places (maybe not even one uniform place). You could also do that by simply constructing this progress object on the fly with a list of the necessary observers though, so probably the choice depends on just how often you might need to do something like this.

Where this mightdon't get awkward is that it might want access to the UI functions at the time of launching the operation unless you can kind of generically pass callbacks through the stack in some kind of generalized way. It might be easier to initialize a GUI-independent progress object towards the bottom of the call stack with UI-based observers, and pass that through as a kind of bundle instead. In that sense, the former design offers this kind of flexibility of just passing a general Progress object through the stack without thinking about propagating individual callbacks through the call stack.

Heuristic Algorithms

There is one last case I forgot to cover, and I see it as inevitably awkward and somewhat unsolvable. It's for heuristic algorithms where the number of iterations cannot be foreseen in advance. The algorithm just finishes when it finishes (kind of like some programmer time estimates -- "it's done when it's done").

Most of the time, it's easy to foresee the amount of work in advance. If we're loading a binary file, for example, a simple trick is just consider how many bytes have been read out of the total. That tends to work well enough.

Yet these heuristic algorithms can't always anticipate the amount of work required in advance. In those cases, I've seen people make suggestions like trying to make the program predict the time it would take based on measurements gathered from previous sessions. To me that's straying a little too far from the KISS territory, and predictions made by the software would be very difficult to make accurate based on simple human factors (ex: a prediction that processing the same amount of input data will take the same amount of time can often fail stupendously due to dynamic factors of the memory access patterns, the differences it introduces to the heuristic algorithm, etc)difference here so much.

The simple method I settled on for these cases is to simply wrap an object for these cases, like HeuristicMonitor, where it actually initializes the total number of steps at 1. Incrementing it does nothing at all except check for abort, but a call to end it (automatically called on destruction) increments it and ends the progress. That turns it into a simple binary state: "not done vs. done". It's kind of ugly with just 0% and 100% states there, but the spinning animated gear and the instant ability to abort keeps it from feeling like the software has locked up or anything of that sort.

Are there completely different techniques of reporting progress that I've overlooked?

Anyway, while rare, these kindsPoll from the front-end in a separate thread with atomic increments in the backend. Polling makes sense here since it's for an operation that finishes in a finite period and the likelihood of heuristic algorithms arethe frontend picking up state changes is high, especially if you're aiming for a bit awkwardsilky smooth progress bar. You could consider condition variables if you don't like the idea of polling from the frontend thread, but in that case you might want to avoid notifying on every single granular progress bar increment.

Are there completely different techniques of reporting progress that I've overlooked?

All my answers tend to be a bit long-winded, but bear with me. I've designed progress bars multiple times over the years for applications (games, audio, VFX -- typically with proprietary GUIs) that do some hefty operations over very large input data. My latest design has made me the happiest, by far. I'll try to cover the main alternative strategy I was exploring before I settled on this design though. Maybe sharing this experience will help in some way.

Pushing

All but my latest incarnation of the progress bar used a push-based design, and all but my latest incarnation had the UI front-end processing (including event processing) and the back-end doing the work in the same thread. They also all had the same needs:

  1. Modality: Operations were synchronous and modal in nature. For example, a progress bar would display to the user when first loading a video game or going to the next stage while the data was being loaded from a floppy disk. More modern examples would be like a progress bar showing up and blocking the user while loading a hefty file after choosing to open a file from a menu. Some tweaks could be made to this design to make it work for asynchronous cases where multiple operations are going on simultaneously (the Progress object would turn into a collection).
  2. Nested Operations: Operations could be nested without explicit knowledge about how much total work was required. An outer operation might know it has 3 iterations of work, for example, but the inner operation it invokes for all 3 iterations might each require 100 iterations of work. The total amount of work is 300 iterations, but the outer operation doesn't know that -- it only knows it has 3 iterations of work.
  3. User Abort: The user can abort at any time (ex: by pressing escape key or clicking a button).
  4. Granular Iterations: Some of the iterations of work could be very, very granular in nature (ex: incrementing progress a million times in a tight loop along side of light iterations of work).

Push Design

The fundamental design for my push-based progress designs haven't changed much even since the days I was writing DOS applications. At the heart of it was a Progress bar object (originally globally-accessible, later passed through the call stack and threads), which was basically a signal with some simple state.

Stack

The state consisted of a simple stack with two integers for each entry (step and num_steps). This allowed for those nested operations described above in #2 so that the total progress could be calculated without the outer operation knowing how many iterations of work would be performed by the inner one, like so:

enter image description here

Beginning a new operation would push to the stack, ending it would pop from it. The UI observer side of the progress bar would not show up if the stack is empty.

Signal

In addition to the stack making up the Progress object's state was also a collection of function pointers that could be called on modifying the progress (effectively a list of observers as people call it nowadays).

The GUI code can hook into that and get notifications of when the progress bar was implemented.

Interface

The interface for the progress object consisted of these functions:

// Returns true when in the middle of an existing operation.
bool active();

// Begins a new/nested operation.
void begin(num_steps);

// Ends the current operation.
void end();

// Increments the current operation by a single step.
// This does nothing if the user aborted already.
void inc();

// Requests to abort the operation.
void abort();

// Returns true if the user requested to abort the operation.
bool aborted();

// Returns the total amount of progress as a percentage in
// the range, [0, 1].
float total();

// Adds an observer that's notified about progress events.
void attach_observer(observer);

// Removes an observer so that it will no longer be notified.
void detach_observer(observer);

... something to this effect. There was some temporal coupling here between begin/inc/end but this was back in C when it wasn't so easy to avoid (no closures, e.g.).

The GUI code would start off adding an observer that would be notified whenever a new operation has begun, when an existing one has ended, and when progress has been made.

Client Code

The client code then looked like this (pseudocode):

void outer_operation(progress):
{
    progress.begin(3);
    for (j=0; j < 3; ++j)
    {
       inner_operation(progress);
       progress.inc();
       if (progress.aborted()) // If user aborted:
       {
          // Roll back any side effects/release resources.
          break;
       }
    }
    progress.end();
}

void inner_operation(progress)
{
    progress.begin(100);
    for (j=0; j < 100; ++j)
    {
       // Do some work.
       progress.inc();
       if (progress.aborted()) // If user aborted:
       {
          // Roll back any side effects/release resources.
          break;
       }
    }
    progress.end();
}

Exception-Handling

One of the pains with this design was just checking to see if the user aborted, as with manual error-handling/propagation in general. Later I got into C++ and that allowed the design to eliminate this aborted query, making it so I could simply throw an exception indicating that the user aborted if inc was called on a progress object which was already in an aborted state. The code then started taking on this shape:

void outer_operation(progress):
{
    Monitor mon(progress, 3);
    try
    {
        for (j=0; j < 3; ++j)
        {
           inner_operation(progress);
           ++mon; // this will throw if user aborted
        }
    }
    catch (exception& ex)
    {
        // Report error if error message is not empty.
    }
}

void inner_operation(progress)
{
    Monitor mon(progress, 100);
    for (j=0; j < 100; ++j)
    {
        // Do some work.
        ++mon; // this will throw if user aborted
    }
}

For user-abort exceptions, I'd just throw an exception with an empty message to avoid showing anything in the UI (since doing so would be kind of redundant when the user explicitly interrupted the operation himself/herself). Might be a questionable practice (and could vary by needs), but I preferred the idea of more catch-all clauses instead of trying to catch each and every different exception type (since I couldn't always anticipate every possible exception that could occur, and most of the time I'd just end up reporting a message).

Smooth, Responsive Progress

The above kind of design worked at a basic level. It was fairly easy to use and the notion of Progress was decoupled from GUI code, making it easy to swap out GUI front-ends in the future without touching the logical aspects of the codebase.

But there existed a latency vs. throughput problem, and it had to do with the interaction of #3 (user abort) and #4 (granular iterations). Since the UI would simply refresh whenever it was notified of a progress change, incrementing the progress bar at a very granular level would yield a very smooth and responsive progress bar, but slow down the whole operation. There was an embarrassing case once where I noticed that I was incrementing the progress bar at such a granular level that a file loading operation took three times longer with the progress updates because I was calling inc so frequently.

To compromise, I captured the system time on the GUI observer side so that it would only refresh the UI every 50 milliseconds or so from the observer, ignoring notifications in between those time intervals (but with some adjustments to always refresh when a progress bar began, e.g.). That made it so these granular calls to inc only increased the time of operations by 35% or so, not more than doubling the time they took. Yet it was still fiddly and kind of ugly that a smooth progress bar would still increase the times by that much.

In some cases I compromised and made it so I don't call inc as often, but that made the progress bar more chunky (not so smooth). For example, I might only increment the progress once per entire scanline of a large image being processed instead of every few pixels. That made it so you'd have to mash the escape key and wait a second or two to abort because inc was being called less frequently. When I started having an abort button inside the GUI itself that users could click on, the responsiveness of clicking the button would drop and feel horrible if inc wasn't called very often to pump UI events.

So there was this ugly juggling act of keeping the progress bar smooth and responsive vs. not slowing down the operation too much as a result of the UI event processing and refreshes.

Thread-Safety

Another problem was that multiprocessor (and later multi-core) hardware was starting to become popular. This design was inherently not thread-safe, as none of the operations involved like incrementing the progress were thread-safe. That was fairly easy to address though by simply implementing a concurrent stack with atomic CAS and making the inc function use atomic increments of the step counter and atomic operations to set the aborted state. The observers would get notified using a deferred mechanism with inc acting as an event pump in the UI thread but as a deferral mechanism in other threads.

Multi-Threaded GUI

Yet it still took a number of years for me to explore a multithreaded GUI application. I often opted in to multithreading with the main thread, by default, processing UI events and also doing some of the heavy-lifting logic. If I needed it, I would simply opt in to distribute work for the operations involved in a separate thread as an optimization detail. The main thread still wanted to, by default, lump processing of UI events together with the UI-independent logic of the operations.

Finally, after some peer pressure, I designed a multithreaded UI kit where the entire UI design was asynchronous in nature. It took a number of iterations to test and get right on all the platforms we were targeting, but after that, it was a piece of cake to run an operation in the main thread which was no longer the UI thread.

... and that finally lead to the pull design.

Pull Design

It might seem backwards to go from a push design (often encouraged) to pull (often discouraged). Yet with the UI processing always residing in a separate thread from the logic, the need to push in every single little call to inc was starting to get incredibly awkward/expensive.

So I actually inverted the paradigm in favor of a pull design. The UI thread would actually sort of poll the progress bar for the current state. To avoid burning up CPU cycles needlessly, however, condition variables were used to put the UI thread to sleep when there was nothing to do (woken up, for example, when begin was called on a progress object or any sort of event was pushed to the GUI event queue).

This made it so calls to inc did nothing more than atomic increment a counter and a check to see if it should throw (if the progress had been aborted). It made it ultra cheap (well, atomic increments are a tad expensive, but vastly cheaper than what I was doing before). The UI thread would then pull that state periodically (not all the time) and update the progress bar as needed.

I found this design to be the most attractive so far, even though it's pull-based. It allowed me to call inc in the most granular iterations of work being done, sometimes even millions of times in an operation with very, very smooth progress and aborts that respond immediately to the touch. It also let me do things like animate a spinning gear while the operation was going without the operation having to pump UI events indirectly through calls to inc.

So I really like this design so far, and it is pull-based, but it gave the most silky-smooth progress bars that instantly abort the operation to the touch (with a little animation that begins the moment you touch the abort key or click the button). Calls to inc became so cheap that I could call them it quite very frequently without a care in the world.

Questions

After sharing that little experience, on to the questions:

Obviously, there has to be some call-back somewhere to make this work.

In my latest case with the pull-based design from another thread, actually no. I would actually recommend exploring a pull design if you end up tackling this multithreaded as I eventually did with similar goals for silky smooth progress and ultra-responsiveness to abort. There are techniques like condition variables/monitors to mitigate burning CPU cycles needlessly querying the state of the progress object.

Pass a mutable object to the back-end, and have the back-end make changes to it on progress. The object notifies the front-end when a change occurs.

This was the way I was originally doing it. It worked out reasonably well except for the problems noted where I was having a hard time balancing the throughput of the operation with the latency of the progress bar.

Having a hard time wrapping my head around this approach where you're kind of passing, say, a GUI callback into the operation. This kind of approach would make the notion of who gets notified when progress has been made very flexible, but I can't imagine a scenario where that kind of flexibility is needed. I think easier is to pass along the progress object which already has a list of observers if you explore the push-style design, since I think most scenarios would have you initializing the list of observers infrequently (very possibly, just once when the UI starts). So I'd personally lean, between these two choices, towards the first and have the GUI-independent progress object encapsulate a list of observers which conform to an abstract interface (possibly just a function signature for function pointers, e.g.).

Maybe this kind of design could be helpful for asynchronous cases where you're firing off a bunch of operations asynchronously and want a bunch of progress bars in various places (maybe not even one uniform place). You could also do that by simply constructing this progress object on the fly with a list of the necessary observers though, so probably the choice depends on just how often you might need to do something like this.

Where this might get awkward is that it might want access to the UI functions at the time of launching the operation unless you can kind of generically pass callbacks through the stack in some kind of generalized way. It might be easier to initialize a GUI-independent progress object towards the bottom of the call stack with UI-based observers, and pass that through as a kind of bundle instead. In that sense, the former design offers this kind of flexibility of just passing a general Progress object through the stack without thinking about propagating individual callbacks through the call stack.

Heuristic Algorithms

There is one last case I forgot to cover, and I see it as inevitably awkward and somewhat unsolvable. It's for heuristic algorithms where the number of iterations cannot be foreseen in advance. The algorithm just finishes when it finishes (kind of like some programmer time estimates -- "it's done when it's done").

Most of the time, it's easy to foresee the amount of work in advance. If we're loading a binary file, for example, a simple trick is just consider how many bytes have been read out of the total. That tends to work well enough.

Yet these heuristic algorithms can't always anticipate the amount of work required in advance. In those cases, I've seen people make suggestions like trying to make the program predict the time it would take based on measurements gathered from previous sessions. To me that's straying a little too far from the KISS territory, and predictions made by the software would be very difficult to make accurate based on simple human factors (ex: a prediction that processing the same amount of input data will take the same amount of time can often fail stupendously due to dynamic factors of the memory access patterns, the differences it introduces to the heuristic algorithm, etc).

The simple method I settled on for these cases is to simply wrap an object for these cases, like HeuristicMonitor, where it actually initializes the total number of steps at 1. Incrementing it does nothing at all except check for abort, but a call to end it (automatically called on destruction) increments it and ends the progress. That turns it into a simple binary state: "not done vs. done". It's kind of ugly with just 0% and 100% states there, but the spinning animated gear and the instant ability to abort keeps it from feeling like the software has locked up or anything of that sort.

Anyway, while rare, these kinds of heuristic algorithms are a bit awkward.

Pass a mutable object to the back-end, and have the back-end make changes to it on progress. The object notifies the front-end when a change occurs.

It's difficult to balance efficiency if the backend notifies in this respect. Without care you might find that incrementing your progress ends up doubling or tripling the time it takes to complete the operation if you're aiming for a very smooth progress update.

I don't get the difference here so much.

Are there completely different techniques of reporting progress that I've overlooked?

Poll from the front-end in a separate thread with atomic increments in the backend. Polling makes sense here since it's for an operation that finishes in a finite period and the likelihood of the frontend picking up state changes is high, especially if you're aiming for a silky smooth progress bar. You could consider condition variables if you don't like the idea of polling from the frontend thread, but in that case you might want to avoid notifying on every single granular progress bar increment.

18 Rollback to Revision 16
source | link

Working on deleting my posts with positive answers. Going to try for maximum negative votes!

Are there completely different techniques of reporting progress that I've overlooked?

All my answers tend to be a bit long-winded, but bear with me. I've designed progress bars multiple times over the years for applications (games, audio, VFX -- typically with proprietary GUIs) that do some hefty operations over very large input data. My latest design has made me the happiest, by far. I'll try to cover the main alternative strategy I was exploring before I settled on this design though. Maybe sharing this experience will help in some way.

Pushing

All but my latest incarnation of the progress bar used a push-based design, and all but my latest incarnation had the UI front-end processing (including event processing) and the back-end doing the work in the same thread. They also all had the same needs:

  1. Modality: Operations were synchronous and modal in nature. For example, a progress bar would display to the user when first loading a video game or going to the next stage while the data was being loaded from a floppy disk. More modern examples would be like a progress bar showing up and blocking the user while loading a hefty file after choosing to open a file from a menu. Some tweaks could be made to this design to make it work for asynchronous cases where multiple operations are going on simultaneously (the Progress object would turn into a collection).
  2. Nested Operations: Operations could be nested without explicit knowledge about how much total work was required. An outer operation might know it has 3 iterations of work, for example, but the inner operation it invokes for all 3 iterations might each require 100 iterations of work. The total amount of work is 300 iterations, but the outer operation doesn't know that -- it only knows it has 3 iterations of work.
  3. User Abort: The user can abort at any time (ex: by pressing escape key or clicking a button).
  4. Granular Iterations: Some of the iterations of work could be very, very granular in nature (ex: incrementing progress a million times in a tight loop along side of light iterations of work).

Push Design

The fundamental design for my push-based progress designs haven't changed much even since the days I was writing DOS applications. At the heart of it was a Progress bar object (originally globally-accessible, later passed through the call stack and threads), which was basically a signal with some simple state.

Stack

The state consisted of a simple stack with two integers for each entry (step and num_steps). This allowed for those nested operations described above in #2 so that the total progress could be calculated without the outer operation knowing how many iterations of work would be performed by the inner one, like so:

enter image description here

Beginning a new operation would push to the stack, ending it would pop from it. The UI observer side of the progress bar would not show up if the stack is empty.

Signal

In addition to the stack making up the Progress object's state was also a collection of function pointers that could be called on modifying the progress (effectively a list of observers as people call it nowadays).

The GUI code can hook into that and get notifications of when the progress bar was implemented.

Interface

The interface for the progress object consisted of these functions:

// Returns true when in the middle of an existing operation.
bool active();

// Begins a new/nested operation.
void begin(num_steps);

// Ends the current operation.
void end();

// Increments the current operation by a single step.
// This does nothing if the user aborted already.
void inc();

// Requests to abort the operation.
void abort();

// Returns true if the user requested to abort the operation.
bool aborted();

// Returns the total amount of progress as a percentage in
// the range, [0, 1].
float total();

// Adds an observer that's notified about progress events.
void attach_observer(observer);

// Removes an observer so that it will no longer be notified.
void detach_observer(observer);

... something to this effect. There was some temporal coupling here between begin/inc/end but this was back in C when it wasn't so easy to avoid (no closures, e.g.).

The GUI code would start off adding an observer that would be notified whenever a new operation has begun, when an existing one has ended, and when progress has been made.

Client Code

The client code then looked like this (pseudocode):

void outer_operation(progress):
{
    progress.begin(3);
    for (j=0; j < 3; ++j)
    {
       inner_operation(progress);
       progress.inc();
       if (progress.aborted()) // If user aborted:
       {
          // Roll back any side effects/release resources.
          break;
       }
    }
    progress.end();
}

void inner_operation(progress)
{
    progress.begin(100);
    for (j=0; j < 100; ++j)
    {
       // Do some work.
       progress.inc();
       if (progress.aborted()) // If user aborted:
       {
          // Roll back any side effects/release resources.
          break;
       }
    }
    progress.end();
}

Exception-Handling

One of the pains with this design was just checking to see if the user aborted, as with manual error-handling/propagation in general. Later I got into C++ and that allowed the design to eliminate this aborted query, making it so I could simply throw an exception indicating that the user aborted if inc was called on a progress object which was already in an aborted state. The code then started taking on this shape:

void outer_operation(progress):
{
    Monitor mon(progress, 3);
    try
    {
        for (j=0; j < 3; ++j)
        {
           inner_operation(progress);
           ++mon; // this will throw if user aborted
        }
    }
    catch (exception& ex)
    {
        // Report error if error message is not empty.
    }
}

void inner_operation(progress)
{
    Monitor mon(progress, 100);
    for (j=0; j < 100; ++j)
    {
        // Do some work.
        ++mon; // this will throw if user aborted
    }
}

For user-abort exceptions, I'd just throw an exception with an empty message to avoid showing anything in the UI (since doing so would be kind of redundant when the user explicitly interrupted the operation himself/herself). Might be a questionable practice (and could vary by needs), but I preferred the idea of more catch-all clauses instead of trying to catch each and every different exception type (since I couldn't always anticipate every possible exception that could occur, and most of the time I'd just end up reporting a message).

Smooth, Responsive Progress

The above kind of design worked at a basic level. It was fairly easy to use and the notion of Progress was decoupled from GUI code, making it easy to swap out GUI front-ends in the future without touching the logical aspects of the codebase.

But there existed a latency vs. throughput problem, and it had to do with the interaction of #3 (user abort) and #4 (granular iterations). Since the UI would simply refresh whenever it was notified of a progress change, incrementing the progress bar at a very granular level would yield a very smooth and responsive progress bar, but slow down the whole operation. There was an embarrassing case once where I noticed that I was incrementing the progress bar at such a granular level that a file loading operation took three times longer with the progress updates because I was calling inc so frequently.

To compromise, I captured the system time on the GUI observer side so that it would only refresh the UI every 50 milliseconds or so from the observer, ignoring notifications in between those time intervals (but with some adjustments to always refresh when a progress bar began, e.g.). That made it so these granular calls to inc only increased the time of operations by 35% or so, not more than doubling the time they took. Yet it was still fiddly and kind of ugly that a smooth progress bar would still increase the times by that much.

In some cases I compromised and made it so I don't call inc as often, but that made the progress bar more chunky (not so smooth). For example, I might only increment the progress once per entire scanline of a large image being processed instead of every few pixels. That made it so you'd have to mash the escape key and wait a second or two to abort because inc was being called less frequently. When I started having an abort button inside the GUI itself that users could click on, the responsiveness of clicking the button would drop and feel horrible if inc wasn't called very often to pump UI events.

So there was this ugly juggling act of keeping the progress bar smooth and responsive vs. not slowing down the operation too much as a result of the UI event processing and refreshes.

Thread-Safety

Another problem was that multiprocessor (and later multi-core) hardware was starting to become popular. This design was inherently not thread-safe, as none of the operations involved like incrementing the progress were thread-safe. That was fairly easy to address though by simply implementing a concurrent stack with atomic CAS and making the inc function use atomic increments of the step counter and atomic operations to set the aborted state. The observers would get notified using a deferred mechanism with inc acting as an event pump in the UI thread but as a deferral mechanism in other threads.

Multi-Threaded GUI

Yet it still took a number of years for me to explore a multithreaded GUI application. I often opted in to multithreading with the main thread, by default, processing UI events and also doing some of the heavy-lifting logic. If I needed it, I would simply opt in to distribute work for the operations involved in a separate thread as an optimization detail. The main thread still wanted to, by default, lump processing of UI events together with the UI-independent logic of the operations.

Finally, after some peer pressure, I designed a multithreaded UI kit where the entire UI design was asynchronous in nature. It took a number of iterations to test and get right on all the platforms we were targeting, but after that, it was a piece of cake to run an operation in the main thread which was no longer the UI thread.

... and that finally lead to the pull design.

Pull Design

It might seem backwards to go from a push design (often encouraged) to pull (often discouraged). Yet with the UI processing always residing in a separate thread from the logic, the need to push in every single little call to inc was starting to get incredibly awkward/expensive.

So I actually inverted the paradigm in favor of a pull design. The UI thread would actually sort of poll the progress bar for the current state. To avoid burning up CPU cycles needlessly, however, condition variables were used to put the UI thread to sleep when there was nothing to do (woken up, for example, when begin was called on a progress object or any sort of event was pushed to the GUI event queue).

This made it so calls to inc did nothing more than atomic increment a counter and a check to see if it should throw (if the progress had been aborted). It made it ultra cheap (well, atomic increments are a tad expensive, but vastly cheaper than what I was doing before). The UI thread would then pull that state periodically (not all the time) and update the progress bar as needed.

I found this design to be the most attractive so far, even though it's pull-based. It allowed me to call inc in the most granular iterations of work being done, sometimes even millions of times in an operation with very, very smooth progress and aborts that respond immediately to the touch. It also let me do things like animate a spinning gear while the operation was going without the operation having to pump UI events indirectly through calls to inc.

So I really like this design so far, and it is pull-based, but it gave the most silky-smooth progress bars that instantly abort the operation to the touch (with a little animation that begins the moment you touch the abort key or click the button). Calls to inc became so cheap that I could call them it quite very frequently without a care in the world.

Questions

After sharing that little experience, on to the questions:

Obviously, there has to be some call-back somewhere to make this work.

In my latest case with the pull-based design from another thread, actually no. I would actually recommend exploring a pull design if you end up tackling this multithreaded as I eventually did with similar goals for silky smooth progress and ultra-responsiveness to abort. There are techniques like condition variables/monitors to mitigate burning CPU cycles needlessly querying the state of the progress object.

Pass a mutable object to the back-end, and have the back-end make changes to it on progress. The object notifies the front-end when a change occurs.

This was the way I was originally doing it. It worked out reasonably well except for the problems noted where I was having a hard time balancing the throughput of the operation with the latency of the progress bar.

Pass a call-back function of the form void f(ProgressObject) or ProgressObject -> unit that the back-end invokes. In this case, the back-end constructs the ProgressObject and it's completely passive. It must construct a new object every time it wants to report progress, I assume.

Having a hard time wrapping my head around this approach where you're kind of passing, say, a GUI callback into the operation. This kind of approach would make the notion of who gets notified when progress has been made very flexible, but I can't imagine a scenario where that kind of flexibility is needed. I think easier is to pass along the progress object which already has a list of observers if you explore the push-style design, since I think most scenarios would have you initializing the list of observers infrequently (very possibly, just once when the UI starts). So I'd personally lean, between these two choices, towards the first and have the GUI-independent progress object encapsulate a list of observers which conform to an abstract interface (possibly just a function signature for function pointers, e.g.).

Maybe this kind of design could be helpful for asynchronous cases where you're firing off a bunch of operations asynchronously and want a bunch of progress bars in various places (maybe not even one uniform place). You could also do that by simply constructing this progress object on the fly with a list of the necessary observers though, so probably the choice depends on just how often you might need to do something like this.

Where this might get awkward is that it might want access to the UI functions at the time of launching the operation unless you can kind of generically pass callbacks through the stack in some kind of generalized way. It might be easier to initialize a GUI-independent progress object towards the bottom of the call stack with UI-based observers, and pass that through as a kind of bundle instead. In that sense, the former design offers this kind of flexibility of just passing a general Progress object through the stack without thinking about propagating individual callbacks through the call stack.

Heuristic Algorithms

There is one last case I forgot to cover, and I see it as inevitably awkward and somewhat unsolvable. It's for heuristic algorithms where the number of iterations cannot be foreseen in advance. The algorithm just finishes when it finishes (kind of like some programmer time estimates -- "it's done when it's done").

Most of the time, it's easy to foresee the amount of work in advance. If we're loading a binary file, for example, a simple trick is just consider how many bytes have been read out of the total. That tends to work well enough.

Yet these heuristic algorithms can't always anticipate the amount of work required in advance. In those cases, I've seen people make suggestions like trying to make the program predict the time it would take based on measurements gathered from previous sessions. To me that's straying a little too far from the KISS territory, and predictions made by the software would be very difficult to make accurate based on simple human factors (ex: a prediction that processing the same amount of input data will take the same amount of time can often fail stupendously due to dynamic factors of the memory access patterns, the differences it introduces to the heuristic algorithm, etc).

The simple method I settled on for these cases is to simply wrap an object for these cases, like HeuristicMonitor, where it actually initializes the total number of steps at 1. Incrementing it does nothing at all except check for abort, but a call to end it (automatically called on destruction) increments it and ends the progress. That turns it into a simple binary state: "not done vs. done". It's kind of ugly with just 0% and 100% states there, but the spinning animated gear and the instant ability to abort keeps it from feeling like the software has locked up or anything of that sort.

Anyway, while rare, these kinds of heuristic algorithms are a bit awkward.

Working on deleting my posts with positive answers. Going to try for maximum negative votes!

Are there completely different techniques of reporting progress that I've overlooked?

All my answers tend to be a bit long-winded, but bear with me. I've designed progress bars multiple times over the years for applications (games, audio, VFX -- typically with proprietary GUIs) that do some hefty operations over very large input data. My latest design has made me the happiest, by far. I'll try to cover the main alternative strategy I was exploring before I settled on this design though. Maybe sharing this experience will help in some way.

Pushing

All but my latest incarnation of the progress bar used a push-based design, and all but my latest incarnation had the UI front-end processing (including event processing) and the back-end doing the work in the same thread. They also all had the same needs:

  1. Modality: Operations were synchronous and modal in nature. For example, a progress bar would display to the user when first loading a video game or going to the next stage while the data was being loaded from a floppy disk. More modern examples would be like a progress bar showing up and blocking the user while loading a hefty file after choosing to open a file from a menu. Some tweaks could be made to this design to make it work for asynchronous cases where multiple operations are going on simultaneously (the Progress object would turn into a collection).
  2. Nested Operations: Operations could be nested without explicit knowledge about how much total work was required. An outer operation might know it has 3 iterations of work, for example, but the inner operation it invokes for all 3 iterations might each require 100 iterations of work. The total amount of work is 300 iterations, but the outer operation doesn't know that -- it only knows it has 3 iterations of work.
  3. User Abort: The user can abort at any time (ex: by pressing escape key or clicking a button).
  4. Granular Iterations: Some of the iterations of work could be very, very granular in nature (ex: incrementing progress a million times in a tight loop along side of light iterations of work).

Push Design

The fundamental design for my push-based progress designs haven't changed much even since the days I was writing DOS applications. At the heart of it was a Progress bar object (originally globally-accessible, later passed through the call stack and threads), which was basically a signal with some simple state.

Stack

The state consisted of a simple stack with two integers for each entry (step and num_steps). This allowed for those nested operations described above in #2 so that the total progress could be calculated without the outer operation knowing how many iterations of work would be performed by the inner one, like so:

enter image description here

Beginning a new operation would push to the stack, ending it would pop from it. The UI observer side of the progress bar would not show up if the stack is empty.

Signal

In addition to the stack making up the Progress object's state was also a collection of function pointers that could be called on modifying the progress (effectively a list of observers as people call it nowadays).

The GUI code can hook into that and get notifications of when the progress bar was implemented.

Interface

The interface for the progress object consisted of these functions:

// Returns true when in the middle of an existing operation.
bool active();

// Begins a new/nested operation.
void begin(num_steps);

// Ends the current operation.
void end();

// Increments the current operation by a single step.
// This does nothing if the user aborted already.
void inc();

// Requests to abort the operation.
void abort();

// Returns true if the user requested to abort the operation.
bool aborted();

// Returns the total amount of progress as a percentage in
// the range, [0, 1].
float total();

// Adds an observer that's notified about progress events.
void attach_observer(observer);

// Removes an observer so that it will no longer be notified.
void detach_observer(observer);

... something to this effect. There was some temporal coupling here between begin/inc/end but this was back in C when it wasn't so easy to avoid (no closures, e.g.).

The GUI code would start off adding an observer that would be notified whenever a new operation has begun, when an existing one has ended, and when progress has been made.

Client Code

The client code then looked like this (pseudocode):

void outer_operation(progress):
{
    progress.begin(3);
    for (j=0; j < 3; ++j)
    {
       inner_operation(progress);
       progress.inc();
       if (progress.aborted()) // If user aborted:
       {
          // Roll back any side effects/release resources.
          break;
       }
    }
    progress.end();
}

void inner_operation(progress)
{
    progress.begin(100);
    for (j=0; j < 100; ++j)
    {
       // Do some work.
       progress.inc();
       if (progress.aborted()) // If user aborted:
       {
          // Roll back any side effects/release resources.
          break;
       }
    }
    progress.end();
}

Exception-Handling

One of the pains with this design was just checking to see if the user aborted, as with manual error-handling/propagation in general. Later I got into C++ and that allowed the design to eliminate this aborted query, making it so I could simply throw an exception indicating that the user aborted if inc was called on a progress object which was already in an aborted state. The code then started taking on this shape:

void outer_operation(progress):
{
    Monitor mon(progress, 3);
    try
    {
        for (j=0; j < 3; ++j)
        {
           inner_operation(progress);
           ++mon; // this will throw if user aborted
        }
    }
    catch (exception& ex)
    {
        // Report error if error message is not empty.
    }
}

void inner_operation(progress)
{
    Monitor mon(progress, 100);
    for (j=0; j < 100; ++j)
    {
        // Do some work.
        ++mon; // this will throw if user aborted
    }
}

For user-abort exceptions, I'd just throw an exception with an empty message to avoid showing anything in the UI (since doing so would be kind of redundant when the user explicitly interrupted the operation himself/herself). Might be a questionable practice (and could vary by needs), but I preferred the idea of more catch-all clauses instead of trying to catch each and every different exception type (since I couldn't always anticipate every possible exception that could occur, and most of the time I'd just end up reporting a message).

Smooth, Responsive Progress

The above kind of design worked at a basic level. It was fairly easy to use and the notion of Progress was decoupled from GUI code, making it easy to swap out GUI front-ends in the future without touching the logical aspects of the codebase.

But there existed a latency vs. throughput problem, and it had to do with the interaction of #3 (user abort) and #4 (granular iterations). Since the UI would simply refresh whenever it was notified of a progress change, incrementing the progress bar at a very granular level would yield a very smooth and responsive progress bar, but slow down the whole operation. There was an embarrassing case once where I noticed that I was incrementing the progress bar at such a granular level that a file loading operation took three times longer with the progress updates because I was calling inc so frequently.

To compromise, I captured the system time on the GUI observer side so that it would only refresh the UI every 50 milliseconds or so from the observer, ignoring notifications in between those time intervals (but with some adjustments to always refresh when a progress bar began, e.g.). That made it so these granular calls to inc only increased the time of operations by 35% or so, not more than doubling the time they took. Yet it was still fiddly and kind of ugly that a smooth progress bar would still increase the times by that much.

In some cases I compromised and made it so I don't call inc as often, but that made the progress bar more chunky (not so smooth). For example, I might only increment the progress once per entire scanline of a large image being processed instead of every few pixels. That made it so you'd have to mash the escape key and wait a second or two to abort because inc was being called less frequently. When I started having an abort button inside the GUI itself that users could click on, the responsiveness of clicking the button would drop and feel horrible if inc wasn't called very often to pump UI events.

So there was this ugly juggling act of keeping the progress bar smooth and responsive vs. not slowing down the operation too much as a result of the UI event processing and refreshes.

Thread-Safety

Another problem was that multiprocessor (and later multi-core) hardware was starting to become popular. This design was inherently not thread-safe, as none of the operations involved like incrementing the progress were thread-safe. That was fairly easy to address though by simply implementing a concurrent stack with atomic CAS and making the inc function use atomic increments of the step counter and atomic operations to set the aborted state. The observers would get notified using a deferred mechanism with inc acting as an event pump in the UI thread but as a deferral mechanism in other threads.

Multi-Threaded GUI

Yet it still took a number of years for me to explore a multithreaded GUI application. I often opted in to multithreading with the main thread, by default, processing UI events and also doing some of the heavy-lifting logic. If I needed it, I would simply opt in to distribute work for the operations involved in a separate thread as an optimization detail. The main thread still wanted to, by default, lump processing of UI events together with the UI-independent logic of the operations.

Finally, after some peer pressure, I designed a multithreaded UI kit where the entire UI design was asynchronous in nature. It took a number of iterations to test and get right on all the platforms we were targeting, but after that, it was a piece of cake to run an operation in the main thread which was no longer the UI thread.

... and that finally lead to the pull design.

Pull Design

It might seem backwards to go from a push design (often encouraged) to pull (often discouraged). Yet with the UI processing always residing in a separate thread from the logic, the need to push in every single little call to inc was starting to get incredibly awkward/expensive.

So I actually inverted the paradigm in favor of a pull design. The UI thread would actually sort of poll the progress bar for the current state. To avoid burning up CPU cycles needlessly, however, condition variables were used to put the UI thread to sleep when there was nothing to do (woken up, for example, when begin was called on a progress object or any sort of event was pushed to the GUI event queue).

This made it so calls to inc did nothing more than atomic increment a counter and a check to see if it should throw (if the progress had been aborted). It made it ultra cheap (well, atomic increments are a tad expensive, but vastly cheaper than what I was doing before). The UI thread would then pull that state periodically (not all the time) and update the progress bar as needed.

I found this design to be the most attractive so far, even though it's pull-based. It allowed me to call inc in the most granular iterations of work being done, sometimes even millions of times in an operation with very, very smooth progress and aborts that respond immediately to the touch. It also let me do things like animate a spinning gear while the operation was going without the operation having to pump UI events indirectly through calls to inc.

So I really like this design so far, and it is pull-based, but it gave the most silky-smooth progress bars that instantly abort the operation to the touch (with a little animation that begins the moment you touch the abort key or click the button). Calls to inc became so cheap that I could call them it quite very frequently without a care in the world.

Questions

After sharing that little experience, on to the questions:

Obviously, there has to be some call-back somewhere to make this work.

In my latest case with the pull-based design from another thread, actually no. I would actually recommend exploring a pull design if you end up tackling this multithreaded as I eventually did with similar goals for silky smooth progress and ultra-responsiveness to abort. There are techniques like condition variables/monitors to mitigate burning CPU cycles needlessly querying the state of the progress object.

Pass a mutable object to the back-end, and have the back-end make changes to it on progress. The object notifies the front-end when a change occurs.

This was the way I was originally doing it. It worked out reasonably well except for the problems noted where I was having a hard time balancing the throughput of the operation with the latency of the progress bar.

Pass a call-back function of the form void f(ProgressObject) or ProgressObject -> unit that the back-end invokes. In this case, the back-end constructs the ProgressObject and it's completely passive. It must construct a new object every time it wants to report progress, I assume.

Having a hard time wrapping my head around this approach where you're kind of passing, say, a GUI callback into the operation. This kind of approach would make the notion of who gets notified when progress has been made very flexible, but I can't imagine a scenario where that kind of flexibility is needed. I think easier is to pass along the progress object which already has a list of observers if you explore the push-style design, since I think most scenarios would have you initializing the list of observers infrequently (very possibly, just once when the UI starts). So I'd personally lean, between these two choices, towards the first and have the GUI-independent progress object encapsulate a list of observers which conform to an abstract interface (possibly just a function signature for function pointers, e.g.).

Maybe this kind of design could be helpful for asynchronous cases where you're firing off a bunch of operations asynchronously and want a bunch of progress bars in various places (maybe not even one uniform place). You could also do that by simply constructing this progress object on the fly with a list of the necessary observers though, so probably the choice depends on just how often you might need to do something like this.

Where this might get awkward is that it might want access to the UI functions at the time of launching the operation unless you can kind of generically pass callbacks through the stack in some kind of generalized way. It might be easier to initialize a GUI-independent progress object towards the bottom of the call stack with UI-based observers, and pass that through as a kind of bundle instead. In that sense, the former design offers this kind of flexibility of just passing a general Progress object through the stack without thinking about propagating individual callbacks through the call stack.

Heuristic Algorithms

There is one last case I forgot to cover, and I see it as inevitably awkward and somewhat unsolvable. It's for heuristic algorithms where the number of iterations cannot be foreseen in advance. The algorithm just finishes when it finishes (kind of like some programmer time estimates -- "it's done when it's done").

Most of the time, it's easy to foresee the amount of work in advance. If we're loading a binary file, for example, a simple trick is just consider how many bytes have been read out of the total. That tends to work well enough.

Yet these heuristic algorithms can't always anticipate the amount of work required in advance. In those cases, I've seen people make suggestions like trying to make the program predict the time it would take based on measurements gathered from previous sessions. To me that's straying a little too far from the KISS territory, and predictions made by the software would be very difficult to make accurate based on simple human factors (ex: a prediction that processing the same amount of input data will take the same amount of time can often fail stupendously due to dynamic factors of the memory access patterns, the differences it introduces to the heuristic algorithm, etc).

The simple method I settled on for these cases is to simply wrap an object for these cases, like HeuristicMonitor, where it actually initializes the total number of steps at 1. Incrementing it does nothing at all except check for abort, but a call to end it (automatically called on destruction) increments it and ends the progress. That turns it into a simple binary state: "not done vs. done". It's kind of ugly with just 0% and 100% states there, but the spinning animated gear and the instant ability to abort keeps it from feeling like the software has locked up or anything of that sort.

Anyway, while rare, these kinds of heuristic algorithms are a bit awkward.

17 deleted 17948 characters in body
source | link

Are there completely different techniques of reporting progress that I've overlooked?

All my answers tend to be a bit long-winded, but bear with me. I've designed progress bars multiple times over the years for applications (games, audio, VFX -- typically with proprietary GUIs) that do some hefty operations over very large input data. My latest design has made me the happiest, by far. I'll try to cover the main alternative strategy I was exploring before I settled on this design though. Maybe sharing this experience will help in some way.

Pushing

All but my latest incarnation of the progress bar used a push-based design, and all but my latest incarnation had the UI front-end processing (including event processing) and the back-end doing the work in the same thread. They also all had the same needs:

  1. Modality: Operations were synchronous and modal in nature. For example, a progress bar would display to the user when first loading a video game or going to the next stage while the data was being loaded from a floppy disk. More modern examples would be like a progress bar showing up and blocking the user while loading a hefty file after choosing to open a file from a menu. Some tweaks could be made to this design to make it work for asynchronous cases where multiple operations are going on simultaneously (the Progress object would turn into a collection).
  2. Nested Operations: Operations could be nested without explicit knowledge about how much total work was required. An outer operation might know it has 3 iterations of work, for example, but the inner operation it invokes for all 3 iterations might each require 100 iterations of work. The total amount of work is 300 iterations, but the outer operation doesn't know that -- it only knows it has 3 iterations of work.
  3. User Abort: The user can abort at any time (ex: by pressing escape key or clicking a button).
  4. Granular Iterations: Some of the iterations of work could be very, very granular in nature (ex: incrementing progress a million times in a tight loop along side of light iterations of work).

Push Design

The fundamental design for my push-based progress designs haven't changed much even since the days I was writing DOS applications. At the heart of it was a Progress bar object (originally globally-accessible, later passed through the call stack and threads), which was basically a signal with some simple state.

Stack

The state consisted of a simple stack with two integers for each entry (step and num_steps). This allowed for those nested operations described above in #2 so that the total progress could be calculated without the outer operation knowing how many iterations of work would be performed by the inner one, like so:

enter image description here

Beginning a new operation would push to the stack, ending it would pop from it. The UI observer side of the progress bar would not show up if the stack is empty.

Signal

In addition to the stack making up the Progress object's state was also a collection of function pointers that could be called on modifying the progress (effectively a list of observers as people call it nowadays).

The GUI code can hook into that and get notifications of when the progress bar was implemented.

Interface

The interface for the progress object consisted of these functions:

// Returns true when in the middle of an existing operation.
bool active();

// Begins a new/nested operation.
void begin(num_steps);

// Ends the current operation.
void end();

// Increments the current operation by a single step.
// This does nothing if the user aborted already.
void inc();

// Requests to abort the operation.
void abort();

// Returns true if the user requested to abort the operation.
bool aborted();

// Returns the total amount of progress as a percentage in
// the range, [0, 1].
float total();

// Adds an observer that's notified about progress events.
void attach_observer(observer);

// Removes an observer so that it will no longer be notified.
void detach_observer(observer);

... something to this effect. There was some temporal coupling here between begin/inc/end but this was back in C when it wasn't so easy to avoid (no closures, e.g.).

The GUI code would start off adding an observer that would be notified whenever a new operation has begun, when an existing one has ended, and when progress has been made.

Client Code

The client code then looked like this (pseudocode):

void outer_operation(progress):
{
    progress.begin(3);
    for (j=0; j < 3; ++j)
    {
       inner_operation(progress);
       progress.inc();
       if (progress.aborted()) // If user aborted:
       {
          // Roll back any side effects/release resources.
          break;
       }
    }
    progress.end();
}

void inner_operation(progress)
{
    progress.begin(100);
    for (j=0; j < 100; ++j)
    {
       // Do some work.
       progress.inc();
       if (progress.aborted()) // If user aborted:
       {
          // Roll back any side effects/release resources.
          break;
       }
    }
    progress.end();
}

Exception-Handling

One of the pains with this design was just checking to see if the user aborted, as with manual error-handling/propagation in general. Later I got into C++ and that allowed the design to eliminate this aborted query, making it so I could simply throw an exception indicating that the user aborted if inc was called on a progress object which was already in an aborted state. The code then started taking on this shape:

void outer_operation(progress):
{
    Monitor mon(progress, 3);
    try
    {
        for (j=0; j < 3; ++j)
        {
           inner_operation(progress);
           ++mon; // this will throw if user aborted
        }
    }
    catch (exception& ex)
    {
        // Report error if error message is not empty.
    }
}

void inner_operation(progress)
{
    Monitor mon(progress, 100);
    for (j=0; j < 100; ++j)
    {
        // Do some work.
        ++mon; // this will throw if user aborted
    }
}

For user-abort exceptions, I'd just throw an exception with an empty message to avoid showing anything in the UI (since doing so would be kind of redundant when the user explicitly interrupted the operation himself/herself). Might be a questionable practice (and could vary by needs), but I preferred the idea of more catch-all clauses instead of trying to catch each and every different exception type (since I couldn't always anticipate every possible exception that could occur, and most of the time I'd just end up reporting a message).

Smooth, Responsive Progress

The above kind of design worked at a basic level. It was fairly easy to use and the notion of Progress was decoupled from GUI code, making it easy to swap out GUI front-ends in the future without touching the logical aspects of the codebase.

But there existed a latency vs. throughput problem, and it had to do with the interaction of #3 (user abort) and #4 (granular iterations). Since the UI would simply refresh whenever it was notified of a progress change, incrementing the progress bar at a very granular level would yield a very smooth and responsive progress bar, but slow down the whole operation. There was an embarrassing case once where I noticed that I was incrementing the progress bar at such a granular level that a file loading operation took three times longer with the progress updates because I was calling inc so frequently.

To compromise, I captured the system time on the GUI observer side so that it would only refresh the UI every 50 milliseconds or so from the observer, ignoring notifications in between those time intervals (but with some adjustments to always refresh when a progress bar began, e.g.). That made it so these granular calls to inc only increased the time of operations by 35% or so, not more than doubling the time they took. Yet it was still fiddly and kind of ugly that a smooth progress bar would still increase the times by that much.

In some cases I compromised and made it so I don't call inc as often, but that made the progress bar more chunky (not so smooth). For example, I might only increment the progress once per entire scanline of a large image being processed instead of every few pixels. That made it so you'd have to mash the escape key and wait a second or two to abort because inc was being called less frequently. When I started having an abort button inside the GUI itself that users could click on, the responsiveness of clicking the button would drop and feel horrible if inc wasn't called very often to pump UI events.

So there was this ugly juggling act of keeping the progress bar smooth and responsive vs. not slowing down the operation too much as a result of the UI event processing and refreshes.

Thread-Safety

Another problem was that multiprocessor (and later multi-core) hardware was starting to become popular. This design was inherently not thread-safe, as none of the operations involved like incrementing the progress were thread-safe. That was fairly easy to address though by simply implementing a concurrent stack with atomic CAS and making the inc function use atomic increments of the step counter and atomic operations to set the aborted state. The observers would get notified using a deferred mechanism with inc acting as an event pump in the UI thread but as a deferral mechanism in other threads.

Multi-Threaded GUI

Yet it still took a number of years for me to explore a multithreaded GUI application. I often opted in to multithreading with the main thread, by default, processing UI events and also doing some of the heavy-lifting logic. If I needed it, I would simply opt in to distribute work for the operations involved in a separate thread as an optimization detail. The main thread still wanted to, by default, lump processing of UI events together with the UI-independent logic of the operations.

Finally, after some peer pressure, I designed a multithreaded UI kit where the entire UI design was asynchronous in nature. It took a number of iterations to test and get right on all the platforms we were targeting, but after that, it was a piece of cake to run an operation in the main thread which was no longer the UI thread.

... and that finally lead to the pull design.

Pull Design

It might seem backwards to go from a push design (often encouraged) to pull (often discouraged). Yet with the UI processing always residing in a separate thread from the logic, the need to push in every single little call to inc was starting to get incredibly awkward/expensive.

So I actually inverted the paradigm in favor of a pull design. The UI thread would actually sort of poll the progress bar for the current state. To avoid burning up CPU cycles needlessly, however, condition variables were used to put the UI thread to sleep when there was nothing to do (woken up, for example, when begin was called on a progress object or any sort of event was pushed to the GUI event queue).

This made it so calls to inc did nothing more than atomic increment a counter and a check to see if it should throw (if the progress had been aborted). It made it ultra cheap (well, atomic increments are a tad expensive, but vastly cheaper than what I was doing before). The UI thread would then pull that state periodically (not all the time) and update the progress bar as needed.

I found this design to be the most attractive so far, even though it's pull-based. It allowed me to call inc in the most granular iterations of work being done, sometimes even millions of times in an operation with very, very smooth progress and aborts that respond immediately to the touch. It also let me do things like animate a spinning gear while the operation was going without the operation having to pump UI events indirectly through calls to inc.

So I really like this design so far, and it is pull-based, but it gave the most silky-smooth progress bars that instantly abort the operation to the touch (with a little animation that begins the moment you touch the abort key or click the button). Calls to inc became so cheap that I could call them it quite very frequently without a care in the world.

Questions

After sharing that little experience, on to the questions:

Obviously, there has to be some call-back somewhere to make this work.

In my latest case with the pull-based design from another thread, actually no. I would actually recommend exploring a pull design if you end up tackling this multithreaded as I eventually did with similar goals for silky smooth progress and ultra-responsiveness to abort. There are techniques like condition variables/monitors to mitigate burning CPU cycles needlessly querying the state of the progress object.

Pass a mutable object to the back-end, and have the back-end make changes to it on progress. The object notifies the front-end when a change occurs.

This was the way I was originally doing it. It worked out reasonably well except for the problems noted where I was having a hard time balancing the throughput of the operation with the latency of the progress bar.

Pass a call-back function of the form void f(ProgressObject) or ProgressObject -> unit that the back-end invokes. In this case, the back-end constructs the ProgressObject and it's completely passive. It must construct a new object every time it wants to report progress, I assume.

Having a hard time wrapping my head around this approach where you're kind of passing, say, a GUI callback into the operation. This kind of approach would make the notion of who gets notified when progress has been made very flexible, but I can't imagine a scenario where that kind of flexibility is needed. I think easier is to pass along the progress object which already has a list of observers if you explore the push-style design, since I think most scenarios would have you initializing the list of observers infrequently (very possibly, just once when the UI starts). So I'd personally lean, between these two choices, towards the first and have the GUI-independent progress object encapsulate a list of observers which conform to an abstract interface (possibly just a function signature for function pointers, e.g.).

Maybe this kind of design could be helpful for asynchronous cases where you're firing off a bunch of operations asynchronously and want a bunch of progress bars in various places (maybe not even one uniform place). You could also do that by simply constructing this progress object on the fly with a list of the necessary observers though, so probably the choice depends on just how often you might need to do something like this.

Where this might get awkward is that it might want access to the UI functions at the time of launching the operation unless you can kind of generically pass callbacks through the stack in some kind of generalized way. It might be easier to initialize a GUI-independent progress object towards the bottom of the call stack with UI-based observers, and pass that through as a kind of bundle instead. In that sense, the former design offers this kind of flexibility of just passing a general Progress object through the stack without thinking about propagating individual callbacks through the call stack.

Heuristic Algorithms

There is one last case I forgot to cover, and I see it as inevitably awkward and somewhat unsolvable. It's for heuristic algorithms where the number of iterations cannot be foreseen in advance. The algorithm just finishes when it finishes (kind of like some programmer time estimates -- "it's done when it's done").

Most of the time, it's easy to foresee the amount of work in advance. If we're loading a binary file, for example, a simple trick is just consider how many bytes have been read out of the total. That tends to work well enough.

Yet these heuristic algorithms can't always anticipate the amount of work required in advance. In those cases, I've seen people make suggestions like trying to make the program predict the time it would take based on measurements gathered from previous sessions. To me that's straying a little too far from the KISS territory, and predictions made by the software would be very difficult to make accurate based on simple human factors (ex: a prediction that processing the same amount of input data will take the same amount of time can often fail stupendously due to dynamic factors of the memory access patterns, the differences it introduces to the heuristic algorithm, etc).

The simple method I settled on for these cases is to simply wrap an object for these cases, like HeuristicMonitor, where it actually initializes the total number of steps at 1. Incrementing it does nothing at all except check for abort, but a call to end it (automatically called on destruction) increments it and ends the progress. That turns it into a simple binary state: "not done vs. done". It's kind of ugly with just 0% and 100% states there, but the spinning animated gear and the instant ability to abort keeps it from feeling like the software has locked up or anything of that sort.

Anyway, while rare, these kinds of heuristic algorithms are a bit awkward.

Working on deleting my posts with positive answers. Going to try for maximum negative votes!

Are there completely different techniques of reporting progress that I've overlooked?

All my answers tend to be a bit long-winded, but bear with me. I've designed progress bars multiple times over the years for applications (games, audio, VFX -- typically with proprietary GUIs) that do some hefty operations over very large input data. My latest design has made me the happiest, by far. I'll try to cover the main alternative strategy I was exploring before I settled on this design though. Maybe sharing this experience will help in some way.

Pushing

All but my latest incarnation of the progress bar used a push-based design, and all but my latest incarnation had the UI front-end processing (including event processing) and the back-end doing the work in the same thread. They also all had the same needs:

  1. Modality: Operations were synchronous and modal in nature. For example, a progress bar would display to the user when first loading a video game or going to the next stage while the data was being loaded from a floppy disk. More modern examples would be like a progress bar showing up and blocking the user while loading a hefty file after choosing to open a file from a menu. Some tweaks could be made to this design to make it work for asynchronous cases where multiple operations are going on simultaneously (the Progress object would turn into a collection).
  2. Nested Operations: Operations could be nested without explicit knowledge about how much total work was required. An outer operation might know it has 3 iterations of work, for example, but the inner operation it invokes for all 3 iterations might each require 100 iterations of work. The total amount of work is 300 iterations, but the outer operation doesn't know that -- it only knows it has 3 iterations of work.
  3. User Abort: The user can abort at any time (ex: by pressing escape key or clicking a button).
  4. Granular Iterations: Some of the iterations of work could be very, very granular in nature (ex: incrementing progress a million times in a tight loop along side of light iterations of work).

Push Design

The fundamental design for my push-based progress designs haven't changed much even since the days I was writing DOS applications. At the heart of it was a Progress bar object (originally globally-accessible, later passed through the call stack and threads), which was basically a signal with some simple state.

Stack

The state consisted of a simple stack with two integers for each entry (step and num_steps). This allowed for those nested operations described above in #2 so that the total progress could be calculated without the outer operation knowing how many iterations of work would be performed by the inner one, like so:

enter image description here

Beginning a new operation would push to the stack, ending it would pop from it. The UI observer side of the progress bar would not show up if the stack is empty.

Signal

In addition to the stack making up the Progress object's state was also a collection of function pointers that could be called on modifying the progress (effectively a list of observers as people call it nowadays).

The GUI code can hook into that and get notifications of when the progress bar was implemented.

Interface

The interface for the progress object consisted of these functions:

// Returns true when in the middle of an existing operation.
bool active();

// Begins a new/nested operation.
void begin(num_steps);

// Ends the current operation.
void end();

// Increments the current operation by a single step.
// This does nothing if the user aborted already.
void inc();

// Requests to abort the operation.
void abort();

// Returns true if the user requested to abort the operation.
bool aborted();

// Returns the total amount of progress as a percentage in
// the range, [0, 1].
float total();

// Adds an observer that's notified about progress events.
void attach_observer(observer);

// Removes an observer so that it will no longer be notified.
void detach_observer(observer);

... something to this effect. There was some temporal coupling here between begin/inc/end but this was back in C when it wasn't so easy to avoid (no closures, e.g.).

The GUI code would start off adding an observer that would be notified whenever a new operation has begun, when an existing one has ended, and when progress has been made.

Client Code

The client code then looked like this (pseudocode):

void outer_operation(progress):
{
    progress.begin(3);
    for (j=0; j < 3; ++j)
    {
       inner_operation(progress);
       progress.inc();
       if (progress.aborted()) // If user aborted:
       {
          // Roll back any side effects/release resources.
          break;
       }
    }
    progress.end();
}

void inner_operation(progress)
{
    progress.begin(100);
    for (j=0; j < 100; ++j)
    {
       // Do some work.
       progress.inc();
       if (progress.aborted()) // If user aborted:
       {
          // Roll back any side effects/release resources.
          break;
       }
    }
    progress.end();
}

Exception-Handling

One of the pains with this design was just checking to see if the user aborted, as with manual error-handling/propagation in general. Later I got into C++ and that allowed the design to eliminate this aborted query, making it so I could simply throw an exception indicating that the user aborted if inc was called on a progress object which was already in an aborted state. The code then started taking on this shape:

void outer_operation(progress):
{
    Monitor mon(progress, 3);
    try
    {
        for (j=0; j < 3; ++j)
        {
           inner_operation(progress);
           ++mon; // this will throw if user aborted
        }
    }
    catch (exception& ex)
    {
        // Report error if error message is not empty.
    }
}

void inner_operation(progress)
{
    Monitor mon(progress, 100);
    for (j=0; j < 100; ++j)
    {
        // Do some work.
        ++mon; // this will throw if user aborted
    }
}

For user-abort exceptions, I'd just throw an exception with an empty message to avoid showing anything in the UI (since doing so would be kind of redundant when the user explicitly interrupted the operation himself/herself). Might be a questionable practice (and could vary by needs), but I preferred the idea of more catch-all clauses instead of trying to catch each and every different exception type (since I couldn't always anticipate every possible exception that could occur, and most of the time I'd just end up reporting a message).

Smooth, Responsive Progress

The above kind of design worked at a basic level. It was fairly easy to use and the notion of Progress was decoupled from GUI code, making it easy to swap out GUI front-ends in the future without touching the logical aspects of the codebase.

But there existed a latency vs. throughput problem, and it had to do with the interaction of #3 (user abort) and #4 (granular iterations). Since the UI would simply refresh whenever it was notified of a progress change, incrementing the progress bar at a very granular level would yield a very smooth and responsive progress bar, but slow down the whole operation. There was an embarrassing case once where I noticed that I was incrementing the progress bar at such a granular level that a file loading operation took three times longer with the progress updates because I was calling inc so frequently.

To compromise, I captured the system time on the GUI observer side so that it would only refresh the UI every 50 milliseconds or so from the observer, ignoring notifications in between those time intervals (but with some adjustments to always refresh when a progress bar began, e.g.). That made it so these granular calls to inc only increased the time of operations by 35% or so, not more than doubling the time they took. Yet it was still fiddly and kind of ugly that a smooth progress bar would still increase the times by that much.

In some cases I compromised and made it so I don't call inc as often, but that made the progress bar more chunky (not so smooth). For example, I might only increment the progress once per entire scanline of a large image being processed instead of every few pixels. That made it so you'd have to mash the escape key and wait a second or two to abort because inc was being called less frequently. When I started having an abort button inside the GUI itself that users could click on, the responsiveness of clicking the button would drop and feel horrible if inc wasn't called very often to pump UI events.

So there was this ugly juggling act of keeping the progress bar smooth and responsive vs. not slowing down the operation too much as a result of the UI event processing and refreshes.

Thread-Safety

Another problem was that multiprocessor (and later multi-core) hardware was starting to become popular. This design was inherently not thread-safe, as none of the operations involved like incrementing the progress were thread-safe. That was fairly easy to address though by simply implementing a concurrent stack with atomic CAS and making the inc function use atomic increments of the step counter and atomic operations to set the aborted state. The observers would get notified using a deferred mechanism with inc acting as an event pump in the UI thread but as a deferral mechanism in other threads.

Multi-Threaded GUI

Yet it still took a number of years for me to explore a multithreaded GUI application. I often opted in to multithreading with the main thread, by default, processing UI events and also doing some of the heavy-lifting logic. If I needed it, I would simply opt in to distribute work for the operations involved in a separate thread as an optimization detail. The main thread still wanted to, by default, lump processing of UI events together with the UI-independent logic of the operations.

Finally, after some peer pressure, I designed a multithreaded UI kit where the entire UI design was asynchronous in nature. It took a number of iterations to test and get right on all the platforms we were targeting, but after that, it was a piece of cake to run an operation in the main thread which was no longer the UI thread.

... and that finally lead to the pull design.

Pull Design

It might seem backwards to go from a push design (often encouraged) to pull (often discouraged). Yet with the UI processing always residing in a separate thread from the logic, the need to push in every single little call to inc was starting to get incredibly awkward/expensive.

So I actually inverted the paradigm in favor of a pull design. The UI thread would actually sort of poll the progress bar for the current state. To avoid burning up CPU cycles needlessly, however, condition variables were used to put the UI thread to sleep when there was nothing to do (woken up, for example, when begin was called on a progress object or any sort of event was pushed to the GUI event queue).

This made it so calls to inc did nothing more than atomic increment a counter and a check to see if it should throw (if the progress had been aborted). It made it ultra cheap (well, atomic increments are a tad expensive, but vastly cheaper than what I was doing before). The UI thread would then pull that state periodically (not all the time) and update the progress bar as needed.

I found this design to be the most attractive so far, even though it's pull-based. It allowed me to call inc in the most granular iterations of work being done, sometimes even millions of times in an operation with very, very smooth progress and aborts that respond immediately to the touch. It also let me do things like animate a spinning gear while the operation was going without the operation having to pump UI events indirectly through calls to inc.

So I really like this design so far, and it is pull-based, but it gave the most silky-smooth progress bars that instantly abort the operation to the touch (with a little animation that begins the moment you touch the abort key or click the button). Calls to inc became so cheap that I could call them it quite very frequently without a care in the world.

Questions

After sharing that little experience, on to the questions:

Obviously, there has to be some call-back somewhere to make this work.

In my latest case with the pull-based design from another thread, actually no. I would actually recommend exploring a pull design if you end up tackling this multithreaded as I eventually did with similar goals for silky smooth progress and ultra-responsiveness to abort. There are techniques like condition variables/monitors to mitigate burning CPU cycles needlessly querying the state of the progress object.

Pass a mutable object to the back-end, and have the back-end make changes to it on progress. The object notifies the front-end when a change occurs.

This was the way I was originally doing it. It worked out reasonably well except for the problems noted where I was having a hard time balancing the throughput of the operation with the latency of the progress bar.

Pass a call-back function of the form void f(ProgressObject) or ProgressObject -> unit that the back-end invokes. In this case, the back-end constructs the ProgressObject and it's completely passive. It must construct a new object every time it wants to report progress, I assume.

Having a hard time wrapping my head around this approach where you're kind of passing, say, a GUI callback into the operation. This kind of approach would make the notion of who gets notified when progress has been made very flexible, but I can't imagine a scenario where that kind of flexibility is needed. I think easier is to pass along the progress object which already has a list of observers if you explore the push-style design, since I think most scenarios would have you initializing the list of observers infrequently (very possibly, just once when the UI starts). So I'd personally lean, between these two choices, towards the first and have the GUI-independent progress object encapsulate a list of observers which conform to an abstract interface (possibly just a function signature for function pointers, e.g.).

Maybe this kind of design could be helpful for asynchronous cases where you're firing off a bunch of operations asynchronously and want a bunch of progress bars in various places (maybe not even one uniform place). You could also do that by simply constructing this progress object on the fly with a list of the necessary observers though, so probably the choice depends on just how often you might need to do something like this.

Where this might get awkward is that it might want access to the UI functions at the time of launching the operation unless you can kind of generically pass callbacks through the stack in some kind of generalized way. It might be easier to initialize a GUI-independent progress object towards the bottom of the call stack with UI-based observers, and pass that through as a kind of bundle instead. In that sense, the former design offers this kind of flexibility of just passing a general Progress object through the stack without thinking about propagating individual callbacks through the call stack.

Heuristic Algorithms

There is one last case I forgot to cover, and I see it as inevitably awkward and somewhat unsolvable. It's for heuristic algorithms where the number of iterations cannot be foreseen in advance. The algorithm just finishes when it finishes (kind of like some programmer time estimates -- "it's done when it's done").

Most of the time, it's easy to foresee the amount of work in advance. If we're loading a binary file, for example, a simple trick is just consider how many bytes have been read out of the total. That tends to work well enough.

Yet these heuristic algorithms can't always anticipate the amount of work required in advance. In those cases, I've seen people make suggestions like trying to make the program predict the time it would take based on measurements gathered from previous sessions. To me that's straying a little too far from the KISS territory, and predictions made by the software would be very difficult to make accurate based on simple human factors (ex: a prediction that processing the same amount of input data will take the same amount of time can often fail stupendously due to dynamic factors of the memory access patterns, the differences it introduces to the heuristic algorithm, etc).

The simple method I settled on for these cases is to simply wrap an object for these cases, like HeuristicMonitor, where it actually initializes the total number of steps at 1. Incrementing it does nothing at all except check for abort, but a call to end it (automatically called on destruction) increments it and ends the progress. That turns it into a simple binary state: "not done vs. done". It's kind of ugly with just 0% and 100% states there, but the spinning animated gear and the instant ability to abort keeps it from feeling like the software has locked up or anything of that sort.

Anyway, while rare, these kinds of heuristic algorithms are a bit awkward.

Working on deleting my posts with positive answers. Going to try for maximum negative votes!

16 Fixed some goofs.
source | link
15 added 23 characters in body
source | link
14 added 1 character in body
source | link
13 added 1925 characters in body
source | link
12 added 50 characters in body
source | link
11 added 438 characters in body
source | link
10 added 438 characters in body
source | link
9 added 1 character in body
source | link
8 Forgot an important detail using a guard resource for progress and also operator++ in C++.
source | link
7 syntax highlighting
source | link
6 Missed a function in the progress bar design for the observer side.
source | link
5 added 161 characters in body
source | link
4 added 55 characters in body
source | link
3 added 79 characters in body
source | link
2 added 79 characters in body
source | link
1
source | link