24 ms·

{n} times faster than C

447 points by 414owen 3y ago

rajnathani 3y ago
Really interesting. The recent HN article on branchless binary search also covered cmov: https://news.ycombinator.com/item?id=35737862 https://news.ycombinator.com/item?id=35737862
414owen 3y ago
A clickbait title for an in-depth look at hand-optimizing a very simple loop.
- ftxbro 3y ago
  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?
  - twoodfin 3y ago
    This is the right answer: https://news.ycombinator.com/item?id=36622584 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.
    - ftxbro 3y ago
      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?
      - tylerhou 3y ago
        The compiler will generate different code if it knew the rates at which branches were taken. If a branch is almost always taken or almost never taken, a compiler will want to emit a jump. The frontend will be able to predict the jump with high probability, and a successfully-predicted jump is "free." The cost of a misprediction is paid for by the near-zero cost of the many successful predictions. If a branch is hard to predict (and taking versus not taking it would load a different value into a register/memory), the compiler wants to emit a conditional move (cmov). A conditional move is slightly "more expensive" in the backend because the CPU has to wait for the condition to resolve before it can execute instructions dependent on the output. However, it is much cheaper than many mispredicted branches (mispredicts around half of the time). FDO (feedback-directed optimization) or PGO (profile-guided optimization) means "run the code on some sample input and profile how often branches are taken/not taken." It gives the compiler more information to generate better code. The problem with the blog post is that the compiler has no idea what the function's input data will look like. It (arbitrarily) chose to generate branches instead of cmovs. However, if the benchmark input is better suited for cmovs, then the benchmark will (wrongly) show that the compiler generates "slow" assembly. But that's not a fair test, because with PGO/FDO the compiler would generate equivalent assembly to the "fast" assembly (actually, probably faster). Finally, the human (OP) is using their knowledge of the benchmark data "unfairly" to write better assembly than the compiler. The takeaway is: most of the time, one can't optimize code/assembly in a vacuum. You also need to know what the input data and access patterns look like. FDO/PGO gives the compiler more data to understand what the input data/access patterns look like.
        ftxbro 3y ago
        Thank you this is an amazingly comprehensive answer! Now I wonder what would be the workflow for using these compiler features. Like if I am a normal or bad C programmer and I write my program and use valgrind to check that it doesn't have obvious problems and I compile it with -march native or whatever, then I can add some step to the workflow to somehow re-compile it in a way that uses the branching or access patterns of some examples that I let it process for that purpose?
        3y ago
  - cjensen 3y ago
    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.
    - 414owen 3y ago
      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 :)
      - cjensen 3y ago
        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.
        414owen 3y ago
        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 branches is interesting, and I needed a program to apply it to.
  - moonchild 3y ago
    > 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%.
    - bruce343434 3y ago
      > 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?
      - moonchild 3y ago
        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 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.
  - zokier 3y ago
    I wonder what superoptimizers like stoke and souper would do with this code.
- bjourne 3y ago
  Don't get discouraged by the comments and that others made faster variants. I liked both your articles very much and learned a few new things.
torstenvl 3y ago
There's an error in the pseudocode. cmp ecx, 's' # if (c == 's') jne loop # continue add eax, 1 # res++ jmp loop # continue should be cmp ecx, 's' # if (c != 's') jne loop # continue add eax, 1 # res++ jmp loop # continue
- agumonkey 3y ago
  I believe the first `jne` should be `je`, right ?
  - torstenvl 3y ago
    No, the assembler is correct. Jump (early) back to the beginning of the loop if not equal to s; otherwise, continue executing the next instruction (add eax, 1) and then unconditionally jump back to the beginning of the loop.
    - agumonkey 3y ago
      well then there's a magical bit somewhere since both assembly listing are identical
      - torstenvl 3y ago
        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.
        agumonkey 3y ago
        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 :)
vardump 3y ago
I think it's straightforward to optimize to a point it's maybe about 10x faster than the "optimized" version. The answer is of course SIMD vectorization.
aidenn0 3y ago
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.
- whartung 3y ago
  What's some examples of the code changes that you made? And did you just do repeated disassemblies of the functions to see that it was using the correct instructions, or did you do some benchmarking to show your changes were actual improvements?
  - aidenn0 3y ago
    Gosh, I'd have to see if I can dig it up this was a few years ago. I did all of the above, plus profiling (sb-sprof combined with disassemble will show assembly level profiling).
- moonchild 3y ago
  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?
  - aidenn0 3y ago
    I ran separate benchmarks on all-ASCII, BMP-only, and ascii with non-BMP. ASCII was not slower on the low-branch version.
