Parsing time stamps faster with SIMD instructions
lemire.me
lemire.me
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
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/...
No mention of calendar in either place.
Did you see something in the article or code, or are you just asking us to check?
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 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.
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)
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;
This is how you get leap seconds bugs?
If you're subtracting Unix timestamps to get durations you may have bugs, but those bugs might align better to your user's expectations anyway.
Unix time is seconds since 1970... If you convert between time formats you MAY loose information. That has nothing to do with unix time.
In this case, without leap seconds, you'd have still lost the precision, but you wouldn't have actually violated causality. Winding back during a leap second makes it so that a timestamp that's > 1 second later in real time still ends up being ordered as strictly before the earlier time. That's a bug, regardless of how you slice it.
Now this can be partially avoided by saturating the subtraction at the boundary rather than winding it back, and I'm not sure how many implementations do this. That seems better, but it's still surprising (and thus bug-prone) given the input and output representation otherwise appear to have sufficient precision.
If converting things from one system to another means two very close events get the same timestamp? Eh, that can happen in many ways with many systems. That's not bugginess.
This is unfortunately common misconception. Unix time in reality is seconds since epoch minus the number of leap seconds
I it just a guy hwo started counting at 1970
UTC: 58, 59, 60, 00, 01
UNIX: 58, 59, 00, 00, 01
That depends. 30th June 2015 23:59:59 has the timestamp 1435708799. 1st July 2015 00:00:00 has the timestamp 1435708800. But what about the leap second that happened between those two seconds? I think most people would claim it also has timestamp 1435708799. but then "Each Unix timestamp corresponds to one unique point in time" isn't true, because 1435708799 now corresponds to two different points in time (30th June 2015 23:59:59 and 30th June 2015 23:59:60). Saying there is a unique mapping from unix timestamp to time would only be true if you either say that 30th June 2015 23:59:60 has no unix timestamp (which isn't a valid return value of any time API I've seen) or if you smear time.
This means you can just adjust the mapping around the leap second. A naive implementation might have those two real-life seconds tick twice as fast to take only one Unix second. Or you could have the whole day’s seconds tick 86401/86400 times as fast, etc. In terms of the mapping from continuous time to discrete time, this is just as fine as the non-leap-second case.
This is plain false. For example 1435708799 corresponds to both 2015-06-30T23:59:59Z and 2015-06-30T23:59:60Z
https://elixir.bootlin.com/linux/v6.4.1/source/kernel/time/n...
sure leap smearing could be considered compatible with posix in the sense that posix does afaik not require any level of accuracy from clocks, so even something silly like xkcd 2266 could be considered posix compatible https://xkcd.com/2266/
UNIX time ignores leap seconds.
I.e. it's the number of seconds ignoring leap seconds since 1970.
And apparently these strings don't have second 60.
Works for me.
Side note but I always found this phrasing to be incredibly confusing (hence the need for the "i.e."...); it's the exact opposite of what I would think it means to "ignore" leap seconds. Ignoring something means you don't change your behavior when that something happens. But when leap seconds happen, the epoch timestamp halts its counting. That's not ignoring leap seconds -- that's actively countering the leap seconds!
Normally, UNIX time goes up by one each second.
Unless, it's a leap second, in which case UNIX time does nothing.
Example: You're driving your car when pedestrians appear in front of you. What does "ignoring" them constitute? Stopping the car, or running into them at the previous speed?
At the point they needed to be inserted, Unix systems carry on counting seconds as units of time as they pass, "ignoring" the need to add 1 for the purposes of accounting.
unix systems essentially will roll back clocks during leap seconds. here is handy dandy table as an example:
Time tv_sec tv_usec
2015-06-30T23:59:58.9Z 1435708798 900000
2015-06-30T23:59:59.0Z 1435708799 0
2015-06-30T23:59:59.1Z 1435708799 100000
... ... ...
2015-06-30T23:59:59.9Z 1435708799 900000
2015-06-30T23:59:60.0Z 1435708799 0
2015-06-30T23:59:60.1Z 1435708799 100000
... ... ...
2015-06-30T23:59:60.9Z 1435708799 900000
2015-07-01T00:00:00.0Z 1435708800 0
2015-07-01T00:00:00.1Z 1435708800 100000
... ... ...
But when I count people passing me, I press my clicker each time to count them. Except once in a while I don't do anything, i.e. ignore them.
Doing anything else means handling them by adding custom behavior.
You can make a pretty good argument that "every day is 86400 seconds" is ignoring leap seconds. And that's what "Unix time" does.
Though you can also make a good argument that "seconds since 1970, no idea what a 'day' is" ignores leap seconds.
https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1...
This seems like a major overcorrection. It's equivalent to saying "you can't know anything" "no one is qualified to do anything"
You really have to consider the downsides. In cryptography, "don't roll you own crypto" is the maxim because the downside is pretty bad. Make sure you're an expert before writing crypto.
What's the downside to mis-parsing leap seconds? Maybe a 500 on a super rare request? Then they patch it and it's fine? Most computers are off by more than 1 second anyway.
I think this mindset comes from developers looking into some field and realizing it's super deep ("Did you know there are missing dates in the gregorian calendar if you go back hundreds of years? Your time library is incorrect if it doesn't handle these cases!"). And sure, most things aren't completely correct, but you have to consider what the downside is to being slightly wrong. Maybe it'll be wrong in cases that will never actually happen in practice.
How is anything going to be made then ?
Also, the author isn't just anybody and has created stuff that you've most likely interacted with. If almost nobody should "roll his own", he's one of those who should.
When I got there time comparisons were a mess, parsing in multiple places, some comparisons not taking into account the TZ, some add and subtract operations incorrectly code, and other issues.
I tried to make the case that parsing and compare timestamps was a core operation, and the system should have all that functionality polished and packaged up to its own module so programmers could focus on the rest of the system, but was unsuccessful. We were writing in Go, so the language libraries did about 80% of the work, and the less experienced programmers thought it was sufficient.
When I left they were struggling with issues around determining passenger age at the time of flight and getting off-by-one errors around certain cutoff ages.
Time is Hard. https://gist.github.com/timvisee/fcda9bbdff88d45cc9061606b4b...
pub fn parseYear4(text: *const [4]u8) !u16 {
const nnnn: @Vector(4, u16) = .{ text[0], text[1], text[2], text[3] };
const zero: @Vector(4, u16) = .{ '0', '0', '0', '0' };
const mmmm: @Vector(4, u16) = .{ 1000, 100, 10, 1 };
const result = @reduce(.Add, (nnnn -% zero) *% mmmm);
if (result > 9999) return error.CertificateTimeInvalid;
return result;
}
machine code example: https://godbolt.org/z/ezrPEdPx7
In the most common case, you'd have something like 2023-07-02T15:46:00Z possibly with a ".123" been the last "0" and "Z".
Would it be fastest to just copy the relevant chars to the correct place for the code in the post? Or could you do it in place somehow?
That site is really good to play with SIMD code.
Frequently we end up with solutions that use tricks that would not be applicable to the n=1 problem in TFA ("parse 1 timestamp") when we try to get the fastest solutions for "find the sum of all these timestamps."
I know that `wide`, `faster`, and `simdeez` are options for crates to do cross-platform SIMD in safe Rust. Eventually we'll have `std::simd`, but I don't know what the timeline is or what the blockers are.
Here's an article I wrote about using SIMD in rust, with a real-world example: https://neosmart.net/blog/using-simd-acceleration-in-rust-to...
Not as fast as SIMD, perhaps, but much faster than the Java standard library…
That doesn't seem related?
If that's a performance concern, a (potentially zero-padded, but realistically you don't even needed that) Unix timestamp works just as well.
People timestamp stuff for different reasons. If you do it to avoid collisions then adding sub-second precision makes sense, but in many contexts second or even day precision is all you care about.
The important point is that %Y%m%d%H%M%S is human parsable and still sorts correctly (though humans typically prefer %Y-%m-%d %H:%M:%S for readability)