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

91–100 of 100 posts

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

#91

Post by Marsymars »

dxdm wrote: post #74
toast0 wrote: post #65

Earlier quoted context omitted.

If Unix Time enumerated leap seconds, you couldn't convert future timestamps into localized times.

Could you elaborate on what you mean? I think it's already impossible to accurately turn a future timestamp into a local time, leap seconds or not, because of timezone shenanigans. So I'm probably misunderstanding what you're talking about.

I think it depends on whether you consider “localized” to refer to a point in time in a particular time zone, or to a point in time in a particular physical location.

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

#92

Post by dxdm »

Marsymars wrote: post #91
dxdm wrote: post #74

Earlier quoted context omitted.

Could you elaborate on what you mean? I think it's already impossible to accurately turn a future timestamp into a local time, leap seconds or not, because of timezone shenanigans. So I'm probably misunderstanding what you're talking about.

I think it depends on whether you consider “localized” to refer to a point in time in a particular time zone, or to a point in time in a particular physical location.

> or to a point in time in a particular physical location

But how does this not take the local time zone into account? For "time at location", the local time zone is by necessity always involved in conversions, isn't it? There's just a difference between the time zone being explicit in your data representation, or merely implied.

But you cannot with any sort of confidence assume a future "implied" time zone, which makes turning a future timestamp into a local time, even using a timezone-naive representation, into an usure proposition.

Maybe I'm simply not aware of specific conventions around this topic, though, hence my original question.

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

#93

Post by kilna »

dxdm wrote: post #74
toast0 wrote: post #65

Earlier quoted context omitted.

If Unix Time enumerated leap seconds, you couldn't convert future timestamps into localized times.

Could you elaborate on what you mean? I think it's already impossible to accurately turn a future timestamp into a local time, leap seconds or not, because of timezone shenanigans. So I'm probably misunderstanding what you're talking about.

Leap seconds are not deterministic.

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

#94

Post by Marsymars »

dxdm wrote: post #92
Marsymars wrote: post #91

Earlier quoted context omitted.

I think it depends on whether you consider “localized” to refer to a point in time in a particular time zone, or to a point in time in a particular physical location.

> or to a point in time in a particular physical location But how does this not take the local time zone into account? For "time at location", the local time zone is by necessity always involved in conversions, isn't it? There's just a difference between the time zone being explicit in your data representation, or merely implied. But you cannot with any sort of confidence assume a future "implied" time zone, which ma…

Oh I'm saying the reverse, I think. Future timestamp for "time at location" is impossible because you don't know within which time zone a location will be in the future. But for the right time zone database structure you can have indeterminate time zones - so you can know future timestamps for a time zone, but you don't know if any particular location (or any location at all) is using that time zone in the future.

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

#95

Post by benjoffe »

digitalPhonix wrote: post #3
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 nice writeup! > Years are calculated backwards How did that insight come about?

Thanks.

I was fortunate enough to be programming on an ARM based device, which meant that the terms (x * 4 + 3) strongly stood out to me as highly inefficient, being 2 cycle prep for the more important division. On x64 computers, those two operations are calculated in only one operation by using the 'LEA' assembly instruction (which I wasn't aware of at the time), and so others using that type of computer might not have felt this step needed any simplification.

I tried everything under the sun to get rid of these steps. The technique noted in the article of using the year 101 BC was for a long time my strongest candidate, you can view the implementation of that attempt at the link below [1].

An epoch of 101 BC still meant that there was extra work required to re-normalise the timeline after the century calculation, but it was only a single addition of 365 in the calculation of `jul`. The explanation of how this works is probably a whole blog post in itself, but now that this algorithm has been discarded it's not worth the time to explain it fully.

I also had the year-modulus-bitshift technique developed at that time, but it couldn't be integrated cleanly with any of my algorithm attempts yet. My plan was to simply document it as an interesting but slower concept.

I don't know what sparked the idea of going backwards other than immersing myself deeply in the problem in my spare time for about a month. It finally came to me one evening, and I thought it was only going to save 1-cycle, but when it also meant the year-modulus-bitshift could be utilised, the entire thing fit together like a glove and the speed collapsed down from 20% time saving to 40%.

[1] https://github.com/benjoffe/fast-date-benchmarks/blob/218356...

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

#96

Post by benjoffe »

zokier wrote: post #25
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...

not completely coincidentally, March was also the first month of the year in many historical calendars. Afaik that also explains why the month names have offset to them (sept, oct, nov, dec) edit: I just love that there are like 5 different comments pointing out this same thing

The first article in this blog post series has a little section talking briefly about this history, and there's a representation of this that I think sheds a lot of light on the original design. See the heading "Side-Note on Month / Day Determination" in the below link [1].

Displaying the months like the following helps see the regularity at a glance. Columns 1, 3 and 5 are the long months, others being shorter:

  +-----+-----+-----+-----+-----+
  | 31  | 30  | 31  | 30  | 31  |
  |  I  | II  | III | IV  |  V  |
  | MAR | APR | MAY | JUN | JUL |
  |-----+-----+-----+-----+-----+
  | 31  | 30  | 31  | 30  | 31  |
  | VI  |VII  |VIII | IX  |  X  |
  | AUG | SEP | OCT | NOV | DEC |
  +-----+-----+-----+-----+-----+
  | 31  |28/29|
  | XI  |XII  |
  | Jan | FEB |
  +-----+-----+
> To a person who natively thinks in Roman numerals, remembering that the short months are: II, VII, XII, along with IV & IX would be much easier than the way us modern folks have to memorise it.

[1] https://www.benjoffe.com/fast-date

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

#97

Post by benjoffe »

sltkr wrote: post #11
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” w…

Thanks, that is a good idea. This was originally a blog post series, and the first article gave a bit of an introduction.

When I started the blog series, I expected the first article to be the most noteworthy, with the 2nd and 3rd being lesser supplementary topics.

Now that the 3rd blog post ended up with a much larger result than I was expecting, it stands on its own and could do with some editing as you suggest.

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

#98

Post by benjoffe »

zozbot234 wrote: post #47
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.

How would this algorithm change on 16-bit or 8-bit devices? Or does some variety of the traditional naïve algorithm turn out to be optimal in that case? There's quite a bit of microcontroller software that might have to do date conversions, where performance might also matter. It's also worth exploring alternative epochs and how they would affect the calculation.

That is an interesting question.

It might also come into play if developing SIMD alternatives for batch date processing, as one can have more lanes with 16-bit. I plan to make a blog post covering SIMD and if 16-bit algorithms have reasonable performance then that will be covered.

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

#99

Post by eru »

Dylan16807 wrote: post #77
eru wrote: post #67

Earlier quoted context omitted.

Equinox or something like that?

The precise equinox sounds fussy to measure and even then you need to know three weeks before the equinox. While counting days is very easy.

Yes. But they also added leap days on an ad hoc basis right until the Caesar reformed the calendar. So some fussiness would probably not deter the much earlier Romans.

(It's still evidence in the direction you suggest, just much weaker than it looks at first.)

Post reply on HN