eklitzke 3y ago
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 the branch is very unpredictable. Since they got a 6x speedup with cmov, I assume that their test input (which isn't described in the post, and is also not in their GitHub repo) consists of random strings consisting almost entirely of s and p characters. There's nothing wrong with this, but it does make the post seem a little misleading to me, as their clever speedup is mostly about exploiting an unmentioned property of the data that is highly specific to their benchmark.
- 414owen 3y ago
  > because without FDO (or PGO) the compiler has no idea how likely each branch is to be taken So, the maximum amount of times you can hit '\0' is once in the string, because then the function returns, but you can hit the other characters many times, which seems to be information a compiler has access to without PGO. PGO does help, of course, and on my machine gives me 2.80s, which is better than the code at the end of the `Rearranging blocks` section :) > I assume that their test input (which isn't described in the post, and is also not in their GitHub repo) It's described under `Benchmarking setup`, and is in the repository here: https://github.com/414owen/blog-code/blob/master/01-six-times-faster-than-c/bench.c https://github.com/414owen/blog-code/blob/master/01-six-time... Side note: There's a part two to this post (linked at the bottom) where I make the C code as fast as I possibly can, and it beats all the assembly in this post. I never said writing assembly is (necessarily) a good idea, I just find optimizing it, and deciphering compiler output, an interesting challenge, and a good learning opportunity.
  - aengvs 3y ago
    Imagine a scenario where most of the strings being processed contain a single null character, with no other characters. In that case checking for the null character first would be optimal. Does the compiler know that this isn't true? No, it doesn't. The author of the article is making an assumption about the contents of the data that might seem reasonable but isn't necessarily true.
anthony88 3y ago
[flagged]
- deleted 3y ago
  [deleted]
Sesse__ 3y ago
This code screams for SIMD! If you can change the prototype to take an explicit length, you could easily read and process 16 bytes at a time (the compares will give you values you can just add and subtract directly). Heck, even calling strlen() at the function's start to get the explicit length would probably be worth it.
camel-cdr 3y ago
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_b1(__riscv_vmseq_vx_u8m8_b1(v, 'p', vl), vl); p += vl; } vl = __riscv_vsetvl_e8m8(end); vuint8m8_t v = __riscv_vle8_v_u8m8(p, vl); res += __riscv_vcpop_m_b1(__riscv_vmseq_vx_u8m8_b1(v, 's', vl), vl); res -= __riscv_vcpop_m_b1(__riscv_vmseq_vx_u8m8_b1(v, 'p', vl), vl); return res; } Here are the results from the above, the switch and the table c implementation, ran on my mangopi mq pro (C906, in order rv64gc with rvv 0.7.1, and a 128 bit vector length): switch: 0.19 Bytes/Cycle tbl: 0.17 Bytes/Cycle rvv: 1.57 Bytes/Cycle (dips down to 1.35 after ~30 KiB) Edit: you can go up to 2/1.7 Bytes/Cycle, if you make sure the pointer is page aligned (and vl isn't larger than the page size), see comments
- dzaima 3y ago
  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.
  - camel-cdr 3y ago
    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.
    - dzaima 3y ago
      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.
torstenvl 3y ago
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++; if (c == 's') r++; if (c == 'p') r--; if (c == '\0') break; } return r; } Results: [16:50:14 user@boxer ~/looptest] $ gcc -O3 bench.c loop1.c -o lone [16:50:37 user@boxer ~/looptest] $ gcc -O3 bench.c loop2.c -o ltwo [16:50:47 user@boxer ~/looptest] $ time ./lone 1000 1 449000 ./lone 1000 1 3.58s user 0.00s system 99% cpu 3.589 total [16:50:57 user@boxer ~/looptest] $ time ./ltwo 1000 1 449000 ./ltwo 1000 1 0.65s user 0.00s system 99% cpu 0.658 total
- BoppreH 3y ago
  What version of GCC are you using? For me both versions perform the same, both on Ubuntu and Windows: $ time ./lone 1000 1 851000 real 0m3.578s user 0m3.574s sys 0m0.004s $ time ./ltwo 1000 1 851000 real 0m3.583s user 0m3.583s sys 0m0.000s $ gcc --version gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0 Copyright (C) 2019 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  - torstenvl 3y ago
    Sorry, I write 'gcc' purely out of force of habit. I'm using Clang/LLVM. [17:23:00 user@boxer ~/looptest] $ uname -a Darwin boxer.local 21.6.0 Darwin Kernel Version 21.6.0: Thu Jun 8 23:57:12 PDT 2023; root:xnu-8020.240.18.701.6~1/RELEASE_X86_64 x86_64 [17:23:47 user@boxer ~/looptest] $ cc -v Apple clang version 14.0.0 (clang-1400.0.29.202) Target: x86_64-apple-darwin21.6.0 Thread model: posix InstalledDir: /Library/Developer/CommandLineTools/usr/bin Clang generates the sete instruction for me with the above code: [17:23:49 user@boxer ~/looptest] $ gcc -c -O3 loop2.c [17:25:00 user@boxer ~/looptest] $ objdump -d --symbolize-operands --x86-asm-syntax=intel --no-show-raw-insn loop2.o loop2.o: file format mach-o 64-bit x86-64 Disassembly of section __TEXT,__text: 0000000000000000 <_run_switches>: 0: push rbp 1: mov rbp, rsp 4: xor eax, eax 6: nop word ptr cs:[rax + rax] <L0>: 10: movzx ecx, byte ptr [rdi] 13: add rdi, 1 17: xor edx, edx 19: cmp cl, 115 1c: sete dl 1f: add eax, edx 21: xor edx, edx 23: cmp cl, 112 26: sete dl 29: sub eax, edx 2b: test cl, cl 2d: jne <L0> 2f: pop rbp 30: ret
BoppreH 3y ago
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.
- svachalek 3y ago
  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.
  - 414owen 3y ago
    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?
failuser 3y ago
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?
- gpderetta 3y ago
  AVX512? Also the original ARM 32 bit instruction sent had extensive predication.
nwallin 3y ago
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 insignificant. However it won't unroll and vectorize the loop. If you write it like this: int run_switches_vectorized(const char* s, size_t size) { int result = 0; for (; size--; ++s) { result += *s == 's'; result -= *s == 'p'; } return result; } It will know the size of the loop, and will unroll it and use AVX-512 instructions if they're available. This will be substantially faster than the first loop for large inputs, although I'm too lazy to benchmark just how much faster it is. Now, this requires knowing the size of your string in advance, and maybe you're the sort of C programmer who doesn't keep track of how big your strings are. I'm not your coworker, I don't review your code. Do what you want. But you really really probably shouldn't. https://godbolt.org/z/rde51zMd8 https://godbolt.org/z/rde51zMd8
- jonny_eh 3y ago
  > But you really really probably shouldn't. Shouldn't "not" keep track of string length?
  - darig 3y ago
    [dead]
  - nwallin 3y ago
    Err... yes. You shouldn't not keep track of string/buffer sizes.
- 414owen 3y ago
  The version that's friendly to the compiler is described in part two: https://owen.cafe/posts/the-same-speed-as-c/ 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 :)
RobotToaster 3y ago
Was the C compiled with optimisation enabled?
- 414owen 3y ago
  Yes, I explained in the `Benchmarking setup` section that I used `march=native`, but I guess I forgot to mention I used -O3.
gavinray 3y ago
Fantastic post, I appreciated that the ASM was displayed in tabs as both "standard" and "visual-arrows"-annotated. Kept me reading into the follow-up article. Also, I love the UI of this blog.
- 414owen 3y ago
  Kind words, much appreciated!
