[dead]
Summing ASCII encoded integers on Haswell at almost the speed of memcpy
31–40 of 41 posts
Re: Summing ASCII encoded integers on Haswell at almost the speed of memcpy
#32Earlier quoted context omitted.
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.
"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…
Yeah, I buy AMD Epyc almost exclusively, primarily because it’s so freaking annoying to even decide which Intel CPU will work for a given application. Plus you can usually get current or previous generation Epyc cores new for less than half the MSRP.
Re: Summing ASCII encoded integers on Haswell at almost the speed of memcpy
#33Knew 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. Thi…
Mojo should get a mention since we are in topic of SIMD.
Re: Summing ASCII encoded integers on Haswell at almost the speed of memcpy
#34First 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.
As part of that Haswell brought FMA support which was a boon to those of us doing a lot of multiplication and addition (made those workloads twice as fast).
Re: Summing ASCII encoded integers on Haswell at almost the speed of memcpy
#35Is 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
So SIMD would need to set the overflow flag also to catch em.
Which would be much faster than the checked add (adc). Does any hardware support such checked SIMD arithmetic already?
Or can you still assume that most arithmetic is still broken in most languages/libraries.
Re: Summing ASCII encoded integers on Haswell at almost the speed of memcpy
#36Earlier quoted context omitted.
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
So SIMD would need to set the overflow flag also to catch em. Which would be much faster than the checked add (adc). Does any hardware support such checked SIMD arithmetic already? Or can you still assume that most arithmetic is still broken in most languages/libraries.
AVX-512 has evolved from the Larrabee New Instructions (2009), passing through Knights Ferry (2010), Knights Corner (2012) and Knights Landing (2016), to reach Skylake Server (2017), whose set of AVX-512 instructions has remained a subset of the instruction sets of all later CPUs with AVX-512 support.
At each step from Larrabee to Skylake Server, some instructions have been lost, because the initial set of instructions was more complete in order to enable the writing of efficient GPU algorithms, while later Intel believed that for a general-purpose CPU they can reduce the costs by omitting some of those instructions.
(Nevertheless, later they have added many other instructions, some of which may be less useful and more expensive than the original instructions that have been removed.)
Among the original Larrabee instructions that have been deleted, was addition with unsigned overflow (a.k.a. carry), where the output overflow flags were stored in a mask register, enabling their use in a later conditional SIMD instruction.
Signed overflow can be implemented in hardware with negligible additional complexity (a single gate per each result number), so it would have been easy to also add to Larrabee/AVX-512 an addition instruction with signed overflow flags stored in a mask register. Even when only unsigned overflow is available, it is possible to preprocess the operands in such a way that detecting signed overflow would be possible with the unsigned overflow bits, though that requires multiple instructions, slowing down a lot the algorithm.
However in this problem the numbers that are added are non-negative, so the addition with unsigned overflow of the original Larrabee ISA would have been sufficient, had Intel not removed it from AVX-512.
Re: Summing ASCII encoded integers on Haswell at almost the speed of memcpy
#37Earlier quoted context omitted.
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. Thi…
Mojo should get a mention since we are in topic of SIMD.
Corrective upvote from me :)
Mojo's effort in bringing portable SIMD abstraction to Python audience is commendable. I'm looking forward to open-sourcing of it to try it out!
For anyone's curious, the reason I'm mostly talking about C# above is that its Vector API is the most accessible and mature portable SIMD abstraction that is part of standard library / comes out of box among most other options - you really only need to install SDK and `dotnet new console` to start working with it over more complex alternatives.
Re: Summing ASCII encoded integers on Haswell at almost the speed of memcpy
#38Earlier quoted context omitted.
So SIMD would need to set the overflow flag also to catch em. Which would be much faster than the checked add (adc). Does any hardware support such checked SIMD arithmetic already? Or can you still assume that most arithmetic is still broken in most languages/libraries.
AVX-512 has evolved from the Larrabee New Instructions (2009), passing through Knights Ferry (2010), Knights Corner (2012) and Knights Landing (2016), to reach Skylake Server (2017), whose set of AVX-512 instructions has remained a subset of the instruction sets of all later CPUs with AVX-512 support. At each step from Larrabee to Skylake Server, some instructions have been lost, because the initial set of instructio…
As a minor note, overflow checking for add & sub can be done reasonably-efficiently in software by comparing the wrapping result with a saturating one, good for i8/i16/u8/u16 on x86, should be roughly the same for signed overflow compared to repurposing hardware unsigned overflow (though of course worse than would-be-native for unsigned).
And, regardless, this would be at least one more uop in the core loop (and a somewhat-unpredictable branch at that) which you'd still want to avoid.
Re: Summing ASCII encoded integers on Haswell at almost the speed of memcpy
#39First 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.
The correct solution to this optimization problem is to write the integers raw, not as ASCII.
Re: Summing ASCII encoded integers on Haswell at almost the speed of memcpy
#40Earlier quoted context omitted.
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.
As part of that Haswell brought FMA support which was a boon to those of us doing a lot of multiplication and addition (made those workloads twice as fast).
It does depend a little on what ratio of additions to multiplies you had. Haswell dropped down to one execution unit capable of floating point addition, so for addition-heavy workloads you basically had to replace half the additions with fma instructions just to keep your old performance from dropping by 2x.