4 ms·

> There's a pair of `if`s that if I swap their order, that part of the code allocates. How do people deal with these issues? A large fraction of this code is st

> There's a pair of `if`s that if I swap their order, that part of the code allocates. How do people deal with these issues? A large fraction of this code is still allocating, and I haven't a clue where or why. Are you sure that allocation is a problem? Nursery allocation is extremely fast: it's just one overflow check and a pointer bump. Usually it's around 3-6 instructions. Allocation in modern generational GCs is in a completely different performance category than C-style malloc is.

vanderZwan 9y ago
Not GP, but as someone who has worked with image manipulation and typed arrays in JS (which seems similar to what the GP was doing) I can say that this often boils down to linearly looping through a typed array and doing very simple operations. You know, one of those "best case" scenarios for cpu utilisation where memory access tends to be the bottleneck. If the allocation happens inside a tight loop like that I can imagine it ruining performance
Veedrac 9y ago
Pointer-bump allocations are fast in isolation, but if your code is doing one it means the compiler has gotten itself confused, and every time it gets confused it makes it harder for later code to be optimized. Compilers only really reason reasonably about value types (and even then you should never assume they're smart[1]). That said, I don't actually know allocation is the problem; it's a suspect, but unlike a native script I can't just run `perf` to get performance counters and assembly listings. All I really know is that the non-allocating order is a lot faster. [1]: If you can read assembly, this one's hilarious: https://godbolt.org/g/81qWoq https://godbolt.org/g/81qWoq
- pjmlp 9y ago
  You can at least use the browser profiler tools.
  - Veedrac 9y ago
    I do! It's missing a lot of detail, though; it's optimized much more for overall performance analysis.
  - fenomas 9y ago
    Browser profiling tools are great but their granularity stops at the function level - they can't tell you anything about what happens within a given function, just how that function compares to others.
    - pjmlp 9y ago
      I haven't used them much, specially since I tend to choose native projects if possible. Thanks for the heads up.
- foldr 9y ago
  >[1]: If you can read assembly, this one's hilarious: https://godbolt.org/g/81qWoq https://godbolt.org/g/81qWoq I only barely read assembly, so I was just trying to figure this one out. So, the compiler has figured out that it just needs to test v against 0 (since the array is immutable), but it does this 2 times, and with a couple of apparently redundant 'je' instructions. Is that what's weird about the output? In case it changed, this is the output I saw: example::exists_in_table: push rbp mov rbp, rsp mov al, 1 test edi, edi je .LBB0_5 je .LBB0_5 test edi, edi je .LBB0_5 je .LBB0_5 xor eax, eax .LBB0_5: pop rbp ret
  - Veedrac 9y ago
    Basically, yes. The first test and je show the compiler has managed the hard part, but the next je obviously can't be hit, the test after that literally doesn't do anything, and the two jumps after that also can't be hit. It's funny because this is all so trivial. If I write it as some C bool should_jump = edi == 0; if (should_jump) goto LBB0_5; if (should_jump) goto LBB0_5; bool should_jump = edi == 0; if (should_jump) goto LBB0_5; if (should_jump) goto LBB0_5; I can guarantee the compiler is going to produce good code from it.
- eddyb 9y ago
  This looks like yet-another-phase-ordering-issue in LLVM. I hit so many of these it's not even funny. Arguably one could find C code that shows the exact problem under clang. Example of optimized LLVM IR for that sample (press LLVM IR on https://play.rust-lang.org/?gist=b60ec85886eff967b21c7abc89973fd6&version=nightly&mode=release https://play.rust-lang.org/?gist=b60ec85886eff967b21c7abc899...): br i1 false, label %bb9, label %bb6 SimplifyCFG would instantly kill that. But it doesn't get to run again after whatever simplified the branch condition. I've heard rumors that LLVM is working on a new pass manager, maybe they will eventually fix this pervasive issue.
  - Veedrac 9y ago
    Apologies for prodding a sore spot! The phase ordering problem is a well known demon for compilers; makes me wonder why I've not heard anything about unphased compilation.
    - eddyb 9y ago
      No worries, I'm just surprised you managed to find a simple testcase that exhibits it, so, really, thank you! I've opened a (a bit vague for now) issue so at least I don't forget about it: https://github.com/rust-lang/rust/issues/44041 https://github.com/rust-lang/rust/issues/44041 As for phase ordering - someone did show me recently VSDG, which claims to solve at least part of the problem (specifically, https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-705.pdf https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-705.pdf and http://sro.sussex.ac.uk/7576/1/Stanier%2C_James.pdf http://sro.sussex.ac.uk/7576/1/Stanier%2C_James.pdf).
      - Veedrac 9y ago
        Awesome references, seems I have some fun reading :). (Trivia: Alan Mycroft actually supervised me for my undergraduate dissertation.)
