Code-used-on-Daniel-Lemire-s-blog
FastPFor
Our great sponsors
Code-used-on-Daniel-Lemire-s-blog | FastPFor | |
---|---|---|
24 | 4 | |
791 | 835 | |
- | - | |
9.4 | 8.6 | |
6 days ago | 13 days ago | |
C | C++ | |
- | Apache License 2.0 |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
Code-used-on-Daniel-Lemire-s-blog
- Estimating Your Memory Bandwidth
- First 96-Core AMD Zen 4 Threadripper Tests Show Utter Domination over Intel
-
Parsing time stamps faster with SIMD instructions
It's not bad at all https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/...
-
Under Linux, libSegFault and addr2line are underrated
A newline is missing in the example code. As given there's a segfault at line 5 not line 6.
However, the code at https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/... shows it's indeed at line 6, because it has an extra newline after the '#include '.
-
Best Websites For Coders
Daniel Lemire's Blog : Daniel Lemire's blog
-
Technical Blogs You Recommend?
Dr. Daniel Lemire's blog: https://lemire.me/blog, covers lots of technical items on optimizations in various programming languages, Lemire's work is currently in use across a number of projects and he consistently delivers fantastic improvements, he usually accompanies these improvements with a blog post describing what he did. He also occasionally posts interesting Science and Technology links on various topics not limited to tech, but health and education as well.
- suggest some c language blogs....
-
What are some cool modern libraries you enjoy using?
Nope, simdjson is originally from Daniel Lemire who also often blogs about fancy low level optimizations: https://lemire.me/blog/ I'm just a happy user :)
-
Escaping strings faster with AVX-512
Added this pull request with some interesting results.
There's a copy of the loop used on the escape function inside the avx512_escape function [0]. Is it needed or just a copy and paste mistake? (I know nothing about vector instructions)
0: https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/...
FastPFor
-
Making CRDTs 98% More Efficient
Well if your integers are sequential you can encode huge numbers of them using diff + RLE in just a few bytes, likely far fewer than 1/2 a byte on average, for the right dataset (in theory you can store 1,2,3,4,5...10_000 in 2 bytes).
But for other integer datasets there's FastPFOR
https://github.com/lemire/FastPFor
The linked papers there will talk about techniques that can be used to store multiple 32bit integers into a single byte, etc. Integer compression is pretty powerful if your data isn't random. The thing with UUIDs is that your data is pretty random - even a UUIDv7 contains a significant amount of random data.
-
Time-Series Compression Algorithms
One notable omission from this piece is a technique to compress integer time series with both positive and negative values.
If you naively apply bit-packing using the Simple8b algorithm, you'll find that negative integers are not compressed. This is due to how signed integers are represented in modern computers: negative integers will have their most significant bit set [1].
Zigzag encoding is a neat transform that circumvents this issue. It works by mapping signed integers to unsigned integers so that numbers with a small absolute value can be encoded using a small number of bits. Put another way, it encodes negative numbers using the least significant bit for sign. [2]
If you're looking for a quick way to experiment with various time series compression algorithm I highly recommend Daniel Lemire's FastPFor repository [3] (as linked in the article). I've used the Python bindings [4] to quickly evaluate various compression algorithms with great success.
Finally I'd like to humbly mention my own tiny contribution [5], an adaptation of Lemire's C++ Simple8b implementation (including basic methods for delta & zigzag encoding/decoding).
I used C++ templates to make the encoding and decoding routines generic over integer bit-width, which expands support up to 64 bit integers, and offers efficient usage with smaller integers (eg 16 bit). I made a couple other minor tweaks including support for arrays up to 2^64 in length, and tweaking the API/method signatures so they can be used in a more functional style. This implementation is slightly simpler to invoke via FFI, and I intend to add examples showing how to compile for usage via JS (WebAssembly), Python, and C#. I threw my code up quickly in order to share with you all, hopefully someone finds it useful. I intend to expand on usage examples/test cases/etc, and am looking forward to any comments or contributions.
[1] https://en.wikipedia.org/wiki/Signed_number_representation
[2] https://en.wikipedia.org/wiki/Variable-length_quantity#Zigza...
[3] https://github.com/lemire/FastPFor
[4] https://github.com/searchivarius/PyFastPFor
[5] https://github.com/naturalplasmoid/simple8b-timeseries-compr...
- The big-load anti-pattern
- FastPFOR: Fast Integer Compression in C++
What are some alternatives?
farmhash - Automatically exported from code.google.com/p/farmhash
simple8b-timeseries-compression
rust - Empowering everyone to build reliable and efficient software.
simple8b-timeseries-compr
simonwillisonblog - The source code behind my blog
interpolative_coding - A flexible and efficient C++ implementation of the Binary Interpolative Coding algorithm.
developer-roadmap - Interactive roadmaps, guides and other educational content to help developers grow in their careers.
cheatsheets - Cheatsheets for web development - devhints.io
zune-jpeg - A jpeg decoder with wings
cmake_template - CMake for C++ Best Practices
free-programming-books - :books: Freely available programming books
Code-Server - VS Code in the browser