It's a somewhat known tradeoff, you can streamline and make the format friendlier to do memcpy which this library targets, the more memcpys you do, the faster it is overall to decode. On highly compressible data lz4, snappy become faster. Snappy on level 2 has faster decompression speed
But you have to pay the price that you need a slower encoding, because finding matches, putting restrictions on match lengths, putting things in different streams have costs you need to pay upfront.
Anyway good work, there is probably a need for that.
// Currently own Google's snappy and do compression at Google
P.S. if you want better snappy's results, compile with clang.
Popular narrative that NEON does not have a move mask alternative. Some time ago I published an article to simulate popular bit packing use cases with NEON with 1-2 instructions. This does not include unpacking cases but can be great for real world applications like compare+find, compare+iterate, compare+test.
I am the author of the optimization of partial sorting and selection in Clickhouse. It uses Floyd-Rivest algorithm and we tried a lot of different things back at the time, read [1]
Overall clickhouse reads blocks of fixed sizes (64k) and finds top elements and then does top of the top until it converges.
That's a difficult question. As I am working at Google I need to consult each open source I want to publish on my behalf. This does not involve contributing to the list of the approved projects and telling about these contributions.
If you want to workaround this for now, I suggest looking into libdivide (https://github.com/ridiculousfish/libdivide), it is published with the boost license and the library contains all the needed artifacts I described in the article (unfortunately, not combined).
Hi, I thought that this is not the most interesting part of all the benchmarks, for example, all we need to test that with the quotient and the remainder: dividend = quotient * divisor + remainder, remainder < divisor and multiplication does not overflow which is free of division operations.
Yet, I added several tests like dividend < divisor, close to zero remainders, a lot of random stuff just to make sure each time I add a new approach, it is correct.
Hi everyone, the author is here. Yes, I believe the title should be changed to `Optimizing 128-bit Division`
Yet, I was not expecting it to be here. Overall, I put some knowledge hidden in Hacker's Delight book, Knuth, GMP and GNU in the article with my knowledge of low level optimizations. In the end it turned out to be a good thing to write and to submit into LLVM
But you have to pay the price that you need a slower encoding, because finding matches, putting restrictions on match lengths, putting things in different streams have costs you need to pay upfront.
Anyway good work, there is probably a need for that.
// Currently own Google's snappy and do compression at Google
P.S. if you want better snappy's results, compile with clang.
P.S.S you can optimize aarch64 speed by movemasks from shrn instruction. https://developer.arm.com/community/arm-community-blogs/b/se...