CODEWITHSUNDEEP
c++linuxtimecpu-registers
michael
michael

Reputation: 630

Fastest way to get a timestamp

I am implementing some data structure in which I need to invalidate some entries after some time, so for each entry I need to maintain its insertion timestamp. When I get an entry I need to get a timestamp again and calculate the elapsed time from the insertion (if it's too old, I can't use it).

This data structure is highly contented by many threads, so I must get this timestamp (on insert and find) in the most efficient way possible. Efficiency is extremely important here.

If it matters, I am working on a linux machine, developing in C++. What is the most efficient way to retrieve a timestamp?

BTW, in some old project I was working on, I remember I saw some assembly command which gets a timestamp directly from the CPU (can't remember the command).

Upvotes: 5

Views: 7146

Answers (1)

michael
michael

Reputation: 630

I have created the following benchmark to test several methods for retrieving a timestamp. The benchmark was compiled with GCC with -O2, and tested on my mac. I have measured the time it takes to get 1M timestamps for each method, and from the results it looks like rdtsc is faster than the others.

EDIT: The benchmark was modified to support multiple threads.

Benchmark code:

#include <iostream>
#include <chrono>
#include <sys/time.h>
#include <unistd.h>
#include <vector>
#include <thread>
#include <atomic>

#define NUM_SAMPLES 1000000
#define NUM_THREADS 4

static inline unsigned long long getticks(void)
{
    unsigned int lo, hi;

    // RDTSC copies contents of 64-bit TSC into EDX:EAX
    asm volatile("rdtsc" : "=a" (lo), "=d" (hi));
    return (unsigned long long)hi << 32 | lo;
}

std::atomic<bool> g_start(false);
std::atomic<unsigned int> totalTime(0);

template<typename Method>
void measureFunc(Method method)
{
    // warmup
    for (unsigned int i = 0; i < NUM_SAMPLES; i++)
    {   
        method();
    }

    auto start = std::chrono::system_clock::now();

    for (unsigned int i = 0; i < NUM_SAMPLES; i++)
    {   
        method();
    }

    auto end = std::chrono::system_clock::now();
    totalTime += std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
}

template<typename Method>
void measureThread(Method method)
{
    while(!g_start.load());

    measureFunc(method);
}

template<typename Method>
void measure(const std::string& methodName, Method method)
{
    std::vector<std::thread> threads;

    totalTime.store(0);
    g_start.store(false);

    for (unsigned int i = 0; i < NUM_THREADS; i++)
    {
        threads.push_back(std::thread(measureThread<Method>, method));
    }

    g_start.store(true);

    for (std::thread& th : threads)
    {
        th.join();
    }

    double timePerThread = (double)totalTime / (double)NUM_THREADS;

    std::cout << methodName << ": " << timePerThread << "ms per thread" << std::endl;
}

int main(int argc, char** argv)
{
    measure("gettimeofday", [](){ timeval tv; return gettimeofday(&tv, 0); });
    measure("time", [](){ return time(NULL); });
    measure("std chrono system_clock", [](){ return std::chrono::system_clock::now(); });
    measure("std chrono steady_clock", [](){ return std::chrono::steady_clock::now(); });
    measure("clock_gettime monotonic", [](){ timespec tp; return clock_gettime(CLOCK_MONOTONIC, &tp); });
    measure("clock_gettime cpu time", [](){ timespec tp; return clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tp); });
    measure("rdtsc", [](){ return getticks(); });

    return 0;
}

Results (in milliseconds) for a single thread:

gettimeofday: 54ms per thread
time: 260ms per thread
std chrono system_clock: 62ms per thread
std chrono steady_clock: 60ms per thread
clock_gettime monotonic: 102ms per thread
clock_gettime cpu time: 493ms per thread
rdtsc: 8ms per thread

With 4 threads:

gettimeofday: 55.25ms per thread
time: 292.5ms per thread
std chrono system_clock: 69.25ms per thread
std chrono steady_clock: 68.5ms per thread
clock_gettime monotonic: 118.25ms per thread
clock_gettime cpu time: 2975.75ms per thread
rdtsc: 10.25ms per thread

From the results, it looks like std::chrono has some small overhead when called from multiple threads, the gettimeofday method stays stable as the number of threads increases.

Upvotes: 11

Related Questions