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

21–30 of 249 posts

Re: {n} times faster than C

#21

Post by failuser »

Having a full-blown predicate support is so nice to have, but it interferes with compact instruction encoding.

Such bloated ISA like x86 might actually handle predicate support, but who will try such a radical change?

Re: {n} times faster than C

#22

Post by nwallin »

IMHO the original code wasn't written in a way that's particularly friendly to compilers. If you write it like this:

    int run_switches_branchless(const char* s) {
        int result = 0;
        for (; *s; ++s) {
            result += *s == 's';
            result -= *s == 'p';
        }
        return result;
    }
...the compiler will do all the branchless sete/cmov stuff as it sees fit. It will be the same speed as the optimized assembly in the post, +/- something insignificant. However it won't unroll and vectorize the loop. If you write it like this:

    int run_switches_vectorized(const char* s, size_t size) {
        int result = 0;
        for (; size--; ++s) {
            result += *s == 's';
            result -= *s == 'p';
        }
        return result;
    }
It will know the size of the loop, and will unroll it and use AVX-512 instructions if they're available. This will be substantially faster than the first loop for large inputs, although I'm too lazy to benchmark just how much faster it is.

Now, this requires knowing the size of your string in advance, and maybe you're the sort of C programmer who doesn't keep track of how big your strings are. I'm not your coworker, I don't review your code. Do what you want. But you really really probably shouldn't.

https://godbolt.org/z/rde51zMd8

Re: {n} times faster than C

#23

Post by torstenvl »

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

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

Sorry, I write 'gcc' purely out of force of habit. I'm using Clang/LLVM.

    [17:23:00 user@boxer ~/looptest] $ uname -a
    Darwin boxer.local 21.6.0 Darwin Kernel Version 21.6.0: Thu Jun  8 23:57:12 PDT 2023; root:xnu-8020.240.18.701.6~1/RELEASE_X86_64 x86_64
    [17:23:47 user@boxer ~/looptest] $ cc -v
    Apple clang version 14.0.0 (clang-1400.0.29.202)
    Target: x86_64-apple-darwin21.6.0
    Thread model: posix
    InstalledDir: /Library/Developer/CommandLineTools/usr/bin
Clang generates the sete instruction for me with the above code:

    [17:23:49 user@boxer ~/looptest] $ gcc -c -O3 loop2.c   
    [17:25:00 user@boxer ~/looptest] $ objdump -d --symbolize-operands --x86-asm-syntax=intel --no-show-raw-insn loop2.o
    
    loop2.o: file format mach-o 64-bit x86-64
    
    Disassembly of section __TEXT,__text:
    
    0000000000000000 :
           0:       push rbp
           1:       mov rbp, rsp
           4:       xor eax, eax
           6:       nop word ptr cs:[rax + rax]
    :
          10:       movzx ecx, byte ptr [rdi]
          13:       add rdi, 1
          17:       xor edx, edx
          19:       cmp cl, 115
          1c:       sete dl
          1f:       add eax, edx
          21:       xor edx, edx
          23:       cmp cl, 112
          26:       sete dl
          29:       sub eax, edx
          2b:       test cl, cl
          2d:       jne  
          2f:       pop rbp
          30:       ret

Re: {n} times faster than C

#24

Post by DeathArrow »

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?

Re: {n} times faster than C

#25

Post by [deleted] »

torstenvl wrote: post #3

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

[deleted]

Re: {n} times faster than C

#26

Post by svachalek »

BoppreH wrote: post #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.

Nice. The way I read the cmove version, it's more or less this except the trick line goes

    res += (c == 's') ? 1 : (c == 'p') ? -1 : 0
I haven't done C in decades so I don't trust myself to performance test this but I'm curious how it compares. Pretty disappointed that TFA didn't go back and try that in C.

Re: {n} times faster than C

#27

Post by camel-cdr »

dzaima wrote: post #16
camel-cdr wrote: post #10

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.

I'm not sure I fully understand fault-only-first load, but reading the description of vle8ff.v I think I only need to exchange the load inside of the loop?

How does the normal load deal with faults?

I'll update the parent comment, it slowed down the speed from 2/1.7 to 1.57/1.36 Bytes/Cycle.

Re: {n} times faster than C

#29

Post by jonny_eh »

nwallin wrote: post #22

IMHO the original code wasn't written in a way that's particularly friendly to compilers. If you write it like this: int run_switches_branchless(const char* s) { int result = 0; for (; *s; ++s) { result += *s == 's'; result -= *s == 'p'; } return result; } ...the compiler will do all the branchless sete/cmov stuff as it sees fit. It will be the same speed as the optimized assembly in the post, +/- something insignifi…

> But you really really probably shouldn't.

Shouldn't "not" keep track of string length?

Re: {n} times faster than C

#30

Post by twoodfin »

ftxbro wrote: post #20
414owen wrote: 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?

This is the right answer:

https://news.ycombinator.com/item?id=36622584

Optimal assembly (forgoing SIMD, at least) for this loop on modern x86 is highly dependent on the entropy of the runtime data.

Post reply on HN