27

If I have a time_point for an arbitrary clock (say high_resolution_clock::time_point), is there a way to convert it to a time_point for another arbitrary clock (say system_clock::time_point)?

I know there would have to be limits, if this ability existed, because not all clocks are steady, but is there any functionality to help such conversions in the specification at all?

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Cort Ammon
  • 10,221
  • 31
  • 45
  • 4
    Tagging [chrono] to attract Howard Hinnant, but the only (approximate) way I can think of is to take `now()` of one clock, subtract it from the time point and then add the resulting `duration` to the `now()` of the other clock. Obviously this won't be exact (since the two `now()`s are unlikely to represent the exact same time point), but might be close enough. – T.C. Feb 09 '16 at 01:24
  • 2
    I'm soooooo predictable... ;-) – Howard Hinnant Feb 09 '16 at 01:59
  • This question deserves an accepted answer and my vote is for 5gon12eder's. This is an answer that is worthy of study, and which provides so much information and possibilities. His answer is built on mine, so I don't want to delete mine (so readers get the background). – Howard Hinnant Feb 10 '16 at 03:17
  • 2
    @HowardHinnant I'll definitely be accepting an answer. You guys made it hard to decide which one to go with, so I've been giving SE some time to vote =) – Cort Ammon Feb 10 '16 at 05:15
  • Howard's answer is exactly what gcc's condition_variable::wait_until() does now, and it's fine most of the time. However, time_point ranges are limited by the representation data type, so this conversion only works for the range where time_points on both clocks overlap. You have to be very careful when using very distant time_points, especially time_point::max(). See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=58931 – Aaron Graham Jan 29 '18 at 21:52

3 Answers3

33

I was wondering whether the accuracy of the conversion proposed by T.C. and Howard Hinnant could be improved. For reference, here is the base version that I tested.

template
<
  typename DstTimePointT,
  typename SrcTimePointT,
  typename DstClockT = typename DstTimePointT::clock,
  typename SrcClockT = typename SrcTimePointT::clock
>
DstTimePointT
clock_cast_0th(const SrcTimePointT tp)
{
  const auto src_now = SrcClockT::now();
  const auto dst_now = DstClockT::now();
  return dst_now + (tp - src_now);
}

Using the test

int
main()
{
    using namespace std::chrono;
    const auto now = system_clock::now();
    const auto steady_now = CLOCK_CAST<steady_clock::time_point>(now);
    const auto system_now = CLOCK_CAST<system_clock::time_point>(steady_now);
    const auto diff = system_now - now;
    std::cout << duration_cast<nanoseconds>(diff).count() << '\n';
}

where CLOCK_CAST would be #defined to, for now, clock_cast_0th, I collected a histogram for an idle system and one under high load. Note that this is a cold-start test. I first tried calling the function in a loop where it gives much better results. However, I think that this would give a false impression because most real-world programs probably convert a time point every now and then and will hit the cold case.

The load was generated by running the following tasks parallel to the test program. (My computer has four CPUs.)

  • A matrix multiplication benchmark (single-threaded).
  • find /usr/include -execdir grep "$(pwgen 10 1)" '{}' \; -print
  • hexdump /dev/urandom | gzip | hexdump | gzip | hexdump | gzip | hexdump | gzip | hexdump | gzip | hexdump | gzip | hexdump | gzip | hexdump | gzip | hexdump | gzip | hexdump | gzip| gunzip > /dev/null
  • dd if=/dev/urandom of=/tmp/spam bs=10 count=1000

Those commands that would terminate in finite time were run in an infinite loop.

The following histogram – as well as those that will follow – shows the errors of 50 000 runs with the worst 1 ‰ removed.

Histogram of round-trip errors for the zeroth approach on an idle system

Histogram of round-trip errors for the zeroth approach on a highly contended system

Note that the ordinate has a logarithmic scale.

The errors roughly fall into the range between 0.5 µs and 1.0 µs in the idle case and 0.5 µs and 1.5 µs in the contended case.

The most striking observation is that the error distribution is far from symmetric (there are no negative errors at all) indicating a large systematic component in the error. This makes sense because if we get interrupted between the two calls to now, the error is always in the same direction and we cannot be interrupted for a “negative amount of time”.

