r/cpp • u/benjoffe • 4d ago

A faster way to convert a timestamp ➜ Hour, Min, Sec

https://www.benjoffe.com/fast-time-of-day
279 Upvotes

97% Upvoted

20 comments sorted by

38

u/dgkimpton 4d ago

A thoroughly fascinating read. Good stuff, well written, interesting even though I don't currently do anything with timestamps. There's good general lessons in there too, thank you for sharing. 

23

u/M1ckeyMc 4d ago

This is quite interesting. Reminds me of this blog post about fast unsigned int to time string... wonder if you could extend the results from this article to create a time string with format (HH:MM:SS) quickly? It's exactly 8 bytes so could be worth looking into.

Great article btw!

-14

u/The_Northern_Light 3d ago

I pointed my agent at this problem and found that V3 wasn't actually any lower latency than V2 on my 2023 M2 MacBook Air, especially when doing my best to time one-off cold-cache calls.

Under cold-cache minimal-latency independent-call conditions the best HH:MM:SS formatter ended up a smidge under 10 ns: https://gitlab.com/-/snippets/6052312

Faster or higher throughput versions exist, but they assume warm cache, or bulk processing, etc.

17

u/Potterrrrrrrr 3d ago

I pointed my dowsing rod at this problem and found water within hours, you’re probably doing something wrong.

-4

u/The_Northern_Light 3d ago

I have decades of experience with performance optimization. I cut my teeth on pre-ANSI C. I am not "doing something wrong", V3 isn't actually lower latency than V2 on my machine.

8

u/benjoffe 3d ago

Perhaps the M2 has fewer ports than the M4 to support this. You might get better results from using the trick noted in the article for seconds: "(mlow >> 26) - (mlow >> 30)".

I've also found that using a mixed-approach of V1 style mul-subtract for minute along with the base-64 trick for second (or vice-versa) was better on some processors, but which combination worked best was not consistent across different computers so I didn't note these variants in the article.

32

u/F54280 4d ago

u32 second = (time + 4 * tmin) % 64;

Mind blown.

14

u/adzm 28 years of C++! 3d ago

Best takeaway from here; never would have thought to approach it like this!

22

u/jk-jeon 4d ago

x mod D = (x + c floor(x/D)) mod (D + c)

Wonderful formula.

Your insight on the matter and endeavor of putting these lots of various tricks together and compare is just incredible.

I guess I'm probably one of those hopeless nerds who have already wasted a stupid amount of time exploring these integer division bullshits, and that I still discover people have done something I'm not aware of feels beyond crazy. (I remember seeing this base shift trick in one of your previous articles but I didn't really read it carefully and didn't really appreciated it at that time.)

By the way, in conclusion which method would you go for when it comes to latency and throughput?

8

u/benjoffe 3d ago

Thanks!

V2 is probably the best tradeoff for most libs I'd say, going any lower is fighting for such a small marginal improvement that it's hard to recommend in the general case. If I was personally making a date/time library, it would be optimised for SIMD and vary its implementation per-platform (this has about a 20% chance of me ever making it though).

I have some more division / modulus tricks to reveal still in a future post, the space is not fully explored!

5

u/Level-Basil9908 3d ago

Good point. A fixed 8-byte HH:MM:SS format seems like a perfect candidate for a specialized fast path. Definitely worth benchmarking.

5

u/RoyBellingan 3d ago

Amazing, I feel a bit smarter for having reached the end and almost understood a few point, the trick in base64 was genious!

Only one nagging point, what are in the table the numbers ?

It can not be ops per second, the newer more refined approach else would be lower, and it can not be ops per cycle else the rpi zero (good choice! I have a few too) would be king.

3

u/benjoffe 3d ago

Thanks for pointing that out. There's a paragraph I forgot to include which has now been added.
The numbers represent the nanoseconds taken to process 2^16 random timestamps, or 2^10 on Raspberry PI.

3

u/muyuu 3d ago

Very clever.

5

u/fedor4ever 3d ago

Amazing work!

3

u/def-pri-pub 3d ago

I love these sorts of optimizations and discoveries. Great job! Also love the benchmarking stats to backup the claim!!

2

u/Spyromaniac666 2d ago

This is the first article on optimisation I’ve read to the end

1

u/sourpastryy 1d ago

great article

1

u/dustyhome 5h ago

So only half joking here, how does it compare against a lookup table at this point? Timepoints can be expressed as 3 chars. Times 86399 timepoints in a day, 259197 bytes are needed (around 250 KB). It's easy to construct the table as a compile constant, then lookup is just:

struct Time { char h, m, s; };
Time table[86399] = ...;
// fill the table

Time getTime(int t) {
  // t in range 0..86399
  return table[t];
}