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

71–80 of 249 posts

Re: {n} times faster than C

#71

Post by AnotherGoodName »

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…

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.

Re: {n} times faster than C

#72

Post by torstenvl »

AnotherGoodName wrote: post #71
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…

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.

Re: {n} times faster than C

#73

Post by [deleted] »

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…

[deleted]

Re: {n} times faster than C

#74

Post by 414owen »

cjensen wrote: post #35
ftxbro wrote: post #20

Earlier quoted context omitted.

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?

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 I'm happy to learn :)

Re: {n} times faster than C

#75

Post by xoranth »

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…

Interesting. I think you can vectorize the prologue using movemask + popcnt instead of keeping a counter in the ymm registers (warning: untested code, still need to benchmark it):

    const __m256i zero = _mm256_setzero_si256();
    const __m256i s = _mm256_set1_epi8( 's' );
    const __m256i p = _mm256_set1_epi8( 'p' );

    const size_t a = (size_t)input;
    const size_t rem = a % 32;
    const char* aligned = input - rem;

    const __m256i v = _mm256_load_si256(( const __m256i*) input);
    const __m256i z = _mm256_cmpeq_epi8( v, zero );

    size_t m_plus = _mm256_movemask_epi8(_mm_cmpeq_epi8(v, s));
    size_t m_minus = _mm256_movemask_epi8(_mm_cmpeq_epi8(v, p));
    size_t m_zero = _mm256_movemask_epi8(_mm_cmpeq_epi8(v, z));
    size_t offset_zero = _mm_tzcnt_64(m_zero >> rem);

    m_plus = _bzhi_u64(m_plus >> rem, offset_zero);
    m_minus = _bzhi_u64(m_minus >> rem, offset_zero);

    // Skip loop we already found the end of the string...
    while (m_zero == 0) {
        // ...
    }
    
    // ...
    
    return m_plus + res - m_minus;

Re: {n} times faster than C

#76

Post by [deleted] »

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.

[deleted]

Re: {n} times faster than C

#77

Post by smcin »

cjensen wrote: post #35
ftxbro wrote: post #20

Earlier quoted context omitted.

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?

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…

Ok the author should have written "this makes no sense... on this particular case"

Re: {n} times faster than C

#78

Post by Karellen »

p1necone wrote: post #65
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.

It shouldn't be.

If the fastest way to implement a particular `switch` in assembly is with the equivalent of a set of `if`s, a reasonably smart compiler "should" be able to output the assembly to do that. And I thought that gcc and clang at least have actually been smart enough to do that for a while now.

But if the number of `if`s is high and the distribution sufficiently dense, where a jump table is better than a bunch of `if`s, then a `switch` should output that.

OTOH, a sufficiently smart compiler could theoretically turn a bunch of `if`s into a `switch`-like jump table - but it's much harder to reason that case through correctly than it is the other way, so I'm not sure any current compilers are sufficiently smart to do that.

Re: {n} times faster than C

#79

Post by 414owen »

svachalek wrote: post #26
BoppreH wrote: post #19

You can also use math to avoid most of the jumps: int run_switches(char *input) { int res = 0; while (true) { char c = *input++; if (c == '\0') return res; // Here's the trick: res += (c == 's') - (c == 'p'); } } This gives a 3.7x speed compared to loop-1.c. The lower line count is also nice.

Nice. The way I read the cmove version, it's more or less this except the trick line goes res += (c == 's') ? 1 : (c == 'p') ? -1 : 0 I haven't done C in decades so I don't trust myself to performance test this but I'm curious how it compares. Pretty disappointed that TFA didn't go back and try that in C.

So I actually did try that, but and IIRC it didn't produce a CMOV with either gcc or clang. I didn't put it in the repo because it wasn't an improvement (on my machine) and I decided not to write about it.

Maybe you get different results though?

Re: {n} times faster than C

#80

Post by cjensen »

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 just that the C compiler lacks the information... but the reader of this article also lacks this information.

String length tells you the frequency with which nul terminators will be found. Without knowing frequency of occurrence of the nul terminator, 's', and 'p' then you cannot know which one occurs most often.

Consider two benchmark cases: (1) every string tested contains exactly one character (2) every string tested is 1MB long and is composed entirely of 's' and 'p'.

The author's first "optimization" assumes nul is rare. It would make benchmark (1) worse, and (2) better.

The article is a good example of "specification is hard, code is easy." He insufficiently specified the problem to be solved, and his test cases contained information not in the code and not in the text of the article.

Post reply on HN