The histogram for the contended case almost looks like a perfect exponential distribution (mind the log-scale!) with a rather sharp cut-off which seems plausible; the chance that you are interrupted for time t is roughly proportional to et.

I then tried using the following trick

template
<
  typename DstTimePointT,
  typename SrcTimePointT,
  typename DstClockT = typename DstTimePointT::clock,
  typename SrcClockT = typename SrcTimePointT::clock
>
DstTimePointT
clock_cast_1st(const SrcTimePointT tp)
{
  const auto src_before = SrcClockT::now();
  const auto dst_now = DstClockT::now();
  const auto src_after = SrcClockT::now();
  const auto src_diff = src_after - src_before;
  const auto src_now = src_before + src_diff / 2;
  return dst_now + (tp - src_now);
}

hoping that interpolating scr_now would partially cancel the error introduced by inevitably calling the clocks in sequential order.

In the first version of this answer, I claimed that this didn't help anything. As it turns out, this wasn't true. After Howard Hinnant pointed out that he did observe improvements, I improved my tests and now there is some observable improvement.

Histogram of round-trip errors for the first approach on an idle system

Histogram of round-trip errors for the first approach on a highly contended system

It wasn't so much an improvement in terms of the error span, however, the errors are now roughly centered around zero which means that we now have errors in the range from −0.5&#1202f;µs to 0.5&#1202f;µs. The more symmetric distribution indicates that the statistic component of the error became more dominant.

Next, I tried calling the above code in a loop that would pick the best value for src_diff.

template
<
  typename DstTimePointT,
  typename SrcTimePointT,
  typename DstDurationT = typename DstTimePointT::duration,
  typename SrcDurationT = typename SrcTimePointT::duration,
  typename DstClockT = typename DstTimePointT::clock,
  typename SrcClockT = typename SrcTimePointT::clock
>
DstTimePointT
clock_cast_2nd(const SrcTimePointT tp,
               const SrcDurationT tolerance = std::chrono::nanoseconds {100},
               const int limit = 10)
{
  assert(limit > 0);
  auto itercnt = 0;
  auto src_now = SrcTimePointT {};
  auto dst_now = DstTimePointT {};
  auto epsilon = detail::max_duration<SrcDurationT>();
  do
    {
      const auto src_before = SrcClockT::now();
      const auto dst_between = DstClockT::now();
      const auto src_after = SrcClockT::now();
      const auto src_diff = src_after - src_before;
      const auto delta = detail::abs_duration(src_diff);
      if (delta < epsilon)
        {
          src_now = src_before + src_diff / 2;
          dst_now = dst_between;
          epsilon = delta;
        }
      if (++itercnt >= limit)
        break;
    }
  while (epsilon > tolerance);
#ifdef GLOBAL_ITERATION_COUNTER
  GLOBAL_ITERATION_COUNTER = itercnt;
#endif
  return dst_now + (tp - src_now);
}

The function takes two additional optional parameters to specify the desired accuracy and maximum number of iterations and returns the current-best value when either condition becomes true.

I'm using the following two straight-forward helper functions in the above code.

namespace detail
{

  template <typename DurationT, typename ReprT = typename DurationT::rep>
  constexpr DurationT
  max_duration() noexcept
  {
    return DurationT {std::numeric_limits<ReprT>::max()};
  }

  template <typename DurationT>
  constexpr DurationT
  abs_duration(const DurationT d) noexcept
  {
    return DurationT {(d.count() < 0) ? -d.count() : d.count()};
  }

}

Histogram of round-trip errors for the second approach on an idle system

Histogram of round-trip errors for the second approach on a highly contended system

The error distribution is now very symmetric around zero and the magnitude of the error dropped down by as much as a factor of almost 100.

I was curious how often the iteration would run on average so I added the #ifdef to the code and #defined it to the name of a global static variable that the main function would print out. (Note that we collect two iteration counts per experiment so this histogram has a sample size of 100 000.)

The histogram for the contended case, on the other hand, seems more uniform. I have no explanation for this and would have expected the opposite.

Histogram of iteration counts in the second approach on an idle system

Histogram of iteration counts in the second approach on a highly contended system

