Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A first look at WebAssembly performance

stefankrause.net

Post reply on HN
Print view View original

111–120 of 130 posts

Re: A first look at WebAssembly performance

#111

Post by Coding_Cat »

sqeaky wrote: post #99
Coding_Cat wrote: post #81

Earlier quoted context omitted.

I'll take that challenge. Here's how to do it, with a little bit of sneaky interpretation of 'memory layout': have an algorithm which takes a large struct S and looks at a subset Sf to determine what to do with S, for some value of Sf use all of S, otherwise skip it. (e.g. when distance between 2 particles Now have a very low pass-rate for the filter so that total time ~= time taken to read all of Sf. Make Sf a singl…

So you can write code that is 64x times slower when you specifically optimize for a slowdown. Cool. Can you run that in web assembly and get the same slowdown. If so most of the same things that allow C/C++ to faster than other languages on systems will also allow them to be faster in the browser.

Yeah, this will affect any language that stores structs as POD (plain old data) as long as it has somewhat sensible alignment rules and allocation (i.e. doesn't hide every struct behind a pointer, doesn't align char's to 8 bytes).

Re: A first look at WebAssembly performance

#112

Post by strainer »

rch wrote: post #79
hajile wrote: post #70

Earlier quoted context omitted.

> I, for one, hope that WebAssembly will enable, say, Lua as a first class citizen on the web. I can think of several languages I'd like to use on the web, but never really considered Lua. I'm curious. Why Lua?

Apart from general fitness for embedding and extending, I like the versatility of Lua tables: https://www.lua.org/pil/3.6.html In particular, to initialize a table to be used as a record: a = {x=0, y=0} which is equivalent to: a = {}; a.x=0; a.y=0 and: a.x = nil -- removes field "x" But I think Guido's right about 0-based indexing: http://python-history.blogspot.com/2013/10/why-python-uses-0...

local a = {x=0,y=0} --lua table definition

is very similar to

var a ={x:0,y:0} //javascript object definition

Lua is great but that 1-based indexing is very unfortunate - works fine in itself but clashes badly with the norm.

Re: A first look at WebAssembly performance

#113

Post by strainer »

wyldfire wrote: post #62
strainer wrote: post #44

Earlier quoted context omitted.

I do mean body.x[body_index], body.y[body_index], etc as: body={ x:[] ,y:[] ,z:[] ,vx:[] ,vy:[] ,vz:[] ,mass:[] } I find this is running 20% faster than the fastest on my chrome browser (an old version) but is slightly slower on firefox, but catches up a bit with 11 bodies. I expect it could run faster yet by crunching the code up more and maybe removing objects altogether, but i made few changes as possible just to…

SoA vs AoS, see also [1] [2]. [1] https://software.intel.com/sites/default/files/article/39227... [2] https://en.wikipedia.org/wiki/AOS_and_SOA

Thanks. I note a different aspect of SoA is when different functions or loops involve only a subset of the feilds, only the arrays of the involved fields are fetched. With AoS the feilds are scrunched in memory next to each other byRecord. That could benefit algorithms which only touch some of the records, however every record usually needs accessed to see whether its involved or not - the 'involving feild' would need stored separately for AoS to have any benefit.

Re: A first look at WebAssembly performance

#114

Post by strainer »

gjjrfcbugxbhf wrote: post #82
strainer wrote: post #44

Earlier quoted context omitted.

I do mean body.x[body_index], body.y[body_index], etc as: body={ x:[] ,y:[] ,z:[] ,vx:[] ,vy:[] ,vz:[] ,mass:[] } I find this is running 20% faster than the fastest on my chrome browser (an old version) but is slightly slower on firefox, but catches up a bit with 11 bodies. I expect it could run faster yet by crunching the code up more and maybe removing objects altogether, but i made few changes as possible just to…

Floating point errors accumulate quite quickly when dt is small it could be a smoothing function.

Forgive me a boast about a nbody simulation ive been developing: I got the details 60 planets and moons etc. from Nasas JPL server and put them into it. Running at a timestep of 30 minutes or hours (virtual time) for a year, the Earth ends up within a moons orbit of where JPL says its supposed to go. I think the innaccuracy is due to limitation of javascripts 64bit float (rather than, possible relativistic effect). Not sure yet, Solar system scales are so huge.

When dt is too large and bodies get too close, they get super-attracted to each other in one step, and by the time of the next step, they have travelled too far to get slowed again, this is where I see major errors can occur. Its necessary to put a throttle in the force calculation, or to reduce dt to deal with that 'near missing'. Or to substep but that seems to require excessive adjustments.

Re: A first look at WebAssembly performance

#115

Post by [deleted] »

Coding_Cat wrote: post #109
joakleaf wrote: post #104

Earlier quoted context omitted.

Sorry, I don't quite understand the explanation... Do you have some simple pseudo-code? 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.

>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…

[deleted]

Re: A first look at WebAssembly performance

#116

Post by pacaro »

joakleaf wrote: post #108
pacaro wrote: post #106

Earlier quoted context omitted.

No I'm saying that a poor choice of data structure will have an amplified impact on an O(N^3) algorithm. Giving it as an example of where you could have the different implementations of the same algorithm have massively different runtimes on the same processor.

If the algorithm has a running time of O(N^3), that implies that it takes O(N^3) If we disregard c, and set N = 100, that is 1,000,000 operations. We have two situations. 1) Either we use a good layout where each operation is fast because each memory access is from cache. 2) Or we use a bad layout where each operation is slow because we have a cache-miss and have to access the RAM. These access times are independent…

