Predict C++ program running time

Question

How to predict C++ program running time, if program executes different functions (working with database, reading files, parsing xml and others)? How installers do it?

Answer 1

They do not predict the time. They calculate the number of operations to be done on a total of operations.

Answer 2

You can't predict it entirely.

What you can do is wait until a fraction of the work is done, say 1%, and estimate the remaining time by that - just time how long it takes for 1% and multiply by 100, for example. That is easily done if you can enumerate all that you have to do in advance, or have some kind of a loop going on..

Answer 3

There really is no way to do this in any sort of reliable way, since it depends on thousands of factors.

Progress bars typically measure this in one of two ways:

• Overall progress - I have n number of bytes/files/whatever to transfer, and so far I have done m.
• Overall work divided by current speed - I have n bytes to transfer, and so far I have done m and it took t seconds, so if things continue at this rate it will take u seconds to complete.

Answer 4

You should make estimation of time needed for different phases of the program. For example: reading files - 50, working with database - 30, working with network - 20. In ideal it would be good if you make some progress callback during all of those phases, but it requires coding the progress calculation into the iterations of algorithm.

Answer 5

As others have said, you can't predict the time. Approaches suggested by Partial and rmn are valid solutions.

What you can do more is assign weights to certain operations (for instance, if you know a db call takes roughly twice as long as some processing step, you can adjust accordingly).

Answer 6

You can predict the time by using measurement and estimation. Of course the quality of the predictions will differ. And BTW: The word "predict" is correct.

You split the workload into small tasks, and create an estimation rule for each task, e.g.: if copying files one to ten took 10s, then the remaining 90 files may take another 90s. Measure the time that these tasks take at runtime, and update your estimations.

Each new measurement will make the prediction a bit more precise.

Answer 7

In general it is impossible to predict the running time of a program. It is even impossible to predict whether a program will even halt at all. This is undecidable.

http://en.wikipedia.org/wiki/Halting%5Fproblem

Answer 8

Short answer:

No you can't. For progress bars and such, most applications simply increase the bar length with a percentage based on the overall tasks done. Some psuedo-code:

for(int i=0; i<num_files_to_load; ++i){
    files.push_back(File(filepath[i]));
    SetProgressBarLength((float)i/((float)num_files_to_load) - 1.0f);
}

This is a very simplified example. Making a for-loop like this would surely block the window system's event/message queue. You would probably add a timed event or something similar instead.

Longer answer:

Given N known parameters, the problem finding whether a program completes at all is undecidable. This is called the Halting problem. You can however, find the time it takes to execute a single instruction. Some very old games actually depended on exact cycle timings, and failed to execute correctly on newer computers due to race conditions that occur because of subtle differences in runtime. Also, on architectures with data and instruction caches, the cycles the instructions consume is not constant anymore. So cache makes cycle-counting unpredictable.

Answer 9

As I mentioned in a previous answer, it is impossible in general to predict the running time.

However, empirically it may be possible to predict with good accuracy.

Typically all of these programs are approximatelyh linear in some input.

But if you wanted a more sophisticated approach, you could define a large number of features (database size, file size, OS, etc. etc.) and input those feature values + running time into a neural network. If you had millions of examples (obviously you would have an automated method for gathering data, e.g. some discovery programs) you might come up with a very flexible and intelligent prediction algorithm.

Of course this would only be worth doing for fun, as I'm sure the value to your company over some crude guessing algorithm will probably be nil :)

Answer 10

Raymond Chen discussed this issue in his blog.

Why does the copy dialog give such horrible estimates?

Because the copy dialog is just guessing. It can't predict the future, but it is forced to try. And at the very beginning of the copy, when there is very little history to go by, the prediction can be really bad.

Answer 11

A cool installer compiler would execute a faux install, time each op, then save this to disk for the future.

I used such a technique for a 3D application once, which had a pretty dead-on progress bar for loading and mashing data, after you've run it a few times. It wasn't that hard, and it made development much nicer. (Since we had to see that bar 10-15 times/day, startup was 10-20 secs)