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

201–210 of 249 posts

Re: {n} times faster than C

#201

Post by gpderetta »

orlp wrote: post #189

I made a variant that is (on my Apple m1 machine) 20x faster than the naive C version in the blog by branchlessly processing the string word-by-word: int run_switches(const char* input) { int res = 0; // Align to word boundary. while ((uintptr_t) input % sizeof(size_t)) { char c = *input++; res += c == 's'; res -= c == 'p'; if (c == 0) return res; } // Process word-by-word. const size_t ONES = ((size_t) -1) / 255; //…

If I read it correctly, your implementation might read beyond the end of the buffer, and if it crosses a page boundary into an unmapped page, it will segfault. That's one of the many evils of null terminated strings.

Re: {n} times faster than C

#202

Post by gpderetta »

failuser wrote: post #21

Having a full-blown predicate support is so nice to have, but it interferes with compact instruction encoding. Such bloated ISA like x86 might actually handle predicate support, but who will try such a radical change?

AVX512?

Also the original ARM 32 bit instruction sent had extensive predication.

Re: {n} times faster than C

#203

Post by orlp »

gpderetta wrote: post #201
orlp wrote: post #189

I made a variant that is (on my Apple m1 machine) 20x faster than the naive C version in the blog by branchlessly processing the string word-by-word: int run_switches(const char* input) { int res = 0; // Align to word boundary. while ((uintptr_t) input % sizeof(size_t)) { char c = *input++; res += c == 's'; res -= c == 'p'; if (c == 0) return res; } // Process word-by-word. const size_t ONES = ((size_t) -1) / 255; //…

If I read it correctly, your implementation might read beyond the end of the buffer, and if it crosses a page boundary into an unmapped page, it will segfault. That's one of the many evils of null terminated strings.

If we go by the absolute strictest interpretation of the C standard, yes, the above is UB.

But in practice no one has page boundaries that cross word boundaries, and I align to a word boundary before doing the word-by-word loop.

Re: {n} times faster than C

#204

Post by orlp »

fuber2018 wrote: post #196
orlp wrote: post #189

I made a variant that is (on my Apple m1 machine) 20x faster than the naive C version in the blog by branchlessly processing the string word-by-word: int run_switches(const char* input) { int res = 0; // Align to word boundary. while ((uintptr_t) input % sizeof(size_t)) { char c = *input++; res += c == 's'; res -= c == 'p'; if (c == 0) return res; } // Process word-by-word. const size_t ONES = ((size_t) -1) / 255; //…

Almost the same as my SWAR version - which is what you're doing. But aren't you reading off the end of the buffer in your memcpy(&w...)? Say with an empty input string whose start address is aligned to sizeof(size_t) bytes? I just passed in the string length since the caller had that info, otherwise you'd scan the whole string again looking for the zero terminator.

> But aren't you reading off the end of the buffer in your memcpy(&w...)?

If we go by the absolute strictest interpretation of the C standard my above implementation is UB.

But in practice, if p is word-aligned and is at least valid for 1 byte, then you will not pagefault for reading a whole word. In fact, this is how GCC/musl implement strlen itself.

> Say with an empty input string whose start address is aligned to sizeof(size_t) bytes?

Then the start address is valid (it must contain the null byte), and aligned to a word boundary, in which case I assume it is ok to also read a whole word there.

Re: {n} times faster than C

#205

Post by Const-me »

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?

For a starting point, I wrote that article couple years ago: http://const.me/articles/simd/simd.pdf

I don’t recommend assembly. Intrinsics are typically good enough performance wise, and writing correct assembly is hard. For instance, Chromium has non-trivial dependencies with code written in assembly, and they caused tons of fun debugging issues like that https://bugs.chromium.org/p/chromium/issues/detail?id=121838... Using intrinsics would have solved that because modern compilers follow ABI conventions of the target platforms very carefully.

About that highway, I don’t have any experience but based on the documentation I don’t like it too much. They say that’s a thin wrapper over intrinsics, but I believe it still breaks things. Specifically, Intel and ARM don’t document highway, but they have decent documentation on their intrinsics. Similarly, stackoverflow has thousands of questions and answers with tags like SSE and AVX, most of them are related to intrinsics, but nothing related to highway.

Re: {n} times faster than C

#206

Post by LegionMammal978 »

gjm11 wrote: post #200
stkdump wrote: post #178

Earlier quoted context omitted.

If we are being cryptic already, why not int num_empty_strings = !!*s1 + !!*s2 + !!*s3;

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.

Re: {n} times faster than C

#207

Post by gpderetta »

orlp wrote: post #203
gpderetta wrote: post #201

Earlier quoted context omitted.

If I read it correctly, your implementation might read beyond the end of the buffer, and if it crosses a page boundary into an unmapped page, it will segfault. That's one of the many evils of null terminated strings.

If we go by the absolute strictest interpretation of the C standard, yes, the above is UB. But in practice no one has page boundaries that cross word boundaries, and I align to a word boundary before doing the word-by-word loop.

good point of course!

Re: {n} times faster than C

#208

Post by NohatCoder »

bjourne wrote: post #171
haberman wrote: post #136

Earlier quoted context omitted.

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

The difference is that in the case where the condition is false and predicted false the jump variant will not delay if the value being moved into rax is delayed, the cmov variant will. Effectively that value becomes a false dependency.

As best I can tell this case is rare enough that one shouldn't generally be afraid of cmov, and probably compiler authors should consider using it more frequently.

What one shouldn't do is to load values, that are likely in memory or L3, unnecessarily in order to be able to use cmov. It is the case that runs the greatest risk of degrading performance, and it puts extra load on resources that are shared between cores.

Re: {n} times faster than C

#209

Post by MisterTea »

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…

You can shorten the loop to just tree conditionals:

  while (c = *input++) {
      if (c == 's') r++;
      if (c == 'p') r--;
  }

Re: {n} times faster than C

#210

Post by dzaima »

okaleniuk wrote: post #161
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…

Yes, but this will backfire on ARM, where jumps are as roughly fast as conditional arithmetic. The whole point of using C is not to think about the underlying architecture. As soon as you start taking "jumps are a lot slower than conditional arithmetic on x86" into account, you're not writing in C, you're writing in assembly with extra steps :-)

Note, that's only ARMv7; ARMv8 dropped most of the conditionally executed instruction stuff. And so it isn't even jumps that's fast on ARMv7, it's specifically cases that can be (and are) converted to predicated instrs; jumps are still gonna be slow in general on anything high-perf enough that it needs speculation, which can include the actual jumps of ARMv7.

If a compiler can convert jumpy code to the predicated instrs, it should be able to trivially convert conditional arith to such too (even easier & more consistently than branches I'd say).

Post reply on HN