Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

benjoffe.com

Post reply on HN
Print view View original

11–20 of 100 posts

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#11

Post by sltkr »

benjoffe wrote: post #2

A write-up of a new Gregorian date conversion algorithm. It achieves a 30–40% speed improvement on x86-64 and ARM64 (Apple M4 Pro) by reversing the direction of the year count and reducing the operation count (4 multiplications instead of the usual 7+). Paper-style explanation, benchmarks on multiple architectures, and full open-source C++ implementation.

Very cool algorithm and great write-up!

I was a bit confused initially about what your algorithm actually did, until I got to the pseudo-code. Ideally there would be a high level description of what the algorithm is supposed to do before that.

Something as simple as: “a date algorithm converts a number of days elapsed since the UNIX epoch (1970-01-01) to a Gregorian calendar date consisting of day, month, and year” would help readers understand what they're about to read.

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#13

Post by silisili »

kccqzy wrote: post #7

I wrote my own date calculation functions a while ago. And during that, I had an aha moment to treat March 1 as the beginning of the year during internal calculations[0]. I thought it was a stroke of genius. It turns out this article says that’s the traditional way. [0]: https://github.com/kccqzy/smartcal/blob/9cfddf7e85c2c65aa6de...

At this risk of me feeling stupid, could you briefly explain the benefit of this?

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#14

Post by da_chicken »

silisili wrote: post #13
kccqzy wrote: post #7

I wrote my own date calculation functions a while ago. And during that, I had an aha moment to treat March 1 as the beginning of the year during internal calculations[0]. I thought it was a stroke of genius. It turns out this article says that’s the traditional way. [0]: https://github.com/kccqzy/smartcal/blob/9cfddf7e85c2c65aa6de...

At this risk of me feeling stupid, could you briefly explain the benefit of this?

It's easy to know what day of the year it is because leap days are at the end.

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#15

Post by kittikitti »

Thank you for sharing. This is a great achievement not only in the ability to invent a novel algorithm with significant performance gains but also the presentation of the work. It's very thorough and detailed, and I appreciated reading it.

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#16

Post by jandrese »

fnordsensei wrote: post #10
vladde wrote: post #5

> The algorithm provides accurate results over a period of ±1.89 Trillion years i'm placing my bets that in a few thousand years we'll have changed calendar system entirely haha but, really interesting to see the insane methods used to achieve this

Wouldn’t it be accurate for that as well? Unless we change to base 10 time units or something. Then we all have a lot of work to do. But if it’s just about starting over from 0 being the AI apocalypse or something, I’m sure it’ll be more manageable, and the fix could hopefully be done on a cave wall using a flint spear tip.

Or set 0 to be the Big Bang and make the type unsigned. Do it the same time we convert all temperature readings to Kelvin.

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#17

Post by kccqzy »

silisili wrote: post #13
kccqzy wrote: post #7

I wrote my own date calculation functions a while ago. And during that, I had an aha moment to treat March 1 as the beginning of the year during internal calculations[0]. I thought it was a stroke of genius. It turns out this article says that’s the traditional way. [0]: https://github.com/kccqzy/smartcal/blob/9cfddf7e85c2c65aa6de...

At this risk of me feeling stupid, could you briefly explain the benefit of this?

I just added a link to the code with a brief comment. Basically, it simplifies the leap year date calculation. If February is the last month of the year, then the possibly-existing leap day is the last day of the year. If you do it the normal way your calculations for March through December need to know whether February is a leap year. Now none of that is needed. You don’t even need explicit code to calculate whether a given year is a leap year: it’s implicit in the constants 146097, 36524, and 1461.

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#19

Post by Lammy »

masfuerte wrote: post #18

The Windows epoch starts on 1601-01-01. I always assumed that was because it slightly simplifies the calculation, as described in the article. But it's not as good as the article's method of counting backwards.

Relevant Old New Thing: https://devblogs.microsoft.com/oldnewthing/20090306-00/?p=18...

https://stackoverflow.com/questions/10849717/what-is-the-sig...

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#20

Post by wood_spirit »

Admittedly in a different league speed wise but also scope wise is my very fast timestamp library for Java https://github.com/williame/TimeMillis

This focuses on string timestamp and a few other utilities that are super common in data processing and where the native Java date functions are infamously slow.

I wrote it for some hot paths in some pipelines but was super pleased my employer let me share it. Hope it helps others.

Post reply on HN