6 ms·

Most SIMD hardware instruction sets don't support (dynamic) vector arguments to provide the indices for shuffling, so it wouldn't be fast if SIMD.js' API had it

by sunfish 11y ago

Most SIMD hardware instruction sets don't support (dynamic) vector arguments to provide the indices for shuffling, so it wouldn't be fast if SIMD.js' API had it.

JoshTriplett 11y ago
Exactly. In general, SIMD.js intentionally implements only vector operations that translate nicely to hardware, not all potentially useful vector operations. Then, when used together with asm.js, browsers can translate it directly to hardware vector instructions.
- mtklein 11y ago
  Though, it does seem like anyTrue() and allTrue() are pretty non trivial on ARM with NEON. Those functions seem pretty geared towards x86 movemask/ptest instructions. I'd think those would have to be compound, if not serial, on ARM.
  - sunfish 11y ago
    You're right. There's enough diversity in SIMD instruction sets that no single rule seems sufficient for deciding what to include. Operations which are "fast" on all popular hardware are obviously great, but SIMD.js also includes some operations needed by popular use cases, such as allTrue() and anyTrue(). Also, while these operations are "fast" on x86 as you say, on NEON they're at least no worse than what applications would do otherwise.
    - Marat_Dukhan 11y ago
      I think SIMD.js need more operations, which may not directly map to hardware, but are "at least no worse than what applications would do otherwise": 1. The most obvious operation is multiply-accumulate, which would map to either multiply + add instructions, multiply-add instruction (with intermediate rounding), or FMA instruction. For a linear algebra (BLAS) library, it would be a one-minute fix to make use of this operation, and it would double performance on modern CPUs. 2. Another kind of operations I would like to see is load-and-deinterleave/store-and-interleave, e.g. operation which loads 12 floats of interleaved RGB data and returns 3 Float32x4 vectors with red, green, blue components. These operations map to a single instruction on ARM, and map to a nice sequence of instruction on x86 with SSSE3, and to a much longer sequence of instructions on x86 with SSE2. The best a developer can do with the current SIMD.js API is the analog of very suboptimal SSE2 code. 3. Operations which extend the type, e.g. load 4 16-bit signed integers and extend them to 4x32 vector. The optimal sequence is: - PMOVSXWD xmm, [mem] on x86 with SSE 4.1 - MOVQ xmm, [mem] + PXOR xmm2, xmm2 + PCMPGTB xmm2, xmm + PUNPCKLBW xmm, xmm2 on x86 with SSE2 - VLD1.16 dTemp, [rAddr] + VMOVL.S16 qOut, dTemp on ARMv7. The best the developer can do with SIMD.js now is SSE2 approach. If you are interested in these ideas, I have more operations in mind that would be useful.
      - sunfish 11y ago
        Thanks for the suggestions! FMA is definitely something we want to add. The question is what to do when hardware doesn't have FMA, as it's quite expensive to compute manually. Some applications would want to fall back to discrete multiply and add, but of course that rounds differently and other applications don't want implicit rounding differences between platforms. I believe the solution is to give applications a say in what happens, though the details are still being discussed. The load-and-deinterleave/store-and-interleave operations are good ideas too. They're a little more complex than we could accommodate the initial version of SIMD.js, but they're definitely things we should consider. Working with 8-bit and 16-bit data is an area where the current version of SIMD.js is fairly limited overall. Extending loads are a good idea, and in general I'm hoping a future version of SIMD.js will provide a much more complete set of operations. I'm interested in any other ideas you have as well. SIMD.js is being developed at https://github.com/tc39/ecmascript_simd https://github.com/tc39/ecmascript_simd and you're welcome to file issues to send us your ideas. Thanks!
  - dbaupp 11y ago
    Yeah, they're compound but don't have to be serial, due to the VPMIN/VPMAX instructions, but definitely much nicer on x86. For instance: int all(uint32x4_t v) { uint32x2_t x = vpmin_u32(vget_low_u32(v), vget_high_u32(v)); uint32x2_t y = vpmin_u32(x, x); return y[0] != 0; } (You can get away with a single UMINV/UMAXV on AArch64.)
mtklein 11y ago
I'd argue most SIMD hardware instruction sets do support that. x86 has had pshufb since SSSE3 (most desktop+laptop, and ~all mobile x86), providing an arbitrary byte shuffle across 16 bytes, and NEON has vtbl, pretty much the same but limited to 8 bytes of output per instruction. Now, I will admit that those instructions are not always a good idea (particularly on mobile x86, where pshufb is often several cycles), and they're essentially never a good idea when a specialized instruction (e.g. punpcklbw, vtrn) can do the job.
- ndesaulniers 11y ago
  > x86 has had pshufb since SSSE3 SIMD.js uses SSE2 as the baseline, due to NEON compatibility, though our implementer and TC39 champion, sunfish, can probably answer more in depth.
  - sunfish 11y ago
    It's not just SSE2; SIMD.js also includes things like Int32x4.mul, which is a little tricky without SSE4.1's pmulld. It's kind of a balancing act between several concerns. Also, it's a base, and we definitely plan to iterate and add more features on top of it.
