[RFC] Support references to multiple DDicts by senhuang42 · Pull Request #2446 · facebook/zstd

senhuang42 · 2020-12-29T00:05:42Z

This PR adds a new experimental param ZSTD_d_refMultipleDDicts which controls the behavior of ZSTD_refDDict().

If enabled, then multiple calls to ZSTD_refDDict() will persist the multiple referenced ZSTD_DDict* in memory rather than overwriting the last reference. Under the hood, we use a hash set w/ linear probing to keep track of the ZSTD_DDict*. Example usage is in the included unit test in fuzzer.c, but is basically as simple as:

ZSTD_DCtx* dctx = ZSTD_createDCtx();
ZSTD_DCtx_setParameter(dctx, ZSTD_d_refMultipleDDicts, ZSTD_rmd_refMultipleDDicts);
ZSTD_DCtx_refDDict(dctx, ddict1);
ZSTD_DCtx_refDDict(dctx, ddict2);
ZSTD_DCtx_refDDict(dctx, ddict3);
...
ZSTD_decompress...

The goal is no changes to the existing API, leaving existing behavior/usages of ZSTD_refDDict() unchanged.
Only when we call setParameter() with the new experimental param can behavior change.

There are still issues with this PR, but I wanted to put this up to get some initial comments to see if this was roughly the direction we wanted to head in.

Open questions/followups:

Hash table allocation entry point (is refDDict() best?)
Performance (hash table param tuning/hash function)
API Extensions? (un-reference a dictionary)
Add streaming unit test
Still need to test more extensively
Some code cleanup

senhuang42 · 2020-12-29T00:07:55Z

lib/decompress/zstd_decompress.c

+ * Returns an index between [0, hashSet->ddictPtrTableSize]
+ */
+static size_t ZSTD_DDictHashSet_getIndex(const ZSTD_DDictHashSet* hashSet, U32 dictID) {
+    U32 hash = XXH64(&dictID, sizeof(U32), 0);


One thing I can't quite figure out is why on certain builds/CI tests, zstd_decompress.c can't see XXH64, but can see XXH64_digest(), etc.? As far as I can tell, xxhash.h is within the graph of dependencies, and locally, it seems fine. Is there an additional macro I need to invoke?

Is this related to the linux kernel test ?

Yeah, I do see a line about Replacing XXH64 prefix with xxh64 in the logs, and I assume it might be related.

You should just need to change this line:

zstd/contrib/freestanding_lib/freestanding.py

Line 579 in bc0a1e4

(re.compile(r"([^\w]|^)(?P<orig>XXH64)_"), self._xxh64_prefix)

Something like: re.compile(r"([^\w]|^)(?P<orig>XXH64)[\(_]")

lib/decompress/zstd_decompress.c

Cyan4973 · 2020-12-29T19:06:02Z

lib/decompress/zstd_decompress.c

+            return 0;
+        }
+        if (idx == hashSet->ddictPtrTableSize - 1) {
+            idx = 0;


minor (potential suggestion) : could also use a mask if ddictPtrTableSize is a clean power of 2.

facebook-github-bot added the CLA Signed label Dec 29, 2020

senhuang42 changed the title ~~Multiple ddicts v3~~ [RFC] Support references to multiple DDicts Dec 29, 2020

senhuang42 commented Dec 29, 2020

View reviewed changes

senhuang42 force-pushed the multiple_ddicts_v3 branch from 1b7c515 to 6705993 Compare December 29, 2020 00:12