A first look at WebAssembly performance

> I don't think this is a good assessment.

It's not so much an assessment as one of the main stated goals of the project. The initial point of WebAssembly is to do what asm.js does but with a smaller on-the-wire size and much less processing overhead to get from the on-the-wire format to executable code. And more cross-vendor buy-in, so the results are more reliable.

> an in-memory representation is produced (probably LLVM IR),

It's not LLVM IR in either Firefox or Chrome, fwiw. In the case of Firefox, it's the IR that Ion (the "fastest" tier of the JIT) uses. I expect this to be a pretty common approach across browsers, actually; it lets you leverage your existing code generation infrastructure.

Safari actually tried using using LLVM for this sort of thing. They stopped. See https://webkit.org/blog/5852/introducing-the-b3-jit-compiler... for details.

> This task is comparable in complexity to a JavaScript interpreter with a JIT compiler.

Not really. Once you've got the IR you just use your existing codepaths for it; the IR generation from webasm is a much simpler task than IR generation from JS, complete with runtime instrumentation and whatnot.

No...

If you use a "bonehead" data structure each memory reference will force a cache-miss, i.e. taking q CPU cycles instead of 1 CPU cycles.

If the algorithms has a running time of O(N^3), it means it is using some number of instructions Now, if each operation takes q CPU cycles instead of 1 cycles due to cache-miss on every operation, the running time of your algorithm is still bounded by q * (c * N^3) operations.

For the example with N=100 -> The fast version takes c * 1,000,000 operations to complete, for some value c. For the slow version, as each operation is now q times slower, it will take q * c * 1,000,000 operations to complete for values q and c.

I.e. it takes q times as long, not q * q * q.

What you were saying is that, if you run a O(N) algorithm on a 100 MHZ CPU, it will take 10 times as long as on a 1000 MHZ CPU, but an O(N^3) algorithm would take 1000 times as long. And that is obviously, not true. Both will take 10 times longer.

WebAssembly is tied to asm.js, which is about performance.

Integers are the worry.

the JIT being able to say "This here is an int, which means that this function takes an in and returns an int always, i'm going to compile it that way" means that now that function is "C-Speed".

If your program were filled with functions similar to that where the compiler is easily able to optimize the shit out of it, then it will run suprisingly close to "C-Speed".

Custom types (which I took to mean different data storage formats) aren't really something that the compiler can help with (any compiler). If you use a hashmap, you've got a hashmap, if you use a doubly-linked-list you've got a doubly-linked-list. C or JS iterating over an entire hashmap is going to be slower than iterating over memory addresses.

But luckily JS has stuff like TypedArrays which are basically C arrays with bounds checking.

And if you loop over it in a way that the compiler can determine you won't go out of bounds (say, with a simple for loop that runs while x So you "can" (technically, on paper) make a JS program that would run at C speeds in most cases, but at the end of the day some part of your stack is going to begin using the dynamic parts of the language, and then you get the big speed roadblocks again. (by the way, the above is basically what ASM.js is, a well curated subset of JS which doesn't allow anything dynamic so that the JIT can compile it to run at "C speeds")

The benefits of a static language aren't in what they allow, but what they don't. Tying your hands and saying "No, you can't make an array of half strings and half integers" lets the compiler be simpler and not have to worry about those "edge cases", which means that it can focus on the "fast path" more. (in practice this almost always shows up as a faster language because JITs aren't perfect, so they can get confused by code that could technically be compiled more optimally but won't because the JIT can't identify it)

It's also why adding optional static typing to a language won't make it faster on it's own (after all, the JIT already knows what types variables are at calling time, telling it that again won't solve anything...)

>Sorry, I don't quite understand the explanation...

define a

  struct S{char flag, data[63];}
  

then do

  foreach s in std::vector(big number){
    if s.flag == 0{ //set this variable to be very rarely 0
     do_something_with(s.data);
    }

this will load the entire struct into memory each iteration because loads from memory happen on cacheline granularity (i.e. 64 bytes at a time)

then the optimized version is

>And are you using the same number of instructions in both cases?

  //define S as struct of arrays now
  struct S{char* flags, (*data)[63];}
  s = initialize_S(big number);
  for(i = 0; i 

This one will load 64 flags into the L1 cache at a time. because the L1 cache is much much faster than main memory access time will be ~64x faster for the checking of the flags. Because it is rare for the loop to enter the if, this means the overal speed will be ~64x faster. As proven by the graph I posted where it is about 16x faster (because I use an int instead of a byte as flag).

Syntax is slightly different between SoA and AoS, but functionally they are the same except for how multiple S's are laid out in memory.

>And are you using the same number of instructions in both cases? >Note also: If you are moving data structures of different sizes, you are not using the same number of instructions(calculations), as the challenge required.

The same number of instructions is an arbitrary and impossible task. I'm not going to handwrite assembly for some internet points, I only do that for fun ;). Do they perform the same amount of cpu work though, yes. They are functionally the same and use the same types of instructions. That's about as good as anyone can get it. In any case, the program is completely limited by memory throughput not computation. I could make one of the inner loops a sqrt and the other a nop and the difference would be the exact same.

If you really want to see it in assembly to prove it uses the same amount of instructions, then it's just a mov rax, [rcx], cmp rax, r8, je INNER_FUNCTION, inc rcx {sizeof(S),1} depending on the method. Add 0x90 where appropriate to match instruction counts. The rest is left as an exercise to the reader.