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

21–30 of 72 posts

Re: Speed Without Wizardry

#21

Post by DannyBee »

tmandry wrote: post #17
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…

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 any of these things claim, so i'm going to leave this alone.

"EDIT: If you want to learn more about memory management in Rust, see https://doc.rust-lang.org/book/first-edition/the-stack-and-t...

Again, i see no guarantees here.

I see it saying things like "This program has one variable binding, x. This memory needs to be allocated from somewhere. Rust ‘stack allocates’ by default, which means that basic values ‘go on the stack’."

Can someone point me to an actual language level guarantee in a spec? I looked, and i don't see it.

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.

  But again, i didn't spend more than a few minutes browsing, so i may have missed it (For example, https://doc.rust-lang.org/reference/memory-allocation-and-lifetime.html says nothing here, the requirements i can find in this entire chapter can easily be met by using dynamic allocation. There are not guarantees on space or time usage that would require a real stack :P).
In fact, the vast majority of requirements here look like they could be met by a garbage collected heap/stack. It would be horribly inefficient, but ...

I'm totally willing to believe nobody has written down a good enough spec yet, just saying i don't see it ATM :)

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.

Re: Speed Without Wizardry

#22

Post by DannyBee »

acemarke wrote: post #19
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…

I think the author's primary point was that the work done by mraleph required _deep_ knowledge of the V8 JIT internals and low-level profiling to get those "3x speedup" results, plus the algorithmic improvements. Meanwhile, the original Rust implementation got the same "3x" results without having to do deep analysis of how the compiler was behaving. It also seems (based on the commentary) that the way JS/JIT engines…

"but the end users of the compiler aren't having to spend time digging through the guts of it to guess what kind of magic sequences are needed to get fairly good performance."

That's precisely my point: The claims they make about this in this article that claim to prove this are demonstrably false. So that may even be true, but it's definitely not anything in this article that shows that.

If the author had just said "hey, when i wrote this version, it performed better and was easier", that'd be great, and awesome.

Instead, it seems they wanted to make more general claims, and to be honest, don't seem to have a lot of idea what they are talking about on that front, and to anyone who does have experience in this area, like i said, it comes off very badly.

I'll also point out, if you expect to not need to do profiling and algorithmic improvement to anything to get significant speedups, that's also similarly silly. It's just not realistic for any language in the real world. The only question is "which of the code you write will this be true for" not whether it will be true.

Re: Speed Without Wizardry

#23

Post by recursive »

IncRnd wrote: post #8

> This is a factor of 4 improvement! This is a common mistake. It should read, "This is a factor of 3 improvement!" x+x+x+x is an improvement over x of 3x not of 4x. The improvement factor is 3.

It's 3x faster than, but 4x as fast as.

Re: Speed Without Wizardry

#24

Post by dbaupp »

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

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.

Re: Speed Without Wizardry

#25

Post by [deleted] »

recursive wrote: post #23
IncRnd wrote: post #8

> This is a factor of 4 improvement! This is a common mistake. It should read, "This is a factor of 3 improvement!" x+x+x+x is an improvement over x of 3x not of 4x. The improvement factor is 3.

It's 3x faster than , but 4x as fast as .

[deleted]

Re: Speed Without Wizardry

#26

Post by dbaupp »

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 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 fewer static guarantees like JS makes it much harder for compilers to emit that good code. I don't think there's any ground to contest that.

In any case, if you just replace "stack allocates" etc. with "semantically stack allocates", you get the language's guaranteed behaviour (although Rust has no ISO spec or anything, so you're probably going to say that even that isn't truly guaranteed).

Mean, it's fair that the language used is quite strong, but still, spelling literally everything out with every possible caveat is a great way to have bad pedagogy.

Re: Speed Without Wizardry

#27

Post by yorwba »

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

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 you can do it.

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. It is not generated by running a program on increasingly larger inputs, so there's nothing to be put in the exponential runtime complexity class, but it's exponential nonetheless.

Re: Speed Without Wizardry

#28

Post by colanderman »

dbaupp wrote: post #24
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.…

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

Re: Speed Without Wizardry

#29

Post by nickloewen »

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

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 will increment 125 (5^3) times
More interesting are the number of definitions and tests:

  levels    tests    defines
  1         15       1 
  2         30       6
  3         155      31
But I don't know is how the interpreter works and whether it has tricks to shrink those numbers; those just reflect my naive mental model of how things work.

Re: Speed Without Wizardry

#30

Post by yorwba »

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

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.

Post reply on HN