danlark1

Congrats, that's incredible news. Watched apavlo@'s lectures while studying in the university and finished my bachelor thesis implementing features and doing research at ClickHouse. Surprised to see these worlds being together now!

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.

P.S.S you can optimize aarch64 speed by movemasks from shrn instruction. https://developer.arm.com/community/arm-community-blogs/b/se...

Surprisingly I didn't put 2023, it was merged with another submission possibly with the help of mods

Yes, sorry, it should be "disclosure"

Disclaimer: the author of the comment is the founder and CTO of ClickHouse

Great work!

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.

https://community.arm.com/arm-community-blogs/b/servers-and-...

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.

[1] https://danlark.org/2020/11/11/miniselect-practical-and-gene...

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

For compiler-rt it is Apache 2.0 license

https://github.com/llvm/llvm-project/blob/master/compiler-rt...

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, I believe they can be done for 32 bit platforms also with the multiword division in Knuth https://skanthak.homepage.t-online.de/division.html what I've chosen for fallback if not x86_64 platform.

I will try to implement the same optimizations in Rust in the upcoming weeks

UPD And we opened an issue :) https://github.com/rust-lang/compiler-builtins/issues/368

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