10 ms·
Show HN: 10-40% faster LZMA decoder using x86 CMOVcc
- jpegqs 5y agoLZMA compression (used in 7-zip, XZ, LZMA2) is known as one of the best, but it has a noticeable drawback - it's slow. I tried to improve the decompression speed by removing excessive branching at decoding of every bit from the compressed data. Decompression speedup from this patch largely depends on the compression ratio, more ratio - less speedup. Compressed text, such as source code, gives the least speedup. That's the result from my Skylake, compiled with GCC. Please help me with testing on different x86 CPUs. x86 (32-bit) - should work, but haven't tested yet. Compiled with Clang should work as well.
- jeffbee 5y agoIf you're going for decoding speed wouldn't you be using brotli anyway? At a given compression ratio brotli is ~4x faster on decode path, and they are similar on the encode path. Your corpus may vary etc etc.
- pletnes 5y agoLinux distros often ship xz out of the box. I’ve never seen brotli in the wild. YMMV of course - I am sure there are exceptions. I’ve used brotli myself, but only as it’s included in some parquet read/write libs.
- peter-m80 5y agocloudflare uses brotli (not sure if optional or by default)
- stillicidious 5y agoProbably 10-40% of what your browser is served nowadays is brotli, it's in Chrome so all the major CDNs support it by default
- pletnes 5y agoI’m sure you’re right, but files-on-disk is another story. I was referring to the latter.
- ByTheBook 5y agoJpeg-XL makes use of Brotli, and once it hits 1.0 it will most likely be turned on by default in browsers and thus you will probably see a lot of jxl in the wild, particularly since it provides lossless recompression to existing jpeg files with ~20% smaller size as a result.
- throwaway1777 5y agoIt’s definitely in use by Meta and Google.
- GordonS 5y agoI'm not the OP, but I took their comment to mean "on the command line".
- deleted 5y ago[deleted]
- orev 5y agoContrary to popular belief (sadly, even among the tech crowd here), people use computers for more than just web stuff.
- skyde 5y agoBrotli is not just for Web stuff.
- duskwuff 5y agoBrotli is heavily tuned for "web stuff". It's literally got a built-in dictionary full of commonly used HTML fragments: https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e
- sebazzz 5y agoShoot me, works well for the average desktop (=Electron) application then.
- adgjlsfhk1 5y agoElectron is just web stuff.
- throwthere 5y agoSure but it actually benchmarks well broadly maybe despite its heavy web optimizations.
- orev 5y agoSure. In theory. But every other response to this comment are clearly talking about web stuff, and in practice brotli is really only used for web stuff.
- jeffbee 5y agoI don't know what's theoretical about it. There are Debian packages for brotli and it just behaves like a stdio codec, same as the `xz` command.
- dragontamer 5y agoBut this seems like a patch given to the LZMA project, with an interesting low-level result to boot.
- rwmj 5y agoI don't know about web use, but xz's major advantage for me is the seekable format. We build disk image pipelines based on remote xz-compressed images where only the parts of the file being accessed need to be downloaded and uncompressed. https://libguestfs.org/nbdkit-xz-filter.1.html https://libguestfs.org/nbdkit-xz-filter.1.html
- jack_pp 5y agoI've recently watched this talk that may help you profile better : https://youtu.be/r-TLSBdHe1A https://youtu.be/r-TLSBdHe1A
- Tiberium 5y agoFor the impatient, the profiler is available at https://github.com/plasma-umass/coz https://github.com/plasma-umass/coz
- CyberShadow 5y agoWould using compiler intrinsics instead of raw assembler have any benefits here, such as being applicable to more architectures?
- dragontamer 5y agoWell, ideally, compilers should be compiling into CMOV vs Branching decisions much better. I'm shocked, but not that shocked (https://tenor.com/view/shocked-gif-5787388 https://tenor.com/view/shocked-gif-5787388), that compilers today still are weaker than a dedicated raw-assembly programmer in these kinds of microarchitectural decisions. Even with what should be normal 64-bit code with compilers that have very good modeling of throughputs / latencies per instruction. --------- I'm now more curious as to which compilers can turn the raw C-code into a cmov and which compilers turn the code into the less efficient form (I assume branching??)
- CyberShadow 5y agoUsing CMOV vs. branching seems like a strategic decision which does make sense to fall under the programmer's decision making, as there is a trade-off of always calculating a value which may be unused vs. the cost of the conditional branch.
- danachow 5y ago> as there is a trade-off of always calculating a value which may be unused vs. the cost of the conditional branch. I don’t really understand the point you’re trying to make. Figuring out if a value is unused is most definitely the purview of an optimizer. Also, the “calculating a value” isn’t really the trade off being made between cmov and branching.
- CyberShadow 5y ago> I don’t really understand the point you’re trying to make. Figuring out if a value is unused is most definitely the purview of an optimizer. If the conditional move doesn't happen, then the source (insofar as the move is concerned) is unused. Consider this pseudocode: int value = some_nontrivial_function_with_no_side_effects(); if (condition) *target = value; Note that the function can be as simple as a memory read. The compiler could compile this in two ways: 1. Observing that the function's result is used only if condition is true, move the function call inside the if block. 2. Always call the function, as in the source code, but compile the if block to a conditional move. In such situations, it would make sense to allow programmers to indicate the desired strategy to the compiler. I suppose CPUs might elide calculating the value even with a conditional move if they can predict the condition is [likely to be] false; I don't know how true that is in practice. > Also, the “calculating a value” isn’t really the trade off being made between cmov and branching. Depending on the situation and interpretation of terms, I also agree.
- hasmanean 5y agoWhen did CMOVs become efficient again? The x86 optimization guide used to warn people not to use them, around 2008.
- 10000truths 5y agohttps://www.agner.org/optimize/optimizing_assembly.pdf#page=70 https://www.agner.org/optimize/optimizing_assembly.pdf#page=... TL;DR rule of thumb is that conditional jump is better than CMOV if the code is part of a dependency chain and the prediction rate is better than 75%.
- mirker 5y agoAre dependency chains complex functions or a few instructions? For example, I see people using ternary expressions “a > b : c ? d”. I’m trying to understand if this is an algorithmic problem or a microarchitecture problem. Are “c” and “d” simple? If both are heavy-duty and approximately the same complexity, evaluating both would be 2x slower than evaluating one, but then you’d have to account for probability of misprediction. Meanwhile, if they are simple, I could imagine the CPU tracking both branch register-level states simultaneously with minimal impact on performance (using register-renaming, for example). In other words, how much better would CMOV be if the hardware was given more micro architecture resources?
- wolf550e 5y agoCMOVs were terrible on Pentium 4 but ok on PPro, Pentium M, Core, Core 2, Sandybridge, Skylake, etc. Also ok on Atom and on AMD chips.
- speed_spread 5y agoAt that point, we might just simplify this to "Pentium 4 was terrible"
- ncmncm 5y agoCmov is, and was, efficient whenever branch prediction is unreliable. Clang will turn eligible ?: expressions into cmov. Gcc will do no more than one of those per basic block, subject to fragile conditions. Gcc got its fingers badly burned by overuse of cmov. [Edit: I am wrong! Gcc would not do it when I was trying. More research needed.] Generally, branches break dependency chains, enabling more implicit speculative parallelism. Older cores stuck cmov ops onto dependency chains, where more recently they are treated more like branches. That gives you less speculative evaluation, but consumes less state that would be discarded on a mis-predicted branch.
- deleted 5y ago[deleted]
- injinj 5y agoDecent speedup on my 3970x. Including this patch reduced the number of instructions in lzma_decoder.s (using gcc 8.3.1) by about 8% (4417 lines of asm vs 4824). With perf stat, an astonishing branches-missed reduction from 409K to 104K. Using the firefox example from the gist: $ tar -cJf lib.tar.xz /usr/lib64/firefox The xz shipped from the system: $ perf stat xz -c -d lib.tar.xz > /dev/null Performance counter stats for 'xz -c -d lib.tar.xz': 4,650.32 msec task-clock:u # 1.000 CPUs utilized 0 context-switches:u # 0.000 K/sec 0 cpu-migrations:u # 0.000 K/sec 591 page-faults:u # 0.127 K/sec 19,849,912,300 cycles:u # 4.269 GHz (83.33%) 425,290,878 stalled-cycles-frontend:u # 2.14% frontend cycles idle (83.33%) 1,831,640,390 stalled-cycles-backend:u # 9.23% backend cycles idle (83.34%) 23,973,036,103 instructions:u # 1.21 insn per cycle # 0.08 stalled cycles per insn (83.33%) 2,939,144,233 branches:u # 632.031 M/sec (83.34%) 409,371,860 branch-misses:u # 13.93% of all branches (83.33%) 4.650679926 seconds time elapsed 4.611657000 seconds user 0.011931000 seconds sys The xz patched. $ git clone http://git.tukaani.org/xz.git $ cd xz/src $ patch -l -p1 < ../faster_lxma_decoder_x86.patch $ cd .. ; autogen.sh && configure && make $ LD_PRELOAD=./liblzma/.libs/liblzma.so $ perf stat ./xz/.libs/xz -c -d ../../lib.tar.xz > /dev/null Performance counter stats for './xz/.libs/xz -c -d ../../lib.tar.xz': 3,578.54 msec task-clock:u # 1.000 CPUs utilized 0 context-switches:u # 0.000 K/sec 0 cpu-migrations:u # 0.000 K/sec 593 page-faults:u # 0.166 K/sec 15,186,685,715 cycles:u # 4.244 GHz (83.32%) 108,663,507 stalled-cycles-frontend:u # 0.72% frontend cycles idle (83.32%) 8,753,057,119 stalled-cycles-backend:u # 57.64% backend cycles idle (83.34%) 27,322,182,837 instructions:u # 1.80 insn per cycle # 0.32 stalled cycles per insn (83.35%) 1,979,944,734 branches:u # 553.282 M/sec (83.34%) 104,752,154 branch-misses:u # 5.29% of all branches (83.34%) 3.578973194 seconds time elapsed 3.549329000 seconds user 0.011942000 seconds sys
- viraptor 5y agoWhen I've seen CMOVcc, my mind jumped to the callcc name and now I can't stop thinking in what absurd way could you create an actual CMOV-with-current-continuation. Conditional-MOV-value-or-EIP-otherwise seems too trivial.
- mgaunard 5y agoI find it sad that you need to use inline asm for this. Why isn't GCC providing a built-in to reliably use cmov? Every time I use ?: it's a lottery whether I get it or not. I've had to resort to using the slower bitwise logic to get branch-free code reliably.
- mananaysiempre 5y agoI think I’ve observed reliably-emitted CMOVs when using equivalent (but contrived) arithmetic branchless idioms, e.g. instead of (a ? b : c) write (-!!a & b | -!a & c) (yes, this is rather repulsive, but less so if you think about the negation as turning C-style booleans into Forth/BASIC/mask-style booleans). It should just be a builtin.
- mgaunard 5y agothat is what I meant by "the slower bitwise logic". I didn't know GCC was able to optimize that down to cmov.
- mananaysiempre 5y agoIt’s not, it turns out, I misremembered :( Clang 13 does compile this down to a CMOV in my tests, but GCC 11.1 just translates it as is even with -mtune=native (on Haswell).
- jpegqs 5y agoIt would be great to have builtin for CMOV. But I also want GCC to utilize the hack with the SBB instruction when I write something like: (unsigned)a < (unsigned)b ? ~0 : 0 Instead of three instructions what it generates.
- account42 5y agoIt does use cmp + sbb? https://godbolt.org/z/hnvqrcTcW https://godbolt.org/z/hnvqrcTcW
- floatboth 5y agoHm, should the same be done for aarch64? Generally compilers (well, clang) seem to use CSEL all the time anyway, would be interesting to investigate this.
- jpegqs 5y agoCan be done, ARM has better support for predicated instructions. May be done without using inline assembly. But I guess ARM CPUs can also have a smaller branch penalty, which means less speedup from such a patch. You can try it by replacing the inline assembly with the commented code above it (also don't forget to remove i386 and x86_64 from #if). (Although the code could be rewritten a bit to help the compiler make better binary code for ARM.)
- jpegqs 5y agoI tried it and realized that predicated instructions are removed from aarch64, which I was not aware of (because I rarely work with ARM). That sucks. But I'll try to do it without them.
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- jpegqs 5y agoSo far I've got these results: Allwinner H616 (Cortex-A53) 64-bit mode linux-5.15.7.tar.xz : 25.12 --> 24.43 (+3%) linux-firmware-20211027.tar.xz : 22.80 --> 21.63 (+5%) Maybe on more complex ARM processors the results will be better. Update: It looks like I need to use inline assembly for AArch64 or GCC where it can make two CSEL instructions from the same condition - replaces them with if-else branch. And I got better results (below) than when tried to avoid this compiler behavior but didn't use inline assembly (results above). linux-5.15.7.tar.xz : 25.12 --> 23.85 (+5%) linux-firmware-20211027.tar.xz : 22.80 --> 21.10 (+8%)