Hacker News Reader

Comment by dmw_ng | Hacker News Reader

Neatly omits the massively expensive calendar conversion step for turning the timestamp into a useful format for fast arithmetic. Parsing integers from strings is not why parsing timestamps is slow, any more than counting the length of strings is why XML parsing might be slow.

For time-sequential data, one easy speedup hack is caching the UNIX epoch for the current day start and adding the HH:MM:SS manually. No measurements to offer, but would suggest approaches like this would cleanly beat simdification of a trivial part of a complex task

View on HN

Do you mean the conversion from YYYY-MM-DD to Unix Time? That can be quite fast; I wrote a blog article showing some algorithms that take less than 10ns to perform the conversion: https://blog.reverberate.org/2020/05/12/optimizing-date-algo...

Recently I came across another variant of the algorithm that is even smaller and simpler. I've been meaning to test this variant and add it to my article (assuming it is correct), but I haven't had the chance: https://dotat.at/@/2008-09-10-counting-the-days.html. (EDIT: I just tried it out. It works, and while the source code is smaller than my other variants, epoch_days_fast() from my article is still smaller and faster in terms of machine code: https://godbolt.org/z/Kjnafzqcx vs https://godbolt.org/z/e7nchjKGW)

Amazing work :) Do you know if glibc gmtime_r() might be impacted by the active timezone? My "massively expensive" experience above came from gmtime_r() on Amazon Linux running in Lambda, but I can't remember the exact scenario involved (or e.g. if TZ were set), it certainly seems unlikely worth putting the effort into it that I did if the costs were similar to those observed in your post.

Thanks! I didn't experiment with gmtime_r() since it goes in the other direction (UnixTime -> civil time). I wouldn't expect timegm() or gmtime_r() to depend on current timezone, since both are hard-coded to use UTC. I never did figure out why the macOS version is performing mutex locks on global data.

That's amazing! Long time ago I wrote a conversion function that took longer than 10ns but had the input normalization feature you skipped in your blog post. (Say January 32nd will be automatically transformed to February 1st, and specifying the thirteenth month of a year will become January of the following year.) Those are simple to implement and I doubt it costs much.

To normalize months outside of the 1–12 range:

    --month;
    if (month >= 12 || month < 0) {
      year += month / 12;
      month %= 12;
      if (month < 0) {
        --year;
        month += 12;
      }
    }
    ++month;

To fix incorrect days that's even easier. Most algorithms do not need any changes.

Indeed! It was a while ago but Im quite proud of the fast timestamp functions I made for Java after the standard library timestamp performance turned out to be critical to some data pipelines I was working on.

The early versions of the code did cache the last parsed date etc but as the parser got quicker this became diminishing returns.

The fastest way I found for the calendar month numbers etc was to use a precomputed table etc.

https://github.com/williame/TimeMillis

Wouldn't it be possible to contribute the faster algorithm to the JDK (e.g. the Instant class)? Maybe you'd need some iterations, but do you see any downsides?

> omits the massively expensive calendar conversion step

Is that not included in what's 6x faster? I agree comparing against strptime is a bit of a gimme and a scalar fixed-format parser would be fairer, but I'm pretty sure it will beat that too.

Edit to reply since rate-limited:

> No mention of calendar in either place. Did you see something in the article or code, or are you just asking us to check?

The (lack so far of) calendar is mentioned in the blog post - "It does not get all the parsing done... We can just use standard C code for the result." - and is very obviously in the GitHub code.

https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/...

After reading twice and scouring the code on GitHub, I don't think so.

No mention of calendar in either place.

Did you see something in the article or code, or are you just asking us to check?

> one easy speedup hack is caching the UNIX epoch for the current day start and adding the HH:MM:SS manually

Side note, this is a really great example of why you'd want an operation such as parsing to be state-mutating when you'd normally expect it not to. i.e. why it makes sense to support passing a Parser object rather than just a parse() function, even for operations where you don't think it's necessary at first glance.

the downside is that now you will have to consider thread safety

Yep, you'd want to copy the parser per thread.

FWIW, the last time I measured the string handling part was far slower than the timezone conversion when loading timestamptz data in postgres.

What are you referring to? The benchmark includes the step to convert to unix time int, at the end of sse_parse_time() even handling leap years.

Reply on news.ycombinator.com