kllrnohj 9y ago
> Allocation in modern generational GCs is in a completely different performance category than C-style malloc is. Yes and no. If enough allocation happens that a GC pass occurs while you're still running your JS hot loop you're pretty much screwed and all your performance vanishes. If you want to see this in the extreme go open an Android systrace or Chrome chrome://tracing trace result and do a JS profile while you do so. The single largest consumer of JS CPU time is the GC at nearly 13%. The problem with modern generation GC langauges is they tend to be designed assuming that allocation is always cheap/free and it just isn't. That's a fairytale. It's just not true. Also just because it only takes 6-13ns for an allocation to be given to you doesn't mean anything when the first access of that allocation is a cache line miss compared to if you did the same thing in C and it was on the stack, which is likely sitting in hot L1 primed and ready to go. Reusing the same memory address range is critical to getting maximum performance, and modern generational GCs are miserably bad at that.
- pcwalton 9y ago
  > Yes and no. If enough allocation happens that a GC pass occurs while you're still running your JS hot loop you're pretty much screwed and all your performance vanishes. GCs are expensive relative to not doing anything, but minor GCs are very fast. > The problem with modern generation GC langauges is they tend to be designed assuming that allocation is always cheap/free and it just isn't. That's a fairytale. It's just not true. I'm not making an argument about language design here. Obviously value types are a good thing. > Reusing the same memory address range is critical to getting maximum performance, and modern generational GCs are miserably bad at that. Not at all. The nursery is usually in cache, just as the stack is. Nurseries are usually implemented as two space copying collectors with small spaces, which are excellent for cache locality (arguably even better than stacks, because stacks can grow deep).
  - kllrnohj 9y ago
    > Not at all. The nursery is usually in cache, just as the stack is. Nurseries are usually implemented as two space copying collectors with small spaces, which are excellent for cache locality (arguably even better than stacks, because stacks can grow deep). I think you're still working under the assumption that the GC is keeping up with the allocation rate, which if you have a small allocation in a hot loop will largely not be true. Typically GC'd languages rely on escape analysis to handle this and not the generational GC at all, but if that fails then you're SOL because the generational GC is unable to keep up and unable to keep things in the fast path.

vanderZwan 9y ago

Not GP, but as someone who has worked with image manipulation and typed arrays in JS (which seems similar to what the GP was doing) I can say that this often boils down to linearly looping through a typed array and doing very simple operations. You know, one of those "best case" scenarios for cpu utilisation where memory access tends to be the bottleneck. If the allocation happens inside a tight loop like that I can imagine it ruining performance

Veedrac 9y ago

