{n} times faster than C

Post by Lk7Of3vfJS2n » Fri, Jul 07, 2023, 12:03 AM UTC

haberman wrote: post #61

torstenvl wrote: post #56

Earlier quoted context omitted.

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

> jump-if-equal and set-if-equal would seem to have the same level of predictability. The difference is that branches have dedicated hardware (branch predictors) that will speculatively execute subsequent instructions based on their best guess about which way the branch will go. Whereas conditional moves cannot execute any subsequent instructions until the correct value is available. Put another way, CPUs have contro…

Post by icsa » Fri, Jul 07, 2023, 12:07 AM UTC

ModernMech wrote: post #39

DeathArrow wrote: post #24

Earlier quoted context omitted.

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

Yes, there’s always the “sufficiently smart compiler” that can generate this code. Question is, does that compiler exist?

Post by JohnMakin » Fri, Jul 07, 2023, 12:11 AM UTC

jtriangle wrote: post #84

It's a cardinal rule that any time someone utters "XYZ is n faster than C" someone comes along and shows C is actually 2x faster than XYZ.

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

414owen wrote: post #47

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…

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 :)

    #include 
    
    int run_switches(const char *s, size_t n) {
      int res = 0;
      for (; n--; ++s)
        res += (*s == 's') - (*s == 'p');
      return res;
    }

    #include 
    #include 

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

      return res;
    }

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

Post by kevin_thibedeau » Fri, Jul 07, 2023, 12:26 AM UTC

Karellen wrote: post #78

p1necone wrote: post #65

Earlier quoted context omitted.

Is rewriting switch statements to a bunch of ifs always faster? Or is there some number of cases where the switch is faster? Seems like it should be added as a compiler optimization if it's consistent.

It shouldn't be. If the fastest way to implement a particular `switch` in assembly is with the equivalent of a set of `if`s, a reasonably smart compiler "should" be able to output the assembly to do that. And I thought that gcc and clang at least have actually been smart enough to do that for a while now. But if the number of `if`s is high and the distribution sufficiently dense, where a jump table is better than a b…