Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

blog.mattstuchlik.com

Post reply on HN
Print view View original

11–20 of 41 posts

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

#11

Post by neonsunset »

ashleyn wrote: post #4

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/

Here's the tracking issue for Go if you're interested: 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-guid...

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 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/283de5b5adf08c42d4945... (performs as fast as C++-based mnemonic variant)

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

#14

Post by sYnfo »

raldi wrote: post #12

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

1) if you set BATCH_SIZE > 14 sums_acc may overflow

2) chunks with too many small numbers cannot be processed with just 2 shuffle-adds

3) (not mentioned in the post) HighLoad limits the size of the source code you can submit, so you can't put all possible values in the look-up table

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

#15

Post by _a_a_a_ »

genter wrote: post #13
raldi wrote: post #12

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

> will only produce correct results with probability That's terrifying

Why? So long as you know the probabilities and they are tolerable, why?

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

#16

Post by sgerenser »

dist1ll wrote: post #9

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.

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.

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

#17

Post by kardos »

sYnfo wrote: post #14
raldi wrote: post #12

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

1) if you set BATCH_SIZE > 14 sums_acc may overflow 2) chunks with too many small numbers cannot be processed with just 2 shuffle-adds 3) (not mentioned in the post) HighLoad limits the size of the source code you can submit, so you can't put all possible values in the look-up table

For 1, can you raise that to 28 with unsigned accumulators?

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

#18

Post by kardos »

_a_a_a_ wrote: post #15
genter wrote: post #13

Earlier quoted context omitted.

> will only produce correct results with probability That's terrifying

Why? So long as you know the probabilities and they are tolerable, why?

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

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

#19

Post by nerdponx »

kardos wrote: post #18
_a_a_a_ wrote: post #15

Earlier quoted context omitted.

Why? So long as you know the probabilities and they are tolerable, why?

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

The fact that it's wrong sometimes is a lot less interesting than the probability distribution of wrongness, conditional on magnitude.

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

#20

Post by sYnfo »

kardos wrote: post #18
_a_a_a_ wrote: post #15

Earlier quoted context omitted.

Why? So long as you know the probabilities and they are tolerable, why?

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

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.
Post reply on HN