undefined | Better HN

0 pointsnwallin2y ago0 comments

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 <stddef.h>
    
    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 and giving it permission to do its job properly.

Don't want to pass the string length? That's fine, we can figure that out for ourselves. This code:

    #include <stddef.h>
    #include <string.h>

    int run_switches(const char *s) {
      int res = 0;
      for (size_t n = strlen(s); n--; ++s)
        res += (*s == 's') - (*s == 'p');

      return res;
    }

Is 27GB/s. With a little bit of blocking:

    #include <stddef.h>
    
    int run_switches(const char *s, size_t n) {
      int res = 0;
      char tmp = 0;
      for (size_t i = n & 63; i--; ++s)
        tmp += (*s == 's') - (*s == 'p');
      res += tmp;
    
      for (n >>= 6; n--;) {
        tmp = 0;
        for (size_t i = 64; i--; ++s)
          tmp += (*s == 's') - (*s == 'p');
        res += tmp;
      }
    
      return res;
    }

That's ~55GB/s.

Anyway, the point is, you're pretty far from the point where you ought to give up on C and dive into assembly.

0 comments

utopcell2y ago

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;
    }

nwallinOP2y ago

Neat! Although you'll need to make a copy of `n`. The second loop will reduce the value of n to null.

Edit: Also, there's an off by one error. should be:

    #include <stddef.h>
    #include <stdint.h>
    
    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;
    }

~90GB/s on my machine, compared to 4.5GB/s for his best effort on his blog. So 20x as fast.

repsilat2y ago

This is a wonderful thread.

Which tricks in there are worth playing around with more widely?

Is the uint8_t just "no point in using something bigger" or does it likely help the compiler? Does/can the signedness matter as well as the size?

Ditto looping downwards -- is it often likely to improve things? Can it generalize to pointer/iterator ranges, or is it often worth trying to phrase them in terms of array/index accesses instead?

I guess the compiler's unrolling heuristics generally aren't as good as that blocking "mod then div" alternative to Duff's device? Obviously taking `s` out of the loop condition is part of the magic.

Not checking the 'p' character by comparison is an easy optimization to understand.

Any places to read about this sort of thing, or any tricks or guidelines that come to mind? I write a fair bit of performance-sensitive code but it's all probably 20x slower than it could be because I have no intuition for what transformations compilers will do beyond "this prob gets inlined" etc.

2 more replies

nwallinOP2y ago

Replying to my own post: The off by 1 error was incorrect. It's because I was calling the function wrong. I had been giving it the size of the buffer, not the size of the string.

Also, someone else figured out that we can just use an and instruction instead of cmp. That gives us this version:

    #include <stddef.h>
    #include <stdint.h>

    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 += 1 & *s;
      res += tmp;

      for (int i = n >> 7; i--;) {
        tmp = 0;
        for (int j = 128; j--; ++s)
          tmp += 1 & *s;
        res += tmp;
      }

      return 2 * res - n;
    }

This is 111GB/s, up from 4.5GB/s in the blog. I'm going to try really hard to put this problem down now and work on something more productive.

3 more replies

skavi2y ago

Am I missing something, or does this not really account for alignment? Is the compiler doing smarter loop splitting?

2 more replies

utopcell2y ago

Bummer! Edited the answer. Not sure about the off-by-one though. Say the string is str[] = "spp\0". n = strlen(str) is 3. In the end, res would be 1 and 2 * res - n == -1.

1 more reply

smarnach2y ago

This makes the assumption that the only characters in the string are "s" and "p". There is no basis for this assumption. I think this code solves a different problem rather than being an optimisation of the original code.

utopcell2y ago

The string can only contain 's' or 'p' if you examine how it is constructed in bench.c, and taking that into consideration yields another ~2x speedup.

teo_zero2y ago

But this is not the original problem! Only p's should decrease the counter, in your code every non-s does.

utopcell2y ago

The original problem was working on strings that only hold 's' and 'p' characters, as seen in bench.c. The first implementation checked against 's' and 'p' specifically, and all subsequent version optimized that first version.

magicalhippo2y ago

Another good reason to write optimization-friendly C (or similar) over assembly code, especially in libraries, is that the compiler will evolve with CPUs, while the assembly code will not.

I've seen plenty of cases where replacing hand-written assembly with C (or similar) lead to a substantial performance increase because the assembly code was written for some old CPU and not the best way of doing things on current CPUs.

rajnathani2y ago

This seems like the most efficient solution. I have a neighboring comment on this post which suggests using bit arithmetic, but the above solution is more efficient than that. Here’s what the assembly code for the body of the first loop compiles down to (I had to use ChatGPT-4 as godbolt unfortunately doesn’t work on mobile):

    cmp dl, 's'    ; Compare the character with 's'
    sete dl        ; If the character is 's', set dl to 1. Otherwise, set dl to 0.
    sub al, dl     ; Subtract the result from res

    cmp dl, 'p'    ; Compare the character with 'p'
    sete dl        ; If the character is 'p', set dl to 1. Otherwise, set dl to 0.
    add al, dl     ; Add the result to res