- sunfish 11y ago
  For SIMD types with elements other than Int8, in addition to the pshufb, there's also the cost of computing the pshufb byte indices. For additional context, the current version of SIMD.js is aimed at covering the basics that strike some balance of being fast on most hardware and being useful. It's also just the beginning, and we expect it'll evolve to add many more features, quite likely including pshufb-like functionality.
kragen 11y ago
I guess you probably posted this as some sort of joke, but people seem to be taking you seriously, so I am going to take the bait and respond seriously. I am really at a loss as to how the current SIMD.js API for shuffles could possibly be fast, or how using vector arguments to specify the permutation would make it slower. No hardware instruction set has an instruction that takes 10 or 18 separate operands the way the SIMD.js API does. NEON has VTBL and VTBX, SSE2 doesn't have shuffling instructions at all (unless you count the rather pathetic SHUFPD, which packs two double-precision values into its output), and SSSE3 adds PSHUFB. All of them use vector arguments to provide the indices for shuffling. To compile a SIMD.Int8x16.shuffle call into an efficient PSHUFB, the compiler is going to have to figure out whether the s15:0 arguments are drawn from an existing vector and additionally that they all necessarily index into only one of the vector arguments. VTBL is more powerful, but it still needs the indices to be in a vector. So if the compiler isn't able to figure out that you were extracting the indices from a vector, it has to reconstitute that vector in order to invoke VTBL.
- sunfish 11y ago
  SIMD.js's shuffle instructions closely resemble LLVM's shuffle instructions, and LLVM also require shuffle indices to be constant, so this isn't restriction isn't unique to SIMD.js. Also, x86's shuffle situation is much more involved than your post here acknowledges; it includes shufps, shufpd, movlhps, movlhpd, movhlps, movhlpd, unpcklps, unpcklpd, unpckhps, unpckhpd, movss, movsd, and more, and all of these are effectively constant shuffle masks. I agree that there's more we can do here, and there are some interesting questions if we want to abstract over pshufb and VTBL and so on. Fortunately, SIMD.js is an evolving API and we can add things to it.
  - kragen 11y ago
    Oh, I didn't realize SIMD.js required the shuffle indices to be constant in order to generate efficient code. In that case, sure, you can generate efficient code and take advantage of the panoply of special-purpose shunting instructions you mention, and writing and reading the SIMD.js code is even going to be easier than SSE. Thank you for correcting my understanding!

by sunfish 11y ago

Most SIMD hardware instruction sets don't support (dynamic) vector arguments to provide the indices for shuffling, so it wouldn't be fast if SIMD.js' API had it.

JoshTriplett 11y ago

Exactly. In general, SIMD.js intentionally implements only vector operations that translate nicely to hardware, not all potentially useful vector operations. Then, when used together with asm.js, browsers can translate it directly to hardware vector instructions.

mtklein 11y ago
Though, it does seem like anyTrue() and allTrue() are pretty non trivial on ARM with NEON. Those functions seem pretty geared towards x86 movemask/ptest instructions. I'd think those would have to be compound, if not serial, on ARM.
- sunfish 11y ago
  You're right. There's enough diversity in SIMD instruction sets that no single rule seems sufficient for deciding what to include. Operations which are "fast" on all popular hardware are obviously great, but SIMD.js also includes some operations needed by popular use cases, such as allTrue() and anyTrue(). Also, while these operations are "fast" on x86 as you say, on NEON they're at least no worse than what applications would do otherwise.
  - Marat_Dukhan 11y ago
    I think SIMD.js need more operations, which may not directly map to hardware, but are "at least no worse than what applications would do otherwise": 1. The most obvious operation is multiply-accumulate, which would map to either multiply + add instructions, multiply-add instruction (with intermediate rounding), or FMA instruction. For a linear algebra (BLAS) library, it would be a one-minute fix to make use of this operation, and it would double performance on modern CPUs. 2. Another kind of operations I would like to see is load-and-deinterleave/store-and-interleave, e.g. operation which loads 12 floats of interleaved RGB data and returns 3 Float32x4 vectors with red, green, blue components. These operations map to a single instruction on ARM, and map to a nice sequence of instruction on x86 with SSSE3, and to a much longer sequence of instructions on x86 with SSE2. The best a developer can do with the current SIMD.js API is the analog of very suboptimal SSE2 code. 3. Operations which extend the type, e.g. load 4 16-bit signed integers and extend them to 4x32 vector. The optimal sequence is: - PMOVSXWD xmm, [mem] on x86 with SSE 4.1 - MOVQ xmm, [mem] + PXOR xmm2, xmm2 + PCMPGTB xmm2, xmm + PUNPCKLBW xmm, xmm2 on x86 with SSE2 - VLD1.16 dTemp, [rAddr] + VMOVL.S16 qOut, dTemp on ARMv7. The best the developer can do with SIMD.js now is SSE2 approach. If you are interested in these ideas, I have more operations in mind that would be useful.
    - sunfish 11y ago
      Thanks for the suggestions! FMA is definitely something we want to add. The question is what to do when hardware doesn't have FMA, as it's quite expensive to compute manually. Some applications would want to fall back to discrete multiply and add, but of course that rounds differently and other applications don't want implicit rounding differences between platforms. I believe the solution is to give applications a say in what happens, though the details are still being discussed. The load-and-deinterleave/store-and-interleave operations are good ideas too. They're a little more complex than we could accommodate the initial version of SIMD.js, but they're definitely things we should consider. Working with 8-bit and 16-bit data is an area where the current version of SIMD.js is fairly limited overall. Extending loads are a good idea, and in general I'm hoping a future version of SIMD.js will provide a much more complete set of operations. I'm interested in any other ideas you have as well. SIMD.js is being developed at https://github.com/tc39/ecmascript_simd https://github.com/tc39/ecmascript_simd and you're welcome to file issues to send us your ideas. Thanks!
