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

221–230 of 249 posts

Re: {n} times faster than C

#221

Post by cjensen »

414owen wrote: post #152
cjensen wrote: post #80

Earlier quoted context omitted.

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…

I guess the question is whether the compiler should optimize a function containing a loop for a single null terminator, or for more data. I would suggest the latter is what you want most of the time. There's also the option of running a quick check for the null terminator before the loop, and then optimizing the loop for the other options. But in any case, I think the demonstration of the technique of rearranging bra…

It was still worth reading. Every critic needs something to read and nitpick ;-)

Keep at it! Just as every program is a chance to improve programming, every article written is a chance to improve writing. It was well written.

Re: {n} times faster than C

#222

Post by utopcell »

nwallin wrote: post #198
nwallin wrote: post #119

Earlier quoted context omitted.

Neat! Although you'll need to make a copy of `n`. The second loop will reduce the value of n to null. Edit: Also, there's an off by one error. should be: #include #include int run_switches(const char *s, const size_t n) { int res = 0; uint8_t tmp = 0; for (int i = n & 127; i--; ++s) tmp += *s == 's'; res += tmp; for (int size = n >> 7; size--;) { tmp = 0; for (int i = 128; i--; ++s) tmp += *s == 's'; res += tmp; } re…

Replying to my own post: The off by 1 error was incorrect. It's because I was calling the function wrong. I had been giving it the size of the buffer, not the size of the string. Also, someone else figured out that we can just use an and instruction instead of cmp. That gives us this version: #include #include int run_switches(const char *s, const size_t n) { int res = 0; uint8_t tmp = 0; for (int i = n & 127; i--; +…

ANDs vs cmps seem to be a mixed bag. They are faster on my older Broadwell system (E5-2690V4 / 128GiB RAM) but they are actually consistently slower on my Rome system (AMD EPYC 7B12 / 512GiB RAM). Of course, neither Broadwells nor Romes have AVX512, so likely this is where you're getting the win from.

Re: {n} times faster than C

#223

Post by fuber2018 »

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; //…

I assume the M1's SIMD registers are wider/more numerous than just the couple of size_t registers used for the loading/masking/accumulating inner loop in your run_swtches().

You can speedup the code by unrolling your inner loop a few times (try 4x or 8x) - it does mean that your overflow prevention limit is lowered (to a multiple of the unrolled grouping number) and run a few more times. But the speedup offsets the increased bookkeeping.

A version I played with showed increased speed by saving the in-progress accumulation in an array and then doing the final accumulation after the main loop is done. But that may be due to the CPU arch/compiler I'm using.

Re: {n} times faster than C

#224

Post by fuber2018 »

fuber2018 wrote: post #223
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; //…

I assume the M1's SIMD registers are wider/more numerous than just the couple of size_t registers used for the loading/masking/accumulating inner loop in your run_swtches(). You can speedup the code by unrolling your inner loop a few times (try 4x or 8x) - it does mean that your overflow prevention limit is lowered (to a multiple of the unrolled grouping number) and run a few more times. But the speedup offsets the i…

If this code only runs on one compiler version/CPU arch, then ASSUMING the compiler will do the RIGHT THING and auto-vectorize the code is okay.

But if your code will be cross-platform/run on different OSes/CPU arch's, then a SWAR version may be more consistently performant - no need to guess if the compiler's optimization heuristics decided to go with the general purpose CPU registers or faster SIMD registers.

Downside is that the devs are exposed to the gnarly optimized code.

Re: {n} times faster than C

#225

Post by redf1sh »

nwallin wrote: post #198
nwallin wrote: post #119

Earlier quoted context omitted.

Neat! Although you'll need to make a copy of `n`. The second loop will reduce the value of n to null. Edit: Also, there's an off by one error. should be: #include #include int run_switches(const char *s, const size_t n) { int res = 0; uint8_t tmp = 0; for (int i = n & 127; i--; ++s) tmp += *s == 's'; res += tmp; for (int size = n >> 7; size--;) { tmp = 0; for (int i = 128; i--; ++s) tmp += *s == 's'; res += tmp; } re…

Replying to my own post: The off by 1 error was incorrect. It's because I was calling the function wrong. I had been giving it the size of the buffer, not the size of the string. Also, someone else figured out that we can just use an and instruction instead of cmp. That gives us this version: #include #include int run_switches(const char *s, const size_t n) { int res = 0; uint8_t tmp = 0; for (int i = n & 127; i--; +…

I don't understand something. What does n&127 and n>>7 mean here?

Re: {n} times faster than C

#226

Post by lukas099 »

garenp wrote: post #70
lukas099 wrote: post #62

Would it be possible to write a code profiler and compiler that work together to optimize code based on real-world data? The profiler would output data that would feed back into the compiler, telling it which branches were selected most often, which would recompile optimizing for the profile. Would this even work? Has it already been done?

It's a thing: https://en.wikipedia.org/wiki/Profile-guided_optimization

Cool, thanks.

Re: {n} times faster than C

#227

Post by SleepyMyroslav »

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…

>Anyway, the point is, you're pretty far from the point where you ought to give up on C and dive into assembly.

Thank you. I hope people who post random assembly listings on HN written in some extinct ISA will read your posts.

Re: {n} times faster than C

#228

Post by EVa5I7bHFq9mnYK »

kaba0 wrote: post #177
EVa5I7bHFq9mnYK wrote: post #167

Earlier quoted context omitted.

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…

Its not that compilers are stupid, they just dont know what humans know about their data, it's ranges, invariants, symmetries etc. They work on most general case, which can be horribly inefficient.

Re: {n} times faster than C

#229

Post by utopcell »

redf1sh wrote: post #225
nwallin wrote: post #198

Earlier quoted context omitted.

Replying to my own post: The off by 1 error was incorrect. It's because I was calling the function wrong. I had been giving it the size of the buffer, not the size of the string. Also, someone else figured out that we can just use an and instruction instead of cmp. That gives us this version: #include #include int run_switches(const char *s, const size_t n) { int res = 0; uint8_t tmp = 0; for (int i = n & 127; i--; +…

I don't understand something. What does n&127 and n>>7 mean here?

127 is 128-1 or 2^7-1, or 1111111b (in binary). It is a faster way to compute n%D when D is known to be a power-of-two.

n>>7 is equal to n/(2^7), and is a faster way to divide with a power-of-two.

Re: {n} times faster than C

#230

Post by [deleted] »

redf1sh wrote: post #225
nwallin wrote: post #198

Earlier quoted context omitted.

Replying to my own post: The off by 1 error was incorrect. It's because I was calling the function wrong. I had been giving it the size of the buffer, not the size of the string. Also, someone else figured out that we can just use an and instruction instead of cmp. That gives us this version: #include #include int run_switches(const char *s, const size_t n) { int res = 0; uint8_t tmp = 0; for (int i = n & 127; i--; +…

I don't understand something. What does n&127 and n>>7 mean here?

[deleted]
Post reply on HN