8 ms·

Summing ASCII encoded integers on Haswell at almost the speed of memcpy

132 points by iliekcomputers 2y ago

wolf550e 2y ago
I think the trick with dereferencing unmapped memory is cool, but I only really care about techniques that work reliably and I can use in production.
- sYnfo 2y ago
  To be clear, it’s not dereferencing unmapped memory, I just haven’t shown how it’s being mapped, because it’s a little complex. As I note in the post, you can imagine as if I mmap all the necessary addresses at the start of the program.
  - camel-cdr 2y ago
    Given that the input is "integers uniformly sampled from [0, 2³¹−1]" couldn't you use a LUT for the 99.99% case of just 10/9/8 digit numbers instead and have a cold branch the handle the very rare smaller numbers.
    - anonymoushn 2y ago
      Yes, maybe if one is clever and lucky this could cost only a popcnt and a branch? not sure.
- the9 2y ago
  [flagged]
  - apantel 2y ago
    Looks like a scam.
ashleyn 2y ago
Knew it'd be SIMD. Such an underrated feature of modern CPUs. Hopefully with cross-platform SIMD in Rust and Golang, it'll be more commonly used. Thinking parallel gets you enormous speed benefits for any number of arbitrary algorithms: https://mcyoung.xyz/2023/11/27/simd-base64/ https://mcyoung.xyz/2023/11/27/simd-base64/
- neonsunset 2y ago
  Here's the tracking issue for Go if you're interested: https://github.com/golang/go/issues/67520 https://github.com/golang/go/issues/67520 I wouldn't be holding my breath though - proper support of high-level portable SIMD abstraction requires quite a lot of compiler complexity due to how wide (heh) the API surface of SIMD extensions is in most ISAs, and because of details necessary to get right to keep data in appropriate (vector and/or mask) registers. This, naturally, goes in the complete opposite direction to the design philosophy of Go's compiler. Instead, you are supposed to write a custom Go ASM syntax, with byte literals used to encode opcodes if they are not natively supported (which is common). If you're interested in what high-effort SIMD implementation in this kind of language looks like, take a look at C#'s cross-platform Vector API: https://github.com/dotnet/runtime/blob/main/docs/coding-guidelines/vectorization-guidelines.md https://github.com/dotnet/runtime/blob/main/docs/coding-guid... https://lemire.me/blog/2024/07/05/scan-html-faster-with-simd-instructions-net-c-edition/ https://lemire.me/blog/2024/07/05/scan-html-faster-with-simd... (uses platform intrisics, but showcases that you can go one abstraction level lower, retaining the same Vector128<T> type if you need to specialize a particular part of your algorithm for a platform, without having to maintain separate copy for each one) Here's high-effort vectorized CRC64 implementation that uses these: https://github.com/dotnet/runtime/blob/283de5b5adf08c42d49452208bde54cd7108514a/src/libraries/System.IO.Hashing/src/System/IO/Hashing/Crc64.Vectorized.cs#L46-L158 https://github.com/dotnet/runtime/blob/283de5b5adf08c42d4945... (performs as fast as C++-based mnemonic variant)
  - ziofill 2y ago
    Mojo should get a mention since we are in topic of SIMD.
the9 2y ago
[flagged]
dist1ll 2y ago
First time I hear about HighLoad. Seems really interesting to me on the first glance. I personally find SIMD and ISA/μarch-specific optimizations more rewarding than pure algorithmic challenges (codeforces and such). Though Haswell seems like a pretty obsolete platform to optimize for at this point. Even Skylake will be a decade old next year.
- deleted 2y ago
  [deleted]
