Automated notifications in C++ loops

6 Comments
Posted February 26th, 2009 in Software. Tags: , .

As a computational physicist, I’m often running programs that consist of many nested for-loops. At the moment, my outermost loop cycles through millions of data points and various inner loops explore tens of thousands of parameters. I’m always fiddling with the settings on the inner loops in ways that cause the run time to vary between 10 seconds and 10 weeks.

Annoyingly, it’s not always easy to predict how long the program will run after each set of modifications. Also, my code occasionally has bugs which make it hang indefinitely. When a program’s expected run time is measured in weeks, it’s reassuring to see regular progress reports. Otherwise I worry that the program has silently crashed.

At first I just slapped a print statement into the outermost for-loop, encased in an if-then statement which only activated once every 1000 loops. The print statement used the time elapsed since the start of the loop and the progress made to estimate the time remaining. It looked a little like this (plus some type casting):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
start_time=time(NULL);//Grab starting time.
for(i=0;i<i_end;i++){
  if((i+1) % 1000==0){//Only print every 1000 loops.
    current_time=time(NULL);//Grab current time.
    timespan=current_time-start_time;
    //The TOTAL time to completion can be obtained by
    //dividing timespan by the fraction already done.
    //After subtracting timespan, the time remaining
    //is left (in seconds, which is often confusing).
    time_remaining=timespan/(i+1)/(i_end+1) - timespan;
    cout<<(i+1)/i_end*100<<"% finished, "
        <<time_remaining<<"seconds remaining."<<endl;
  }

  for(j=0;j<j_end;j++){
    //Do lots of stuff here.
  }
}

This sufficed until I altered the settings of the inner loops in a way that increased the run time dramatically. The first notification took hours to appear, which I consider unacceptably slow. Then I tried making the print statement activate every 10 loops to speed up notifications when the run time is very long, but that filled the log file with megabytes of print statements and slowed down the program. It became clear that quick hacks were going to require a lot of ongoing maintenance. I needed a notification system that could automatically adapt to short and long run times.

I call my solution “Automated Notifications”. The latest version is v1.2, which can be downloaded here.

Features:

  • The time until the first notification appears can be controlled separately from the other notifications, and it defaults to 10 seconds.
  • The amount of time between all subsequent notifications are controlled by a variable which specifies a target interval between notifications. The actual intervals will be within 30% of this target (5 minute default).
  • A minimum number (default is 4) of notifications will be printed by notify(). This only activates if the projected run time is less than the chosen interval between notifications.
  • The time remaining is printed in a human-readable format using the seconds_to_string() function. Time is reported in years, weeks, days, hours, minutes, seconds. No more than 2 units will be printed in each statement to reduce clutter (though this value is customizable).
  • A print statement reports the time elapsed at the end of the loop, so the estimated time remaining can be judged against how long the loop actually took.
  • The outer loop can start at any (positive! — need to fix this!) index, not just 0 as in the example above.
  • Most notification options are set above each loop, so multiple loops can be configured differently (see custom_example.cpp).
  • It’s probably a good idea to put code into the notification function that saves your data to disk so that if the computer crashes or the power goes out, the application can be restarted from the last notification point. The variable notification.partial_saves_enabled is meant to turn on this unwritten code, but you’ll also need to pass a new argument to the notify() function containing the data you want written to disk.

Requirements:

  • Intended for use in C++ programs, tested using the g++ compiler that comes with Ubuntu 8.10 64-bit.
  • Your outermost loop must cycle over many indices (dozens or more). The loop can start at any index you want, but it needs to increase by 1 in each loop.
  • Requires the iostream, iomanip and vector libraries (available in Ubuntu by default).

The program is split up into 3 files: common_declarations.hpp contains datatype definitions and function declarations, common_functions.cpp has function definitions for notify() and sec2human() while example.cpp is just an example loop which uses Automated Notifications.

This division isn’t necessary, but I’ve found it’s a good way to organize larger software projects. This way, widely used functions that are rarely changed can be declared and defined in the common files and compiled separately from the programs which merely use those functions.

The Makefile included with Automated Notifications compiles in two steps to illustrate this technique. After adding many functions to my version of the common files, the first compilation step takes almost a minute on my computer. This step only occurs when the common files are edited, however, which means it’s rarely needed. The second compilation step, on the other hand, is more frequent and much faster.

By the way, common_declarations.hpp contains the line “using namespace std”. I’ve read that this is bad programming practice, but I haven’t run into any serious consequences yet, and it’s convenient not to have to type “std::” every time I want to use “cout”.

Here’s what example.cpp looks like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/********************************************************
Purpose:
          This program runs a set of nested loops that
          perform useless calculations for several
          minutes (exact time depends on the speed of
          your computer and the limits of the nested
          loops). It's meant to demonstrate the
          notify() function.
*********************************************************
Written by Dumb Scientist
First written:  2009-02-26
Last modified:  2009-03-08
********************************************************/


//Header file "common_declarations.hpp" declares many
//functions, constants and datatypes. In order to use the
//functions declared in it, you must link this program
//with object code made using common_functions.cpp.
#include "common_declarations.hpp"

