Hacker News Reader

Comment by Veedrac | Hacker News Reader

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

View on HN

>[1]: If you can read assembly, this one's hilarious: 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

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.

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

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.

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

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 and http://sro.sussex.ac.uk/7576/1/Stanier%2C_James.pdf).

Awesome references, seems I have some fun reading :). (Trivia: Alan Mycroft actually supervised me for my undergraduate dissertation.)

You can at least use the browser profiler tools.

I do! It's missing a lot of detail, though; it's optimized much more for overall performance analysis.

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.

I haven't used them much, specially since I tend to choose native projects if possible.

Thanks for the heads up.

Reply on news.ycombinator.com