As it seems, we almost always hit the iteration count limit (but that's okay) and sometimes we do return early. The shape of this histogram can of course be influenced by altering the values of tolerance and limit passed to the function.

Finally, I thought I could be clever and instead of looking at src_diff use the round-trip error directly as a quality criterion.

template
<
  typename DstTimePointT,
  typename SrcTimePointT,
  typename DstDurationT = typename DstTimePointT::duration,
  typename SrcDurationT = typename SrcTimePointT::duration,
  typename DstClockT = typename DstTimePointT::clock,
  typename SrcClockT = typename SrcTimePointT::clock
>
DstTimePointT
clock_cast_3rd(const SrcTimePointT tp,
               const SrcDurationT tolerance = std::chrono::nanoseconds {100},
               const int limit = 10)
{
  assert(limit > 0);
  auto itercnt = 0;
  auto current = DstTimePointT {};
  auto epsilon = detail::max_duration<SrcDurationT>();
  do
    {
      const auto dst = clock_cast_0th<DstTimePointT>(tp);
      const auto src = clock_cast_0th<SrcTimePointT>(dst);
      const auto delta = detail::abs_duration(src - tp);
      if (delta < epsilon)
        {
          current = dst;
          epsilon = delta;
        }
      if (++itercnt >= limit)
        break;
    }
  while (epsilon > tolerance);
#ifdef GLOBAL_ITERATION_COUNTER
  GLOBAL_ITERATION_COUNTER = itercnt;
#endif
  return current;
}

It turns out that this was not such a good idea.

Histogram of round-trip errors for the third approach on an idle system

Histogram of round-trip errors for the first approach on a highly contended system

We have moved back to a non-symmetric error distribution again and the magnitude of the error has also increased. (While the function also became more expensive!) Actually, the histogram for the idle case just looks weird. Could it be that the spikes correspond to how often we are interrupted? This doesn't actually make sense.

The iteration frequency shows the same trend as before.

Histogram of iteration counts in the third approach on an idle system

Histogram of iteration counts in the third approach on an idle system

In conclusion, I would recommend to use the 2nd approach and I think that the default values for the optional parameters are reasonable but of course, this is something that may vary from machine to machine. Howard Hinnant has commented that a limit of only four iterations worked well for him.

If you implement this for real, you wouldn't like to miss the optimization opportunity to check whether std::is_same<SrcClockT, DstClockT>::value and in this case, simply apply std::chrono::time_point_cast without ever calling any now function (and thus not introducing error).

In case you want to repeat my experiments, I'm providing the full code here. The clock_castXYZ code is already complete. (Just concatenate all examples together into one file, #include the obvious headers and save as clock_cast.hxx.)

Here is the actual main.cxx that I used.

#include <iomanip>
#include <iostream>

#ifdef GLOBAL_ITERATION_COUNTER
static int GLOBAL_ITERATION_COUNTER;
#endif

#include "clock_cast.hxx"

int
main()
{
    using namespace std::chrono;
    const auto now = system_clock::now();
    const auto steady_now = CLOCK_CAST<steady_clock::time_point>(now);
#ifdef GLOBAL_ITERATION_COUNTER
    std::cerr << std::setw(8) << GLOBAL_ITERATION_COUNTER << '\n';
#endif
    const auto system_now = CLOCK_CAST<system_clock::time_point>(steady_now);
#ifdef GLOBAL_ITERATION_COUNTER
    std::cerr << std::setw(8) << GLOBAL_ITERATION_COUNTER << '\n';
#endif
    const auto diff = system_now - now;
    std::cout << std::setw(8) << duration_cast<nanoseconds>(diff).count() << '\n';
}

The following GNUmakefile builds and runs everything.

CXX = g++ -std=c++14
CPPFLAGS = -DGLOBAL_ITERATION_COUNTER=global_counter
CXXFLAGS = -Wall -Wextra -Werror -pedantic -O2 -g

runs = 50000
cutoff = 0.999

execfiles = zeroth.exe first.exe second.exe third.exe

datafiles =                            \
  zeroth.dat                           \
  first.dat                            \
  second.dat second_iterations.dat     \
  third.dat third_iterations.dat

picturefiles = ${datafiles:.dat=.png}

all: ${picturefiles}

zeroth.png: errors.gp zeroth.freq
    TAG='zeroth' TITLE="0th Approach ${SUBTITLE}" MICROS=0 gnuplot $<

first.png: errors.gp first.freq
    TAG='first' TITLE="1st Approach ${SUBTITLE}" MICROS=0 gnuplot $<

second.png: errors.gp second.freq
    TAG='second' TITLE="2nd Approach ${SUBTITLE}" gnuplot $<

second_iterations.png: iterations.gp second_iterations.freq
    TAG='second' TITLE="2nd Approach ${SUBTITLE}" gnuplot $<

third.png: errors.gp third.freq
    TAG='third' TITLE="3rd Approach ${SUBTITLE}" gnuplot $<

third_iterations.png: iterations.gp third_iterations.freq
    TAG='third' TITLE="3rd Approach ${SUBTITLE}" gnuplot $<

zeroth.exe: main.cxx clock_cast.hxx
    ${CXX} -o $@ ${CPPFLAGS} -DCLOCK_CAST='clock_cast_0th' ${CXXFLAGS} $<

first.exe: main.cxx clock_cast.hxx
    ${CXX} -o $@ ${CPPFLAGS} -DCLOCK_CAST='clock_cast_1st' ${CXXFLAGS} $<

second.exe: main.cxx clock_cast.hxx
    ${CXX} -o $@ ${CPPFLAGS} -DCLOCK_CAST='clock_cast_2nd' ${CXXFLAGS} $<

third.exe: main.cxx clock_cast.hxx
    ${CXX} -o $@ ${CPPFLAGS} -DCLOCK_CAST='clock_cast_3rd' ${CXXFLAGS} $<

%.freq: binput.py %.dat
    python $^ ${cutoff} > $@

${datafiles}: ${execfiles}
    ${SHELL} -eu run.sh ${runs} $^

clean:
    rm -f *.exe *.dat *.freq *.png

.PHONY: all clean

The auxiliary run.sh script is rather simple. As an improvement to an earlier version of this answer, I am now executing the different programs in the inner loop so as to be more fair and maybe also better get rid of caching effects.

#! /bin/bash -eu

n="$1"
shift

for exe in "$@"
do
    name="${exe%.exe}"
    rm -f "${name}.dat" "${name}_iterations.dat"
done

i=0
while [ $i -lt $n ]
do
    for exe in "$@"
    do
        name="${exe%.exe}"
        "./${exe}" 1>>"${name}.dat" 2>>"${name}_iterations.dat"
    done
    i=$(($i + 1))
done

And I also wrote the binput.py script because I couldn't figure out how to do the histograms in Gnuplot alone.

#! /usr/bin/python3

import sys
import math

def main():
    cutoff = float(sys.argv[2]) if len(sys.argv) >= 3 else 1.0
    with open(sys.argv[1], 'r') as istr:
        values = sorted(list(map(float, istr)), key=abs)
    if cutoff < 1.0:
        values = values[:int((cutoff - 1.0) * len(values))]
    min_val = min(values)
    max_val = max(values)
    binsize = 1.0
    if max_val - min_val > 50:
        binsize = (max_val - min_val) / 50
    bins = int(1 + math.ceil((max_val - min_val) / binsize))
    histo = [0 for i in range(bins)]
    print("minimum: {:16.6f}".format(min_val), file=sys.stderr)
    print("maximum: {:16.6f}".format(max_val), file=sys.stderr)
    print("binsize: {:16.6f}".format(binsize), file=sys.stderr)
    for x in values:
        idx = int((x - min_val) / binsize)
        histo[idx] += 1
    for (i, n) in enumerate(histo):
        value = min_val + i * binsize
        frequency = n / len(values)
        print('{:16.6e} {:16.6e}'.format(value, frequency))

if __name__ == '__main__':
    main()

Finally, here are the errors.gp

tag = system('echo ${TAG-hist}')
file_hist = sprintf('%s.freq', tag)
file_plot = sprintf('%s.png', tag)
micros_eh = 0 + system('echo ${MICROS-0}')

set terminal png size 600,450
set output file_plot

set title system('echo ${TITLE-Errors}')

if (micros_eh) { set xlabel "error / µs" } else { set xlabel "error / ns" }
set ylabel "relative frequency"

set xrange [* : *]
set yrange [1.0e-5 : 1]

set log y
set format y '10^{%T}'
set format x '%g'

set style fill solid 0.6

factor = micros_eh ? 1.0e-3 : 1.0
plot file_hist using (factor * $1):2 with boxes notitle lc '#cc0000'

… and iterations.gp scripts.

tag = system('echo ${TAG-hist}')
file_hist = sprintf('%s_iterations.freq', tag)
file_plot = sprintf('%s_iterations.png', tag)

set terminal png size 600,450
set output file_plot

set title system('echo ${TITLE-Iterations}')
set xlabel "iterations"
set ylabel "frequency"

set xrange [0 : *]
set yrange [1.0e-5 : 1]

set xtics 1
set xtics add ('' 0)

set log y
set format y '10^{%T}'
set format x '%g'

set boxwidth 1.0
set style fill solid 0.6

plot file_hist using 1:2 with boxes notitle lc '#3465a4'
Catskul
  • 17,916
  • 15
  • 84
  • 113
5gon12eder
  • 24,280
  • 5
  • 45
  • 92
  • 1
    Nice analysis! I'm surprised your first technique didn't show any improvement. – Howard Hinnant Feb 09 '16 at 15:55
  • 2
    Fwiw, I implemented and measured your first technique (with the 3 calls to `now()`) and on my system, and it did cut round-trip error by a factor of two on my system. Your second technique on my system cut the error by another factor of 10. I found `limit = 4` and `tolerance = 100ns` to be good. – Howard Hinnant Feb 11 '16 at 23:26
  • @HowardHinnant You are right, thank you. I didn't measure this properly at first. I have improved my tests now and updated my answer accordingly. I cannot reproduce your numbers exactly but I can confirm the overall trend. – 5gon12eder Feb 14 '16 at 03:09
  • Amazing answer. Any reason you created a `max_duration` function instead of using `SrcDurationT::max()` ? – Siler Sep 27 '18 at 17:03
  • 2
    seriously? no one considered inter-clock convertability in the standard? they really expect us to do the above for checking the last write time ot a file against, say, the wall clock? yikes... – maddanio Apr 20 '21 at 05:17
  • 1
    Yes, it was considered. C++20 introduces `std::chrono::clock_cast` which converts among `system_clock`, `utc_clock`, `gps_clock`, `tai_clock`, `file_clock`, and any user-defined clock which opts-in to the `clock_cast` infrastructure. `steady_clock` does not participate in this system because there is no one correct tradeoff between accuracy and performance in doing this conversion. – Howard Hinnant Jun 01 '22 at 00:59
  • And the conversion itself is not consistent between runs. E.g. you can use this technique to convert a `system_clock::time_point` to a `steady_clock::time_point` and stream it out. And when you stream it in during another run and do the reverse conversion from `steady_clock::time_point` to `system_clock::time_point`, it is quite likely to be a different `system_clock::time_point` than the original. This is not a tool for the casual user. – Howard Hinnant Jun 01 '22 at 00:59
  • "`Ҳf;`" doesn't render, and "`Ҳ`" (without "`f`") is "`Ҳ`" (which doesn't seem to be right). What is the intent? [Non-breaking space](https://en.wikipedia.org/wiki/Non-breaking_space)? Something else? – Peter Mortensen May 12 '23 at 12:13
  • OK, the OP has left the building: *"Last seen more than 4 years ago"* – Peter Mortensen May 12 '23 at 12:18
22

There's no way to do this precisely unless you know the precise duration difference between the two clock's epochs. And you don't know this for high_resolution_clock and system_clock unless is_same<high_resolution_clock, system_clock>{} is true.

That being said, you can program up an approximately correct translation and it goes much like T.C. says in his comment. Indeed, libc++ plays this trick in its implementation of condition_variable::wait_for:

https://github.com/llvm-mirror/libcxx/blob/78d6a7767ed57b50122a161b91f59f19c9bd0d19/include/__mutex_base#L455

The calls to now of the different clocks are made as close together as possible, and one hopes that the thread isn't pre-empted between these two calls for too long. It's the best I know how to do, and the spec has wiggle room in it to allow for these types of shenanigans. E.g. something is allowed to wake up a little late, but not a little early.

In the case of libc++, the underlying OS only knows how to wait on system_clock::time_point, but the spec says you must wait on steady_clock (for good reasons). So you do what you can.

Here is a HelloWorld sketch of the idea:

#include <chrono>
#include <iostream>

std::chrono::system_clock::time_point
to_system(std::chrono::steady_clock::time_point tp)
{
    using namespace std::chrono;
    auto sys_now = system_clock::now();
    auto sdy_now = steady_clock::now();
    return time_point_cast<system_clock::duration>(tp - sdy_now + sys_now);
}

std::chrono::steady_clock::time_point
to_steady(std::chrono::system_clock::time_point tp)
{
    using namespace std::chrono;
    auto sdy_now = steady_clock::now();
    auto sys_now = system_clock::now();
    return tp - sys_now + sdy_now;
}

int
main()
{
    using namespace std::chrono;
    auto now = system_clock::now();
    std::cout << now.time_since_epoch().count() << '\n';
    auto converted_now = to_system(to_steady(now));
    std::cout << converted_now.time_since_epoch().count() << '\n';
}

For me, using Apple clang/libc++ at -O3 this output:

1454985476610067
1454985476610073

indicating the combined conversion had an error of 6 microseconds.

Update

I have arbitrarily reversed the order of the calls to now() in one of the conversions above such that one conversion calls them in one order, and the other calls them in the reverse order. This should have no impact on the accuracy of any one conversion. However when converting both ways as I do in this HelloWorld, there should be a statistical cancellation which helps to reduce the round-trip conversion error.

Gill Bates
  • 14,330
  • 23
  • 70
  • 138
Howard Hinnant
  • 206,506
  • 52
  • 449
  • 577
  • I wrote a test for your suggested conversion to investigate the accuracy of the approach and derived a more accurate version at the expense of additional clock calls. Hope you find this interesting. – 5gon12eder Feb 09 '16 at 13:28
  • Why not just have an Epoch concept in the standard library? time_point should not need to know about any clock, it shouldn't need to be aware of how more time_point's can be created. time_point should only know Epoch, every clock should produce time_points with a certain epoch. Two clocks with the same Epochs could then compare their measurements directly, which they should be able to do (of course, this could have surprising results depending on clock errors, but that is also the case with comparing a clocks measurements to itself, e.g. unstable clocks). – Nir Friedman Apr 20 '18 at 16:01
  • One would have to define epochs in terms of some time standard such as UTC. For something like `steady_clock` this can get impractical on some platforms. `steady_clock` is often just a count of cpu cycles since boot. It doesn't have to be related at all to UTC. So the best one can do is ask each clock how far back in time is its epoch, subtract those two results to get a time duration which is the difference in epochs, and use that diff to convert. – Howard Hinnant Apr 20 '18 at 21:16
  • First, thanks for that answer @HowardHinnant. I used it to convert `file_clock` (from [last_write_time](https://en.cppreference.com/w/cpp/filesystem/last_write_time)) to `system_clock` in C++17. Second, I ran into issues during testing that the same unmodified file can yield slightly different system_clock timestamps, forcing me to change my unit-test to have a fudge factor. – ddevienne Jan 11 '21 at 13:03
  • 1
    For `file_clock` each platform should have a deterministic epoch. I believe for Apple and Linux OS's that epoch will be the same as `system_clock`: 1970-01-01 00:00:00 UTC (excluding leap seconds). For Windows: 1601-01-01 00:00:00 UTC excluding leap seconds. With such known epochs, you can just add/subtract the difference of the epochs to convert between these two clocks. E.g. the Windows offset would be 11644473600s. – Howard Hinnant Jan 11 '21 at 14:11
  • I believe that reversing the order of the calls made the roundtrip error *worse*. Now you always sample the return clock before the input clock, so both functions will tend to return a value that's slightly earlier than the input, and composing them will compound this effect. – Ben Voigt Jun 29 '23 at 16:23
0

Until you have C++20 you can use this in C++17:

std::chrono::system_clock::time_point a = std::filesystem::file_time_type::clock::to_sys(std::filesystem::file_time_type)

The returned clock from file_time_type will be platform specific but it's better to go that way rather than use "now()" on both clocks to convert the timestamp. Because there is a timing sensitive factor which is undesirable in unit tests, a context switch between getting both "now" timestamps could cause a test to fail.