Re: [webkit-dev] SIMD support in JavaScript

[Nadav Rotem]

Hi Dan!

> On Sep 28, 2014, at 6:44 AM, Dan Gohman  wrote:
> 
> Hi Nadav,
> 
> I agree with much of your assessment of the the proposed SIMD.js API.
> However, I don't believe it's unsuitability for some problems
> invalidates it for solving other very important problems, which it is
> well suited for. Performance portability is actually one of SIMD.js'
> biggest strengths: it's not the kind of performance portability that
> aims for a consistent percentage of peak on every machine (which, as you
> note, of course an explicit 128-bit SIMD API won't achieve), it's the
> kind of performance portability that achieves predictable performance
> and minimizes surprises across machines (though yes, there are some
> unavoidable ones, but overall the picture is quite good).

There is a tradeoff between the performance portability of the SIMD.js ISA and 
its usefulness. A small number of instructions (that only targets 32bit data 
types, no masks, etc) is not useful for developing non-trivial vector programs. 
You need 16bit vector elements to support WebGL vertex indices, and 
lane-masking for implementing predicated control flow for programs like ray 
tracers. Introducing a large number of vector instructions will expose the 
performance portability problems. I don’t believe that there is a sweet spot in 
this tradeoff. I don’t think that we can find a small set of instructions that 
will be useful for writing non-trivial vector code that is performance portable.

> 
> On 09/26/2014 03:16 PM, Nadav Rotem wrote:
>> So far, I’ve explained why I believe SIMD.js will not be
>> performance-portable and why it will not utilize modern instruction
>> sets, but I have not made a suggestion on how to use vector
>> instructions to accelerate JavaScript programs. Vectorization, like
>> instruction scheduling and register allocation, is a code-generation
>> problem. In order to solve these problems, it is necessary for the
>> compiler to have intimate knowledge of the architecture. Forcing the
>> compiler to use a specific instruction or a specific data-type is the
>> wrong answer. We can learn a lesson from the design of compilers for
>> data-parallel languages. GPU programs (shaders and compute languages,
>> such as OpenCL and GLSL) are written using vector instructions because
>> the domain of the problem requires vectors (colors and coordinates).
>> One of the first thing that data-parallel compilers do is to break
>> vector instructions into scalars (this process is called
>> scalarization). After getting rid of the vectors that resulted from
>> the problem domain, the compiler may begin to analyze the program,
>> calculate profitability, and make use of the available instruction set.
> 
>> I believe that it is the responsibility of JIT compilers to use vector
>> instructions. In the implementation of the Webkit’s FTL JIT compiler,
>> we took one step in the direction of using vector instructions. LLVM
>> already vectorizes some code sequences during instruction selection,
>> and we started investigating the use of LLVM’s Loop and SLP
>> vectorizers. We found that despite nice performance gains on a number
>> of workloads, we experienced some performance regressions on Intel’s
>> Sandybridge processors, which is currently a very popular desktop
>> processor. JavaScript code contains many branches (due to dynamic
>> speculation). Unfortunately, branches on Sandybridge execute on Port5,
>> which is also where many vector instructions are executed. So,
>> pressure on Port5 prevented performance gains. The LLVM vectorizer
>> currently does not model execution port pressure and we had to disable
>> vectorization in FTL. In the future, we intend to enable more
>> vectorization features in FTL.
> 
> This is an example of a weakness of depending on automatic vectorization
> alone. High-level language features create complications which can lead
> to surprising performance problems. Compiler transformations to target
> specialized hardware features often have widely varying applicability.
> Expensive analyses can sometimes enable more and better vectorization,
> but when a compiler has to do an expensive complex analysis in order to
> optimize, it's unlikely that a programmer can count on other compilers
> doing the exact same analysis and optimizing in all the same cases. This
> is a problem we already face in many areas of compilers, but it's more
> pronounced with vectorization than many other optimizations.

I agree with this argument. Compiler optimizations are unpredictable. You never 
know when the register allocator will decide to spill a variable inside a hot 
loop.  or a memory operation confuse the alias an

[webkit-dev] SIMD support in JavaScript

[Nadav Rotem]

Recently members of the JavaScript community at Intel and Mozilla have 
suggested  adding SIMD types to the 
JavaScript language. In this email would like to share my thoughts about this 
proposal and to start a technical discussion about SIMD.js support in Webkit. I 
BCCed some of the authors of the proposal to allow them to participate in this 
discussion. 

Modern processors feature SIMD (Single Instruction Multiple Data) 
 instructions, which perform the same 
arithmetic operation on a vector of elements. SIMD instructions are used to 
accelerate compute intensive code, like image processing algorithms, because 
the same calculation is applied to every pixel in the image. A single SIMD 
instruction can process 4 or 8 pixels at the same time. Compilers try to make 
use of SIMD instructions in an optimization that is called vectorization. 

The SIMD.js API  
adds new types, such as float32x4, and operators that map to vector 
instructions on most processors. The idea behind the proposal is that manual 
use of vector instructions, just like intrinsics in C, will allow developers to 
accelerate common compute-intensive JavaScript applications. The idea of using 
SIMD instructions to accelerate JavaScript code is compelling because high 
performance applications in JavaScript are becoming very popular. 

Before I became involved with JavaScript through my work on the FTL project 
, I developed 
the LLVM vectorizer  and worked on a 
vectorizing compiler for a data-parallel programming language. Based on my 
experience with vectorization, I believe that the current proposal to include 
SIMD types in the JavaScript language is not the right approach to utilize SIMD 
instructions. In this email I argue that vector types should not be added to 
the JavaScript language.

Vector instruction sets are sparse, asymmetrical, and vary in size and features 
from one generation to another. For example, some Intel processors feature 
512-bit wide vector instructions 
. This means 
that they can process 16 floating point numbers with one instruction. However, 
today’s high-end ARM processors feature 128-bit wide vector instructions 
 and can only 
process 4 floating point elements. ARM processors support byte-sized blend 
instructions but only recent Intel processors added support for byte-sized 
blends. ARM processors support variable shifts but only Intel processors with 
AVX2 support variable shifts. Different generations of Intel processors support 
different instruction sets with different features such as broadcasting from a 
local register, 16-bit and 64-bit arithmetic, and varied shuffles. Modern 
processors even feature predicated arithmetic and scatter/gather instructions 
that are very difficult to model using target independent high-level 
intrinsics. 
The designers of the high-level target independent API should decide if they 
want to support the union of all vector instruction sets, or the intersection. 
A subset of the vector instructions that represent the intersection of all 
popular instruction sets is not useable for writing non-trivial vector 
programs. And the superset of the vector instructions will cause huge 
performance regressions on platforms that do not support the used instructions.

Code that uses SIMD.js is not performance-portable. Modern vectorizing 
compilers feature complex cost models and heuristics for deciding when to 
vectorize, at which vector width, and how many loop iterations to interleave. 
The cost models takes into account the features of the vector instruction set, 
properties of the architecture such as the number of vector registers, and 
properties of the current processor generation. Making a poor selection 
decision on any of the vectorization parameters can result in a major 
performance regression. Executing vector intrinsics on processors that don’t 
support them is slower than executing multiple scalar instructions because the 
compiler can’t always generate efficient with the same semantics.
I don’t believe that it is possible to write non-trivial vector code that will 
show performance gains on processors from different families. Executing vector 
code with insufficient hardware support will cause major performance 
regressions. One of the motivations for SIMD.js was to allow Emscripten 
 to 
vectorize C code and to emit JavaScript SIMD intrinsics. One problem with this 
suggestion is that the Emscripten compiler should not be assuming that the 
target is an x86 machine and that a specific vector width and interleave width 
is the