xoranth 3y ago
I think I managed to improve on both this post, and its sequel, at the cost of specializing the function for the case of a string made only of 's' and 'p'. The benchmark only tests strings made of 's' and 'p', so I think it is fair. The idea is as follow. We want to increase `res` by one when the next character is `s`. Naively, we might try something like this: res += (c - 'r'); // is `res += 1` when c == 's' This doesn't work, as `'p' - 'r' == -2`, and we'd need it to be -1. But `'p' - 'r'`, when viewer as an unsigned integer, underflows, setting the carry flag. Turns out x64 has an instruction (adc) that adds two registers _plus_ the carry flag. Therefore we can replace two `cmp, cmov` with one `sub, adc`: run_switches: xor eax, eax # res = 0 loop: movsx ecx, byte ptr [rdi] test ecx, ecx je ret inc rdi sub ecx, 'r' adc eax, ecx # Magic happens here jmp loop ret: ret Benchmarks are as follows (`bench-x64-8` is the asm above): Summary '01-six-times-faster-than-c/bench-x64-8 1000 1' ran 1.08 ± 0.00 times faster than '02-the-same-speed-as-c/bench-c-4-clang 1000 1' 1.66 ± 0.00 times faster than '01-six-times-faster-than-c/bench-x64-7 1000 1' Of course, one could improve things further using SWAR/SIMD...
- 414owen 3y ago
  Very interesting approach. I should probably have specified that the somewhat naive assembly in `02-the-same-speed-as-c/loop-5.x64.s` is the fastest version I have. On my machine I'm getting 0.244s for `loop-5.x64.s` and 0.422s for your implementation above. I'm not sure why exactly we're seeing this discrepancy, and for what it's worth your implementation looks faster to me. I guess this is why you need to always benchmark on the hardware you're going to be running the code on...
  - xoranth 3y ago
    I rerun the benchmark vs loop-5 and loop-7 from the second post. Runtime is basically the same on my machine. I would have expected yours to be faster given that it needs to execute fewer instructions per loop iteration. Though maybe the CPU can run `adc` on more ports compared to a load from memory? Summary '01-six-times-faster-than-c/bench-x64-8 1000 1' ran 1.00 ± 0.00 times faster than '02-the-same-speed-as-c/bench-x64-7 1000 1' 1.66 ± 0.00 times faster than '01-six-times-faster-than-c/bench-x64-7 1000 1' Summary '01-six-times-faster-than-c/bench-x64-8 1000 1' ran 1.01 ± 0.00 times faster than '02-the-same-speed-as-c/bench-x64-5 1000 1' 1.66 ± 0.00 times faster than '01-six-times-faster-than-c/bench-x64-7 1000 1'
Const-me 3y ago
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/3ade77faad47f0fbb0538965ae7f8e04 https://gist.github.com/Const-me/3ade77faad47f0fbb0538965ae7... That’s 61x speedup compared to the original version, without any assembly, based on AVX2 intrinsics.
- gavinray 3y ago
  Do you know if this is possible using "std::experimental::simd" out of curiosity? https://en.cppreference.com/w/cpp/experimental/simd https://en.cppreference.com/w/cpp/experimental/simd
  - Const-me 3y ago
    I don’t have any experience with that library. Still, based on the documentation you have linked, I’m not sure it could possibly generate some code similar to my version. I could be wrong but I don’t see APIs which aggregate or accumulate the `simd_mask` vectors they output for results of vector comparisons.
- xoranth 3y ago
  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;
lukas099 3y ago
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?
- garenp 3y ago
  It's a thing: https://en.wikipedia.org/wiki/Profile-guided_optimization https://en.wikipedia.org/wiki/Profile-guided_optimization
  - lukas099 3y ago
    Cool, thanks.
sltkr 3y ago
How much faster is this: int run_switches(const char *buf) { size_t len = strlen(buf); int res = 0; for (size_t i = 0; i < len; ++i) { res += (buf[i] == 's') - (buf[i] == 'p'); } return res; } strlen() should be implemented in a pretty fast way, and after the buffer size is known, the compiler can autovectorize the inner loop, which does happen in practice: https://gcc.godbolt.org/z/qYfadPYoq https://gcc.godbolt.org/z/qYfadPYoq
kristianpaul 3y ago
How fast is forth compared to C these days?
- stefncb 3y ago
  Close to nobody works on forth compilers nowadays, and the compilers that are optimising or even fast is very small. People say that forth isn't very optimisable for our register machines, but I reckon that you can get pretty good results with some clever stack analysis. It's actually possible to determine arity statically if you don't have multiple-arity words, which are very rare. That allows you to pass arguments by register. Anyway, I'm not even close to an expert so don't take what I said as facts.
jtriangle 3y ago
It's a cardinal rule that any time someone utters "XYZ is n faster than C" someone comes along and shows C is actually 2x faster than XYZ.
- JohnMakin 3y ago
  I had an old compilers professor say something like this once. “If you think you can do something better than the C compiler, I promise you you can’t.”
  - saagarjha 3y ago
    Someone has to teach the compiler how to be clever.
  - kstrauser 3y ago
    To a point. A modern C compiler generates mind boggingly fast assembler. However, some languages make it way easier to write sophisticated algorithms more easily. For instance, suppose you're writing a program to find the nth Fibonacci number for whatever reason. In Python, the naive version might look like: def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) On my machine, that takes about 12 seconds to find the 40th number. Altering that slightly like: from functools import cache @cache def fib(n): ... makes the whole program take about 30 milliseconds total. The 400th takes about 32ms and emits an answer that won't fit in a 256-bit int. Of course you can do the exact same kind of caching in C! I mean, the main Python interpreter's written in C, so by extension any algorithm you can express in Python you can also express in C. It'd probably be a lot faster, too! But in practice, if I'm writing that in Python, I can use the obvious algorithm, spent 10 seconds slapping a caching decorator on it, verify that the end result is ridiculous fast and efficient, then move on to other problems. Any reasonable C compiler will emit assembler that's vastly better than anything I could come up with. Conversely, I personally can write far better algorithms in Python than I could in C, because it's easier for me to express cleverness in that language. Those algorithmic improvements tend to have a far better speed payoff than I'd personally get from a more efficient implementation of a crappy method.
throwaway14356 3y ago
naive q: could one just count one of the letters and subtract it from the total number of letters?
- saagarjha 3y ago
  You’d need to count both as other characters are ignored.
  - throwaway14356 3y ago
    naïve q2: does that mean most comparisons are no match 3 times? could one do a bitwise operation and fuzzy test for all 3 in one go?
    - 6510 3y ago
      Is it still ASCII? If so p is 01110000 and s is 01110011(?) but I don't know what \0 is, is it 00000000? Is there anything else know about the data? If the rest of the characters are all numbers, those all start with 0011 but that doesn't seem of much use. 4-9 have either the 5th or 6th bit set. Only if AND with 00001100 yields zero the other 3 tests are needed. Ofc I have no idea what opcodes the language provides.
      - throwaway14356 3y ago
        Here is a perfectly useless idea: AND with 00000010 would give 2 for s an 0 for p. (-1 and you have +1 for s and -1 for p as the article describes) Then you have a number that one could just add in stead of jumping to +1 or -1.
