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

Speed Without Wizardry

fitzgeraldnick.com

Post reply on HN
Print view View original

41–50 of 72 posts

Re: Speed Without Wizardry

#41

Post by AstralStorm »

kazagistar wrote: post #38
whatyoucantsay wrote: post #16

Earlier quoted context omitted.

> "It is exponential in the number of nested loops, which is what's important for the realization that adding more nested loops is bad." Adding more nested loops is bad, but it's not exponential. It's polynomial. As you nest more and more loops, the big O complexity goes from N to N^2 (quadratic) to N^3 (cubic) to N^4, etc... N^(any number) is polynomial. Exponential would be 2^N or 3^N or any number raised to the N.…

If N is the number of nested loops, and M is the number of times through the loop, then it is indeed a O(M^N). So indeed, complexity scales exponentially with the level of nesting. The wording was just off amd confusing due to it being a nontraditonal formulation of the problem, but what he was saying does actually make sense.

You will probably blow up stack on counters or iterators way before you reach even close to 2^N behaviour.

Re: Speed Without Wizardry

#42

Post by AstralStorm »

wwwigham wrote: post #40
nickm12 wrote: post #39

I've got to admire the graciousness in this response. It's making the point that mraleph's “Maybe you don’t need Rust and WASM to speed up your JS” article completely neglected code maintainability as a factor, but it does so without turning the whole thing into a pissing match. It's all been a fascinating to read.

It's also probably not worth overtly begging the question of weather maintaining multiple languages within one project is worth the burden (seriously the full build for the `source-map` package is complex in comparison to the usual JS state of affairs if you want to experiment with the now-Rust bits), especially considering that at least part of the reason node became popular was to have one language for all needs, s…

Unfortunately, JS does not lend itself to ease of maintenance - it is bad that it became language for the web browsers.

You get dynamic weak typing making reuse more complex, unpredictable (nonlinear in performance with coffee changes) GC and JIT, weird type system. No error handling facilities in the language either.

Heck, compared to JS even modern Java (which shares the GC and JIT unpredictability) or C++ (incl. arcane syntax and less safety if you like living dangerously) seem easy to achieve predictable results with.

Rust takes more work you front - but not that much more.

Re: Speed Without Wizardry

#43

Post by vanillaboy »

AstralStorm wrote: post #42
wwwigham wrote: post #40

Earlier quoted context omitted.

It's also probably not worth overtly begging the question of weather maintaining multiple languages within one project is worth the burden (seriously the full build for the `source-map` package is complex in comparison to the usual JS state of affairs if you want to experiment with the now-Rust bits), especially considering that at least part of the reason node became popular was to have one language for all needs, s…

Unfortunately, JS does not lend itself to ease of maintenance - it is bad that it became language for the web browsers. You get dynamic weak typing making reuse more complex, unpredictable (nonlinear in performance with coffee changes) GC and JIT, weird type system. No error handling facilities in the language either. Heck, compared to JS even modern Java (which shares the GC and JIT unpredictability) or C++ (incl. a…

Only if you're bad at writing organized code in the first place. Which isn't a problem with JS itself.

Re: Speed Without Wizardry

#44

Post by maaark »

titzer wrote: post #7
austincheney wrote: post #4

Earlier quoted context omitted.

The two expressions are equivalent. V8 cannot compile that logic into optimized bytecode due to a violation in its code engine that conflicts with other optimization logic. So instead of fast compiled code the code in the local scope of that expression is slow string interpreted code. https://github.com/vhf/v8-bailout-reasons

That list is for CrankShaft which has been replaced by TurboFan > 6 months ago. If you continue to experience slowdowns please file a bug and it can be investigated.

There's an automotive engineer somewhere reading this, irrationally upset at the idea of replacing a crankshaft with a turbofan.

Re: Speed Without Wizardry

#45

Post by littlestymaar »

DannyBee wrote: post #13

I really don't understand this article, and the claims really rub me the wrong way. The main point it makes is, again "He perfectly demonstrates one of the points my “Oxidizing” article was making: with Rust and WebAssembly we have reliable performance without the wizard-level shenanigans that are required to get the same performance in JavaScript." This doesn't make a lot of sense as a claim. Why? Because underneath…

Allocation in Rust are opt-in, you allocate when using the `Box` keyword, when using reference-counted pointers or when using a heap-allocated data structure (vector, hashmap, etc.). If you do neither of those, you have zero heap allocation, 100% of the time, there is no heuristic involved here.

For optimizations, you're right : LLVM uses a lot of heuristic. But this happens at compile time, when you generate your webassembly blob. When you have it, it will run at a consistent speed across browsers and between several generations of the same browsers. None of this is achievable in plain JavaScript, where JS optimized for old V8 (crankshaft) won't be optimal for SpiderMonkey or newer version of V8 (Turbofan).

Re: Speed Without Wizardry

#46

Post by austincheney »

tachyoff wrote: post #20
austincheney wrote: post #10

Earlier quoted context omitted.

Before I begin just let me say I am not a mathematician. I program so that I don't have to do complex math. I know in reality the frequency of iterations varies considerably but for simplicity of discussion let's remove variability. Say we have a loop with 1000 iterations. That is at minimum 1000 statements in the loop body plus expression overhead from the loop itself. If this loop is nested once with a same sized l…

I wouldn’t call time complexity particularly complex math. Imagine a loop. It does something n times. Within that loop, you do something n times. For each outer looo through n,you do an inner loop through n. Trivially, this is n*n, or n^2, also known as quadratic time. If you nest another loop, it becomes n^3, or cubic time. Anyway, there might be some confusion of terms, perhaps. Exponential time in the algorithmic…

I am sooo not a math person.

Let's not forget there is overhead to loops. At a minimum let's assume there is a single statement in the loop body, an increment statement and a terminal condition. In a single loop of 1000 iterations there are 3000 things to evaluate. The math becomes:

(n * 3)^x

If a simple loop is nested twice (3 depths) there would be 1 billion iterations but about 27 billion evaluations. Would it be correct to say that is just slightly faster polynomial growth?

Re: Speed Without Wizardry

#47

Post by tedmielczarek »

DannyBee wrote: post #13

I really don't understand this article, and the claims really rub me the wrong way. The main point it makes is, again "He perfectly demonstrates one of the points my “Oxidizing” article was making: with Rust and WebAssembly we have reliable performance without the wizard-level shenanigans that are required to get the same performance in JavaScript." This doesn't make a lot of sense as a claim. Why? Because underneath…

> Why? Because underneath all that rust .... is an optimizing compiler, and it happens the author has decided to stay on the happy path of that.

There are two big differences here: 1) You're comparing "staying on the happy path" of a JIT compiler in the JS case, vs. an optimizing compiler in the Rust case. With the latter you can just compile your code and see what comes out and it tends to be fairly predictable. With the former, I'm not even sure there are tools to inspect the generated JIT code, and you're constantly walking the line of JS engines changing their heuristics and throwing you off the fast path. This was one of the primary motivations for the asm.js/WebAssembly work: the ability to get predictable performance.

