{n} times faster than C

Post by [deleted] » Fri, Jul 07, 2023, 2:35 AM UTC

Guvante wrote: post #110

torstenvl wrote: post #72

Earlier quoted context omitted.

Better than random input, but still only ~half as fast as using sete [19:13:34 user@boxer ~/src/looptest] $ diff -u bench.c bench-alls.c --- bench.c 2023-07-06 16:04:16.000000000 -0400 +++ bench-alls.c 2023-07-06 19:13:34.000000000 -0400 @@ -17,7 +17,7 @@ int num_rand_calls = number / CHAR_BIT + 1; unsigned char *buffer = malloc(num_rand_calls * CHAR_BIT); for (int i = 0; i Jumps are slower.

Microbenchmarks are hard. You aren't doing any meaningful work that could benefit from speculatively executing instead of stalling for the conditional value. Similarly you might be busting the pipeline by chaining together the jumps so close together. Not saying your point is wrong, just saying your proof isn't super solid.

Post by utopcell » Fri, Jul 07, 2023, 2:45 AM UTC

nwallin wrote: post #87

414owen wrote: post #47

Earlier quoted context omitted.

The version that's friendly to the compiler is described in part two: https://owen.cafe/posts/the-same-speed-as-c/ It achieves 3.88GiB/s I intentionally didn't go down the route of vectorizing. I wanted to keep the scope of the problem small, and show off the assembly tips and tricks in the post, but maybe there's potential for a future post, where I pad the input string and vectorize the algorithm :)

So I downloaded your code. On my desktop, with loop-9 gcc I got ~4.5GB/s, and with loop-7 I got ~4.4GB/s. With the following code: #include int run_switches(const char *s, size_t n) { int res = 0; for (; n--; ++s) res += (*s == 's') - (*s == 'p'); return res; } I got ~31GB/s in GCC and ~33GB/s in Clang. This is without any padding, or SIMD intrinsics, or any such nonsense. This is just untying the compiler's hands an…

    int run_switches(const char *s) {
      int res = 0;
      uint8_t tmp = 0;
      size_t n = strlen(s);
      for (size_t i = n & 127; i--; ++s)
        tmp += (*s == 's');
      res += tmp;
    
      for (size_t j = n >> 7; j--;) {
        tmp = 0;
        for (size_t i = 128; i--; ++s)
          tmp += (*s == 's');
        res += tmp;
      }
    
      return 2 * res - n;
    }

Post by utopcell » Fri, Jul 07, 2023, 2:53 AM UTC

Const-me wrote: post #60

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... Tha…

Post by plorkyeran » Fri, Jul 07, 2023, 3:01 AM UTC

eyegor wrote: post #88

icsa wrote: post #83

Earlier quoted context omitted.

These days, I's put my money on zig cc. I.E. zig cc -Os or zig cc -O3

Does the zig compiler have many fancy bits? I was under the impression the c support was a "nothing special" compiler that punted to llvm for optimizations.

Post by nwallin » Fri, Jul 07, 2023, 3:16 AM UTC

utopcell wrote: post #113

nwallin wrote: post #87

Earlier quoted context omitted.

So I downloaded your code. On my desktop, with loop-9 gcc I got ~4.5GB/s, and with loop-7 I got ~4.4GB/s. With the following code: #include int run_switches(const char *s, size_t n) { int res = 0; for (; n--; ++s) res += (*s == 's') - (*s == 'p'); return res; } I got ~31GB/s in GCC and ~33GB/s in Clang. This is without any padding, or SIMD intrinsics, or any such nonsense. This is just untying the compiler's hands an…

Indeed. I suppose the two lessons are, stick with C, and don't forget the semantics of your original problem when optimizing. int run_switches(const char *s) { int res = 0; uint8_t tmp = 0; size_t n = strlen(s); for (size_t i = n & 127; i--; ++s) tmp += (*s == 's'); res += tmp; for (size_t j = n >> 7; j--;) { tmp = 0; for (size_t i = 128; i--; ++s) tmp += (*s == 's'); res += tmp; } return 2 * res - n; }

    #include 
    #include 
    
    int run_switches(const char *s, const size_t n) {
      int res = 0;
      uint8_t tmp = 0;
      for (int i = n & 127; i--; ++s)
        tmp += *s == 's';
      res += tmp;
    
      for (int size = n >> 7; size--;) {
        tmp = 0;
        for (int i = 128; i--; ++s)
          tmp += *s == 's';
        res += tmp;
      }
    
      return 2 * res - n + 1;
    }