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

51–60 of 72 posts

Re: Speed Without Wizardry

#51

Post by jdright »

dbaupp wrote: post #26
DannyBee wrote: post #21

Earlier quoted context omitted.

"here are also guarantees about when objects you allocate on the heap are freed; there is no garbage collection. This is in contrast to JavaScript where objects are always allocated on the heap, and are garbage collected." Surely you realize that this, and what the author wrote, are basically the same ever rehashed GC vs non-GC language discussion. Performance characteristics of each is not anywhere near as simple as…

> I can't see anything that makes it non-conformant to build a rust compiler that dynamically allocates and places all of these on the heap, and is very non-constant time for local variable allocation. This is such a ... pointless nitpick? https://www.xkcd.com/115/ I mean sure, the language doesn't require that compilers don't emit dumb code, it is just designed so that it's easy to emit good code. Something with few…

He is a lawyer, what would you expect? Being pendandic is his job. Not that I agree with him btw. I think he just does not have enough real practical engineering experience to understand it well.

Re: Speed Without Wizardry

#53

Post by IncRnd »

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.

What you are describing now is called superpolynomial time in computer science.

Re: Speed Without Wizardry

#54

Post by imtringued »

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…

The article clearly admits that the LLVM compiler uses heuristics. You even quoted that part of the article.

>WebAssembly is designed to perform well without relying on heuristic-based optimizations, avoiding the performance cliffs that come if code doesn’t meet those heuristics. It is expected that the compiler emitting the WebAssembly (in this case rustc and LLVM) already has sophisticated optimization infrastructure, that the engine is receiving WebAssembly code that has already had optimization passes applied, and that the WebAssembly is close to its final form.

But really the point of the article is the last part.

>that the engine is receiving WebAssembly code that has already had optimization passes applied, and that the WebAssembly is close to its final form.

The compiler applies heuristics once during the compilation step and then never again. Compare this to JITs which are constantly changing and can pull the rug from under you.

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

Yes but it gets even better! If you limit yourself to a formalised subset of javascript called asm.js which gives you fine control over memory layout and allocation you can reach even the performance of C! Have you heard of it's successor? I think it's name was Web Assembly and every major browser has integrated it. It's a really cool technology that shows how sandboxed JITs can have the same performance characteristics as AOT compilers.

Re: Speed Without Wizardry

#55

Post by pcwalton »

DannyBee wrote: post #21
tmandry wrote: post #17

Earlier quoted context omitted.

To address your question about allocations, in Rust, you always know when you are allocating on the heap vs on the stack. The way you write your code guarantees it. Stack allocations are “basically free” compared to the heap because the memory management overhead is negligible or nonexistent. There are also guarantees about when objects you allocate on the heap are freed; there is no garbage collection. This is in co…

"here are also guarantees about when objects you allocate on the heap are freed; there is no garbage collection. This is in contrast to JavaScript where objects are always allocated on the heap, and are garbage collected." Surely you realize that this, and what the author wrote, are basically the same ever rehashed GC vs non-GC language discussion. Performance characteristics of each is not anywhere near as simple as…

> I want to strongly differentiate between what "one implementation of rust does" and what "the language guarantees". Because if you are going to claim it's rust that makes the guarantee, as the author did, you should be able to back the claim up.

It's perfectly reasonable to use "Rust" as a proxy for the only implementation that can be realistically deployed to the Web (rustc). Everyone knows what the author meant.

Re: Speed Without Wizardry

#56

Post by pcwalton »

jdright wrote: post #51
dbaupp wrote: post #26

Earlier quoted context omitted.

> I can't see anything that makes it non-conformant to build a rust compiler that dynamically allocates and places all of these on the heap, and is very non-constant time for local variable allocation. This is such a ... pointless nitpick? https://www.xkcd.com/115/ I mean sure, the language doesn't require that compilers don't emit dumb code, it is just designed so that it's easy to emit good code. Something with few…