2) Many of the optimizations mraleph performed were tricks to avoid allocation (which is normal optimization stuff, but more of a pain in GCed languages). In JS he winds up having to effectively write C-in-JS which looks pretty hairy. In Rust controlling allocation is a built-in language feature, so you can write very idiomatic code without heap allocation.

Re: Speed Without Wizardry

#48

Post by hobofan »

> But a distinction between JavaScript and Rust+WebAssembly emerges when we consider the effort required to attain inlining and monomorphization, or to avoid allocations.

I'm not sure that is true. Having worked/interacted with a lot of people working with Rust on different experience levels, most of them (that includes me) don't have a deep knowledge of what Rust concept maps to a specific concept with which performance implications. And if they do it's often only partial. I'd say that right now, only very few people that don't work on the Rust compiler have a broad knowledge in that area. Sure, it's much better to have to Result of the optimization expressed in code itself, but I'd say that the amount of knowledge and effort required to get to such a level of optimization is similar to optimizing Javascript.

I also found the hint to `#[inline]` suggestions, a bit disingenuous. In the end they are just _suggestions_, and your are just as much at the mercy of the Rust/LLVM optimizer to accept them, as you are with a Javascript JIT.

I'm a big fan of Rust, and I'm a big fan of Rust+Webassembly (working with it is the most fun I had programming in a long time!). Generally I think that Rust has one of the better performance optimzation stories, I just don't a gree with some of the sentiments in the post. There are also enough other reasons to love Rust+WebAssembly than just the peformance!

Re: Speed Without Wizardry

#49

Post by hobofan »

tedmielczarek wrote: post #47
DannyBee wrote: post #13

I really don't understand this article, and the claims really rub me the wrong way. The main point it makes is, again "He perfectly demonstrates one of the points my “Oxidizing” article was making: with Rust and WebAssembly we have reliable performance without the wizard-level shenanigans that are required to get the same performance in JavaScript." This doesn't make a lot of sense as a claim. Why? Because underneath…

> Why? Because underneath all that rust .... is an optimizing compiler, and it happens the author has decided to stay on the happy path of that. There are two big differences here: 1) You're comparing "staying on the happy path" of a JIT compiler in the JS case, vs. an optimizing compiler in the Rust case. With the latter you can just compile your code and see what comes out and it tends to be fairly predictable. Wit…

> what comes out and it tends to be fairly predictable

Predictable as long as you stay on the same version of the compiler (yes, I know that there are crater runs to prevent regressions). Also, how does much can/does the output for different target architetures differ in performance? Couldn't that be likened to trying to optimize for multiple JS engines?

Re: Speed Without Wizardry

#50

Post by simonbw »

whatyoucantsay wrote: post #6
austincheney wrote: post #2

The simple rule I have found for achieving superior performance in high level languages, particularly JavaScript is to simply do less . It isn't that simple though. Doing less really means less code totally at the current compilation target, essentially feeding fewer total instructions to the compiler. This means no frameworks and minimal abstractions. It means having a clear appreciation for the APIs you are writing…

> "It means minimizing use of nested loops, which exponentially increase statement count." Nesting two loops has an n^2 cost and nesting 3 levels deep costs n^3. At no point does it ever cost 2^n or any x^n. It's polynomial, not exponential.

> At no point does it ever cost 2^n or any x^n.

That's only true if your n is referring to the number of iterations of each loop. If your n instead refers to the number of nested loops, you will indeed get a runtime of O(2^n).

Seeing as in this context we were talking about varying the number of nested loops, it makes sense that we would define our variable n = number of nested loops.

Post reply on HN