eru 3y ago
Compare also https://codegolf.stackexchange.com/a/236630/32575 https://codegolf.stackexchange.com/a/236630/32575 "High throughput Fizz Buzz" where someone uses assembly to generate Fizz Buzz at around 54-56GiB/s.
sitkack 3y ago
This is such a wonderful post! Heavenly.
red2awn 3y ago
I experimented with different optimizations and ended with 128x speedup. The improvement mainly comes from manual SIMD intrinsics, but you can go a long way just by making the code more auto-vectorization friendly as some other comments have mentioned. See: https://ipthomas.com/blog/2023/07/n-times-faster-than-c-where-n-128/ https://ipthomas.com/blog/2023/07/n-times-faster-than-c-wher...
vpastore 3y ago
[dead]
olliej 3y ago
I see other people have done minor rewrites, but the post does mention reordering branches, so the obvious question is whether there was any attempt to use PGO, which is an obvious first step in optimization.
arun-mani-j 3y ago
Any guide on how a person who uses Python or JavaScript can learn such things? I mean knowing which assembly code would be better, which algorithm makes better usage of processor etc.? :) Also, how is such optimization carried out in a large scale software? Like, do you tweak the generated assembly code manually? (Sorry I'm a very very very beginner to low-level code)
- 414owen 3y ago
  This is pretty much `assembly language the game`: https://tomorrowcorporation.com/humanresourcemachine https://tomorrowcorporation.com/humanresourcemachine It's not a useful architecture, but it teaches the thought process really well, and you end up discovering a lot of optimization naturally. For this article, I'm measuring every step to see what the performance implications of the changes are, which, along with some educated guesses and some googling/reading other articles, was enough for me to figure out what was going on. In part two (https://owen.cafe/posts/the-same-speed-as-c/ https://owen.cafe/posts/the-same-speed-as-c/) especially, I didn't know what was going on with the benchmarks for a long time. Eventually I got lucky and made a change, which led to a hypothesis, which lead to more tests, which led to a conclusion.
- dottedmag 3y ago
  You could try this (in-progress) course: https://www.computerenhance.com/p/table-of-contents https://www.computerenhance.com/p/table-of-contents
- sigmoid10 3y ago
  You do this by first learning C (or similar languages) and then compilers and maybe also operating systems. What you're seeing in this blog is the equivalent result of at least one or two years university level education, so it's not like there is a single book or tutorial you could use to get you up to speed, especially if you have no previous experience in that area. And building a better compiler optimisation in general is a PhD thesis level task. But it's also not necessary if you want to design user applications on today's hardware.
- secondcoming 3y ago
okaleniuk 3y ago
I think, it's a particular quirk of x86 architecture. Branching is expensive in comparison because not doing branching is super cheap. https://wordsandbuttons.online/challenge_your_performance_intuition_with_cpp_operators.html https://wordsandbuttons.online/challenge_your_performance_in... However, on other processors, this might not be the case. https://wordsandbuttons.online/using_logical_operators_for_logical_operations_is_good.html https://wordsandbuttons.online/using_logical_operators_for_l... The good question is what do we need C for in general? Of course, we can hand-tailor our code to run best on one particular piece of hardware. And we don't need C for that, it would be the wrong tool. We need assembly (and a decent macro system for some sugar) But the original goal of C was to make translating system-level code from one platform to another easier. And we're expected to lose efficiency on this operation. It's like instead of writing a poem in Hindi and translating it in Urdu, we write one in Esperanto and then translate to whatever language we want automatically. You don't get two brilliant poems, you only get two poor translations, but you get them fast. That's what C is for.
amm 3y ago
Back-of-the-envelope approach that should eliminate most branching: int table[256] = {0}; void init() { table['s'] = 1; table['p'] = -1; } int run_switches(char *input, int size) { int res = 0; while (size-- >= 0) res += table[input[size]]; return res; }
- 414owen 3y ago
  The array lookup approach taken in part two: https://owen.cafe/posts/the-same-speed-as-c/ https://owen.cafe/posts/the-same-speed-as-c/ But taking the length of the string as a parameter is not, because that changes the problem statement (making the solution vectorizable) Also note that you'll try to read element -1 of the input. You probably want to change the `>=` to a `>`
einpoklum 3y ago
A very instructional post. I wish more people had such a level of mastery of GPU assembly and its effects, and would post such treatments on outsmarting NVIDIA's (or AMD's) optimizers.
fefe23 3y ago
First, before optimizing you should consider correctness and security. input should be const and the return value should be ssize_t (so you don't have numeric overflow on 64-bit). Second, consider this replacement function: ssize_t test(const char \*input) { ssize_t res = 0; size_t l = strlen(input); size_t i; for (i=0; i<l; ++i) { res += (input[i] == 's') - (input[i] == 'p'); } return res; } The timings are (using gcc -O3 -march=native): your function 640 cycles, mine 128 cycles. How can that be? I'm reading the memory twice! I have one call to strlen in there, and memory is slow. Shouldn't this be much slower? No. strlen is a hack that uses vector instructions even though it may technically read beyond the string length. It makes sure not to cross page boundaries so it will not cause adverse reactions, but valgrind needs a suppression exception to not complain about it. If you know the length beforehand, the compiler can vectorize and unroll the loop, which it happens to do here. To great effect, if I may say so. The art of writing fast code is usually to get out of the way of the compiler, which will do a perfectly fine job if you let it. If you really wanted to, you could get rid of the strlen by hacking your logic into what strlen does. That would make the C code much less readable and not actually help that much. My test string is "abcdefghijklmnopqrstuvxyz", so it's all in the l1 cache.
orlp 3y ago
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; // 0x...01010101 const size_t HIGH_BITS = ONES << 7; // 0x...80808080 const size_t SMASK = ONES * (size_t) 's'; // 0x...73737373 const size_t PMASK = ONES * (size_t) 'p'; // 0x...70707070 size_t s_accum = 0; size_t p_accum = 0; int iters = 0; while (1) { // Load word and check for zero byte. // (w - ONES) & ~w has the top bit set in each byte where that byte is zero. size_t w; memcpy(&w, input, sizeof(size_t)); if ((w - ONES) & ~w & HIGH_BITS) break; input += sizeof(size_t); // We reuse the same trick as before, but XORing with SMASK/PMASK first to get // exactly the high bits set where a byte is 's' or 'p'. size_t s_high_bits = ((w ^ SMASK) - ONES) & ~(w ^ SMASK) & HIGH_BITS; size_t p_high_bits = ((w ^ PMASK) - ONES) & ~(w ^ PMASK) & HIGH_BITS; // Shift down and accumulate. s_accum += s_high_bits >> 7; p_accum += p_high_bits >> 7; if (++iters >= 255 / sizeof(size_t)) { // To prevent overflow in our byte-wise accumulators we must flush // them every so often. We use a trick by noting that 2^8 = 1 (mod 255) // and thus a + 2^8 b + 2^16 c + ... = a + b + c (mod 255). res += s_accum % 255; res -= p_accum % 255; iters = s_accum = p_accum = 0; } } res += s_accum % 255; res -= p_accum % 255; // Process tail. while (1) { char c = *input++; res += c == 's'; res -= c == 'p'; if (c == 0) break; } return res; } Fun fact: the above is still 1.6x slower (on my machine) than the naive two-pass algorithm that gets autovectorized by clang: int run_switches(const char* input) { size_t len = strlen(input); int res = 0; for (size_t i = 0; i < len; ++i) { char c = input[i]; res += c == 's'; res -= c == 'p'; } return res; }
- fuber2018 3y ago

447 points by 414owen 3y ago

Really interesting. The recent HN article on branchless binary search also covered cmov: https://news.ycombinator.com/item?id=35737862 https://news.ycombinator.com/item?id=35737862

414owen 3y ago

A clickbait title for an in-depth look at hand-optimizing a very simple loop.

ftxbro 3y ago
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?
- twoodfin 3y ago
  This is the right answer: https://news.ycombinator.com/item?id=36622584 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.
  - ftxbro 3y ago
    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?
    - tylerhou 3y ago
      The compiler will generate different code if it knew the rates at which branches were taken. If a branch is almost always taken or almost never taken, a compiler will want to emit a jump. The frontend will be able to predict the jump with high probability, and a successfully-predicted jump is "free." The cost of a misprediction is paid for by the near-zero cost of the many successful predictions. If a branch is hard to predict (and taking versus not taking it would load a different value into a register/memory), the compiler wants to emit a conditional move (cmov). A conditional move is slightly "more expensive" in the backend because the CPU has to wait for the condition to resolve before it can execute instructions dependent on the output. However, it is much cheaper than many mispredicted branches (mispredicts around half of the time). FDO (feedback-directed optimization) or PGO (profile-guided optimization) means "run the code on some sample input and profile how often branches are taken/not taken." It gives the compiler more information to generate better code. The problem with the blog post is that the compiler has no idea what the function's input data will look like. It (arbitrarily) chose to generate branches instead of cmovs. However, if the benchmark input is better suited for cmovs, then the benchmark will (wrongly) show that the compiler generates "slow" assembly. But that's not a fair test, because with PGO/FDO the compiler would generate equivalent assembly to the "fast" assembly (actually, probably faster). Finally, the human (OP) is using their knowledge of the benchmark data "unfairly" to write better assembly than the compiler. The takeaway is: most of the time, one can't optimize code/assembly in a vacuum. You also need to know what the input data and access patterns look like. FDO/PGO gives the compiler more data to understand what the input data/access patterns look like.
      - ftxbro 3y ago
        Thank you this is an amazingly comprehensive answer! Now I wonder what would be the workflow for using these compiler features. Like if I am a normal or bad C programmer and I write my program and use valgrind to check that it doesn't have obvious problems and I compile it with -march native or whatever, then I can add some step to the workflow to somehow re-compile it in a way that uses the branching or access patterns of some examples that I let it process for that purpose?
        3y ago
- cjensen 3y ago
  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.
  - 414owen 3y ago
    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 :)
    - cjensen 3y ago
      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.
      - 414owen 3y ago
        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 branches is interesting, and I needed a program to apply it to.