SleepyMyroslav2y ago

>Anyway, the point is, you're pretty far from the point where you ought to give up on C and dive into assembly.

Thank you. I hope people who post random assembly listings on HN written in some extinct ISA will read your posts.

j / k navigate · click thread line to collapse

0 pointsnwallin2y ago0 comments

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 <stddef.h>
    
    int run_switches(const char *s, size_t n) {
      int res = 0;
      for (; n--; ++s)
        res += (*s == 's') - (*s == 'p');
      return res;
    }

Don't want to pass the string length? That's fine, we can figure that out for ourselves. This code:

    #include <stddef.h>
    #include <string.h>

    int run_switches(const char *s) {
      int res = 0;
      for (size_t n = strlen(s); n--; ++s)
        res += (*s == 's') - (*s == 'p');

      return res;
    }

Is 27GB/s. With a little bit of blocking:

    #include <stddef.h>
    
    int run_switches(const char *s, size_t n) {
      int res = 0;
      char tmp = 0;
      for (size_t i = n & 63; i--; ++s)
        tmp += (*s == 's') - (*s == 'p');
      res += tmp;
    
      for (n >>= 6; n--;) {
        tmp = 0;
        for (size_t i = 64; i--; ++s)
          tmp += (*s == 's') - (*s == 'p');
        res += tmp;
      }
    
      return res;
    }

That's ~55GB/s.

Anyway, the point is, you're pretty far from the point where you ought to give up on C and dive into assembly.

0 comments

utopcell2y ago

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;
    }

nwallinOP2y ago

Neat! Although you'll need to make a copy of `n`. The second loop will reduce the value of n to null.

Edit: Also, there's an off by one error. should be:

    #include <stddef.h>
    #include <stdint.h>
    
    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;
    }

~90GB/s on my machine, compared to 4.5GB/s for his best effort on his blog. So 20x as fast.

repsilat2y ago

This is a wonderful thread.

Which tricks in there are worth playing around with more widely?

Is the uint8_t just "no point in using something bigger" or does it likely help the compiler? Does/can the signedness matter as well as the size?

Ditto looping downwards -- is it often likely to improve things? Can it generalize to pointer/iterator ranges, or is it often worth trying to phrase them in terms of array/index accesses instead?

I guess the compiler's unrolling heuristics generally aren't as good as that blocking "mod then div" alternative to Duff's device? Obviously taking `s` out of the loop condition is part of the magic.

Not checking the 'p' character by comparison is an easy optimization to understand.

2 more replies

nwallinOP2y ago

Replying to my own post: The off by 1 error was incorrect. It's because I was calling the function wrong. I had been giving it the size of the buffer, not the size of the string.

Also, someone else figured out that we can just use an and instruction instead of cmp. That gives us this version:

    #include <stddef.h>
    #include <stdint.h>

    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 += 1 & *s;
      res += tmp;

      for (int i = n >> 7; i--;) {
        tmp = 0;
        for (int j = 128; j--; ++s)
          tmp += 1 & *s;
        res += tmp;
      }

      return 2 * res - n;
    }

This is 111GB/s, up from 4.5GB/s in the blog. I'm going to try really hard to put this problem down now and work on something more productive.

3 more replies

skavi2y ago

Am I missing something, or does this not really account for alignment? Is the compiler doing smarter loop splitting?

2 more replies

utopcell2y ago

Bummer! Edited the answer. Not sure about the off-by-one though. Say the string is str[] = "spp\0". n = strlen(str) is 3. In the end, res would be 1 and 2 * res - n == -1.

1 more reply

smarnach2y ago

utopcell2y ago

The string can only contain 's' or 'p' if you examine how it is constructed in bench.c, and taking that into consideration yields another ~2x speedup.

teo_zero2y ago

But this is not the original problem! Only p's should decrease the counter, in your code every non-s does.

utopcell2y ago

magicalhippo2y ago

Another good reason to write optimization-friendly C (or similar) over assembly code, especially in libraries, is that the compiler will evolve with CPUs, while the assembly code will not.

rajnathani2y ago

    cmp dl, 's'    ; Compare the character with 's'
    sete dl        ; If the character is 's', set dl to 1. Otherwise, set dl to 0.
    sub al, dl     ; Subtract the result from res

    cmp dl, 'p'    ; Compare the character with 'p'
    sete dl        ; If the character is 'p', set dl to 1. Otherwise, set dl to 0.
    add al, dl     ; Add the result to res

SleepyMyroslav2y ago

>Anyway, the point is, you're pretty far from the point where you ought to give up on C and dive into assembly.

Thank you. I hope people who post random assembly listings on HN written in some extinct ISA will read your posts.

j / k navigate · click thread line to collapse