5 ms·
Neatly omits the massively expensive calendar conversion step for turning the timestamp into a useful format for fast arithmetic. Parsing integers from strings
by dmw_ng 3y ago
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
- morelisp 3y ago> 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/blob/master/2023/07/01/src/sse_date.c#L11 https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/...
- refulgentis 3y agoAfter 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?
- anarazel 3y agoFWIW, the last time I measured the string handling part was far slower than the timezone conversion when loading timestamptz data in postgres.
- dataflow 3y ago> 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.
- wood_spirit 3y agoIndeed! 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 https://github.com/williame/TimeMillis
- lichtenberger 3y agoWouldn'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?
- haberman 3y agoDo 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-algorithms.html 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 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 https://godbolt.org/z/Kjnafzqcx vs https://godbolt.org/z/e7nchjKGW https://godbolt.org/z/e7nchjKGW)
- dmw_ng 3y agoAmazing 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.
- haberman 3y agoThanks! 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.
- kccqzy 3y agoThat'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.
- carlsborg 3y agoWhat 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.