Live data from Hacker News

{n} times faster than C

owen.cafe

11–20 of 249 posts

Re: {n} times faster than C

#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++;
            if (c == 's') r++;
            if (c == 'p') r--;
            if (c == '\0') break;
        }
        return r;
    }
Results:

    [16:50:14 user@boxer ~/looptest] $ gcc -O3 bench.c loop1.c -o lone
    [16:50:37 user@boxer ~/looptest] $ gcc -O3 bench.c loop2.c -o ltwo
    [16:50:47 user@boxer ~/looptest] $ time ./lone 1000 1
    449000
    ./lone 1000 1  3.58s user 0.00s system 99% cpu 3.589 total
    [16:50:57 user@boxer ~/looptest] $ time ./ltwo 1000 1
    449000
    ./ltwo 1000 1  0.65s user 0.00s system 99% cpu 0.658 total

Re: {n} times faster than C

#13

There's an error in the pseudocode. cmp ecx, 's' # if (c == 's') jne loop # continue add eax, 1 # res++ jmp loop # continue should be cmp ecx, 's' # if (c != 's') jne loop # continue add eax, 1 # res++ jmp loop # continue

I believe the first `jne` should be `je`, right ?

Re: {n} times faster than C

#14

There's an error in the pseudocode. cmp ecx, 's' # if (c == 's') jne loop # continue add eax, 1 # res++ jmp loop # continue should be cmp ecx, 's' # if (c != 's') jne loop # continue add eax, 1 # res++ jmp loop # continue

I believe the first `jne` should be `je`, right ?

No, the assembler is correct. Jump (early) back to the beginning of the loop if not equal to s; otherwise, continue executing the next instruction (add eax, 1) and then unconditionally jump back to the beginning of the loop.

Re: {n} times faster than C

#15
post #8
post #5

A while back, I wrote a UTF-8 decoder in Common Lisp, targeting SBCL (it already has one built in, this was an exercise). Pretty much all of the optimization win (after the obvious low-hanging fruit) was structuring the code so that the compiler would generate cmov* instructions rather than branches.

What's some examples of the code changes that you made? And did you just do repeated disassemblies of the functions to see that it was using the correct instructions, or did you do some benchmarking to show your changes were actual improvements?

Gosh, I'd have to see if I can dig it up this was a few years ago.

I did all of the above, plus profiling (sb-sprof combined with disassemble will show assembly level profiling).

Re: {n} times faster than C

#16

I threw together a quick risc-v vectorized implementation: size_t run(char *str) { uint8_t *p = (uint8_t*)str; long end = 0; size_t res = 0, vl; while (1) { vl = __riscv_vsetvlmax_e8m8(); vuint8m8_t v = __riscv_vle8ff_v_u8m8(p, &vl, vl); end = __riscv_vfirst_m_b1(__riscv_vmseq_vx_u8m8_b1(v, '\0', vl), vl); if (end >= 0) break; res += __riscv_vcpop_m_b1(__riscv_vmseq_vx_u8m8_b1(v, 's', vl), vl); res -= __riscv_vcpop_m…

To be fully correct, you'd need the load to be a fault-only-first load (which rvv does have), otherwise that could fail if the null byte was just before the end of allocated memory.

Re: {n} times faster than C

#17

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…

What version of GCC are you using? For me both versions perform the same, both on Ubuntu and Windows:

    $ time ./lone 1000 1
        851000

        real    0m3.578s
        user    0m3.574s
        sys     0m0.004s
        
    $ time ./ltwo 1000 1
        851000

        real    0m3.583s
        user    0m3.583s
        sys     0m0.000s

    $ gcc --version
        gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
        Copyright (C) 2019 Free Software Foundation, Inc.
        This is free software; see the source for copying conditions.  There is NO
        warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Re: {n} times faster than C

#18
post #5

A while back, I wrote a UTF-8 decoder in Common Lisp, targeting SBCL (it already has one built in, this was an exercise). Pretty much all of the optimization win (after the obvious low-hanging fruit) was structuring the code so that the compiler would generate cmov* instructions rather than branches.

Branches are prone to be faster than conditional moves if they are correctly predicted, because they do not increase the critical path length. And utf-8 decoders are commonly run on all-ascii input. What were you benchmarking on?

Re: {n} times faster than C

#19
You can also use math to avoid most of the jumps:

    int run_switches(char *input) {
      int res = 0;
      while (true) {
        char c = *input++;
        if (c == '\0') return res;
        // Here's the trick:
        res += (c == 's') - (c == 'p');
      }
    }
This gives a 3.7x speed compared to loop-1.c. The lower line count is also nice.

Re: {n} times faster than C

#20
post #2

A clickbait title for an in-depth look at hand-optimizing a very simple loop.

I'm not a compiler expert but if it's a "very simple loop" is it still too complex for the compiler to make good machine code? Did they use a bad compiler on purpose? Or are computers just not yet fast enough to do a good job with very simple loops in practical compilers?
Post reply on HN