6 ms·

Why those particular integer multiplies?

75 points by luu 2y ago

NooneAtAll3 2y ago
> PMADDUBSW produces a word result which, in turns out, does not quite work. The problem is that multiplying unsigned by signed bytes means the individual product terms are in range [-128*255, 128*255] = [-32640,32640]. Our result is supposed to be a signed word, which means its value range is [-32768,32767]. If the two individual products are either near the negative or positive end of the possible output range, the sum overflows. can someone explain this to me? isn't 32640 < 32767? how's this an overflow?
- anonymoushn 2y ago
  The output of the instruction is, for each 16-bit lane, the sum of two products of one i8 and one u8. 32640 * 2 > 32767 As an aside, the quoted section of the article seems to have an error. The maximum value of an i8 is 127 and the maximum value of one of these products is 32385.
wruza 2y ago
Maybe it’s me in the morning, but for some reason it was a very hard read for the text about cpu instructions. Feels like it loads you with details for ages.
- flohofwoe 2y ago
  New to ryg blog posts? :)
  - wruza 2y ago
    Not sure what was so wrong with that or why people like it so much, but yeah.
TekMol 2y ago
How can software run on different CPUs when they support different operations? When you download "debian-live-12.7.0-amd64-kde.iso", all the programs in the repos support all current Intel and AMD CPUs, right? Do they just target the lowest common denominator of operations? Or do they somehow adapt to the operations supported by the user's CPU? Do dynamic languages (Javascript, Python, PHP...) get a speed boost because they can compile just in time and use all the features of the user's CPU?
- theresistor 2y ago
  > Do they just target the lowest common denominator of operations? Or do they somehow adapt to the operations supported by the user's CPU? Mostly the former. Some highly optimized bits of software do the latter—they are built with multiple code paths optimized for different hardware capabilities, and select which one to use at runtime. > Do dynamic languages (Javascript, Python, PHP...) get a speed boost because they can compile just in time and use all the features of the user's CPU? Hypothetically yes, but in practice no for the languages you mentioned because they don't map well to things like SIMD. Some JIT-based numerical computing systems as well as JIT-based ML compilers do reap those benefits.
  - jsheard 2y ago
    .NET/C# does pretty well with SIMD for a high level language, it has portable SIMD primitives which get JITed to whatever the system supports at runtime, and they're used quite extensively throughout the stdlib so you benefit even if you're not writing SIMD routines yourself. They tried to do something similar in Javascript but it added way too much complexity to the runtimes and ended up getting dropped in favor of WASM SIMD.
  - twic 2y ago
    It's possibly worth mentioning that Java is getting a vector API which explicitly abstracts over some of the details of SIMD, including width. You have a type Vector<T> which represents enough of some type T to fill a vector register (eg eight 32-bit numbers in a 256-bit register), operations on Vector<T> which produce another Vector<T>, and some way to break arrays up into Vectors of the right size for the platform. The API is a bit clunky, but you write code with it, the compiler performs a miracle, and efficient platform-specific vector code comes out. https://docs.oracle.com/en/java/javase/23/docs/api/jdk.incubator.vector/jdk/incubator/vector/package-summary.html https://docs.oracle.com/en/java/javase/23/docs/api/jdk.incub... https://docs.oracle.com/en/java/javase/23/docs/api/jdk.incubator.vector/jdk/incubator/vector/Vector.html https://docs.oracle.com/en/java/javase/23/docs/api/jdk.incub...
Const-me 2y ago
Found a bug in the article. Maximum for signed bytes is +127, not +128. Minimum is correct, it's -128.
- Jerrrrrrry 2y ago
  You can always tell when someone counts on their fingers.
- pornel 2y ago
  BTW, this asymmetry makes unary negation in C an unexpected source of Undefined Behavior.
RaisingSpear 2y ago
I suspect Intel uses 32x32b multipliers instead of his theorised 16x16b, just that it only has one every second lane. It lines up more closely with VPMULLQ, and it seems odd that PMULUDQ would be one uOp vs PMULLD's two. PMULLD is probably just doing 2x PMULUDQ and discarding the high bits. (I tried commenting on his blog but it's awaiting moderation - I don't know if that's ever checked, or just sits in the queue forever)
- anonymoushn 2y ago
  Makes sense to me. I have some code that uses a lot of mullo, so I get to pay twice the latency compared to if I wanted full multiplies...
secondcoming 2y ago
It's a shame that SIMD is still a dark art. I've looked at writing a few simple algorithms with it but have to do it in my own time as it'll be difficult to justify it with my employer. I do know that gcc is generally terrible at auto-vectorising code, clang is much better but far from perfect. Using intrinsics directly will just lead to code that's unmaintainable by others not versed in the dark art. Even wrappers over intrinsics don't help much here. I feel there's a lot of efficiency being left on the table because these instructions aren't being used more.
- Sesse__ 2y ago
  The problem is that the different SIMD instruction sets are genuinely... different. The basics of “8-bit unsigned add” and similar are possible to abstract over, but for a lot of cases, you may have to switch your entire algorithm around between different CPUs to get reasonable performance (or even gain over the scalar code at all). There's no way a compiler or SIMD abstraction library will do that for you.
- Miniminix 2y ago
  Re: SIMD Suggest you look at the Julia Language, a high-level but still capable of C-like speed. It has built in support for SIMD (and GPU) processing. Julia is designed to support Scientific Computing, with a growing library spanning different domains. https://docs.julialang.org/en/v1/ https://docs.julialang.org/en/v1/
