Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

{n} times faster than C

owen.cafe

Post reply on HN
Print view View original

51–60 of 249 posts

Re: {n} times faster than C

#51

Post by 414owen »

torstenvl wrote: post #11

I'm not so sure that the right take-away is "hand-written assembler is 6x faster than C." It's more like "jumps are a lot slower than conditional arithmetic." And that can [edit:often] be achieved easily in C by simply not using switch statements when an if statement or two will work fine. Rewriting the C function as follows got a 5.5x speedup: int run_switches(char *input) { int r = 0; char c; while (1) { c = *input…

Nice! There's a part two in which I rewrote the C. I got a 12x speedup :)

https://owen.cafe/posts/the-same-speed-as-c/

And as others have pointed out, you can tweak the input, then vectorize the algo, if you want to go that route.

I considered this a pedagogical exercise and I sincerely hope nobody will start dropping down to assembly without a very good reason to.

Re: {n} times faster than C

#52

Post by ftxbro »

tylerhou wrote: post #45
ftxbro wrote: post #33

Earlier quoted context omitted.

OK so they were abusing the benchmark, like the compiler's output would be faster on less contrived test data? Do I have to search what are fdo or pgo or cmov to understand the answer?

The compiler will generate different code if it knew the rates at which branches were taken. If a branch is almost always taken or almost never taken, a compiler will want to emit a jump. The frontend will be able to predict the jump with high probability, and a successfully-predicted jump is "free." The cost of a misprediction is paid for by the near-zero cost of the many successful predictions. If a branch is hard…

Thank you this is an amazingly comprehensive answer! Now I wonder what would be the workflow for using these compiler features. Like if I am a normal or bad C programmer and I write my program and use valgrind to check that it doesn't have obvious problems and I compile it with -march native or whatever, then I can add some step to the workflow to somehow re-compile it in a way that uses the branching or access patterns of some examples that I let it process for that purpose?

Re: {n} times faster than C

#53

Post by tylerhou »

ftxbro wrote: post #52
tylerhou wrote: post #45

Earlier quoted context omitted.

The compiler will generate different code if it knew the rates at which branches were taken. If a branch is almost always taken or almost never taken, a compiler will want to emit a jump. The frontend will be able to predict the jump with high probability, and a successfully-predicted jump is "free." The cost of a misprediction is paid for by the near-zero cost of the many successful predictions. If a branch is hard…

Thank you this is an amazingly comprehensive answer! Now I wonder what would be the workflow for using these compiler features. Like if I am a normal or bad C programmer and I write my program and use valgrind to check that it doesn't have obvious problems and I compile it with -march native or whatever, then I can add some step to the workflow to somehow re-compile it in a way that uses the branching or access patte…

Yes, Clang supports FDO, but it might be hard to set up (I've never set up FDO myself). You could check out https://github.com/google/autofdo and https://clang.llvm.org/docs/UsersManual.html#profile-guided-....

(People within Google say "FDO", basically everyone else says "PGO".)

Re: {n} times faster than C

#54

Post by dzaima »

camel-cdr wrote: post #50
dzaima wrote: post #38

Earlier quoted context omitted.

You'd probably want to have a new __riscv_vsetvlmax_e8m8 at the start of each loop iteration, as otherwise an earlier iteration could cut off the vl (e.g. page unloaded by the OS), and thus the loop continues with the truncated vl. The normal load should just segfault if any loaded byte is outside of readable memory, same as with a scalar load which is similarly partly outside.

> You'd probably want to have a new __riscv_vsetvlmax_e8m8 at the start of each loop iteration, as otherwise an earlier iteration could cut off the vl (e.g. page unloaded by the OS), and thus the loop continues with the truncated vl. Oh, yeah, that was a big oversight, unfortunately, this didn't undo the performance regression. > The normal load should just segfault if any loaded byte is outside of readable memory, s…

The memcpy doesn't use a vlmax, it uses a hand-chosen vl. The load won't fault on any elements not loaded (here, elements past the vl), so the memcpy is fine as it only loads items it'll definitely need, whereas your original code can read elements past the null byte.

And yeah, aligning the pointer manually would work (though then it wouldn't be portable code, as the spec does allow for rvv implementations with VLEN of up to 65536 (8KB per register; 64KB with LMUL=8), which'll be larger than the regular 4KB pages).

Re: {n} times faster than C

#55

Post by thomasahle »

DeathArrow wrote: post #24
torstenvl wrote: post #11

I'm not so sure that the right take-away is "hand-written assembler is 6x faster than C." It's more like "jumps are a lot slower than conditional arithmetic." And that can [edit:often] be achieved easily in C by simply not using switch statements when an if statement or two will work fine. Rewriting the C function as follows got a 5.5x speedup: int run_switches(char *input) { int r = 0; char c; while (1) { c = *input…

Shouldn't the compiler be able to do that, too?

I tried https://godbolt.org/, and neither Clang nor GCC trunk give the same code for the two programs.

Pretty shocking for such a simple program.

Re: {n} times faster than C

#56

Post by torstenvl »

haberman wrote: post #41
torstenvl wrote: post #11

I'm not so sure that the right take-away is "hand-written assembler is 6x faster than C." It's more like "jumps are a lot slower than conditional arithmetic." And that can [edit:often] be achieved easily in C by simply not using switch statements when an if statement or two will work fine. Rewriting the C function as follows got a 5.5x speedup: int run_switches(char *input) { int r = 0; char c; while (1) { c = *input…

> jumps are a lot slower than conditional arithmetic. This statement is true if the jumps are unpredictable. If the jumps are predictable, then jumps will be faster. Linus had a whole rant about this back in the day, arguing that cmov is not useful if branches are predictable: https://yarchive.net/comp/linux/cmov.html

I haven't run any benchmarks, but jump-if-equal and set-if-equal would seem to have the same level of predictability.

My naive, untested intuition is that there's only one meaningful difference: the former has to dump the entire pipeline on a miss, and the latter only has to nop a single instruction on a miss.

But maybe I'm missing something. I'll re-read his rant.

EDIT:

Linus rants a lot, but makes one concrete claim:

    You can always replace it by
    
      j forward
      mov ..., %reg
     forward:
    
    and assuming the branch is AT ALL predictable (and 95+% of all branches
    are), *the branch-over will actually be a LOT better for a CPU.*
So, I decided to test that.

    [18:50:14 user@boxer ~/src/looptest] $ diff -u loop2.s loop4.s
    --- loop2.s 2023-07-06 18:40:11.000000000 -0400
    +++ loop4.s 2023-07-06 18:46:58.000000000 -0400
    @@ -17,11 +17,15 @@
      incq %rdi
      xorl %edx, %edx
      cmpb $115, %cl
    - sete %dl
    + jne _run_switches_jmptgt1
    + mov $1,   %dl
    +_run_switches_jmptgt1:  
      addl %edx, %eax
      xorl %edx, %edx
      cmpb $112, %cl
    - sete %dl
    + jne _run_switches_jmptgt2
    + mov $1,   %dl
    +_run_switches_jmptgt2:  
      subl %edx, %eax
      testb %cl, %cl
      jne LBB0_1
    [18:50:29 user@boxer ~/src/looptest] $ gcc -O3 bench.c loop2.s -o l2
    [18:50:57 user@boxer ~/src/looptest] $ gcc -O3 bench.c loop4.s -o l4
    [18:51:02 user@boxer ~/src/looptest] $ time ./l2 1000 1
    449000
    ./l2 1000 1  0.69s user 0.00s system 99% cpu 0.697 total
    [18:51:09 user@boxer ~/src/looptest] $ time ./l4 1000 1
    449000
    ./l4 1000 1  4.53s user 0.01s system 99% cpu 4.542 total
I feel pretty confident that Linus has made a poor prediction about poor prediction here. Jumps are indeed slower.

To be fair to Linus, since Clang and I are using sete here, not cmov, I also tested cmov, and the difference was insignificant:

    [19:53:12 user@boxer ~/src/looptest] $ time ./l2 1000 1            
    449000
    ./l2 1000 1  0.69s user 0.00s system 99% cpu 0.700 total
    [19:53:15 user@boxer ~/src/looptest] $ time ./l5 1000 1            
    449000
    ./l5 1000 1  0.68s user 0.00s system 99% cpu 0.683 total
Jumps are slower.

Re: {n} times faster than C

#57

Post by nwallin »

eklitzke wrote: post #6

Rearranging branches (and perhaps blocks too?) will definitely be done if you are building using FDO, because without FDO (or PGO) the compiler has no idea how likely each branch is to be taken. Cmov can also be enabled by FDO in some cases. However, whether or not using cmov is effective compared to a regular test/jump is highly dependent on how predictable the branch is, with cmov typically performing better when t…

> I assume that their test input (which isn't described in the post, and is also not in their GitHub repo) consists of random strings consisting almost entirely of s and p characters.

test code is here: https://github.com/414owen/blog-code/blob/master/02-the-same... it randomly selects between 's' or 'p'. The characters can't be anything other than 's', 'p', or the terminating null. Knowing that particular fact about our input gives us this ...clever... optimization:

    int run_switches(const char* s) {
        int result = 0;
        while (*s)
            result += (1 | *s++) - 'r';
        return result;
    }
which compiles to:

    run_switches:
            movzx   eax, BYTE PTR [rdi]
            xor     edx, edx
            test    al, al
            je      .L1
    .L3:
            or      eax, 1
            inc     rdi
            movsx   eax, al
            lea     edx, [rdx-114+rax]
            movzx   eax, BYTE PTR [rdi]
            test    al, al
            jne     .L3
    .L1:
            mov     eax, edx
            ret
This is too clever by half, of course, but it perfectly illustrates your point about exploiting properties of the data.

Re: {n} times faster than C

#58

Post by camel-cdr »

dzaima wrote: post #54
camel-cdr wrote: post #50

Earlier quoted context omitted.

> You'd probably want to have a new __riscv_vsetvlmax_e8m8 at the start of each loop iteration, as otherwise an earlier iteration could cut off the vl (e.g. page unloaded by the OS), and thus the loop continues with the truncated vl. Oh, yeah, that was a big oversight, unfortunately, this didn't undo the performance regression. > The normal load should just segfault if any loaded byte is outside of readable memory, s…

The memcpy doesn't use a vlmax, it uses a hand-chosen vl. The load won't fault on any elements not loaded (here, elements past the vl), so the memcpy is fine as it only loads items it'll definitely need, whereas your original code can read elements past the null byte. And yeah, aligning the pointer manually would work (though then it wouldn't be portable code, as the spec does allow for rvv implementations with VLEN…

Ah, this makes a lot more sense now. I thought the "fault" was about the kernel interrupting when a new page needs to be loaded into physical memory, which would also happen for memcpy.

Re: {n} times faster than C

#59

Post by 414owen »

xoranth wrote: post #49

I think I managed to improve on both this post, and its sequel, at the cost of specializing the function for the case of a string made only of 's' and 'p'. The benchmark only tests strings made of 's' and 'p', so I think it is fair. The idea is as follow. We want to increase `res` by one when the next character is `s`. Naively, we might try something like this: res += (c - 'r'); // is `res += 1` when c == 's' This do…

Very interesting approach. I should probably have specified that the somewhat naive assembly in `02-the-same-speed-as-c/loop-5.x64.s` is the fastest version I have.

On my machine I'm getting 0.244s for `loop-5.x64.s` and 0.422s for your implementation above.

I'm not sure why exactly we're seeing this discrepancy, and for what it's worth your implementation looks faster to me. I guess this is why you need to always benchmark on the hardware you're going to be running the code on...

Re: {n} times faster than C

#60

Post by Const-me »

I’m probably an optimization expert, and I would solve that problem completely differently.

On my computer, the initial C version runs at 389 MB / second. I haven’t tested the assembly versions, but if they deliver the same 6.2x speedup, would result in 2.4 GB/second here.

Here’s C++ version which for long buffers exceeds 24 GB/second on my computer: https://gist.github.com/Const-me/3ade77faad47f0fbb0538965ae7... That’s 61x speedup compared to the original version, without any assembly, based on AVX2 intrinsics.

Post reply on HN