- sgerenser 2y ago
  Realistically beyond Haswell there hasn’t been a ton of advancement in SIMD. Hawell introduced AVX2, which is what this blog post uses. AVX512 is certainly more powerful, but that’s not even available in the majority of Intel CPUs, even brand new ones.
  - jandrewrogers 2y ago
    AVX-512 has been ubiquitous on Intel server CPUs for a long time. Most people don't run high-performance throughput-oriented codes on consumer-grade CPUs with no ECC, which is the primary application for AVX-512. AVX-512 is a markedly better ISA than AVX2, aside from being wider.
    - adrian_b 2y ago
      "has been" => "had been" AVX-512 is no longer ubiquitous on Intel servers, but only on new AMD servers. Even earlier, there were cheap Intel servers with CPUs using Atom cores, for example the Denverton, Snow Ridge, Denverton Refresh, Snow Ridge Refresh, Parker Ridge and Arizona Beach series of server CPUs. None of these supported AVX-512 and many did not support even AVX. However, now, after the launch of the Sierra Forest server CPUs, which will be followed next year by the Clearwater Forest server CPUs, the Atom cores have expanded up to the biggest Intel server CPUs. While such server CPUs are intended for applications where computations using array operations are less important, like Web servers or the hosting of many small virtual machines, the fragmentation of the Intel ISA is extremely annoying, especially when AMD demonstrates how they can implement the same ISA, but at different levels of performance (by varying the number of vector pipelines and the maximum achievable clock frequency) both in laptop CPUs and in desktop/server CPUs and both in compact cores with low clock frequency and in big cores with high clock frequency. At least for me, the lack of AVX-512 support is the reason that made me stop buying Intel CPUs already some years ago, even if there are some features of the Intel CPUs that I prefer over the AMD CPUs (like TSC deadline), but none of those can compensate the lack of AVX-512 support. The greater width of AVX-512 is not its greater advantage, but the mask registers and a more complete set of instructions, which simplify many algorithms. Therefore when Intel will support AVX10/256 across all their CPUs, that will partially restore the competitivity of the Intel CPUs, but that is not likely to happen before 2026.
raldi 2y ago
Is there an explanation of why it sometimes gives the wrong answer?
- genter 2y ago
  > will only produce correct results with probability < 1, though very close to 1 That's terrifying
  - _a_a_a_ 2y ago
    Why? So long as you know the probabilities and they are tolerable, why?
    - kardos 2y ago
      The challenge is to get the right answer. It's much less interesting if you relax the challenge to no longer require the right answer. Here's a really fast approximate answer: 50000000*(2^31-1)/2
      - nerdponx 2y ago
        The fact that it's wrong sometimes is a lot less interesting than the probability distribution of wrongness, conditional on magnitude.
      - sYnfo 2y ago
        Map vs. territory. The challenge, as defined by the system the competition runs on, is to get 3 correct responses in a row. That's it.
      - Neywiny 2y ago
        Solid point and good example
  - madars 2y ago
    It's worse: Pr[correct output | hard input] = 0, even though they estimate that Pr[correct output | random input] ~ 1. This means that you can't, for example, amplify your success probability by repeating the algorithm a bunch of times and taking the majority vote.
yuhong 2y ago
[dead]

I think the trick with dereferencing unmapped memory is cool, but I only really care about techniques that work reliably and I can use in production.

sYnfo 2y ago
To be clear, it’s not dereferencing unmapped memory, I just haven’t shown how it’s being mapped, because it’s a little complex. As I note in the post, you can imagine as if I mmap all the necessary addresses at the start of the program.
- camel-cdr 2y ago
  Given that the input is "integers uniformly sampled from [0, 2³¹−1]" couldn't you use a LUT for the 99.99% case of just 10/9/8 digit numbers instead and have a cold branch the handle the very rare smaller numbers.
  - anonymoushn 2y ago
    Yes, maybe if one is clever and lucky this could cost only a popcnt and a branch? not sure.
the9 2y ago
[flagged]
- apantel 2y ago
  Looks like a scam.

ashleyn 2y ago

Knew it'd be SIMD. Such an underrated feature of modern CPUs. Hopefully with cross-platform SIMD in Rust and Golang, it'll be more commonly used. Thinking parallel gets you enormous speed benefits for any number of arbitrary algorithms: https://mcyoung.xyz/2023/11/27/simd-base64/ https://mcyoung.xyz/2023/11/27/simd-base64/

neonsunset 2y ago
Here's the tracking issue for Go if you're interested: https://github.com/golang/go/issues/67520 https://github.com/golang/go/issues/67520 I wouldn't be holding my breath though - proper support of high-level portable SIMD abstraction requires quite a lot of compiler complexity due to how wide (heh) the API surface of SIMD extensions is in most ISAs, and because of details necessary to get right to keep data in appropriate (vector and/or mask) registers. This, naturally, goes in the complete opposite direction to the design philosophy of Go's compiler. Instead, you are supposed to write a custom Go ASM syntax, with byte literals used to encode opcodes if they are not natively supported (which is common). If you're interested in what high-effort SIMD implementation in this kind of language looks like, take a look at C#'s cross-platform Vector API: https://github.com/dotnet/runtime/blob/main/docs/coding-guidelines/vectorization-guidelines.md https://github.com/dotnet/runtime/blob/main/docs/coding-guid... https://lemire.me/blog/2024/07/05/scan-html-faster-with-simd-instructions-net-c-edition/ https://lemire.me/blog/2024/07/05/scan-html-faster-with-simd... (uses platform intrisics, but showcases that you can go one abstraction level lower, retaining the same Vector128<T> type if you need to specialize a particular part of your algorithm for a platform, without having to maintain separate copy for each one) Here's high-effort vectorized CRC64 implementation that uses these: https://github.com/dotnet/runtime/blob/283de5b5adf08c42d49452208bde54cd7108514a/src/libraries/System.IO.Hashing/src/System/IO/Hashing/Crc64.Vectorized.cs#L46-L158 https://github.com/dotnet/runtime/blob/283de5b5adf08c42d4945... (performs as fast as C++-based mnemonic variant)
- ziofill 2y ago
  Mojo should get a mention since we are in topic of SIMD.

