fast_float VS rapidgzip

> Google put in significant engineering effort into "Ryu", a parsing library for double-precision floating point numbers: https://github.com/ulfjack/ryu

It's not a parsing library, but a printing one, i.e., double -> string. https://github.com/fastfloat/fast_float is a parsing library, i.e., string -> double, not by Google though, but was indeed motivated by parsing JSON fast https://lemire.me/blog/2020/03/10/fast-float-parsing-in-prac...

For those that don't know, gcc 12.x updated its float parsing logic to something similar to fast_float and it's about 1/6 of the cost presented here (sub 100 in the graph presented here). Strongly suggest using that library or upgrading the compiler if you need the performance.

This makes sense for integers but betware floating point from_chars - libc++ still doesn't implement it and libstdc++ implements it by wrapping locale-dependent libc functions which involves temporarily changing the thread locale and possibly memory allocation to make the passed string 0-terminated. IMO libstdc++'s checkbox "solution" is worse than not implementing it at all - user's are better off using Lemire's API-compatible fast_float implementation [0].

[0] https://github.com/fastfloat/fast_float

I'm a bit stuck on how to do the same thing in c++, due to containers only having a single type. The very inefficient way I'm currently doing it is by passing a program as a vector of strings, and then converting the string constants to doubles with the fast_float library.

Just above this comment is a merged PR, which references fast_float library: https://github.com/fastfloat/fast_float

Daniel Lemire @lemire (creator of the algorithm, author of the C++ implementation, and provided constant feedback to help guide the PR).

And out of 6,000 lines in the file, at least 3000 are other people's code: earcut for polygon triangulation and fast_float because .obj files typically contain a lot of floating point numbers so it's important to parse them quickly.

How this compares to https://github.com/fastfloat/fast_float ?

I tried to compare it against Daniel Lemire's excellent fast_float library. Fast float took about 180ms for the same program, and all I did was change "std" namespace prefix to "fast_float". It's a factor of 12 difference, at least my machine. I tried MSVC next, and it is a lot better, but it is still ~4 times slower than fast float. AFAIK, clang currently does not implement the feature at all.

If you don't mind a 3rd party lib until your stdlib updates, https://github.com/fastfloat/fast_float is best-in-class.

I also did benchmarks with zlib and libarchivemount via their library interface here [0]. It has been a while that I have run them, so I forgot. Unfortunately, I did not add libdeflate.

[0] https://github.com/mxmlnkn/rapidgzip/blob/master/src/benchma...

Hi, author here.

You are right in the index being the easy-mode. Over the years there have been lots of implementations trying to add an index like that to the gzip metadata itself or as a sidecar file, with bgzip probably being the most known one. None of them really did stick, hence the necessity for some generic multi-threaded decompressor. A probably incomplete list of such implementations can be found in this issue: https://github.com/mxmlnkn/rapidgzip/issues/8

The index makes it so easy that I can simply delegate decompression to zlib. And since paper publication I've actually improved upon this by delegating to ISA-l / igzip instead, which is twice as fast. This is already in the 0.8.0 release.

As derived from table 1, the false positive rate is 1 Tbit / 202 = 5 Gbit or 625 MB for deflate blocks with dynamic Huffman code. For non-compressed blocks, the false positive rate is roughly one per 500 KB, however non-compressed blocks can basically be memcpied or skipped over and then the next deflate header can be checked without much latency. On the other hand, for dynamic blocks, the whole block needs to be decompressed first to find the next one. So the much higher false positive rate for non-compressed blocks doesn't introduce that much overhead.

I have some profiling built into rapidgzip, which is printed with -v, e.g., rapidgzip -v -d -o /dev/null 20xsilesia.tar.gz :

    Time spent in block finder              : 0.227751 s

I have not only implemented parallel decompression but also random access to offsets in the stream with https://github.com/mxmlnkn/pragzip I did some benchmarks on some really beefy machines with 128 cores and was able to reach almost 20 GB/s decompression bandwidth. The single-core decoder has lots of potential for optimization because I had to write it from scratch, though.

Decompression of arbitrary gzip files can be parallelized with pragzip: https://github.com/mxmlnkn/pragzip

At the very least you are duplicating logic without the exception. The check for eof has to be done implicitly anyway inside read because it has to fill the bit buffer with data from the byte buffer or the byte buffer with data from the file. And if both fail, then we already know the result of eof, so no need to duplicate checking for eof in the outer read calling loop.

Here is the full commit with ad-hoc benchmark results in the commit message:

https://github.com/mxmlnkn/pragzip/commit/0b1af498377838c30f...

and here the benchmarks I ran at that time:

https://github.com/mxmlnkn/pragzip/blob/0b1af498377838c30fea...

As you can see, it's part of my random-seekable multi-threaded gzip and bzip2 parallel decompression libraries.

What you can also see in the commit message is that it wasn't a 50% time reduction but a 50% bandwidth increase, which would translate to a 30% time reduction. It seems I remembered that partly wrong. But it still was a significant optimization for me.