Pointer-bump allocations are fast in isolation, but if your code is doing one it means the compiler has gotten itself confused, and every time it gets confused it makes it harder for later code to be optimized. Compilers only really reason reasonably about value types (and even then you should never assume they're smart[1]). That said, I don't actually know allocation is the problem; it's a suspect, but unlike a native script I can't just run `perf` to get performance counters and assembly listings. All I really know is that the non-allocating order is a lot faster. [1]: If you can read assembly, this one's hilarious: https://godbolt.org/g/81qWoq https://godbolt.org/g/81qWoq

pjmlp 9y ago
You can at least use the browser profiler tools.
- Veedrac 9y ago
  I do! It's missing a lot of detail, though; it's optimized much more for overall performance analysis.
- fenomas 9y ago
  Browser profiling tools are great but their granularity stops at the function level - they can't tell you anything about what happens within a given function, just how that function compares to others.
  - pjmlp 9y ago
    I haven't used them much, specially since I tend to choose native projects if possible. Thanks for the heads up.
foldr 9y ago
>[1]: If you can read assembly, this one's hilarious: https://godbolt.org/g/81qWoq https://godbolt.org/g/81qWoq I only barely read assembly, so I was just trying to figure this one out. So, the compiler has figured out that it just needs to test v against 0 (since the array is immutable), but it does this 2 times, and with a couple of apparently redundant 'je' instructions. Is that what's weird about the output? In case it changed, this is the output I saw: example::exists_in_table: push rbp mov rbp, rsp mov al, 1 test edi, edi je .LBB0_5 je .LBB0_5 test edi, edi je .LBB0_5 je .LBB0_5 xor eax, eax .LBB0_5: pop rbp ret
- Veedrac 9y ago
  Basically, yes. The first test and je show the compiler has managed the hard part, but the next je obviously can't be hit, the test after that literally doesn't do anything, and the two jumps after that also can't be hit. It's funny because this is all so trivial. If I write it as some C bool should_jump = edi == 0; if (should_jump) goto LBB0_5; if (should_jump) goto LBB0_5; bool should_jump = edi == 0; if (should_jump) goto LBB0_5; if (should_jump) goto LBB0_5; I can guarantee the compiler is going to produce good code from it.
eddyb 9y ago
This looks like yet-another-phase-ordering-issue in LLVM. I hit so many of these it's not even funny. Arguably one could find C code that shows the exact problem under clang. Example of optimized LLVM IR for that sample (press LLVM IR on https://play.rust-lang.org/?gist=b60ec85886eff967b21c7abc89973fd6&version=nightly&mode=release https://play.rust-lang.org/?gist=b60ec85886eff967b21c7abc899...): br i1 false, label %bb9, label %bb6 SimplifyCFG would instantly kill that. But it doesn't get to run again after whatever simplified the branch condition. I've heard rumors that LLVM is working on a new pass manager, maybe they will eventually fix this pervasive issue.
- Veedrac 9y ago
  Apologies for prodding a sore spot! The phase ordering problem is a well known demon for compilers; makes me wonder why I've not heard anything about unphased compilation.
  - eddyb 9y ago
    No worries, I'm just surprised you managed to find a simple testcase that exhibits it, so, really, thank you! I've opened a (a bit vague for now) issue so at least I don't forget about it: https://github.com/rust-lang/rust/issues/44041 https://github.com/rust-lang/rust/issues/44041 As for phase ordering - someone did show me recently VSDG, which claims to solve at least part of the problem (specifically, https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-705.pdf https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-705.pdf and http://sro.sussex.ac.uk/7576/1/Stanier%2C_James.pdf http://sro.sussex.ac.uk/7576/1/Stanier%2C_James.pdf).
    - Veedrac 9y ago
      Awesome references, seems I have some fun reading :). (Trivia: Alan Mycroft actually supervised me for my undergraduate dissertation.)

kllrnohj 9y ago

> Allocation in modern generational GCs is in a completely different performance category than C-style malloc is. Yes and no. If enough allocation happens that a GC pass occurs while you're still running your JS hot loop you're pretty much screwed and all your performance vanishes. If you want to see this in the extreme go open an Android systrace or Chrome chrome://tracing trace result and do a JS profile while you do so. The single largest consumer of JS CPU time is the GC at nearly 13%. The problem with modern generation GC langauges is they tend to be designed assuming that allocation is always cheap/free and it just isn't. That's a fairytale. It's just not true. Also just because it only takes 6-13ns for an allocation to be given to you doesn't mean anything when the first access of that allocation is a cache line miss compared to if you did the same thing in C and it was on the stack, which is likely sitting in hot L1 primed and ready to go. Reusing the same memory address range is critical to getting maximum performance, and modern generational GCs are miserably bad at that.

pcwalton 9y ago
> Yes and no. If enough allocation happens that a GC pass occurs while you're still running your JS hot loop you're pretty much screwed and all your performance vanishes. GCs are expensive relative to not doing anything, but minor GCs are very fast. > The problem with modern generation GC langauges is they tend to be designed assuming that allocation is always cheap/free and it just isn't. That's a fairytale. It's just not true. I'm not making an argument about language design here. Obviously value types are a good thing. > Reusing the same memory address range is critical to getting maximum performance, and modern generational GCs are miserably bad at that. Not at all. The nursery is usually in cache, just as the stack is. Nurseries are usually implemented as two space copying collectors with small spaces, which are excellent for cache locality (arguably even better than stacks, because stacks can grow deep).
- kllrnohj 9y ago
  > Not at all. The nursery is usually in cache, just as the stack is. Nurseries are usually implemented as two space copying collectors with small spaces, which are excellent for cache locality (arguably even better than stacks, because stacks can grow deep). I think you're still working under the assumption that the GC is keeping up with the allocation rate, which if you have a small allocation in a hot loop will largely not be true. Typically GC'd languages rely on escape analysis to handle this and not the generational GC at all, but if that fails then you're SOL because the generational GC is unable to keep up and unable to keep things in the fast path.