- moonchild 3y ago
  > 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%.
  - bruce343434 3y ago
    > 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?
    - moonchild 3y ago
      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 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.
- zokier 3y ago
  I wonder what superoptimizers like stoke and souper would do with this code.
bjourne 3y ago
Don't get discouraged by the comments and that others made faster variants. I liked both your articles very much and learned a few new things.

torstenvl 3y ago

There's an error in the pseudocode. cmp ecx, 's' # if (c == 's') jne loop # continue add eax, 1 # res++ jmp loop # continue should be cmp ecx, 's' # if (c != 's') jne loop # continue add eax, 1 # res++ jmp loop # continue

agumonkey 3y ago
I believe the first `jne` should be `je`, right ?
- torstenvl 3y ago
  No, the assembler is correct. Jump (early) back to the beginning of the loop if not equal to s; otherwise, continue executing the next instruction (add eax, 1) and then unconditionally jump back to the beginning of the loop.
  - agumonkey 3y ago
    well then there's a magical bit somewhere since both assembly listing are identical
    - torstenvl 3y ago
      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.
      - agumonkey 3y ago
        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 :)

vardump 3y ago

I think it's straightforward to optimize to a point it's maybe about 10x faster than the "optimized" version. The answer is of course SIMD vectorization.

aidenn0 3y ago

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.

whartung 3y ago
What's some examples of the code changes that you made? And did you just do repeated disassemblies of the functions to see that it was using the correct instructions, or did you do some benchmarking to show your changes were actual improvements?
- aidenn0 3y ago
  Gosh, I'd have to see if I can dig it up this was a few years ago. I did all of the above, plus profiling (sb-sprof combined with disassemble will show assembly level profiling).
moonchild 3y ago
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?
- aidenn0 3y ago
  I ran separate benchmarks on all-ASCII, BMP-only, and ascii with non-BMP. ASCII was not slower on the low-branch version.

eklitzke 3y ago

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 the branch is very unpredictable. Since they got a 6x speedup with cmov, I assume that their test input (which isn't described in the post, and is also not in their GitHub repo) consists of random strings consisting almost entirely of s and p characters. There's nothing wrong with this, but it does make the post seem a little misleading to me, as their clever speedup is mostly about exploiting an unmentioned property of the data that is highly specific to their benchmark.

414owen 3y ago
> because without FDO (or PGO) the compiler has no idea how likely each branch is to be taken So, the maximum amount of times you can hit '\0' is once in the string, because then the function returns, but you can hit the other characters many times, which seems to be information a compiler has access to without PGO. PGO does help, of course, and on my machine gives me 2.80s, which is better than the code at the end of the `Rearranging blocks` section :) > I assume that their test input (which isn't described in the post, and is also not in their GitHub repo) It's described under `Benchmarking setup`, and is in the repository here: https://github.com/414owen/blog-code/blob/master/01-six-times-faster-than-c/bench.c https://github.com/414owen/blog-code/blob/master/01-six-time... Side note: There's a part two to this post (linked at the bottom) where I make the C code as fast as I possibly can, and it beats all the assembly in this post. I never said writing assembly is (necessarily) a good idea, I just find optimizing it, and deciphering compiler output, an interesting challenge, and a good learning opportunity.
- aengvs 3y ago
  Imagine a scenario where most of the strings being processed contain a single null character, with no other characters. In that case checking for the null character first would be optimal. Does the compiler know that this isn't true? No, it doesn't. The author of the article is making an assumption about the contents of the data that might seem reasonable but isn't necessarily true.

anthony88 3y ago

[flagged]

deleted 3y ago
[deleted]

Sesse__ 3y ago

This code screams for SIMD! If you can change the prototype to take an explicit length, you could easily read and process 16 bytes at a time (the compares will give you values you can just add and subtract directly). Heck, even calling strlen() at the function's start to get the explicit length would probably be worth it.

camel-cdr 3y ago

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_b1(__riscv_vmseq_vx_u8m8_b1(v, 'p', vl), vl); p += vl; } vl = __riscv_vsetvl_e8m8(end); vuint8m8_t v = __riscv_vle8_v_u8m8(p, vl); res += __riscv_vcpop_m_b1(__riscv_vmseq_vx_u8m8_b1(v, 's', vl), vl); res -= __riscv_vcpop_m_b1(__riscv_vmseq_vx_u8m8_b1(v, 'p', vl), vl); return res; } Here are the results from the above, the switch and the table c implementation, ran on my mangopi mq pro (C906, in order rv64gc with rvv 0.7.1, and a 128 bit vector length): switch: 0.19 Bytes/Cycle tbl: 0.17 Bytes/Cycle rvv: 1.57 Bytes/Cycle (dips down to 1.35 after ~30 KiB) Edit: you can go up to 2/1.7 Bytes/Cycle, if you make sure the pointer is page aligned (and vl isn't larger than the page size), see comments

dzaima 3y ago
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.
- camel-cdr 3y ago
  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.
  - dzaima 3y ago
    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.

torstenvl 3y ago

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++; if (c == 's') r++; if (c == 'p') r--; if (c == '\0') break; } return r; } Results: [16:50:14 user@boxer ~/looptest] $ gcc -O3 bench.c loop1.c -o lone [16:50:37 user@boxer ~/looptest] $ gcc -O3 bench.c loop2.c -o ltwo [16:50:47 user@boxer ~/looptest] $ time ./lone 1000 1 449000 ./lone 1000 1 3.58s user 0.00s system 99% cpu 3.589 total [16:50:57 user@boxer ~/looptest] $ time ./ltwo 1000 1 449000 ./ltwo 1000 1 0.65s user 0.00s system 99% cpu 0.658 total

