7 ms·
Parsing time stamps faster with SIMD instructions
- lyu07282 3y agoThis is really cool, I recently wanted to implement a ARGB->RGBA conversion function with SIMD in Rust, but as far as I can tell SIMD is STILL not in stable Rust :(
- lpghatguy 3y agoThe CPU-specific intrinsic stabilized a little while ago for cases where you need SIMD on a specific platform at least. A lot of crates like glam seem to only support SIMD on x86/x86-64 for that reason. 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.
- mirsadm 3y agoYou won't get much speed up using SIMD for such a simple task. You'll be memory bandwidth limited.
- ComputerGuru 3y agoSIMD is stable in rust, it just requires unsafe. 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-create-the-worlds-fastest-tac/ https://neosmart.net/blog/using-simd-acceleration-in-rust-to...
- 3836293648 3y agoGeneric architecture independent SIMD isn't stabilised, aka the proposed std::simd. But yeah, the x86 specific stuff is there
- jeffbee 3y agoI don't think I have ever seen %Y%m%d%H%M%S used in real life.
- wood_spirit 3y agoin datasets that I’ve worked with it is so incredibly common and so incredibly slow that I’ve previously made a fast library to work with them: https://github.com/williame/TimeMillis https://github.com/williame/TimeMillis Not as fast as SIMD, perhaps, but much faster than the Java standard library…
- vardump 3y agoThat's a very common format.
- victor82 3y agoThe solution exposed don't seems competitive enough to solve with good rank the problem exposed here https://highload.fun/tasks/14 https://highload.fun/tasks/14 That site is really good to play with SIMD code.
- reaperman 3y agoHow can I see Yuriy’s top solution for this task?
- anonymoushn 3y agoYou can ask him but he probably won't share
- reaperman 3y agoKind of a weird leaderboard if you can’t even check to see if answers satisfy correctness. I’ve seen plenty of leaderboards where the top answers would fail cases that weren’t covered by the leaderboards testing.
- paulmd 3y agoYeah, most of the leetcode top solutions are a hardcoded table of answers for the scoring questions followed by the general solution.
- anonymoushn 3y agoI think it's not such a big deal because the input generators are usually pretty good and because most solutions that give up some correctness for performance can pretty cheaply detect that they done goofed and fall back to a slow path where they start over and do it some other way. This ends up being useful because scoring is the median runtime of 3 successful runs (so if you fail one of the 3 then your submission fails completely). It also means that probabilistic solutions that would be correct in non-adversarial environments (like using a bloom filter or N bloom filters tuned to give an exact result given the input constraints with probability >99.9%) are admissible.
- 0xr0kk3r 3y ago[flagged]
- brigadier132 3y agoCode from academia is notoriously unreadable
- WJW 3y ago> You'd think a professor would want to encourage better documentation, or at least expose students who are reading this post to some basic commenting. Welcome to academic code. We're lucky there's any comments at all. :)
- dundarious 3y agoLooks to be using a lot of similar ideas to the ones explained well in these articles: https://kholdstare.github.io/technical/2020/05/26/faster-integer-parsing.html https://kholdstare.github.io/technical/2020/05/26/faster-int... http://0x80.pl/articles/simd-parsing-int-sequences.html http://0x80.pl/articles/simd-parsing-int-sequences.html
- aqrit 3y agoThe methods in those articles could be slightly improved by picking better multipliers. https://stackoverflow.com/a/71594769 https://stackoverflow.com/a/71594769
- jakear 3y agoWhat are you even talking about? There's tons of comments and the code isn't obscure. https://github.dev/lemire/Code-used-on-Daniel-Lemire-s-blog/tree/master/2023/07/01 https://github.dev/lemire/Code-used-on-Daniel-Lemire-s-blog/...
- 0xr0kk3r 3y agoWhat do you think I'm talking about? OP pruned the comments out of github and put the code on the page w/o them. I didn't click to the github page. Still confused?
- kolbe 3y agoInteresting. I think you'd find that doing this in chunks of 128-bit wide vectors with platform-agnostic logic would be even better. Have you tried something like Google Highway or writing this exact logic in scalar code and seeing if the compiler will autovectorize it? Then you have the option to do up to 4 of them at once instead of one if your platform supports it.
- mabbo 3y agoHow hard would it be to modify this to work with ISO-8601, the international time stamp format? 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?
- zokier 3y agoShouldn't be too hard, assuming you don't need any validation. There afaik are simd instructions to move bytes around (vpermb maybe?), so that should take care of getting rid of the separators
- anonymoushn 3y agoThe code in the post doesn't seem to finish the job. For a timestamp like "2023-07-02T15:46:00Z" or the other formats you mentioned, the timestamp fits in a single 32-byte register, so you could write code that deals with the stuff as it is. If you have a mix of timestamps with different numbers of decimals or with different time zones, dealing with those things will take a bit of work compered to the ideal case where you had all "Z" or all "+" or all "-" for the time zones and all the same number of decimals for the fractional seconds.
- zokier 3y ago> We know that some character must be smaller than 9, for example, we cannot have more than 59 seconds and never 60 seconds, in the time stamp string. This is how you get leap seconds bugs?
- dataflow 3y agoI believe if you're using epoch timestamps you already have leap seconds bugs. I don't think they increment/decrement when the leap second happens.
- morelisp 3y agoIf you're using epoch timestamps to represent time you don't have leap second bugs. Each Unix timestamp corresponds to one unique point in time which also has some representation in civil time. 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.
- dataflow 3y agoNo, bugs can come up without any subtraction. If an event was recorded as happening at 23:59:60.2, you need it to be sequenced strictly after 23:59:59.9. Winding back the clock by 1 second makes it so you end up with the later event as having occurred at 23:59:59.2, violating causality. Even without sub-second precision the situation is still buggy, just not as bad - you end up with two simultaneous events when there weren't any in the original representation, which is itself quite surprising when the two look like they have the same precision.
- heywhatupboys 3y ago> you end up with the later event as having occurred at 23:59:59.1 Unix time is seconds since 1970... If you convert between time formats you MAY loose information. That has nothing to do with unix time.
- dmw_ng 3y agoNeatly 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.
- cratermoon 3y agoAt one consulting gig I had at an airline, I noted that timestamps were everywhere and among the most frequent operations in the system was comparison with current time. The legacy systems spit out date/time in at least 3 different formats, and almost never included the timezone. The TZ had to be determined by looking up the airport's TZ. 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/fcda9bbdff88d45cc9061606b4b923ca https://gist.github.com/timvisee/fcda9bbdff88d45cc9061606b4b...
- carlsborg 3y agoWhy does month in the limit vector go to 19?
- aqrit 3y agoThere are two digits for months. A check is required per-character to prevent bad chars (e.g 0x3A) from being laundered by the multiply. The '19' comes from fact that the first digit may be only 0 or 1, while the 2nd digit maybe any value 0..9 (e.g September '0'9' October '1'0'). The second check catches bad month values between 13..19 which were not caught by looking at individual digits. Realistically, the first check may be overbuilt, it only needs to check is_digit or not, but it still has to ignore the padding bytes at the end, somehow. Now... I believe there would be a problem with the month value of '00'... because it unconditionally subtracts 1 from that field then uses it as a table index.
- carlsborg 3y agoOk 8 bit unsigned ints and zero padded month, and then they do the zero saturated subtract. I hadn't made it to the second check, doh.
- AndyKelley 3y agoContrast that C code with: 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; } source: https://github.com/ziglang/zig/blob/fc9ab5f0e838196e99d1706e4d4e91f3d761d509/lib/std/crypto/Certificate.zig#L636-L643 https://github.com/ziglang/zig/blob/fc9ab5f0e838196e99d1706e... machine code example: https://godbolt.org/z/ezrPEdPx7 https://godbolt.org/z/ezrPEdPx7
- aqrit 3y agoThat snippet would not reject bad chars, are non-digits rejected somewhere else? A simple scalar loop that multiplies an accumulator by 10, itoa() style, would be faster.
- andrewgazelka 3y ago[dead]