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

91–100 of 249 posts

Re: {n} times faster than C

#91

Post by Tuna-Fish »

Lk7Of3vfJS2n wrote: post #81
haberman wrote: post #61

Earlier quoted context omitted.

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

I'd be curious to learn why CPUs don't have conditional move speculation.

Because modern CPUs as a rule don't speculate on values to arithmetic, only on control flow, and CMOV acts like arithmetic.

That is, if there is an add instruction on rax and rbx, no matter what, the add instruction will not execute until both rbx and rbx are available. If the result went into rax, and there is an another instruction that uses that as a source, no matter what that instruction will not execute until the add has completed.

CMOV is implemented as an ALU instruction that always writes into it's output, and either writes the value that is already in there (which is why it depends on the value of it's output) or the value provided, depending on flags.

Re: {n} times faster than C

#93

Post by bombcar »

jdsalaro wrote: post #90
JohnMakin wrote: post #86

Earlier quoted context omitted.

Thank you for your post and reply but I fear with a post + title like this you may just be chumming the waters.

What do you mean by "chumming the waters" in this context?

People who just skim the headline and article will come away convinced that dropping to assembly is the “way to go fast” even if they never actually do it.

Re: {n} times faster than C

#94

Post by kstrauser »

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

I had an old compilers professor say something like this once. “If you think you can do something better than the C compiler, I promise you you can’t.”

To a point. A modern C compiler generates mind boggingly fast assembler. However, some languages make it way easier to write sophisticated algorithms more easily.

For instance, suppose you're writing a program to find the nth Fibonacci number for whatever reason. In Python, the naive version might look like:

  def fib(n):
      if n
On my machine, that takes about 12 seconds to find the 40th number. Altering that slightly like:

  from functools import cache
  @cache
  def fib(n): ...
makes the whole program take about 30 milliseconds total. The 400th takes about 32ms and emits an answer that won't fit in a 256-bit int.

Of course you can do the exact same kind of caching in C! I mean, the main Python interpreter's written in C, so by extension any algorithm you can express in Python you can also express in C. It'd probably be a lot faster, too!

But in practice, if I'm writing that in Python, I can use the obvious algorithm, spent 10 seconds slapping a caching decorator on it, verify that the end result is ridiculous fast and efficient, then move on to other problems.

Any reasonable C compiler will emit assembler that's vastly better than anything I could come up with. Conversely, I personally can write far better algorithms in Python than I could in C, because it's easier for me to express cleverness in that language. Those algorithmic improvements tend to have a far better speed payoff than I'd personally get from a more efficient implementation of a crappy method.

Re: {n} times faster than C

#95

Post by sriku »

414owen wrote: post #51
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…

Nice! There's a part two in which I rewrote the C. I got a 12x speedup :) https://owen.cafe/posts/the-same-speed-as-c/ And as others have pointed out, you can tweak the input, then vectorize the algo, if you want to go that route. I considered this a pedagogical exercise and I sincerely hope nobody will start dropping down to assembly without a very good reason to.

Wondering how res += (c=='s')-(c=='p') might do. I sure there is some C undefined behaviour relevant there. Curious but too lazy to check it myself!

Re: {n} times faster than C

#96

Post by seventhson »

torstenvl wrote: post #56
haberman wrote: post #41

Earlier quoted context omitted.

> jumps are a lot slower than conditional arithmetic. This statement is true if the jumps are unpredictable. If the jumps are predictable, then jumps will be faster. Linus had a whole rant about this back in the day, arguing that cmov is not useful if branches are predictable: https://yarchive.net/comp/linux/cmov.html

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…

Linus' post is 15+ years old. Much has changed in Intel hardware since then. He was probably right on the money re the hardware available at the time.

Re: {n} times faster than C

#97

Post by bjourne »

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…

> Whereas conditional moves cannot execute any subsequent instructions until the correct value is available.

That is incorrect. Super-scalar processors have no problem executing subsequent instructions before the cmov writebacks. However, the register cmov writes to can of course not be read before cmov has has passed the execution unit. But that's not different from other arithmetic instructions.

Re: {n} times faster than C

#98

Post by elcritch »

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…

Nice! I tried it in Nim and it appears to trigger it with:

    {.overflowChecks:off.}
    proc run_switches*(input: cstring): int {.exportc.} =
      result = 0
      for c in input:
        result.inc int('s' == c)
        result.dec int('p' == c)
That gives a ~5x speedup on an Apple M1. Keeping overflow checks on only gets it up to ~2x the default C version. Always nice to know good ways to trigger SIMD opts.
Post reply on HN