BoppreH 3y ago
What version of GCC are you using? For me both versions perform the same, both on Ubuntu and Windows: $ time ./lone 1000 1 851000 real 0m3.578s user 0m3.574s sys 0m0.004s $ time ./ltwo 1000 1 851000 real 0m3.583s user 0m3.583s sys 0m0.000s $ gcc --version gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0 Copyright (C) 2019 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
- torstenvl 3y ago
  Sorry, I write 'gcc' purely out of force of habit. I'm using Clang/LLVM. [17:23:00 user@boxer ~/looptest] $ uname -a Darwin boxer.local 21.6.0 Darwin Kernel Version 21.6.0: Thu Jun 8 23:57:12 PDT 2023; root:xnu-8020.240.18.701.6~1/RELEASE_X86_64 x86_64 [17:23:47 user@boxer ~/looptest] $ cc -v Apple clang version 14.0.0 (clang-1400.0.29.202) Target: x86_64-apple-darwin21.6.0 Thread model: posix InstalledDir: /Library/Developer/CommandLineTools/usr/bin Clang generates the sete instruction for me with the above code: [17:23:49 user@boxer ~/looptest] $ gcc -c -O3 loop2.c [17:25:00 user@boxer ~/looptest] $ objdump -d --symbolize-operands --x86-asm-syntax=intel --no-show-raw-insn loop2.o loop2.o: file format mach-o 64-bit x86-64 Disassembly of section __TEXT,__text: 0000000000000000 <_run_switches>: 0: push rbp 1: mov rbp, rsp 4: xor eax, eax 6: nop word ptr cs:[rax + rax] <L0>: 10: movzx ecx, byte ptr [rdi] 13: add rdi, 1 17: xor edx, edx 19: cmp cl, 115 1c: sete dl 1f: add eax, edx 21: xor edx, edx 23: cmp cl, 112 26: sete dl 29: sub eax, edx 2b: test cl, cl 2d: jne <L0> 2f: pop rbp 30: ret

BoppreH 3y ago

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.

svachalek 3y ago
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.
- 414owen 3y ago
  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?

failuser 3y ago

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?

gpderetta 3y ago
AVX512? Also the original ARM 32 bit instruction sent had extensive predication.

nwallin 3y ago

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 insignificant. However it won't unroll and vectorize the loop. If you write it like this: int run_switches_vectorized(const char* s, size_t size) { int result = 0; for (; size--; ++s) { result += *s == 's'; result -= *s == 'p'; } return result; } It will know the size of the loop, and will unroll it and use AVX-512 instructions if they're available. This will be substantially faster than the first loop for large inputs, although I'm too lazy to benchmark just how much faster it is. Now, this requires knowing the size of your string in advance, and maybe you're the sort of C programmer who doesn't keep track of how big your strings are. I'm not your coworker, I don't review your code. Do what you want. But you really really probably shouldn't. https://godbolt.org/z/rde51zMd8 https://godbolt.org/z/rde51zMd8

jonny_eh 3y ago
> But you really really probably shouldn't. Shouldn't "not" keep track of string length?
- darig 3y ago
  [dead]
- nwallin 3y ago
  Err... yes. You shouldn't not keep track of string/buffer sizes.
414owen 3y ago
The version that's friendly to the compiler is described in part two: https://owen.cafe/posts/the-same-speed-as-c/ 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 :)

RobotToaster 3y ago

Was the C compiled with optimisation enabled?

414owen 3y ago
Yes, I explained in the `Benchmarking setup` section that I used `march=native`, but I guess I forgot to mention I used -O3.

gavinray 3y ago

Fantastic post, I appreciated that the ASM was displayed in tabs as both "standard" and "visual-arrows"-annotated. Kept me reading into the follow-up article. Also, I love the UI of this blog.

414owen 3y ago
Kind words, much appreciated!

xoranth 3y ago

I think I managed to improve on both this post, and its sequel, at the cost of specializing the function for the case of a string made only of 's' and 'p'. The benchmark only tests strings made of 's' and 'p', so I think it is fair. The idea is as follow. We want to increase `res` by one when the next character is `s`. Naively, we might try something like this: res += (c - 'r'); // is `res += 1` when c == 's' This doesn't work, as `'p' - 'r' == -2`, and we'd need it to be -1. But `'p' - 'r'`, when viewer as an unsigned integer, underflows, setting the carry flag. Turns out x64 has an instruction (adc) that adds two registers _plus_ the carry flag. Therefore we can replace two `cmp, cmov` with one `sub, adc`: run_switches: xor eax, eax # res = 0 loop: movsx ecx, byte ptr [rdi] test ecx, ecx je ret inc rdi sub ecx, 'r' adc eax, ecx # Magic happens here jmp loop ret: ret Benchmarks are as follows (`bench-x64-8` is the asm above): Summary '01-six-times-faster-than-c/bench-x64-8 1000 1' ran 1.08 ± 0.00 times faster than '02-the-same-speed-as-c/bench-c-4-clang 1000 1' 1.66 ± 0.00 times faster than '01-six-times-faster-than-c/bench-x64-7 1000 1' Of course, one could improve things further using SWAR/SIMD...

