Thursday, September 26, 2013

Measuring Execution Time Accurately and Setting Deadlines

If you do benchmarking, a common task is to measure the execution time of a particular block of code.

The canonical and portable way to do this in C++ is as follows:

#include <chrono>
// Starting timepoint
const auto start_time = std::chrono::steady_clock::now();
// ... Code here ...
double time_in_seconds = std::chrono::duration_cast<std::chrono::milliseconds>
  (std::chrono::steady_clock::now() - start_time).count() / 1000.0;

This will measure execution time in seconds, with millisecond precision. If you want better precision, you can of course go for say microsecond resolution:

// Starting timepoint
const auto start_time = std::chrono::steady_clock::now();
// ... Code here ...
double time_in_seconds = std::chrono::duration_cast<std::chrono::microseconds>
  (std::chrono::steady_clock::now() - start_time).count() / 1000000.0;

If your code block may throw exceptions, and the execution time is actually updated to some variable that is outside of this scope, you may want to catch the exception:

// time_in_seconds reference to variable declared outside this scope
// Starting timepoint
const auto start_time = std::chrono::steady_clock::now();
try {
  // ... Code here ...
} catch (...) {
  // Update execution time and rethrow
  time_in_seconds = std::chrono::duration_cast<std::chrono::milliseconds>
    (std::chrono::steady_clock::now() - start_time).count() / 1000.0;
  throw;
}
// Normal execution ended, update time
time_in_seconds = std::chrono::duration_cast<std::chrono::milliseconds>
  (std::chrono::steady_clock::now() - start_time).count() / 1000.0;

steady_clock is a monotonic clock: its value never decreases. This can be compared to std::chrono::system_clock, which can in fact decrease if the user changes the value. There's also std::chrono::high_resolution_clock which may or may not be monotonic (as the name suggests, it is intended to primarily be used as a high resolution clock, i.e. ideally with nanosecond precision).

The start_time is a timepoint, and taking the difference of two timepoints (the two now()s) yields a duration. We then convert the duration into millisecond "ticks", which are obtained using count(). Alternatively, we can convert the duration into microsecond "ticks" (as shown above), or even nanosecond ticks. Finally, we refactor the numerical value from milliseconds to seconds (this step is obviously not needed, but is used because it is many times easier to use SI units).

Deadlines can be created in a similar way:

// Define type used for deadline
typedef std::chrono::steady_clock::time_point deadline_t;

deadline_t soon = std::chrono::steady_clock::now() + std::chrono::minutes(2);
// or, equivalently: now() + std::chrono::seconds(2*60);

for (const auto& e : vec) {
  if (std::chrono::steady_clock::now() > soon) throw out_of_time();
  // ... process vector elements ...
}


3 comments:

  1. / 1000.0;

    With chrono you usually should avoid conversion constants, and instead just use durations with the appropriate period. Also avoid count() until you want to print the value or you need to interoperate with an API that can't use chrono::duration types.

    auto const end_time = std::chrono::steady_clock::now();
    auto rounded = std::chrono::duration(
    std::chrono::duration_cast(end_time -
    start_time));

    std::cout << rounded.count() << '\n';

    This way you keep the type safety offered by chrono and if you want a different precision you just change 'milliseconds' to something else; no need to duplicate that info in some hard coded constant.

    For making the timing work for code with exceptions you should use RAII instead of explicit exception handling. One way is Boost's scope exit:

    auto const start_time = std::chrono::steady_clock::now();
    {
    BOOST_SCOPE_EXIT((&time_in_seconds)(start_time)) {
    auto const end_time = std::chrono::steady_clock::now();
    time_in_seconds = std::chrono::duration(
    std::chrono::duration_cast(end_time -
    start_time));
    }
    BOOST_SCOPE_EXIT_END

    // ... Code here ...
    }

    ReplyDelete
  2. The biggest problem with benchmarking is actually in the "code here" part. You also need to run multiple tests and select the average or mean time (depending on what you care about). The simple method only works for large benchmarks, which do not need high-precision timers anyway.

    ReplyDelete
  3. An eternal question of timing - http://www.viva64.com/en/b/0097/

    ReplyDelete