- deleted 2y ago
  [deleted]

75 points by luu 2y ago

> PMADDUBSW produces a word result which, in turns out, does not quite work. The problem is that multiplying unsigned by signed bytes means the individual product terms are in range [-128*255, 128*255] = [-32640,32640]. Our result is supposed to be a signed word, which means its value range is [-32768,32767]. If the two individual products are either near the negative or positive end of the possible output range, the sum overflows. can someone explain this to me? isn't 32640 < 32767? how's this an overflow?

anonymoushn 2y ago
The output of the instruction is, for each 16-bit lane, the sum of two products of one i8 and one u8. 32640 * 2 > 32767 As an aside, the quoted section of the article seems to have an error. The maximum value of an i8 is 127 and the maximum value of one of these products is 32385.

wruza 2y ago

Maybe it’s me in the morning, but for some reason it was a very hard read for the text about cpu instructions. Feels like it loads you with details for ages.

flohofwoe 2y ago
New to ryg blog posts? :)
- wruza 2y ago
  Not sure what was so wrong with that or why people like it so much, but yeah.

TekMol 2y ago

How can software run on different CPUs when they support different operations? When you download "debian-live-12.7.0-amd64-kde.iso", all the programs in the repos support all current Intel and AMD CPUs, right? Do they just target the lowest common denominator of operations? Or do they somehow adapt to the operations supported by the user's CPU? Do dynamic languages (Javascript, Python, PHP...) get a speed boost because they can compile just in time and use all the features of the user's CPU?

theresistor 2y ago
> Do they just target the lowest common denominator of operations? Or do they somehow adapt to the operations supported by the user's CPU? Mostly the former. Some highly optimized bits of software do the latter—they are built with multiple code paths optimized for different hardware capabilities, and select which one to use at runtime. > Do dynamic languages (Javascript, Python, PHP...) get a speed boost because they can compile just in time and use all the features of the user's CPU? Hypothetically yes, but in practice no for the languages you mentioned because they don't map well to things like SIMD. Some JIT-based numerical computing systems as well as JIT-based ML compilers do reap those benefits.
- jsheard 2y ago
  .NET/C# does pretty well with SIMD for a high level language, it has portable SIMD primitives which get JITed to whatever the system supports at runtime, and they're used quite extensively throughout the stdlib so you benefit even if you're not writing SIMD routines yourself. They tried to do something similar in Javascript but it added way too much complexity to the runtimes and ended up getting dropped in favor of WASM SIMD.
- twic 2y ago
  It's possibly worth mentioning that Java is getting a vector API which explicitly abstracts over some of the details of SIMD, including width. You have a type Vector<T> which represents enough of some type T to fill a vector register (eg eight 32-bit numbers in a 256-bit register), operations on Vector<T> which produce another Vector<T>, and some way to break arrays up into Vectors of the right size for the platform. The API is a bit clunky, but you write code with it, the compiler performs a miracle, and efficient platform-specific vector code comes out. https://docs.oracle.com/en/java/javase/23/docs/api/jdk.incubator.vector/jdk/incubator/vector/package-summary.html https://docs.oracle.com/en/java/javase/23/docs/api/jdk.incub... https://docs.oracle.com/en/java/javase/23/docs/api/jdk.incubator.vector/jdk/incubator/vector/Vector.html https://docs.oracle.com/en/java/javase/23/docs/api/jdk.incub...

Const-me 2y ago

Found a bug in the article. Maximum for signed bytes is +127, not +128. Minimum is correct, it's -128.

Jerrrrrrry 2y ago
You can always tell when someone counts on their fingers.
pornel 2y ago
BTW, this asymmetry makes unary negation in C an unexpected source of Undefined Behavior.

RaisingSpear 2y ago

I suspect Intel uses 32x32b multipliers instead of his theorised 16x16b, just that it only has one every second lane. It lines up more closely with VPMULLQ, and it seems odd that PMULUDQ would be one uOp vs PMULLD's two. PMULLD is probably just doing 2x PMULUDQ and discarding the high bits. (I tried commenting on his blog but it's awaiting moderation - I don't know if that's ever checked, or just sits in the queue forever)

anonymoushn 2y ago
Makes sense to me. I have some code that uses a lot of mullo, so I get to pay twice the latency compared to if I wanted full multiplies...

secondcoming 2y ago

It's a shame that SIMD is still a dark art. I've looked at writing a few simple algorithms with it but have to do it in my own time as it'll be difficult to justify it with my employer. I do know that gcc is generally terrible at auto-vectorising code, clang is much better but far from perfect. Using intrinsics directly will just lead to code that's unmaintainable by others not versed in the dark art. Even wrappers over intrinsics don't help much here. I feel there's a lot of efficiency being left on the table because these instructions aren't being used more.

Sesse__ 2y ago
The problem is that the different SIMD instruction sets are genuinely... different. The basics of “8-bit unsigned add” and similar are possible to abstract over, but for a lot of cases, you may have to switch your entire algorithm around between different CPUs to get reasonable performance (or even gain over the scalar code at all). There's no way a compiler or SIMD abstraction library will do that for you.
Miniminix 2y ago
Re: SIMD Suggest you look at the Julia Language, a high-level but still capable of C-like speed. It has built in support for SIMD (and GPU) processing. Julia is designed to support Scientific Computing, with a growing library spanning different domains. https://docs.julialang.org/en/v1/ https://docs.julialang.org/en/v1/
deleted 2y ago
[deleted]