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

101–110 of 249 posts

Re: {n} times faster than C

#101

Post by hinkley »

kstrauser wrote: post #94
JohnMakin wrote: post #85

Earlier quoted context omitted.

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

How many brains has the Fibonacci example broken...

You'd unroll it to a loop on both C and Python. Fibonacci doesn't need a cache. It needs K previous values, where K=1.

Re: {n} times faster than C

#102

Post by MobiusHorizons »

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…

Jumps are slower on completely random input. If I understand Linus’s point correctly, he is suggesting that random inputs like this are unusual (although a good way to measure worst case performance)

Re: {n} times faster than C

#103

Post by sh34r »

bombcar wrote: post #93
jdsalaro wrote: post #90

Earlier quoted context omitted.

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.

Anyone with a passing understanding of Assembly or compilers would find that idea laughable. As for the others, it turns out not knowing what you don’t know can be very expensive.

Re: {n} times faster than C

#104

Post by Tempest1981 »

sriku wrote: post #95
414owen wrote: post #51

Earlier quoted context omitted.

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!

While `false` evaluates to 0, not sure `true` always evaluate to 1 in C... maybe compiler dependent. Maybe add `? 1 : 0`

Re: {n} times faster than C

#105

Post by kstrauser »

hinkley wrote: post #101
kstrauser wrote: post #94

Earlier quoted context omitted.

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

How many brains has the Fibonacci example broken... You'd unroll it to a loop on both C and Python. Fibonacci doesn't need a cache. It needs K previous values, where K=1.

Yeah, I almost said “suppose you were writing a Fibonacci program because who did you annoy to make this your life now...”

Like, obviously you’re not going to be writing `fib(n)` for real. I still claim that other languages — not just Python, either — make it easier to express cleverer algorithms than C does. You can’t write anything in Rust you can’t write in C, but it’ll probably be easier to say it more efficiently, and more correctly, in Rust. And much of the time, using a better design is going to blow compiler improvements out of the water.

(The professor was right if you limit the scope of the statement to “programs written in C or assembler”, of course. Unless you’re a freaking genius, a compiler’s going to write better object code.)

Re: {n} times faster than C

#107

Post by bluedevilzn »

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?

Re: {n} times faster than C

#108

Post by sitkack »

Tuna-Fish wrote: post #91
Lk7Of3vfJS2n wrote: post #81

Earlier quoted context omitted.

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

I hope you work on compiler backends.

Re: {n} times faster than C

#109

Post by aengvs »

414owen wrote: post #43
eklitzke wrote: post #6

Rearranging branches (and perhaps blocks too?) will definitely be done if you are building using FDO, because without FDO (or PGO) the compiler has no idea how likely each branch is to be taken. Cmov can also be enabled by FDO in some cases. However, whether or not using cmov is effective compared to a regular test/jump is highly dependent on how predictable the branch is, with cmov typically performing better when t…

> because without FDO (or PGO) the compiler has no idea how likely each branch is to be taken So, the maximum amount of times you can hit '\0' is once in the string, because then the function returns, but you can hit the other characters many times, which seems to be information a compiler has access to without PGO. PGO does help, of course, and on my machine gives me 2.80s, which is better than the code at the end o…

Imagine a scenario where most of the strings being processed contain a single null character, with no other characters. In that case checking for the null character first would be optimal.

Does the compiler know that this isn't true? No, it doesn't. The author of the article is making an assumption about the contents of the data that might seem reasonable but isn't necessarily true.

Re: {n} times faster than C

#110

Post by Guvante »

torstenvl wrote: post #72
AnotherGoodName wrote: post #71

Earlier quoted context omitted.

The inputs here are random which is the problem and why this isn't demonstrating that. Create an input of all 's' and compare it.

Better than random input, but still only ~half as fast as using sete [19:13:34 user@boxer ~/src/looptest] $ diff -u bench.c bench-alls.c --- bench.c 2023-07-06 16:04:16.000000000 -0400 +++ bench-alls.c 2023-07-06 19:13:34.000000000 -0400 @@ -17,7 +17,7 @@ int num_rand_calls = number / CHAR_BIT + 1; unsigned char *buffer = malloc(num_rand_calls * CHAR_BIT); for (int i = 0; i Jumps are slower.

Microbenchmarks are hard. You aren't doing any meaningful work that could benefit from speculatively executing instead of stalling for the conditional value.

Similarly you might be busting the pipeline by chaining together the jumps so close together.

Not saying your point is wrong, just saying your proof isn't super solid.

Post reply on HN