414owen 3y ago
Very interesting approach. I should probably have specified that the somewhat naive assembly in `02-the-same-speed-as-c/loop-5.x64.s` is the fastest version I have. On my machine I'm getting 0.244s for `loop-5.x64.s` and 0.422s for your implementation above. I'm not sure why exactly we're seeing this discrepancy, and for what it's worth your implementation looks faster to me. I guess this is why you need to always benchmark on the hardware you're going to be running the code on...
- xoranth 3y ago
  I rerun the benchmark vs loop-5 and loop-7 from the second post. Runtime is basically the same on my machine. I would have expected yours to be faster given that it needs to execute fewer instructions per loop iteration. Though maybe the CPU can run `adc` on more ports compared to a load from memory? Summary '01-six-times-faster-than-c/bench-x64-8 1000 1' ran 1.00 ± 0.00 times faster than '02-the-same-speed-as-c/bench-x64-7 1000 1' 1.66 ± 0.00 times faster than '01-six-times-faster-than-c/bench-x64-7 1000 1' Summary '01-six-times-faster-than-c/bench-x64-8 1000 1' ran 1.01 ± 0.00 times faster than '02-the-same-speed-as-c/bench-x64-5 1000 1' 1.66 ± 0.00 times faster than '01-six-times-faster-than-c/bench-x64-7 1000 1'

Const-me 3y ago

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/3ade77faad47f0fbb0538965ae7f8e04 https://gist.github.com/Const-me/3ade77faad47f0fbb0538965ae7... That’s 61x speedup compared to the original version, without any assembly, based on AVX2 intrinsics.

gavinray 3y ago
Do you know if this is possible using "std::experimental::simd" out of curiosity? https://en.cppreference.com/w/cpp/experimental/simd https://en.cppreference.com/w/cpp/experimental/simd
- Const-me 3y ago
  I don’t have any experience with that library. Still, based on the documentation you have linked, I’m not sure it could possibly generate some code similar to my version. I could be wrong but I don’t see APIs which aggregate or accumulate the `simd_mask` vectors they output for results of vector comparisons.
xoranth 3y ago
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;

lukas099 3y ago

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?

garenp 3y ago
It's a thing: https://en.wikipedia.org/wiki/Profile-guided_optimization https://en.wikipedia.org/wiki/Profile-guided_optimization
- lukas099 3y ago
  Cool, thanks.

sltkr 3y ago

How much faster is this: int run_switches(const char *buf) { size_t len = strlen(buf); int res = 0; for (size_t i = 0; i < len; ++i) { res += (buf[i] == 's') - (buf[i] == 'p'); } return res; } strlen() should be implemented in a pretty fast way, and after the buffer size is known, the compiler can autovectorize the inner loop, which does happen in practice: https://gcc.godbolt.org/z/qYfadPYoq https://gcc.godbolt.org/z/qYfadPYoq

kristianpaul 3y ago

How fast is forth compared to C these days?

stefncb 3y ago
Close to nobody works on forth compilers nowadays, and the compilers that are optimising or even fast is very small. People say that forth isn't very optimisable for our register machines, but I reckon that you can get pretty good results with some clever stack analysis. It's actually possible to determine arity statically if you don't have multiple-arity words, which are very rare. That allows you to pass arguments by register. Anyway, I'm not even close to an expert so don't take what I said as facts.

jtriangle 3y ago

It's a cardinal rule that any time someone utters "XYZ is n faster than C" someone comes along and shows C is actually 2x faster than XYZ.

JohnMakin 3y ago
I had an old compilers professor say something like this once. “If you think you can do something better than the C compiler, I promise you you can’t.”
- saagarjha 3y ago
  Someone has to teach the compiler how to be clever.
- kstrauser 3y ago
  To a point. A modern C compiler generates mind boggingly fast assembler. However, some languages make it way easier to write sophisticated algorithms more easily. For instance, suppose you're writing a program to find the nth Fibonacci number for whatever reason. In Python, the naive version might look like: def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) On my machine, that takes about 12 seconds to find the 40th number. Altering that slightly like: from functools import cache @cache def fib(n): ... makes the whole program take about 30 milliseconds total. The 400th takes about 32ms and emits an answer that won't fit in a 256-bit int. Of course you can do the exact same kind of caching in C! I mean, the main Python interpreter's written in C, so by extension any algorithm you can express in Python you can also express in C. It'd probably be a lot faster, too! But in practice, if I'm writing that in Python, I can use the obvious algorithm, spent 10 seconds slapping a caching decorator on it, verify that the end result is ridiculous fast and efficient, then move on to other problems. Any reasonable C compiler will emit assembler that's vastly better than anything I could come up with. Conversely, I personally can write far better algorithms in Python than I could in C, because it's easier for me to express cleverness in that language. Those algorithmic improvements tend to have a far better speed payoff than I'd personally get from a more efficient implementation of a crappy method.

throwaway14356 3y ago

naive q: could one just count one of the letters and subtract it from the total number of letters?

saagarjha 3y ago
You’d need to count both as other characters are ignored.
- throwaway14356 3y ago
  naïve q2: does that mean most comparisons are no match 3 times? could one do a bitwise operation and fuzzy test for all 3 in one go?
  - 6510 3y ago
    Is it still ASCII? If so p is 01110000 and s is 01110011(?) but I don't know what \0 is, is it 00000000? Is there anything else know about the data? If the rest of the characters are all numbers, those all start with 0011 but that doesn't seem of much use. 4-9 have either the 5th or 6th bit set. Only if AND with 00001100 yields zero the other 3 tests are needed. Ofc I have no idea what opcodes the language provides.
    - throwaway14356 3y ago
      Here is a perfectly useless idea: AND with 00000010 would give 2 for s an 0 for p. (-1 and you have +1 for s and -1 for p as the article describes) Then you have a number that one could just add in stead of jumping to +1 or -1.

eru 3y ago

Compare also https://codegolf.stackexchange.com/a/236630/32575 https://codegolf.stackexchange.com/a/236630/32575 "High throughput Fizz Buzz" where someone uses assembly to generate Fizz Buzz at around 54-56GiB/s.

sitkack 3y ago

This is such a wonderful post! Heavenly.

red2awn 3y ago

I experimented with different optimizations and ended with 128x speedup. The improvement mainly comes from manual SIMD intrinsics, but you can go a long way just by making the code more auto-vectorization friendly as some other comments have mentioned. See: https://ipthomas.com/blog/2023/07/n-times-faster-than-c-where-n-128/ https://ipthomas.com/blog/2023/07/n-times-faster-than-c-wher...

vpastore 3y ago

[dead]

olliej 3y ago