Obviously N and f are independent (although they might not be, your N may dictate how often a cache miss occurs).

Right, so now let's assume that our O(N^3) algorithm is simply a triple nested loop. And that we have an expensive operation f, but that through choice of data structures we can choose in which layer that operation occurs. All other costs are constant.

If f is in the outer loop, it happens N times, in the middle loop N^2, in the inner loop N^3.

So our choice of data structure impacts our running times by any factor from linear through cube of N.

I was simply answering the question of is it really possible to have two implementations of the same algorithm have such disparate run times, and it's trivially possible.

Another way of saying it, is that the mistake need not look expensive on cursory inspection, a simple way to have very different runtimes is through the accumulation of a large number of small costs.

Maybe the important point is to use a profiler.

I've recently gained a 60x improvement in real-world run time of what is considered in the literature to be the best known algorithm for a particular problem. The speed up didn't come from improving on the algorithm, it came from improving data locality, removing memory allocations, and general modern code hygiene (to be fair the canonical implementation is ~20 years old)

Re: A first look at WebAssembly performance

#117

Post by fulafel »

Veedrac wrote: post #47
MereInterest wrote: post #45

Earlier quoted context omitted.

As a comparison, I wrote an identical program in both C++ and JavaScript. It was doing repeated calls to a kd-tree, and was CPU-limited in both cases. The JavaScript version was slower, but only by a factor of 5-7 or so. I was rather surprised, because I was expecting a factor of 100-500, as I get with C++/CPython. I don't expect WebAssembly to improve much on the speed, because it is already pretty fast.

Javascript engines are fairly speedy compared to CPython; not only are they industrial-grade JITs (as opposed to CPython being a naive interpreter), but JS is an easier language to optimize. Further, WebAssembly has overhead. 5-7x difference seems reasonable to me.

The CPython interpreter has actually seen a lot of performance work, they've long been pushing the boundaries of interpreter optimizations that you can do portably & compatibly. I wouldn't describe it as a "naive interpreter".

Re: A first look at WebAssembly performance

#118

Post by Derbasti »

hajile wrote: post #70
Derbasti wrote: post #25

The way I understand it, WebAssembly is all about the size of the binary and parsing overhead. Or, at a higher level, about enabling a level playing field between more languages than just JavaScript. Speed improvements from a common runtime and bytecode are certainly welcome, but if they are possible with WebAssembly, they are also be possible with plain JavaScript, and therefore shouldn't be visible in a comparison…

> I, for one, hope that WebAssembly will enable, say, Lua as a first class citizen on the web. I can think of several languages I'd like to use on the web, but never really considered Lua. I'm curious. Why Lua?

Most popular dynamic programming languages are well-loved because they have huge standard libraries, which can largely not be ported to a browser sandbox. This is why I don't see how, say, Python or Ruby would be good sources of WebAssembly.

Lua, on the other hand, is a tiny language. It is remarkably well-designed, with a very simple type system, a very simple syntax, but nevertheless, Lua is extremely flexible.

I have spent a few years with Lue, and I have come to admire it, for it feels as flexible as Ruby, but at the same time more consistent than Python, and faster and simpler than either of those. And, needless to say, none of the inconsistencies of JavaScript.

Lua's stated goal is embeddability. The whole language including the parser and the standard library fit in a few hundred Kb. The bytecode only has a handful of very simple instructions. The source code is exceedingly well-structured and easy to understand.

I think Lua could be a very simple drop-in replacement for JavaScript, doing exactly the same thing that JS does today, but using a much nicer programming language. And it already comes with an object system, modules, and a string manipulation library.

I like Lua.

Re: A first look at WebAssembly performance

#119

Post by zigzigzag »

flukus wrote: post #11
foota wrote: post #9

Earlier quoted context omitted.

I think that's almost certainly false. JIT'd java is almost certainly faster than bytecode interpreted java. edit: or do you mean that the overhead of applying optimizations and profiling outweigh the performance gains relative to compiling from something like c directly to machine code?

I mean the collection and application of the optimizations take up more CPU than the optimizations remove. This isn't JIT but real time optimizations ( https://en.wikipedia.org/wiki/Adaptive_optimization ) while the system is running.

It depends a lot on things like how long the program runs for, and whether you consider spare cores on the machine to be "taking up CPU" or not.

Profile-guided optimisations win you about 20% in most industrial Java, apparently. So if you have a server that starts, warms up in say 30 seconds, and then runs for a week, you can see that it is easily profitable. For a command line app that lives for 500 msec, not so much.

Re: A first look at WebAssembly performance

#120

Post by zigzigzag »

wyldfire wrote: post #65
simooooo wrote: post #12

Am I the only one that was expecting web assembly to be like 10x JS speeds?

The promise that WASM holds IMO is for portability, not (merely) performance. How cool is it that I could write a game or application or library in C/C++/Rust/golang/swift/etc and expect it to be able to run on any modern CPU but also a browser?

I wouldn't say that's "cool", that's just what browsers could do 20 years ago with Java applets and ActiveX. Lots of languages target the JVM and you can compile C to it as well if you're willing to treat memory as a large byte array (there is a project that runs JIT-compiles LLVM bytecode on the JVM even).

The article shows that WebAssembly implementations often struggle to match Java. I see no reason to believe that browsers are actually easier to secure than a JVM, especially Firefox which doesn't even really do renderer sandboxing. They seem about the same level of difficulty. All the browser guys have done here is reinvent the same concepts of 20 years ago with a different instruction set that has "Web" in the name.

Post reply on HN