From 9a211d1f05bd8cb6cb80780bf1880c23204b7b68 Mon Sep 17 00:00:00 2001 From: Nick Terrell Date: Fri, 12 Jan 2018 12:26:47 -0800 Subject: [PATCH] Load more dictionary positions into table if empty If the hash table is empty load positions into the hash table that we would otherwise skip. | Level | Data Set | Improvement | |-------|--------------|-------------| | 1 | github | 0.44% | | 1 | hg-changelog | 0.13% | | 1 | hg-commands | 1.28% | | 1 | hg-manifest | 0.70% | | 3 | github | 0.74% | | 3 | hg-changelog | 0.87% | | 3 | hg-commands | 1.74% | | 3 | hg-manifest | 0.23% | --- lib/compress/zstd_double_fast.c | 23 +++++++++++++++++------ lib/compress/zstd_fast.c | 18 +++++++++++++----- 2 files changed, 30 insertions(+), 11 deletions(-) diff --git a/lib/compress/zstd_double_fast.c b/lib/compress/zstd_double_fast.c index fee5127c3..a6d8ad889 100644 --- a/lib/compress/zstd_double_fast.c +++ b/lib/compress/zstd_double_fast.c @@ -21,12 +21,23 @@ void ZSTD_fillDoubleHashTable(ZSTD_CCtx* cctx, const void* end, const U32 mls) const BYTE* const base = cctx->base; const BYTE* ip = base + cctx->nextToUpdate; const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE; - const size_t fastHashFillStep = 3; - - while(ip <= iend) { - hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip - base); - hashLarge[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip - base); - ip += fastHashFillStep; + const U32 fastHashFillStep = 3; + + /* Always insert every fastHashFillStep position into the hash tables. + * Insert the other positions into the large hash table if their entry + * is empty. + */ + for (; ip + fastHashFillStep - 1 <= iend; ip += fastHashFillStep) { + U32 const current = (U32)(ip - base); + U32 i; + for (i = 0; i < fastHashFillStep; ++i) { + size_t const smHash = ZSTD_hashPtr(ip + i, hBitsS, mls); + size_t const lgHash = ZSTD_hashPtr(ip + i, hBitsL, 8); + if (i == 0) + hashSmall[smHash] = current + i; + if (i == 0 || hashLarge[lgHash] == 0) + hashLarge[lgHash] = current + i; + } } } diff --git a/lib/compress/zstd_fast.c b/lib/compress/zstd_fast.c index 7b56c3d6a..6497a2d8b 100644 --- a/lib/compress/zstd_fast.c +++ b/lib/compress/zstd_fast.c @@ -19,11 +19,19 @@ void ZSTD_fillHashTable (ZSTD_CCtx* zc, const void* end, const U32 mls) const BYTE* const base = zc->base; const BYTE* ip = base + zc->nextToUpdate; const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE; - const size_t fastHashFillStep = 3; - - while(ip <= iend) { - hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip - base); - ip += fastHashFillStep; + const U32 fastHashFillStep = 3; + + /* Always insert every fastHashFillStep position into the hash table. + * Insert the other positions if their hash entry is empty. + */ + for (; ip + fastHashFillStep - 1 <= iend; ip += fastHashFillStep) { + U32 const current = (U32)(ip - base); + U32 i; + for (i = 0; i < fastHashFillStep; ++i) { + size_t const hash = ZSTD_hashPtr(ip + i, hBits, mls); + if (i == 0 || hashTable[hash] == 0) + hashTable[hash] = current + i; + } } } -- 2.47.2