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

61–70 of 249 posts

Re: {n} times faster than C

#61

Post by haberman »

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…

> 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 control flow speculation, but not conditional move speculation. I don't know if conditional move speculation would be a feasible thing to implement or not, but I'm pretty sure that no mainstream CPUs have such a feature.

Re: {n} times faster than C

#62

Post by lukas099 »

Would it be possible to write a code profiler and compiler that work together to optimize code based on real-world data? The profiler would output data that would feed back into the compiler, telling it which branches were selected most often, which would recompile optimizing for the profile. Would this even work? Has it already been done?

Re: {n} times faster than C

#63

Post by gavinray »

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…

Do you know if this is possible using "std::experimental::simd" out of curiosity?

https://en.cppreference.com/w/cpp/experimental/simd

Re: {n} times faster than C

#64

Post by xoranth »

414owen wrote: post #59
xoranth wrote: post #49

I think I managed to improve on both this post, and its sequel, at the cost of specializing the function for the case of a string made only of 's' and 'p'. The benchmark only tests strings made of 's' and 'p', so I think it is fair. The idea is as follow. We want to increase `res` by one when the next character is `s`. Naively, we might try something like this: res += (c - 'r'); // is `res += 1` when c == 's' This do…

Very interesting approach. I should probably have specified that the somewhat naive assembly in `02-the-same-speed-as-c/loop-5.x64.s` is the fastest version I have. On my machine I'm getting 0.244s for `loop-5.x64.s` and 0.422s for your implementation above. I'm not sure why exactly we're seeing this discrepancy, and for what it's worth your implementation looks faster to me. I guess this is why you need to always be…

I rerun the benchmark vs loop-5 and loop-7 from the second post. Runtime is basically the same on my machine.

I would have expected yours to be faster given that it needs to execute fewer instructions per loop iteration. Though maybe the CPU can run `adc` on more ports compared to a load from memory?

    Summary
      '01-six-times-faster-than-c/bench-x64-8 1000 1' ran
        1.00 ± 0.00 times faster than '02-the-same-speed-as-c/bench-x64-7 1000 1'
        1.66 ± 0.00 times faster than '01-six-times-faster-than-c/bench-x64-7 1000 1'

    Summary
      '01-six-times-faster-than-c/bench-x64-8 1000 1' ran
        1.01 ± 0.00 times faster than '02-the-same-speed-as-c/bench-x64-5 1000 1'
        1.66 ± 0.00 times faster than '01-six-times-faster-than-c/bench-x64-7 1000 1'

Re: {n} times faster than C

#65

Post by p1necone »

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…

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.

Re: {n} times faster than C

#66

Post by sltkr »

How much faster is this:

    int run_switches(const char *buf) {
       size_t len = strlen(buf);
       int res = 0;
       for (size_t i = 0; i
strlen() should be implemented in a pretty fast way, and after the buffer size is known, the compiler can autovectorize the inner loop, which does happen in practice: https://gcc.godbolt.org/z/qYfadPYoq

Re: {n} times faster than C

#68

Post by AnotherGoodName »

DeathArrow wrote: post #24
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…

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

It's not true in general.

In general branching code is faster than branchless code and there's many many places that will demonstrate this with a quick Google. You know how many cycles a correctly predicted branch takes? 0.

On the other hand branchless code has to wait for each calculation to reach a certain stage in the pipeline since the thing to be output is dependent on the result. The CPU will have a whole lot of halts.

So why is this faster? Because the input is literally random(). The branch predictor will be wrong. This isn't normal though. The compiler is creating code that will be faster in most normal use cases.

It's an artificial benchmark that works against the output the compiler produces.

Re: {n} times faster than C

#69

Post by Const-me »

gavinray wrote: post #63
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…

Do you know if this is possible using "std::experimental::simd" out of curiosity? https://en.cppreference.com/w/cpp/experimental/simd

I don’t have any experience with that library.

Still, based on the documentation you have linked, I’m not sure it could possibly generate some code similar to my version. I could be wrong but I don’t see APIs which aggregate or accumulate the `simd_mask` vectors they output for results of vector comparisons.

Re: {n} times faster than C

#70

Post by garenp »

lukas099 wrote: post #62

Would it be possible to write a code profiler and compiler that work together to optimize code based on real-world data? The profiler would output data that would feed back into the compiler, telling it which branches were selected most often, which would recompile optimizing for the profile. Would this even work? Has it already been done?

It's a thing: https://en.wikipedia.org/wiki/Profile-guided_optimization
Post reply on HN