He is a lawyer, what would you expect? Being pendandic is his job. Not that I agree with him btw. I think he just does not have enough real practical engineering experience to understand it well.

Daniel Berlin has way more practical engineering experience than you or I. He's a longtime GCC contributor.

(I just think in this specific instance he's wrong.)

Re: Speed Without Wizardry

#57

Post by colanderman »

dbaupp wrote: post #31
colanderman wrote: post #28

Earlier quoted context omitted.

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.

Given O(f(x)), x is almost always understood to be measurement of the work input to the algorithm. Loop nesting depth is not a measurement of work input, it's a property of the code – "1000^depth" is constant for any given algorithm.

Yes, O(…) is just a mathematical construct, so you can apply it the way you have to mean "the amount of work done for a given input size increases exponentially with respect to the number of nested loops iterating over the input"… but that's not how most people interpret it in the context of a computer algorithm. (The exception would be if the nesting depth were dynamically determined by an input parameter, but I don't think that's what anyone here is talking about.)

Anyway I'm not trying to argue, I agree with your point, but I think everyone here is talking past each other trying to say the same thing, ultimately due to imprecision in semantics.

Re: Speed Without Wizardry

#58

Post by colanderman »

yorwba wrote: post #30
colanderman wrote: post #28

Earlier quoted context omitted.

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

In this case depth is not constant, so 1000^ depth isn't either. And usually when you encounter O(some constant), it's meant as "of the order of magnitude of", i.e. somewhere between some constant/10 and some constant * 10. That isn't the definition used here, but seems to be the cause of most complaints about asymptotic analysis being misapplied when no asymptotic analysis was being done in the first place.

See my answer to the GP. `depth` – the lexical nesting depth of "for" loops in the program text – is constant with respect to any given algorithm.

Re: Speed Without Wizardry

#59

Post by lambda »

hobofan wrote: post #48

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

> I'd say that the amount of knowledge and effort required to get to such a level of optimization is similar to optimizing Javascript.

Really? After reading all of the articles in this series (the original about porting to Rust, the rebuttal about optimizing JavaScript, and this one)?

I'm more familiar with Rust than JavaScript, but I found that other than the algorithmic optimization, the rest of the JavaScript optimizations were very non-obvious in order to achieve an effect that is entirely natural in Rust.

There's no need to be careful to avoid particular types of function calls, since there are no dynamic variadic function calls in Rust. There's no need to resort to using the equivalent of `eval` for monomorphization, it's a natural feature of the language. There's no need to do manual memory management by encoding values into typed arrays of integers; you can simply allocate vectors of structs, borrow references, and so on.

These are all things that had significant cost in JS, and needed to be worked around via some intensive profiling and knowledge of how JIT engines work, but just doing things naturally in Rust leads to a pretty much zero-cost solution.

It's true that if you want to really get into the nitty-gritty of micro-optimization in Rust, you need to learn some more and do things like profiling and inspecting the generated code to see what optimizations the compiler was able to apply or not.

But the Rust rewrite of source maps did none of that; they just rewrote it in fairly idiomatic Rust, and achieved a similar speedup to what a JIT engineer armed with a profiler, a deep knowledge of what affects how well a JIT works, and a willingness to do manual memory management in typed arrays was able to do.

> 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

What parts of Rust do you feel like you don't understand the performance implications of? I feel like the mental model for performance is relatively similar to C or C++, with relatively few things that would surprise you if you're familiar with modern C++ (in fact, a lot fewer performance surprises than modern C++ offers, in addition to the extra safety).

Re: Speed Without Wizardry

#60

Post by mraleph »

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.

> completely neglected code maintainability

Where did I neglect maintainability as a factor? The only optimization that potentially affects maintainability is manually allocating Mapping-s in the typed array. And there I openly acknowledged that it affects readability and makes the code error prone. All other optimizations are not in any way affecting maintainability.

Even typed array optimization is purely confined in the library internals... On the other hand WASM spills out of the library by requiring users to explicitly destroy SourceMapConsumer.

Post reply on HN