I see other people have done minor rewrites, but the post does mention reordering branches, so the obvious question is whether there was any attempt to use PGO, which is an obvious first step in optimization.

arun-mani-j 3y ago

Any guide on how a person who uses Python or JavaScript can learn such things? I mean knowing which assembly code would be better, which algorithm makes better usage of processor etc.? :) Also, how is such optimization carried out in a large scale software? Like, do you tweak the generated assembly code manually? (Sorry I'm a very very very beginner to low-level code)

414owen 3y ago
This is pretty much `assembly language the game`: https://tomorrowcorporation.com/humanresourcemachine https://tomorrowcorporation.com/humanresourcemachine It's not a useful architecture, but it teaches the thought process really well, and you end up discovering a lot of optimization naturally. For this article, I'm measuring every step to see what the performance implications of the changes are, which, along with some educated guesses and some googling/reading other articles, was enough for me to figure out what was going on. In part two (https://owen.cafe/posts/the-same-speed-as-c/ https://owen.cafe/posts/the-same-speed-as-c/) especially, I didn't know what was going on with the benchmarks for a long time. Eventually I got lucky and made a change, which led to a hypothesis, which lead to more tests, which led to a conclusion.
dottedmag 3y ago
You could try this (in-progress) course: https://www.computerenhance.com/p/table-of-contents https://www.computerenhance.com/p/table-of-contents
sigmoid10 3y ago
You do this by first learning C (or similar languages) and then compilers and maybe also operating systems. What you're seeing in this blog is the equivalent result of at least one or two years university level education, so it's not like there is a single book or tutorial you could use to get you up to speed, especially if you have no previous experience in that area. And building a better compiler optimisation in general is a PhD thesis level task. But it's also not necessary if you want to design user applications on today's hardware.
secondcoming 3y ago

okaleniuk 3y ago

I think, it's a particular quirk of x86 architecture. Branching is expensive in comparison because not doing branching is super cheap. https://wordsandbuttons.online/challenge_your_performance_intuition_with_cpp_operators.html https://wordsandbuttons.online/challenge_your_performance_in... However, on other processors, this might not be the case. https://wordsandbuttons.online/using_logical_operators_for_logical_operations_is_good.html https://wordsandbuttons.online/using_logical_operators_for_l... The good question is what do we need C for in general? Of course, we can hand-tailor our code to run best on one particular piece of hardware. And we don't need C for that, it would be the wrong tool. We need assembly (and a decent macro system for some sugar) But the original goal of C was to make translating system-level code from one platform to another easier. And we're expected to lose efficiency on this operation. It's like instead of writing a poem in Hindi and translating it in Urdu, we write one in Esperanto and then translate to whatever language we want automatically. You don't get two brilliant poems, you only get two poor translations, but you get them fast. That's what C is for.

amm 3y ago

Back-of-the-envelope approach that should eliminate most branching: int table[256] = {0}; void init() { table['s'] = 1; table['p'] = -1; } int run_switches(char *input, int size) { int res = 0; while (size-- >= 0) res += table[input[size]]; return res; }

414owen 3y ago
The array lookup approach taken in part two: https://owen.cafe/posts/the-same-speed-as-c/ https://owen.cafe/posts/the-same-speed-as-c/ But taking the length of the string as a parameter is not, because that changes the problem statement (making the solution vectorizable) Also note that you'll try to read element -1 of the input. You probably want to change the `>=` to a `>`

einpoklum 3y ago

A very instructional post. I wish more people had such a level of mastery of GPU assembly and its effects, and would post such treatments on outsmarting NVIDIA's (or AMD's) optimizers.

fefe23 3y ago

First, before optimizing you should consider correctness and security. input should be const and the return value should be ssize_t (so you don't have numeric overflow on 64-bit). Second, consider this replacement function: ssize_t test(const char \*input) { ssize_t res = 0; size_t l = strlen(input); size_t i; for (i=0; i<l; ++i) { res += (input[i] == 's') - (input[i] == 'p'); } return res; } The timings are (using gcc -O3 -march=native): your function 640 cycles, mine 128 cycles. How can that be? I'm reading the memory twice! I have one call to strlen in there, and memory is slow. Shouldn't this be much slower? No. strlen is a hack that uses vector instructions even though it may technically read beyond the string length. It makes sure not to cross page boundaries so it will not cause adverse reactions, but valgrind needs a suppression exception to not complain about it. If you know the length beforehand, the compiler can vectorize and unroll the loop, which it happens to do here. To great effect, if I may say so. The art of writing fast code is usually to get out of the way of the compiler, which will do a perfectly fine job if you let it. If you really wanted to, you could get rid of the strlen by hacking your logic into what strlen does. That would make the C code much less readable and not actually help that much. My test string is "abcdefghijklmnopqrstuvxyz", so it's all in the l1 cache.

orlp 3y ago

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; // 0x...01010101 const size_t HIGH_BITS = ONES << 7; // 0x...80808080 const size_t SMASK = ONES * (size_t) 's'; // 0x...73737373 const size_t PMASK = ONES * (size_t) 'p'; // 0x...70707070 size_t s_accum = 0; size_t p_accum = 0; int iters = 0; while (1) { // Load word and check for zero byte. // (w - ONES) & ~w has the top bit set in each byte where that byte is zero. size_t w; memcpy(&w, input, sizeof(size_t)); if ((w - ONES) & ~w & HIGH_BITS) break; input += sizeof(size_t); // We reuse the same trick as before, but XORing with SMASK/PMASK first to get // exactly the high bits set where a byte is 's' or 'p'. size_t s_high_bits = ((w ^ SMASK) - ONES) & ~(w ^ SMASK) & HIGH_BITS; size_t p_high_bits = ((w ^ PMASK) - ONES) & ~(w ^ PMASK) & HIGH_BITS; // Shift down and accumulate. s_accum += s_high_bits >> 7; p_accum += p_high_bits >> 7; if (++iters >= 255 / sizeof(size_t)) { // To prevent overflow in our byte-wise accumulators we must flush // them every so often. We use a trick by noting that 2^8 = 1 (mod 255) // and thus a + 2^8 b + 2^16 c + ... = a + b + c (mod 255). res += s_accum % 255; res -= p_accum % 255; iters = s_accum = p_accum = 0; } } res += s_accum % 255; res -= p_accum % 255; // Process tail. while (1) { char c = *input++; res += c == 's'; res -= c == 'p'; if (c == 0) break; } return res; } Fun fact: the above is still 1.6x slower (on my machine) than the naive two-pass algorithm that gets autovectorized by clang: int run_switches(const char* input) { size_t len = strlen(input); int res = 0; for (size_t i = 0; i < len; ++i) { char c = input[i]; res += c == 's'; res -= c == 'p'; } return res; }

fuber2018 3y ago