the9 2y ago

[flagged]

dist1ll 2y ago

First time I hear about HighLoad. Seems really interesting to me on the first glance. I personally find SIMD and ISA/μarch-specific optimizations more rewarding than pure algorithmic challenges (codeforces and such). Though Haswell seems like a pretty obsolete platform to optimize for at this point. Even Skylake will be a decade old next year.

deleted 2y ago
[deleted]
sgerenser 2y ago
Realistically beyond Haswell there hasn’t been a ton of advancement in SIMD. Hawell introduced AVX2, which is what this blog post uses. AVX512 is certainly more powerful, but that’s not even available in the majority of Intel CPUs, even brand new ones.
- jandrewrogers 2y ago
  AVX-512 has been ubiquitous on Intel server CPUs for a long time. Most people don't run high-performance throughput-oriented codes on consumer-grade CPUs with no ECC, which is the primary application for AVX-512. AVX-512 is a markedly better ISA than AVX2, aside from being wider.
  - adrian_b 2y ago
    "has been" => "had been" AVX-512 is no longer ubiquitous on Intel servers, but only on new AMD servers. Even earlier, there were cheap Intel servers with CPUs using Atom cores, for example the Denverton, Snow Ridge, Denverton Refresh, Snow Ridge Refresh, Parker Ridge and Arizona Beach series of server CPUs. None of these supported AVX-512 and many did not support even AVX. However, now, after the launch of the Sierra Forest server CPUs, which will be followed next year by the Clearwater Forest server CPUs, the Atom cores have expanded up to the biggest Intel server CPUs. While such server CPUs are intended for applications where computations using array operations are less important, like Web servers or the hosting of many small virtual machines, the fragmentation of the Intel ISA is extremely annoying, especially when AMD demonstrates how they can implement the same ISA, but at different levels of performance (by varying the number of vector pipelines and the maximum achievable clock frequency) both in laptop CPUs and in desktop/server CPUs and both in compact cores with low clock frequency and in big cores with high clock frequency. At least for me, the lack of AVX-512 support is the reason that made me stop buying Intel CPUs already some years ago, even if there are some features of the Intel CPUs that I prefer over the AMD CPUs (like TSC deadline), but none of those can compensate the lack of AVX-512 support. The greater width of AVX-512 is not its greater advantage, but the mask registers and a more complete set of instructions, which simplify many algorithms. Therefore when Intel will support AVX10/256 across all their CPUs, that will partially restore the competitivity of the Intel CPUs, but that is not likely to happen before 2026.

raldi 2y ago

Is there an explanation of why it sometimes gives the wrong answer?

genter 2y ago
> will only produce correct results with probability < 1, though very close to 1 That's terrifying
- _a_a_a_ 2y ago
  Why? So long as you know the probabilities and they are tolerable, why?
  - kardos 2y ago
    The challenge is to get the right answer. It's much less interesting if you relax the challenge to no longer require the right answer. Here's a really fast approximate answer: 50000000*(2^31-1)/2
    - nerdponx 2y ago
      The fact that it's wrong sometimes is a lot less interesting than the probability distribution of wrongness, conditional on magnitude.
    - sYnfo 2y ago
      Map vs. territory. The challenge, as defined by the system the competition runs on, is to get 3 correct responses in a row. That's it.
    - Neywiny 2y ago
      Solid point and good example
- madars 2y ago
  It's worse: Pr[correct output | hard input] = 0, even though they estimate that Pr[correct output | random input] ~ 1. This means that you can't, for example, amplify your success probability by repeating the algorithm a bunch of times and taking the majority vote.

yuhong 2y ago

[dead]