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

31–40 of 72 posts

Re: Speed Without Wizardry

#31

Post by dbaupp »

colanderman wrote: post #28
dbaupp wrote: post #24

Earlier quoted context omitted.

In this case, the number of iterations (1000) of each loop is being held fixed, and the depth of nesting is varying, i.e. the body of the inner loop executes O(1000^depth) times.

Nitpick: "O(…) times" is nonsensical. O-notation applies only to behavior in the limit. Notably, O(some constant) is exactly equivalent to O(1).

What exactly are you nitpicking?

1000^depth is not a constant: the function here is "f(depth) = number of times the inner loop body executes". f(depth) = O(1000^depth).

And, "times" here is serving the same role as "comparisons" in "Mergesort takes O(n log n) comparisons": it's referring to the thing that f is actually counting.

Re: Speed Without Wizardry

#32

Post by gpm »

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…

What you're completely missing here is that a naive rust compiler would be reasonably close in speed to LLVM's non-naive compilation. Sure some inlining helps a bit, and llvm does some really fancy things that help a bit, but even without those Rust would still be a reasonably fast language. As such you can just right normal rust, and your worst case where the compiler completely fails to help is reasonably fast.

A naive javascript interpreter is really slow, spidermoney and V8 do a ton of work to make it reasonably fast. If there's an important piece of code where the compiler doesn't even completely fail to help, but just helps less than normal, the code is no longer reasonably fast.

Re: Speed Without Wizardry

#33

Post by dbaupp »

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 is also an unhappy path there. Is that happy path wider? Maybe

I think you've got a fair point, that all optimizing compilers and JITs have happy paths and unhappy ones, falling off the happy path for either form will result in slower code. But, the happy path being wider kinda seems like the key thing here?

Additionally, AOT has consistency, in that it doesn't depend on runtime data. This can obviously leave some performance on the table if a JIT ends up optimizing for the data that happens to be used in a given session, but also means performance usually doesn't (accidentally) depend on global state.

> Instead, i have watched plenty of patches to LLVM go by to try to improve it's heuristics (oh god, there's that evil word they used above!) for removing allocations for rust

I recall some that just told LLVM the names of the symbols Rust uses instead of malloc/free, so that it could do its standard escape analysis of completely pointless (that is rarely useful for Rust, IME), but didn't actually touch the rest of LLVM.

