About the versioning, glad you spotted it anyway. There isn't as much use of the gzhttp package compared to the other ones, so the bar is a bit higher for that one.
Also making good progress on getting a slimmer version of zstd into the stdlib and improving the stdlib deflate.
Of course zstd compresses to a smaller size - but for things like streams transfers or for fast readbacks from disk you probably want the fastest.
Overall, I would say that MinLZ is about 2x faster decompressing, and compresses about 2x the speed compressing at max speed. But of course with less compression.
I just released about 2 years of work on improving compression with a fixed encoding LZ77 style compressor.
Our goal was to improve compression by combining and tweaking the best aspects of LZ4 and Snappy.
The package provides Block (up to 8MB) and Stream Compression. Both compression and decompression have amd64 assembly that provides speeds of multiple GB - typical at memory throughput limits. But even the pure Go versions outperform the alternatives.
In my experience, the hybrid approach is practically better due to cache locality anyway, so I don't think even native GF16 or GF32 would be of much help.
FWIW, I've ported rs-leopard to Go and found it very effective, except in the "recover one" scenario, where it is only at 50% speed of the "recover all" scenario, since it has to do several reconstructions to get one output. But even so, I am not too sure it would be much better with plain GF16, since you would still need to touch most shards to get one shard out.
Almost all (x86) CPUs sold have GFNI. That can pretty much saturate memory bandwidth on a single core or two. You can use SSSE3 pshufb for the rest which is about half the speed.
ARM has NEON and SVE/SVE 2. They also operate very fast.
Looking at it quickly, it seems like you just moving entropy to the frequency table.
If the frequency table isn't included in the count, I could just make an "infinite" compressor by storing the frequency and cut one byte off the end. From the frequency table I could then deduce what the last byte should be.
> typical entropy encoders (Huffman, ANS, etc) would require 1 bit per symbol,
No. ANS (and range/arithmetic coding) allows for probabilities to be stored with fractional bits.
> If I could change one thing about S3's API I would like an option to read the metadata with the listings.
Agree. In MinIO (disclaimer: I work there) we added a "secret" parameter (metadata=true) to include metadata and tags in listings if the user has the appropriate permissions. Of course it being an extension it is not really something that you can reliably use. But rclone can of course always try it and use it if available :)
> You can create zero length files ending in /
Yeah. Though you could also consider "shared prefixes" in listings as directories by itself. That of course makes directories "stateless" and unable to exist if there are no objects in there - which has pros and cons.
> Or alternatively a way of setting the Last-Modified on an object when you upload it would do too.
Yes, that gives severe limitations to clients. However it does make the "server" time the reference. But we have to deal with the same limitation for client side replication/mirroring.
My personal biggest complaint is that there isn't a `HeadObjectVersions` that returns version information for a single object. `ListObjectVersions` is always going to be a "cluster-wide" operation, since you cannot know if the given prefix is actually a prefix or an object key. AWS recently added "GetObjectAttributes" - but it doesn't add version information, which would have fit in nicely there.
As someone who has dabbled quite a lot with deflate this was a very interesting find. It seems like the format that never wants to die.
First of all I am surprised this is even possible. Given the extremely minimal and non-aligned nature of the deflate headers, I actually discarded this as being feasible, with the false positive rate likely being too high.
The paper and implementation is an amazing piece of engineering. Hats off to the author. With an index, you are in "easy" mode, so I consider the unindexed "hard mode" the big accomplishment.
I am still digesting it. So if I read the paper correctly the false positive rate is approximately 1 for every 5GB. Very reasonable.
Reading it, it seems very similar to the Playstation 3 Cell, with its fate mirroring it very much.
A highly specialized processor that has very high computational throughput for specialized operations, but a quite limited scalar unit.
In both cases you really have to write software specifically for it to get it to perform with any reasonable speed. If you do that, you get great value, but any existing code will need significant modifications to perform.
Granted AVX512 is (now) more common than SPE code ever became. It is slightly better than the Itanium approach, but scalar performance (especially single threaded) will have limited the value you get from this CPU, unless you write your own software and it can utilize AVX-512.
Leopard-RS GF16 support added to reedsolomon package, with SSE3, AVX2 and AVX512 assembly.
This allows to encode up to 65536 data+parity shards at O(K Log M), where K is the original data size, and M is up to twice the size of the recovery set.
> If you see a match that would not be visible from given compression level[...]
Yes, but you'd need to reconstruct the hash table and the link table. For that you'd need to decompress fully. You could compare matches, but you are so far along at this point you might as well just decompress and recompress, comparing the output bit by bit.
There is no way to "rule some levels out". The levels only differ in the quality of the lz matches. Slower levels search further potential matches - you cannot see that from a compressed stream.
You can compare the output from each level and that will be your guess, assuming of course that zlib was used in the first place.