int main(){

  //Declare counters and limits for the loops.
  long temp=0,i,j,i_start=30,i_end=200000,j_end=200000;
 
  //Initialize variables for notify().
  notification_struct notification;
  //Change this string to anything you want.
  notification.prefix = "Example loop";
  //Your starting index will probably be different.
  notification.starting_index = i_start;
  //Your ending index will also likely be different.
  notification.num_loops = i_end-notification.starting_index;

  for(i=notification.starting_index;i<i_end;i++){
    //Periodically print time remaining.
    notify(notification,i);
 
    for(j=0;j<j_end;j++){
      //Utterly useless calculation.
      temp+=(i*j*j*j-2*i+3*j);
    }//End of inner loop.
  }//End of outer loop.

  //Record time at end of program.
  notification.end_time = time(NULL);
  notification.time_total=notification.end_time-notification.start_time;
  cout<<notification.prefix<<" took "
    <<seconds_to_string(notification.time_total)<<endl;
   
  //If temp isn't used somewhere, this program takes
  //0 seconds. I think that's the result of the -O2
  //flag noticing that the above loops aren't needed.
  return temp;
}

When run, it produces output that looks like this (note that the first line appears within seconds, and the subsequent notifications are 25% apart because the estimated run time of this program is less than the default interval):

1
2
3
4
5
6
Example loop is at  8.20%. Time left: 1 minute, 52 seconds
Example loop is at 33.20%. Time left: 1 minute, 20 seconds
Example loop is at 58.19%. Time left: 51 seconds
Example loop is at 83.19%. Time left: 20 seconds
Example loop took   2 minutes,  1 second
`

I changed the limits of the loops by adding 4 zeros each to i_end and j_end, but the first line still appeared within seconds:

1
2
Example loop is at  0.00%. Time left: 285 years, 10 weeks
`

Obviously, I didn’t wait for that one to finish. But the point is that I quickly knew I’d die of old age centuries before it did. Incidentally, I tried adding a few more zeros to j_end and it caused the first notification to take an irritatingly long time to appear. This happens because the outer loop takes a long time to increment just once. I’m not yet sure how I want to address this problem.

Automated Notifications is free software, licensed under the GPLv3 rather than the CC license that the rest of the site uses. If anyone notices any bugs or has any suggestions for how to improve Automated Notifications, please let me know in the comments below. I’m also curious to see how others have solved this problem, regardless of the language it’s written in.

Version History

v1.2 – 2009-03-08 – Simplified default settings to shorten example.cpp, added custom_example.cpp.

v1.1 – 2009-02-27 – Replaced max and min intervals with target_interval.

v1.0 – 2009-02-26 – Original release.

Last modified February 6th, 2012
.
    
.

6 Responses to “Automated notifications in C++ loops”

  1. Anonymous posted on 2009-09-20 at 03:16

    I’m surprised you didn’t use a timer interrupt. No overhead while the loop is running and precise control of sample interval. Just need some way to get the loop variables into the interrupt handler and the results out.

    • Didn’t use that because I’d never heard of it before. Thanks, I’ll look into it.

    • The “production” version of this function accepts a structure with several GB of data and autosaves it to disk. I’m wondering if a timer interrupt could be sent that much data in a transparent fashion? I.e. the entire structure needs to be sent via reference as a single argument without making a local copy of the data (it barely fits into memory already.)

      Also, the function needs to be called at that exact spot in the code, not inside the inner loop, otherwise the autosave function won’t work correctly. If all this is possible with a timer interrupt, someone please point me to some example code.

  2. (Ed. note: this comment was originally posted here.)

    Keeping stuff in separate files and including them is a good organization technique…

    Why? That just means I have to open more files when I want to perform extensive maintenance on the program.

    Compiling is definitely faster if you only change 1 out of 100 similarly sized files, but I’ve chosen to create two main source files: the first is infrequently edited and large (30k lines), while the second is edited dozens of times a day and only has 1k lines. The Makefile compiles the large file into object code which is then linked to the object code from the small file. The large file is thereafter only compiled if the revision date of the large source file is newer than the large object file. Even the compile times for the large file are just ~10 seconds on a netbook if optimization is disabled, and it’s not clear that my compile times will grow faster than CPU speeds will. (Especially if parallel g++ ever gets decent.)

    I suppose one could say that code segmentation helps to enforce the “few interconnections between functions” principle. (Or whatever it’s formally called- the notion that functions should interact in only a few well-defined ways.) This ideal is theoretically attractive, but seems annoying to implement without allowing for occasional exceptions. I don’t want to change a useful guideline into a rigid law that will probably just slow me down.

    I also write code by myself, so reasons involving programming teams aren’t really relevant. A good version control system like Mercurial should minimize these issues anyway.

    Are there any real (i.e. productivity, scalability) reasons to abandon this approach and start putting new functions in separate files? I’m not a professional programmer, so I may have missed something that a computer science PhD would consider obvious and compelling…

    • Anonymous posted on 2010-04-04 at 09:32

      I also write code by myself, so reasons involving programming teams aren’t really relevant

      Since you license your code under GPL (so basically you welcome or at least don’t mind others to study and share your code) then code manageability is nice to have which can be achieved by modularity.

      The most important thing to remember is to split your code according to what it does (logical separation). To be honest I haven’t looked at your code so perhaps it does not apply in this case (maybe one really big file is justified).

      Having said that, at the end of the day there are no rigid laws, just guidelines created from experience and a lot of mistakes :)

.