Comment by Dwedit

6 months ago

Wouldn't branchless UTF-8 encoding always write 3 bytes to RAM for every character (possibly to the same address)?

5 comments

Dwedit

Reply
ack_complete  6 months ago

CPUs are surprisingly good at dealing with this in their store queues. I see this write-all-and-increment-some technique used a lot in optimized code, like branchless left-pack routines or overcopying in the copy handler of an LZ/Deflate decompressor.

  • atq2119  6 months ago

    Yep, same with overlapping unaligned loads. It's just fairly cheap to make that stuff pipelined and run fast. It's only when you mix loads and stores in the same memory region that there are conflicts that can slow you down (and then quite horribly actually, depending on the exact processor).

    • Sesse__  6 months ago

      The place where I see this really hurts goes when Clang/LLVM gets too fancy, in situations like this:

        - Function A calls function B, which returns some struct S (for instance on the stack).
  - B writes S by individual (small) stores.
  - A wants to copy S from some place to another (e.g. store it in some other struct).
  - LLVM coalesces the individual loads/stores needed to copy S, into one or a series of large operations (e.g. 128-bit SSE2 loads+stores).
  - These large loads are issued while the small stores from B are still pending, and necessarily overlap them.

      Boom, store-to-load forwarding failure, and a bad stall. E.g., the Zen series seem to be really bad at this (only tried up to Zen 3), but there are pretty much no out-of-order CPUs that handle this without some kind of penalty.

      1 reply →

ngoldbaum  6 months ago

You could do two passes over the string, first get the total length in bytes, then fill it in codepoint by codepoint.

You could also pessimistically over-allocate assuming four bytes per character and then resize afterwards.

With the API in the linked blog post it's up to the user to decide how they want to use the output [u8;4] array.