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

231–240 of 249 posts

Re: {n} times faster than C

#231

Post by agumonkey »

torstenvl wrote: post #219
agumonkey wrote: post #211

Earlier quoted context omitted.

well then there's a magical bit somewhere since both assembly listing are identical

Yes, the assembly listings are identical. I was very clear that the error was in the pseudocode. That is why I said "There's an error in the pseudocode." There's nothing "magical" about paying attention before condescending to someone.

Oh my bad, I was not condescending, I simply misread your comment and was then very confused after your first answer.

I know I'm the less knowledgeable here, and even then there's nothing to gain in criticizing someone like this online.

Sorry again :)

Re: {n} times faster than C

#232

Post by utopcell »

teo_zero wrote: post #139
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; }

But this is not the original problem! Only p's should decrease the counter, in your code every non-s does.

The original problem was working on strings that only hold 's' and 'p' characters, as seen in bench.c. The first implementation checked against 's' and 'p' specifically, and all subsequent version optimized that first version.

Re: {n} times faster than C

#233

Post by moonchild »

bruce343434 wrote: post #218
moonchild wrote: post #36

Earlier quoted context omitted.

> are computers just not yet fast enough to do a good job with very simple loops in practical compilers? The short answer to this question is 'yes', but there are some extenuating factors: - Although we could do interesting things with unlimited computational resources, the current crop of c compilers is simply not very good, compared with what's possible today. - Performance is always workload-dependent; the compile…

> the current crop of c compilers is simply not very good, compared with what's possible today. That's quite dismissive. What exactly "is possible today" and why aren't these top compilers using them?

One prominent example: the use of intermediate representations based on basic blocks introduces redundancies that increase the complexity of the compiler, requiring attendant redundancies in order to optimise the same. You can see the redundancy manifest here https://godbolt.org/z/8o3oe39hh as different code generation from f and g. (They may change the result of this particular test in the future, but it seems unlikely that the disease—rather than the symptom—can be treated without a complete rearchitecture.)

E-graphs ameliorate phase ordering issues and allow for exploring the space of non-monotonic rewrites; recent research makes them computationally viable.

Put simply: it's legacy. Gcc and llvm are millions of lines of code, and they assume a particular architecture. Changing that is not easy.

Another issue, which I did not mention (but which is pertinent) is that c is a poor language for compilation. (Fran allen famously said 'c has destroyed our ability to advance the state of the art'.) In some respects, the optimisations performed automatically by modern high-performance cpus are more sophisticated than those done by c compilers, howbeit with less reach; the only reason they are able to do this is that they have direct control of the execution and hence have a greater ability to abstract over the side effects which are rampant in most c code.

Re: {n} times faster than C

#234

Post by stkdump »

LegionMammal978 wrote: post #206
gjm11 wrote: post #200

Earlier quoted context omitted.

That isn't only more cryptic, it's also potentially a lot more efficient -- strlen takes time proportional to the length of the string, which of course you don't need to do if you only care whether or not the length is zero. You shouldn't use strlen for empty-string tests.

In practice, GCC and Clang don't seem to have any issues inlining the necessary part of strlen at -O1 or higher ( https://godbolt.org/z/rM198aYea ). But MSVC inlines the empty-string case, while still calling out for nonempty strings, probably since it doesn't realize that the returned length will be nonzero.

I guess since strlen uses an unsigned size, which has specified overflow behavior the compiler not only has to proof the initial iteration, but also all the ULLONG_MAX+1 multiples, which of course refer to the same memory address. But maybe its harder for the optimizer to see.

Re: {n} times faster than C

#236

Post by rajnathani »

414owen wrote: post #51
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…

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.

Great post!

One thought: If the code is rewritten using bit arithmetic, then potentially the result could be even faster as there need not be a pointer look-up.

A bit arithmetic solution would have a mask created for the characters ‘p’ and ‘s’, and then the result could be AND-ed, and then with more bit arithmetic this all 1s value can be translated to a 1 if and only if all the bits are 1. Following which, there would be a no conditional check and simply be both an add and a subtract operation but where the value to be added will only be 1 if the mask for ‘p’ matches and 1 to be subtracted if the mask for ‘s’ matches respectively. I’m not fully sure if this would necessarily be faster than the pointer look-up solution, but it would be interested to try this version of the code and see how fast it performs.

Update: The bit arithmetic could also be done with an XOR on the mask, and following which the ‘popcnt’ x86 instruction could be used to figure out if all are 0 bits.

