A faster way to convert a timestamp to Hour, Min, Sec
76 points by benjoffe
76 points by benjoffe
Nicely explained. Extensively tested. The content is presented in a clear and visually appealing way. I really love it! <3
Thanks! It was fun to write.
The investigation started with the Base 60 -> Base 64 trick, which was a corollary of the previous weekday article. This forced me to try to restructure the function in ways that utilise it best.
I didn't realise until I started writing the blog post itself that the restructure was both the biggest cause for the speed improvement, as well as being an approach that has generally been overlooked in existing date libraries.
As someone more into high-level programming, I've always found it quite nebulous the performance characteristics of low-level operations such as these. Here I am thinking that division and modulo are single processor instructions and therefore the most optimal possible, and then an article like this comes along to give me a reality check.
It makes me wonder how much of what I think I know about compiled code is actually true. I try to avoid unnecessary allocations for performance but then, who knows, maybe for some reason I'm unaware of, some allocations are sometimes actually more optimal because of some other subtlety.
If you take this to the logical extreme, the same is true of every level of abstraction, from the way the compiler generates machine code all the way to how your GUI library is implemented.
No wonder software is slow.
Compilers can rewrite division-by-constant or modulo-by-constant into a multiplication. What's weird is that I haven't yet seen the division-by-constant followed by the modulo-by-that-same-constant be optimized by a single multiplication, but I assume that's just a matter of time (and someone reading this comment and going "Aha!")
See: https://en.wikipedia.org/wiki/Division_algorithm#Division_by_a_constant
And once that work goes into an optimizing compiler, you should be able to pick up the optimization from this article mostly "for free".
Here's the link I was looking for: https://arxiv.org/abs/1902.01961
It's called the FRDC optimization, and I've relied on it a few times already.
I suppose the difficulty with this technique being automatically applied is that it relies on either:
I'm even more surprised that the fast-division by saturating increment and round-down multiplier isn't used by any mainstream compiler, that optimisation at least does not have these two problems.
Reminded me of the times I've look at Go's time.Time implementation since I needed a version that worked with the day split into four units (so an accuracy of just night, morning, afternoon, and evening).
For my initial implementation it was really easy to port the Go code to Rust and make the modifications I needed. Some time later I returned to it and needed to make some changes and the Go codebase had optimized pretty much all of the algorithms and made the code really hard to read and copy from... I spent quite a good while confused at how I had ever ported the code until I realized to look at the git history for the previous version.
All of this to say that I appreciate your closing thoughts of
If you want clean readable math, choose "V1".
instead of automatically assuming that faster is better in all cases.
Thank you for sharing. This (and the previous submission in this series) have been very interesting to read.
The improvements over the naïve approaches seem significant—2× better latency in the best cases. How durable are these results expected to be over time?
The improvements are fairly self-contained, so I suppose updating this article in two or five or ten years and swapping out your datetime routines is not that much of a burden, though an interesting exercise might be to apply these improvements to historical architectures using contemporaneous compiler tooling to see whether whether the best today was, in fact, always the best yesterday (and, one would try to predict, the best to-morrow.)
(In general, is it not the case for µoptimisations that the “dumb, slow” way is often a more visible target for benchmark-motivated hardware designers and, thus, the advantages of the “clever, fast” approaches will necessarily decay over time? Of course, I suppose one might argue that there is something hardware is already quite mature, yet these opportunities are still presenting themselves…)
That is a good question. When working on these problems, I am usually wanting to find a solution that is broadly applicable across different types of hardware, hence why I also benchmark on the Raspberry PI Zero, which does not have superscalar features. I hope that this device is a good proxy indicator of how older hardware would have performed, but I guess I wouldn't know without further testing.
Much older hardware that is not capable of a widening multiply would obviously fall over on many of these functions, however the "NEON SIMD" version would likely perform well there, as it explicitly avoids all widening multiplies.
It's hard to predict the future to see where hardware will move. If someone comes up with a genius way to perform a multiplication in less than 3 cycles, or if shifts and adds become cheaper relative, then the dial will move. I suspect the biggest effect in the not too distant future could come from ISA changes, perhaps say if RISC-V becomes more relevant, perhaps a different function will win there (I really should get one of these for testing).
I agree that sometimes the dumb code can perform better in unexpected environments. A good example is how the Vector benchmarks for the AMD have "V1 Fixed-Pt" performing worse than "V1" (although the other way around on the Macbook). I don't know if these kind of things are the norm or the more visible exception.