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

171–180 of 249 posts

Re: {n} times faster than C

#171

Post by bjourne »

haberman wrote: post #136
bjourne wrote: post #97

Earlier quoted context omitted.

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

You are correct, I should have clarified, subsequent instructions that depend on the result of the cmov cannot execute until the cmov has executed. Whereas subsequent instructions that depend on the result of the branch instruction can be speculatively executed even before the branch conditional has been evaluated.

True, but independently of whether "cmov rax, ..." or "jnz L; mov rax, ...; L:" is used, subsequent instructions that reads rax needs to stall until rax has been written to (or at least until cmov/mov has executed if bypasses are used).

Re: {n} times faster than C

#172

Post by zokier »

aengvs wrote: post #109
414owen wrote: post #43

Earlier quoted context omitted.

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

But because in the single-null case the loop body is executed only once, the gains of arrangement that prefers nulls are pretty slim compared to long-string cases where the loop body is executed many times. For example if your dataset contains 99 cases of single null strings and one case of 100 chars long string, it might still be optimal on aggregate to use the long-string optimizing arrangement.

Of course there are still some cases where non-zero strings are extremely rare and as such optimizing for those makes sense.

Re: {n} times faster than C

#173

Post by fuber2018 »

gpderetta wrote: post #156
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…

Even simpler: just sum all elements of the array. Then at the end subtract 'p'*len from the sum, then divide by ('s'-'p') to get the s count. The 'p' count is len minus the 's' count. The initial sum is easily vectorized as well. If I've not made any mistakes it should work. Only issue is possible overflow on the running sum. Can't be bothered to benchmark it though:). edit: missed the decrement when you see 's'. So…

I took the 64-bit SWAR ('S'IMD-'W'ithin-'A'-'R'egister) road and passed in the string length - the calling code has the length "right there"!!!

Using the original run_switches function, app took 3.554s (average of 10 runs).

With the SWAR-version with the string length passed in, app took 0.117s (average of 10 runs).

That's an overall 27.6x speedup.

Re: {n} times faster than C

#174

Post by kierank »

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?

FFmpeg has a lot of assembly language that can be added to:

https://blogs.gnome.org/rbultje/2017/07/14/writing-x86-simd-...

Re: {n} times faster than C

#175

Post by zokier »

ftxbro wrote: post #20
414owen wrote: post #2

A clickbait title for an in-depth look at hand-optimizing a very simple loop.

I'm not a compiler expert but if it's a "very simple loop" is it still too complex for the compiler to make good machine code? Did they use a bad compiler on purpose? Or are computers just not yet fast enough to do a good job with very simple loops in practical compilers?

I wonder what superoptimizers like stoke and souper would do with this code.

Re: {n} times faster than C

#176

Post by einpoklum »

A very instructional post. I wish more people had such a level of mastery of GPU assembly and its effects, and would post such treatments on outsmarting NVIDIA's (or AMD's) optimizers.

Re: {n} times faster than C

#177

Post by kaba0 »

EVa5I7bHFq9mnYK wrote: post #167
gpderetta wrote: post #146

Earlier quoted context omitted.

Indeed. The cost of bound checking is second order effects like making vectorization harder, slightly higher instruction (and possibly data) cache pressure, or requiring higher decode bandwidth. For the vast majority of programs these bottlenecks do not really matter.

I mean, if the innermost loop is something like 3 assembly instructions, two extra instructions cmp and jg do not make any difference, if jg never executes?

I am by no means an expert, but I believe what you have in mind would likely fit in i-cache without a problem, so you wouldn’t see a significant difference.

There is an interesting talk titled ‘the death of optimizing compilers’ that argues that for most code these optimizations are almost completely meaningless, and in the hot loops where it actually matters, they are not good compared to humans (and sometimes 100x or more improvements are possible and left on the table). While I don’t completely agree with its points, it is a good talk/slides to read through.

Re: {n} times faster than C

#178

Post by stkdump »

sweetjuly wrote: post #158
romnon wrote: post #135

Earlier quoted context omitted.

ive seen people doing += !!(c=='s')-!!(c=='p') for that

I'm sure people do that (even though it's not necessary per some year C standard) but generally the pattern is actually for converting things which are not already 0 or 1 into 0 or 1. For example, you might want to use it here: int num_empty_strings = !!(strlen(s1)) + !!(strlen(s2)) + !!(strlen(s3)) which is equivalent to: int num_empty_strings = (strlen(s1) != 0) + (strlen(s2) != 0) + (strlen(s3) != 0) Which you use…

If we are being cryptic already, why not

    int num_empty_strings = !!*s1 + !!*s2 + !!*s3;

Re: {n} times faster than C

#179

Post by gpderetta »

EVa5I7bHFq9mnYK wrote: post #167
gpderetta wrote: post #146

Earlier quoted context omitted.

Indeed. The cost of bound checking is second order effects like making vectorization harder, slightly higher instruction (and possibly data) cache pressure, or requiring higher decode bandwidth. For the vast majority of programs these bottlenecks do not really matter.

I mean, if the innermost loop is something like 3 assembly instructions, two extra instructions cmp and jg do not make any difference, if jg never executes?

If they are not in the critical path, it doesn't matter. There is no instruction cache issues as the loop is tiny. Also as the loop is tiny it will fit in the u-op cache (or even in the loop cache), so decoding is not an issue either. The only problem is potential lack of vectorization, but a good vector ISA can in principle handle the bound checking with masked reads and writes (but now the check is no longer a predictable branch, but it might end up in the critical path, although it is not necessarily a big cost, or even measurable, anyway).

Re: {n} times faster than C

#180

Post by fuber2018 »

fuber2018 wrote: post #173
gpderetta wrote: post #156

Earlier quoted context omitted.

Even simpler: just sum all elements of the array. Then at the end subtract 'p'*len from the sum, then divide by ('s'-'p') to get the s count. The 'p' count is len minus the 's' count. The initial sum is easily vectorized as well. If I've not made any mistakes it should work. Only issue is possible overflow on the running sum. Can't be bothered to benchmark it though:). edit: missed the decrement when you see 's'. So…

I took the 64-bit SWAR ('S'IMD-'W'ithin-'A'-'R'egister) road and passed in the string length - the calling code has the length "right there"!!! Using the original run_switches function, app took 3.554s (average of 10 runs). With the SWAR-version with the string length passed in, app took 0.117s (average of 10 runs). That's an overall 27.6x speedup.

If I unroll the main while loop to handle 4x as much each time through the loop in the SWAR-version, the runtime drops to 0.0562s (average 10 runs).

That's an overall 57.5x speedup.

Post reply on HN