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

121–130 of 249 posts

Re: {n} times faster than C

#121

Post by utopcell »

nwallin wrote: post #119
utopcell wrote: post #113

Earlier quoted context omitted.

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

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 #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; } re…

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.

Re: {n} times faster than C

#122

Post by celrod »

torstenvl wrote: post #112
Tuna-Fish wrote: post #91

Earlier quoted context omitted.

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

I'm not saying you're wrong — I'm completely ignorant at the microcode level — but it seems to me like between cmp x, y je z and cmp x, y sete z the actual speculative part is the same: speculating as to the result of cmp x, y If that's true, why would it not simply pipeline sete and the following instructions and simply execute (or not execute) sete according to its prediction, and then double check itself and rever…

Taking the example:

      cmpb $115, %cl
      sete %dl
      addl %edx, %eax
vs

      cmpb $115, %cl
      jne _run_switches_jmptgt1
      mov $1,   %dl
     _run_switches_jmptgt1:  
      addl %edx, %eax
The argument about why `jne` might be faster is that that in the former case, the CPU always executes a dependency chain of length 3: `cmpb` -> `sete` -> `addl`. Each of these instructions have to be computed one after the other, as `sete` depends on the result of `cmpb`, and `addl` depends on the result of `sete`.

With `jne`, the CPU might predict the branch is not taken, in which case, the dependency chain is `mov` -> `addl` (the `mov` of an immediate might be handled by register renaming?).

Or that it is taken, in which case in which case the dependency chain is just `addl`.

I guess you're arguing that the CPU should handle `sete` the same way? That is, instead of treating `addl` as dependent on the result, predict what `sete` does and start executing `addl` before `sete` finishes, rewinding if that went wrong?

Re: {n} times faster than C

#123

Post by aengvs »

414owen wrote: post #74
cjensen wrote: post #35

Earlier quoted context omitted.

The problem is the author of the article is making some huge implicit assumptions that the compiler can't possibly know about. Consider this statement: "However, we know some things about this loop. We know that the only time we break out of it is when we hit the null terminator (’\0’). The code clang generates checks for the null terminator first, but this makes no sense." This statement contains huge assumptions ab…

That's the thing, a C compiler has all the information it needs to know that the maximum amount of times a '\0' can be processed in the loop is once (because the function returns), but there's no upper bound on the amount of times other characters are seen in the loop. I might be missing a reason that this information of opaque to the compiler though, in which case, this section of the article is indeed lacking, but…

It's not the upper bound that matters but the frequency. How frequently should the compiler assume an 's' appears in the dataset, or any other character?

We know that E[# of '\0' in a string] == 1.

But what is E[# of 's' in a string]? Is it greater or less than E[# of '\0' in a string], and how should the compiler know this?

You haven't given the compiler any reason to assume that 's' or 'p' will appear more often than '\0'.

Re: {n} times faster than C

#124

Post by nwallin »

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.

Speculative execution is all about control flow. It's about what value is in the instruction pointer at some nebulous point in the future.

A conditional jump can put one of two values into the instruction pointer, they will either increment the instruction pointer (jump not taken) or put the immediate value into the instruction pointer. (jump taken)

cmov/sete are utterly deterministic; they always increment the instruction pointer. There's nothing to speculate on, there's nothing to predict. They just go to the next instruction.

Re: {n} times faster than C

#125

Post by nwallin »

utopcell wrote: post #121
nwallin wrote: post #119

Earlier quoted context omitted.

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 #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; } re…

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.

Oh. Found it. It's because I wasn't using strlen and had been passing over the length of the buffer instead of the length of the string. Only my code had the off by 1.

Re: {n} times faster than C

#126

Post by shusaku »

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…

You forgot an important line of the code:

/* DON’T REFACTOR THIS FOR READABILITY IT WILL SLOW DOWN */

Re: {n} times faster than C

#127

Post by utopcell »

bluedevilzn wrote: post #107
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…

What’s a good source to learn and practice AVX?

You could study Google's Highway library [1].

[1] https://github.com/google/highway

Re: {n} times faster than C

#128

Post by kazinator »

nwallin wrote: post #124
Lk7Of3vfJS2n wrote: post #81

Earlier quoted context omitted.

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

Speculative execution is all about control flow. It's about what value is in the instruction pointer at some nebulous point in the future. A conditional jump can put one of two values into the instruction pointer, they will either increment the instruction pointer (jump not taken) or put the immediate value into the instruction pointer. (jump taken) cmov/sete are utterly deterministic; they always increment the instr…

> Speculative execution is all about control flow. It's about what value is in the instruction pointer at some nebulous point in the future.

.. and all about what we can wheedle out of all the background speculation that will help us get root on this box.

Re: {n} times faster than C

#129

Post by saagarjha »

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.”

Someone has to teach the compiler how to be clever.
Post reply on HN