In any case, rustc (and the current understanding of Rust as a language) doesn't insert allocations itself, because there's no reason to, unlike JS, where the allocations are essentially semantically required. That is to say, Javascript's language model is so flexible that many things have to allocate by default (as it's the only way to get the required shared-mutation behaviour), where as in Rust, heap allocation is implemented as a standard library construct (it's not necessary for the language: e.g. libcore is a bare-metal subset of the standard library that works with no dependencies) and people won't manually put things on the heap unless they have to.

> Maybe it would also surprise the author to learn that their are JITs that beat the pants off LLVM AOT for dynamic languages like javascript (they just don't happen to be integrated into web browsers).

Are you saying that a JIT for JS beats LLVM for... JS? I don't think that's particularly surprising (and probably especially not for someone who seems to have a lot of history with writing JS engines/Spidermonkey, like the author), given things like webkit's experience: https://webkit.org/blog/5852/introducing-the-b3-jit-compiler... .

Re: Speed Without Wizardry

#34

Post by whatyoucantsay »

yorwba wrote: post #27
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.…

Something can be exponential in one context and polynomial in another. Asymptotic analysis is about the growth rate of a function in terms of some input variable. The results you get depend on which values you assume to be fixed while others vary. It is usually applied to analyze the runtime of a program in terms of the input size, which is the basis of classifying the runtime complexity, but that's not the only way…

> If you have a sequence of programs with polynomial runtime, but which grows as N, N^2, N^3, N^4, ..., that's a textbook example of exponential growth

No, it isn't. N, N^2, N^3, N^4, ... is polynomial, not exponential. Exponential would be X^N. Look at the graph on the Wikipedia page I linked to.

Re: Speed Without Wizardry

#35

Post by yorwba »

whatyoucantsay wrote: post #34
yorwba wrote: post #27

Earlier quoted context omitted.

Something can be exponential in one context and polynomial in another. Asymptotic analysis is about the growth rate of a function in terms of some input variable. The results you get depend on which values you assume to be fixed while others vary. It is usually applied to analyze the runtime of a program in terms of the input size, which is the basis of classifying the runtime complexity, but that's not the only way…

> If you have a sequence of programs with polynomial runtime, but which grows as N, N^2, N^3, N^4, ..., that's a textbook example of exponential growth No, it isn't. N, N^2, N^3, N^4, ... is polynomial , not exponential. Exponential would be X^N. Look at the graph on the Wikipedia page I linked to.

Each element of the sequence is a polynomial, but the sequence of polynomials grows exponentially. X^N is exponential in N, polynomial in X. N^X is exponential in X, polynomial in N.

Re: Speed Without Wizardry

#36

Post by whatyoucantsay »

nickloewen wrote: post #29
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.…

OK I had to write things down to try and make sense of this. If anyone is like me, consider this loop that loops 5 times... maybe it will help? defines = 0 tests = 0 increments = 0 defines++ for (let i = 0; i For the sake of space I'm not going too copy nested versions of that, but imagine nesting it two and then three levels deep. 1 level will increment 5 (5^1) times 2 levels will increment 25 (5^2) times 3 levels w…

The confusion here is about math, not syntax.

N^2 is polynomial.

2^N is exponential.

https://stackoverflow.com/questions/4317414/polynomial-time-...

Re: Speed Without Wizardry

#37

Post by whatyoucantsay »

yorwba wrote: post #35
whatyoucantsay wrote: post #34

Earlier quoted context omitted.

> If you have a sequence of programs with polynomial runtime, but which grows as N, N^2, N^3, N^4, ..., that's a textbook example of exponential growth No, it isn't. N, N^2, N^3, N^4, ... is polynomial , not exponential. Exponential would be X^N. Look at the graph on the Wikipedia page I linked to.

Each element of the sequence is a polynomial, but the sequence of polynomials grows exponentially. X^N is exponential in N, polynomial in X. N^X is exponential in X, polynomial in N.

> Each element of the sequence is a polynomial, but the sequence of polynomials grows exponentially.

Bringing this back to the original comment about nesting loops, perhaps what you're describing is some sort of metaprogramming that dynamically generates increasingly deeply nested loops based upon the size of the input. If someone were to write that program then yes, it would be exponential.

In the far more common case of a programmer nesting a few loops, the resulting run-time would be polynomial, not exponential.

Re: Speed Without Wizardry

#38

Post by kazagistar »

whatyoucantsay wrote: post #16
yorwba wrote: post #14

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.

> "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.

Re: Speed Without Wizardry

#39

Post by nickm12 »

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.

Re: Speed Without Wizardry

#40

Post by wwwigham »

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, since focusing on that would invite that charged discussion. As a polyglot developer, I welcome all the mixing of the languages that wasm is bringing (certainly, it makes my flexible skillset more valuable); but honestly I do think we're leaving _something_ of the past homogeneity behind in doing so. (Was FFI quality all that was stopping us from mixing tons of languages in our non-browser projects before?)

Circling back; both authors have their biases - it's best to read both articles skeptically, and IMO, take away the sage bits of advice they both echo and not anything about a specific technology: You should make the right choices for your project and your design, performance, and maintenance needs (including making your own evaluations), rather than jumping on some bandwagon without being properly informed. Also that profile-guided algorithmic improvements are usually the easiest place to make sweet, sweet perf gains (in any language) before you have to get into hairy maintainability trade-off decisions.

Post reply on HN