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

31–40 of 249 posts

Re: {n} times faster than C

#31

Post by aidenn0 »

moonchild wrote: post #18
aidenn0 wrote: post #5

A while back, I wrote a UTF-8 decoder in Common Lisp, targeting SBCL (it already has one built in, this was an exercise). Pretty much all of the optimization win (after the obvious low-hanging fruit) was structuring the code so that the compiler would generate cmov* instructions rather than branches.

Branches are prone to be faster than conditional moves if they are correctly predicted, because they do not increase the critical path length. And utf-8 decoders are commonly run on all-ascii input. What were you benchmarking on?

I ran separate benchmarks on all-ASCII, BMP-only, and ascii with non-BMP. ASCII was not slower on the low-branch version.

Re: {n} times faster than C

#32

Post by camel-cdr »

dzaima wrote: post #16
camel-cdr wrote: post #10

I threw together a quick risc-v vectorized implementation: size_t run(char *str) { uint8_t *p = (uint8_t*)str; long end = 0; size_t res = 0, vl; while (1) { vl = __riscv_vsetvlmax_e8m8(); vuint8m8_t v = __riscv_vle8ff_v_u8m8(p, &vl, vl); end = __riscv_vfirst_m_b1(__riscv_vmseq_vx_u8m8_b1(v, '\0', vl), vl); if (end >= 0) break; res += __riscv_vcpop_m_b1(__riscv_vmseq_vx_u8m8_b1(v, 's', vl), vl); res -= __riscv_vcpop_m…

To be fully correct, you'd need the load to be a fault-only-first load (which rvv does have), otherwise that could fail if the null byte was just before the end of allocated memory.

I just found your rvv intrinsics-viewer [0], that'll be so helpful.

I tried building one, my self, but my miserable web skills didn't allow me to lazily load the instructions, which made it too slow for actual use.

Can I share your project on lemmy?

[0] https://dzaima.github.io/intrinsics-viewer

Re: {n} times faster than C

#33

Post by ftxbro »

twoodfin wrote: post #30
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?

This is the right answer: https://news.ycombinator.com/item?id=36622584 Optimal assembly (forgoing SIMD, at least) for this loop on modern x86 is highly dependent on the entropy of the runtime data.

OK so they were abusing the benchmark, like the compiler's output would be faster on less contrived test data? Do I have to search what are fdo or pgo or cmov to understand the answer?

Re: {n} times faster than C

#35

Post by cjensen »

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?

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 about the lengths of the input strings and the frequency of the letters 's' and 'p' in the input. And then has the chutzpah to call the compiler's failure to read his mind about this as "making no sense."

Good first effort by the author, but has not sufficiently thought through the problem.

Re: {n} times faster than C

#36

Post by moonchild »

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?

> 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 compiler has been somewhat shafted here because it doesn't know what sorts of inputs the function usually receives. The compiler output is better than the 'improved' code for some inputs. (It's possible you could get a better result from the existing compilers and c code just by using profile-guided optimisation.)

- The difference is prone to be more pronounced in simple loops than large ones. This is a contrived use-case. There is not a factor of 6 of performance hiding in optimised c code which could be recovered by doing the sorts of optimisations done by the op. Probably something more like 10-20%.

Re: {n} times faster than C

#37

Post by darig »

jonny_eh wrote: post #29
nwallin wrote: post #22

IMHO the original code wasn't written in a way that's particularly friendly to compilers. If you write it like this: int run_switches_branchless(const char* s) { int result = 0; for (; *s; ++s) { result += *s == 's'; result -= *s == 'p'; } return result; } ...the compiler will do all the branchless sete/cmov stuff as it sees fit. It will be the same speed as the optimized assembly in the post, +/- something insignifi…

> But you really really probably shouldn't. Shouldn't "not" keep track of string length?

[dead]

Re: {n} times faster than C

#38

Post by dzaima »

camel-cdr wrote: post #27
dzaima wrote: post #16

Earlier quoted context omitted.

To be fully correct, you'd need the load to be a fault-only-first load (which rvv does have), otherwise that could fail if the null byte was just before the end of allocated memory.

I'm not sure I fully understand fault-only-first load, but reading the description of vle8ff.v I think I only need to exchange the load inside of the loop? How does the normal load deal with faults? I'll update the parent comment, it slowed down the speed from 2/1.7 to 1.57/1.36 Bytes/Cycle.

You'd probably want to have a new __riscv_vsetvlmax_e8m8 at the start of each loop iteration, as otherwise an earlier iteration could cut off the vl (e.g. page unloaded by the OS), and thus the loop continues with the truncated vl.

The normal load should just segfault if any loaded byte is outside of readable memory, same as with a scalar load which is similarly partly outside.

Re: {n} times faster than C

#39

Post by ModernMech »

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?

Yes, there’s always the “sufficiently smart compiler” that can generate this code. Question is, does that compiler exist?

Re: {n} times faster than C

#40

Post by nwallin »

jonny_eh wrote: post #29
nwallin wrote: post #22

IMHO the original code wasn't written in a way that's particularly friendly to compilers. If you write it like this: int run_switches_branchless(const char* s) { int result = 0; for (; *s; ++s) { result += *s == 's'; result -= *s == 'p'; } return result; } ...the compiler will do all the branchless sete/cmov stuff as it sees fit. It will be the same speed as the optimized assembly in the post, +/- something insignifi…

> But you really really probably shouldn't. Shouldn't "not" keep track of string length?

Err... yes. You shouldn't not keep track of string/buffer sizes.
Post reply on HN