danlark1
Joined 6 years ago
Karma
349
Submissions
15
Member since
Jul 19
Recent submissions
Comment · 2 months ago
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!
Comment · 3 months ago
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...
Comment · 10 months ago
Surprisingly I didn't put 2023, it was merged with another submission possibly with the help of mods
Comment · 1 year ago
Yes, sorry, it should be "disclosure"
Comment · 1 year ago
Disclaimer: the author of the comment is the founder and CTO of ClickHouse
Comment · 1 year ago
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-...
Comment · 1 year ago
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...
Comment · 6 years ago
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).
Comment · 6 years ago
For compiler-rt it is Apache 2.0 license
https://github.com/llvm/llvm-project/blob/master/compiler-rt...
Comment · 6 years ago
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.
Comment · 6 years ago
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
Comment · 6 years ago
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