Daniel Lemire's blog

, 11 min read

Parsing time stamps faster with SIMD instructions

17 thoughts on “Parsing time stamps faster with SIMD instructions”

  1. -.- says:

    The SSE code looks good. Possible tweaks (probably won’t show any difference in benchmarks, but may have theoretical advantages):

    replace _mm_sub_epi8 with _mm_xor_si128 – latter is commutative, so may give compiler more freedom with ordering (e.g. use load-op on the source if the 0x30 vector is already in a register). Some CPUs may have more ports for bitwise ops over arithmetic
    maddubs has longish latency; the _mm_subs_epu16 could actually be done before it if you use a BCD-like representation for limit16 which might help ILP

    1. BCD-like representation for limit16

      There is an endianness mismatch for this to work out?

      1. Flipping bytes might be worth the effort.

      2. -.- says:

        Ah, oops, missed that. Likely not worth it then.

        1. I do flip the bytes and find it worthwhile.

  2. Duck says:

    I solved a very similar problem on Stackoverflow some time ago. Its speed was < 1ns per time stamp.


    1. Indeed. It looks similar at a glance but your version does not compute the time in seconds since Epoch and does not validate.

      1. I doubt you can reach 1 ns per time stamp, at least using single threaded code processing one time stamp at a time.

        1 ns is very short.

        1. Duck says:

          1ns is for the case where it’s a hot-loop that does nothing but parsing timestamp, so everything is 100% in instruction cache and perfectly pipelined.

          The stackoverflow link contains 2 fully runnable programs to benchmark this. Could you add your solution (using methods in this blog)? Then I’ll benchmark and add it to the question.

  3. Arthur Chance says:

    we cannot have more than 59 seconds and never 60 seconds

    A slight nitpick: technically the seconds field can be ’60’ at 23:59 on the 30th of June or 31st of December if there’s a positive leap second.

    1. aqrit says:

      According to my reading of the linked RFC 4034 draft:

      A value of 60+ seconds is explicitly forbidden.

      The field being serialized is a Unix Timestamp. Unix Time explicitly ignores leap seconds.
      Converting Unix Time to UTC will never yield a leap second, as it can not be represented.

      1. Malcolm Parsons says:

        strptime() handles leap seconds, but mktime() does not.
        60 seconds should be accepted in the input, but treated as 59.

        1. Quoting from the RFC: https://www.rfc-editor.org/rfc/rfc4034

          The Time field values MUST be represented either as an unsigned decimal integer indicating seconds since 1 January 1970 00:00:00 UTC, or in the form YYYYMMDDHHmmSS in UTC, where:

            YYYY is the year (0001-9999, but see Section 3.1.5);
            MM is the month number (01-12);
            DD is the day of the month (01-31);
            HH is the hour, in 24 hour notation (00-23);
            mm is the minute (00-59); and
            SS is the second (00-59).
  4. Davidmh says:

    As Arthur indicates, you are ignoring all the leap seconds, which explains at least some of the reasons why the library version is slower.
    Not enough to get to 10 times more instructions, but still not a fair comparison.

    1. I don’t think that impacts the performance, but as pointed out by @aqrit, Unix time ignores leap seconds by its specification.

  5. SQL standard allows 62 seconds (0-61) in a minute, see https://twitter.com/noop_noob/status/1166982640118845442

  6. Daniel says:

    Just wanted to say hello and I’d wish I understood half of the code shared