Re: {n} times faster than C

#237

Post by rajnathani »

nwallin wrote: post #87
414owen wrote: post #47

Earlier quoted context omitted.

The version that's friendly to the compiler is described in part two: https://owen.cafe/posts/the-same-speed-as-c/ It achieves 3.88GiB/s I intentionally didn't go down the route of vectorizing. I wanted to keep the scope of the problem small, and show off the assembly tips and tricks in the post, but maybe there's potential for a future post, where I pad the input string and vectorize the algorithm :)

So I downloaded your code. On my desktop, with loop-9 gcc I got ~4.5GB/s, and with loop-7 I got ~4.4GB/s. With the following code: #include int run_switches(const char *s, size_t n) { int res = 0; for (; n--; ++s) res += (*s == 's') - (*s == 'p'); return res; } I got ~31GB/s in GCC and ~33GB/s in Clang. This is without any padding, or SIMD intrinsics, or any such nonsense. This is just untying the compiler's hands an…

This seems like the most efficient solution. I have a neighboring comment on this post which suggests using bit arithmetic, but the above solution is more efficient than that. Here’s what the assembly code for the body of the first loop compiles down to (I had to use ChatGPT-4 as godbolt unfortunately doesn’t work on mobile):

    cmp dl, 's'    ; Compare the character with 's'
    sete dl        ; If the character is 's', set dl to 1. Otherwise, set dl to 0.
    sub al, dl     ; Subtract the result from res

    cmp dl, 'p'    ; Compare the character with 'p'
    sete dl        ; If the character is 'p', set dl to 1. Otherwise, set dl to 0.
    add al, dl     ; Add the result to res

Re: {n} times faster than C

#238

Post by bruce343434 »

moonchild wrote: post #233
bruce343434 wrote: post #218

Earlier quoted context omitted.

> the current crop of c compilers is simply not very good, compared with what's possible today. That's quite dismissive. What exactly "is possible today" and why aren't these top compilers using them?

One prominent example: the use of intermediate representations based on basic blocks introduces redundancies that increase the complexity of the compiler, requiring attendant redundancies in order to optimise the same. You can see the redundancy manifest here https://godbolt.org/z/8o3oe39hh as different code generation from f and g. (They may change the result of this particular test in the future, but it seems unlik…

E-graphs are interesting, but one still has to deal with combinatorial explosions. Are you alluding to some powerful search heuristic?

Your example touches on the problems of inflexible ABI, namely caller saved registers and the unknowability of side effects of external functions. Very weird that it can't reorder `r = x+y` despite it having no "observable" side effect until `return r`, since that return dominates the assignment, and there's no real relation between (the return, assignment) and (eff()).

Re: {n} times faster than C

#239

Post by bruce343434 »

bruce343434 wrote: post #238
moonchild wrote: post #233

Earlier quoted context omitted.

One prominent example: the use of intermediate representations based on basic blocks introduces redundancies that increase the complexity of the compiler, requiring attendant redundancies in order to optimise the same. You can see the redundancy manifest here https://godbolt.org/z/8o3oe39hh as different code generation from f and g. (They may change the result of this particular test in the future, but it seems unlik…

E-graphs are interesting, but one still has to deal with combinatorial explosions. Are you alluding to some powerful search heuristic? Your example touches on the problems of inflexible ABI, namely caller saved registers and the unknowability of side effects of external functions. Very weird that it can't reorder `r = x+y` despite it having no "observable" side effect until `return r`, since that return dominates the…

I looked at it closer. In C, it is a side effect to assign to a variable. For an extern function not annotated __attribute__((pure)) the compiler has to assume the function call generates side effects. This prevents it from reordering the assignment and function call. Since x86-64 ABI has caller saved registers, in the case where it calls eff() first, it has to save x and y, and after the call, restore them.

Re: {n} times faster than C

#240

Post by sitkack »

epcoa wrote: post #114
sitkack wrote: post #108

Earlier quoted context omitted.

I hope you work on compiler backends.

With all due respect this is quite literally the level of stuff covered in an undergrad EE architecture course and is covered in an elementary text like Patterson and Hennessy.

> With all due respect

> quite literally

You could have conveyed the close to the same thing by saying, "things like this are covered in Patterson and Hennessy"

> elementary text

Jesus, do you even lift? The rest of the discussion is amazing.

Post reply on HN