- dbaupp 11y ago
  Yeah, they're compound but don't have to be serial, due to the VPMIN/VPMAX instructions, but definitely much nicer on x86. For instance: int all(uint32x4_t v) { uint32x2_t x = vpmin_u32(vget_low_u32(v), vget_high_u32(v)); uint32x2_t y = vpmin_u32(x, x); return y[0] != 0; } (You can get away with a single UMINV/UMAXV on AArch64.)

mtklein 11y ago

I'd argue most SIMD hardware instruction sets do support that. x86 has had pshufb since SSSE3 (most desktop+laptop, and ~all mobile x86), providing an arbitrary byte shuffle across 16 bytes, and NEON has vtbl, pretty much the same but limited to 8 bytes of output per instruction. Now, I will admit that those instructions are not always a good idea (particularly on mobile x86, where pshufb is often several cycles), and they're essentially never a good idea when a specialized instruction (e.g. punpcklbw, vtrn) can do the job.

ndesaulniers 11y ago
> x86 has had pshufb since SSSE3 SIMD.js uses SSE2 as the baseline, due to NEON compatibility, though our implementer and TC39 champion, sunfish, can probably answer more in depth.
- sunfish 11y ago
  It's not just SSE2; SIMD.js also includes things like Int32x4.mul, which is a little tricky without SSE4.1's pmulld. It's kind of a balancing act between several concerns. Also, it's a base, and we definitely plan to iterate and add more features on top of it.
sunfish 11y ago
For SIMD types with elements other than Int8, in addition to the pshufb, there's also the cost of computing the pshufb byte indices. For additional context, the current version of SIMD.js is aimed at covering the basics that strike some balance of being fast on most hardware and being useful. It's also just the beginning, and we expect it'll evolve to add many more features, quite likely including pshufb-like functionality.

kragen 11y ago

I guess you probably posted this as some sort of joke, but people seem to be taking you seriously, so I am going to take the bait and respond seriously. I am really at a loss as to how the current SIMD.js API for shuffles could possibly be fast, or how using vector arguments to specify the permutation would make it slower. No hardware instruction set has an instruction that takes 10 or 18 separate operands the way the SIMD.js API does. NEON has VTBL and VTBX, SSE2 doesn't have shuffling instructions at all (unless you count the rather pathetic SHUFPD, which packs two double-precision values into its output), and SSSE3 adds PSHUFB. All of them use vector arguments to provide the indices for shuffling. To compile a SIMD.Int8x16.shuffle call into an efficient PSHUFB, the compiler is going to have to figure out whether the s15:0 arguments are drawn from an existing vector and additionally that they all necessarily index into only one of the vector arguments. VTBL is more powerful, but it still needs the indices to be in a vector. So if the compiler isn't able to figure out that you were extracting the indices from a vector, it has to reconstitute that vector in order to invoke VTBL.

sunfish 11y ago
SIMD.js's shuffle instructions closely resemble LLVM's shuffle instructions, and LLVM also require shuffle indices to be constant, so this isn't restriction isn't unique to SIMD.js. Also, x86's shuffle situation is much more involved than your post here acknowledges; it includes shufps, shufpd, movlhps, movlhpd, movhlps, movhlpd, unpcklps, unpcklpd, unpckhps, unpckhpd, movss, movsd, and more, and all of these are effectively constant shuffle masks. I agree that there's more we can do here, and there are some interesting questions if we want to abstract over pshufb and VTBL and so on. Fortunately, SIMD.js is an evolving API and we can add things to it.
- kragen 11y ago
  Oh, I didn't realize SIMD.js required the shuffle indices to be constant in order to generate efficient code. In that case, sure, you can generate efficient code and take advantage of the panoply of special-purpose shunting instructions you mention, and writing and reading the SIMD.js code is even going to be easier than SSE. Thank you for correcting my understanding!