Re: [PATCH 1/1] lz4: Implement lz4 with dynamic offset length.
From: Nick Terrell <terrelln@fb.com>
Date: 2018-03-21 19:59:21
Also in:
lkml
On (03/21/18 10:10), Maninder Singh wrote:
quoted hunk ↗ jump to hunk
diff --git a/lib/lz4/lz4_compress.c b/lib/lz4/lz4_compress.c index cc7b6d4..185c358 100644 --- a/lib/lz4/lz4_compress.c +++ b/lib/lz4/lz4_compress.c@@ -183,7 +183,8 @@ static FORCE_INLINE int LZ4_compress_generic( const tableType_t tableType, const dict_directive dict, const dictIssue_directive dictIssue, - const U32 acceleration) + const U32 acceleration, + const Dynamic_Offset dynOffset) { const BYTE *ip = (const BYTE *) source; const BYTE *base;@@ -199,6 +200,7 @@ static FORCE_INLINE int LZ4_compress_generic( BYTE *op = (BYTE *) dest; BYTE * const olimit = op + maxOutputSize; + int max_distance = dynOffset ? MAX_DISTANCE_DYN : MAX_DISTANCE;
Lets mark this variable `const`. If the compiler doesn't realize that this variable and `dynOffset` are compile time constants, I expect the speed to be impacted.
quoted hunk ↗ jump to hunk
U32 forwardH; size_t refDelta = 0;@@ -245,6 +247,7 @@ static FORCE_INLINE int LZ4_compress_generic( for ( ; ; ) { const BYTE *match; BYTE *token; + int curr_offset; /* Find a match */ {@@ -285,7 +288,7 @@ static FORCE_INLINE int LZ4_compress_generic( : 0) || ((tableType == byU16) ? 0 - : (match + MAX_DISTANCE < ip)) + : (match + max_distance < ip)) || (LZ4_read32(match + refDelta) != LZ4_read32(ip))); }@@ -328,8 +331,26 @@ static FORCE_INLINE int LZ4_compress_generic( _next_match: /* Encode Offset */ - LZ4_writeLE16(op, (U16)(ip - match)); - op += 2; + if (dynOffset) { + curr_offset = (U16)(ip - match); + + /* + * If Ofsset is greater than 127, we need 2 bytes + * to store it. Otherwise 1 byte is enough. + */ + if (curr_offset > 127) { + curr_offset = (curr_offset << 1) | DYN_BIT; + LZ4_writeLE16(op, (U16)curr_offset); + op += 2; + } else { + curr_offset = curr_offset << 1; + *op = (BYTE)curr_offset; + op++; + }
The standard way to do variable sized integers is to use the high-bit as the control bit, not the low-bit. Do you have benchmarks to show that using the low-bit is faster than using the high-bit? If so, lets comment in the code, if not lets use the high-bit.
quoted hunk ↗ jump to hunk
+ } else { + LZ4_writeLE16(op, (U16)(ip - match)); + op += 2; + } /* Encode MatchLength */ {@@ -480,39 +501,70 @@ static int LZ4_compress_fast_extState( return LZ4_compress_generic(ctx, source, dest, inputSize, 0, noLimit, byU16, noDict, - noDictIssue, acceleration); + noDictIssue, acceleration, NoDynOffset); else return LZ4_compress_generic(ctx, source, dest, inputSize, 0, noLimit, tableType, noDict, - noDictIssue, acceleration); + noDictIssue, acceleration, NoDynOffset); } else { if (inputSize < LZ4_64Klimit) return LZ4_compress_generic(ctx, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict, - noDictIssue, acceleration); + noDictIssue, acceleration, NoDynOffset); else return LZ4_compress_generic(ctx, source, dest, inputSize, maxOutputSize, limitedOutput, tableType, noDict, - noDictIssue, acceleration); + noDictIssue, acceleration, NoDynOffset); } } +static int LZ4_compress_fast_extState_dynamic( + void *state, + const char *source, + char *dest, + int inputSize, + int maxOutputSize, + int acceleration) +{ + LZ4_stream_t_internal *ctx = &((LZ4_stream_t *)state)->internal_donotuse; + + LZ4_resetStream((LZ4_stream_t *)state); + + if (acceleration < 1) + acceleration = LZ4_ACCELERATION_DEFAULT; + + if (maxOutputSize >= LZ4_COMPRESSBOUND(inputSize)) + return LZ4_compress_generic(ctx, source, + dest, inputSize, 0, + noLimit, byU16, noDict, + noDictIssue, acceleration, DynOffset); + else + return LZ4_compress_generic(ctx, source, + dest, inputSize, + maxOutputSize, limitedOutput, byU16, noDict, + noDictIssue, acceleration, DynOffset); +} + int LZ4_compress_fast(const char *source, char *dest, int inputSize, - int maxOutputSize, int acceleration, void *wrkmem) + int maxOutputSize, int acceleration, void *wrkmem, bool dynOffset) { - return LZ4_compress_fast_extState(wrkmem, source, dest, inputSize, + if (!dynOffset) + return LZ4_compress_fast_extState(wrkmem, source, dest, inputSize, + maxOutputSize, acceleration); + + return LZ4_compress_fast_extState_dynamic(wrkmem, source, dest, inputSize, maxOutputSize, acceleration); } EXPORT_SYMBOL(LZ4_compress_fast); int LZ4_compress_default(const char *source, char *dest, int inputSize, - int maxOutputSize, void *wrkmem) + int maxOutputSize, void *wrkmem, bool dynOffset) { return LZ4_compress_fast(source, dest, inputSize, - maxOutputSize, LZ4_ACCELERATION_DEFAULT, wrkmem); + maxOutputSize, LZ4_ACCELERATION_DEFAULT, wrkmem, dynOffset); } EXPORT_SYMBOL(LZ4_compress_default);@@ -900,12 +952,12 @@ int LZ4_compress_fast_continue(LZ4_stream_t *LZ4_stream, const char *source, result = LZ4_compress_generic( streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, - withPrefix64k, dictSmall, acceleration); + withPrefix64k, dictSmall, acceleration, NoDynOffset); } else { result = LZ4_compress_generic( streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, - withPrefix64k, noDictIssue, acceleration); + withPrefix64k, noDictIssue, acceleration, NoDynOffset); } streamPtr->dictSize += (U32)inputSize; streamPtr->currentOffset += (U32)inputSize;@@ -921,12 +973,12 @@ int LZ4_compress_fast_continue(LZ4_stream_t *LZ4_stream, const char *source, result = LZ4_compress_generic( streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, - usingExtDict, dictSmall, acceleration); + usingExtDict, dictSmall, acceleration, NoDynOffset); } else { result = LZ4_compress_generic( streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, - usingExtDict, noDictIssue, acceleration); + usingExtDict, noDictIssue, acceleration, NoDynOffset); } streamPtr->dictionary = (const BYTE *)source; streamPtr->dictSize = (U32)inputSize;diff --git a/lib/lz4/lz4_decompress.c b/lib/lz4/lz4_decompress.c index 141734d..337a828 100644 --- a/lib/lz4/lz4_decompress.c +++ b/lib/lz4/lz4_decompress.c@@ -71,7 +71,9 @@ static FORCE_INLINE int LZ4_decompress_generic( /* only if dict == usingExtDict */ const BYTE * const dictStart, /* note : = 0 if noDict */ - const size_t dictSize + const size_t dictSize, + /* offset == 1; dynamic offset */ + const Dynamic_Offset dynOffset ) { /* Local Variables */@@ -141,8 +143,8 @@ static FORCE_INLINE int LZ4_decompress_generic( /* copy literals */ cpy = op + length; if (((endOnInput) && ((cpy > (partialDecoding ? oexit : oend - MFLIMIT)) - || (ip + length > iend - (2 + 1 + LASTLITERALS)))) - || ((!endOnInput) && (cpy > oend - WILDCOPYLENGTH))) { + || (ip + length > iend - (2 + LASTLITERALS)))) + || ((!endOnInput) && (cpy > oend - WILDCOPYLENGTH - 1))) { if (partialDecoding) { if (cpy > oend) { /*@@ -188,13 +190,31 @@ static FORCE_INLINE int LZ4_decompress_generic( break; } - LZ4_wildCopy(op, ip, cpy); + if (dynOffset && length < 4) + LZ4_copy4(op, ip); + else + LZ4_wildCopy(op, ip, cpy); +
The LZ4 format enforces that the last 5 bytes are literals so that LZ4_wildCopy() can be used here. I suspect that having this extra branch here for `dynOffset` mode hurts decompression speed.
ip += length;
op = cpy;
/* get offset */
- offset = LZ4_readLE16(ip);
- ip += 2;
+ if (dynOffset) {
+ /*
+ * Check if DYN_BIT is set, means 2 Byte Offset,
+ * else 1 Byte Offset.
+ */
+ if (*ip & DYN_BIT) {
+ offset = LZ4_readLE16(ip) >> 1;
+ ip += 2;
+ } else {
+ offset = *ip >> 1;
+ ip += 1;If we use the high-bit as the control bit, this branch simply becomes `offset = *ip`, though the long offset branch becomes a bit longer.
quoted hunk ↗ jump to hunk
+ } + } else { + offset = LZ4_readLE16(ip); + ip += 2; + } match = op - offset; if ((checkOffset) && (unlikely(match < lowLimit))) {@@ -335,11 +355,11 @@ static FORCE_INLINE int LZ4_decompress_generic( } int LZ4_decompress_safe(const char *source, char *dest, - int compressedSize, int maxDecompressedSize) + int compressedSize, int maxDecompressedSize, bool dynOffset) { return LZ4_decompress_generic(source, dest, compressedSize, maxDecompressedSize, endOnInputSize, full, 0, - noDict, (BYTE *)dest, NULL, 0); + noDict, (BYTE *)dest, NULL, 0, dynOffset);
You'll need to use the same trick that LZ4_compress_fast() uses, by hard coding `dynOffset`. We want the compiler to generate too version of LZ4_decompress_generic(), one with `dynOffset` and one with `!dynOffset`. That way the tight loop won't the branches that check `dynOffset`. if (dynOffset) return LZ4_decompress_generic(..., true); else return LZ4_decompress_generic(..., false); Without this trick, I expect that this patch causes a regression to both LZ4 and LZ4_DYN decompression speed.
quoted hunk ↗ jump to hunk
} int LZ4_decompress_safe_partial(const char *source, char *dest,@@ -347,14 +367,14 @@ int LZ4_decompress_safe_partial(const char *source, char *dest, { return LZ4_decompress_generic(source, dest, compressedSize, maxDecompressedSize, endOnInputSize, partial, - targetOutputSize, noDict, (BYTE *)dest, NULL, 0); + targetOutputSize, noDict, (BYTE *)dest, NULL, 0, NoDynOffset); } int LZ4_decompress_fast(const char *source, char *dest, int originalSize) { return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, - (BYTE *)(dest - 64 * KB), NULL, 64 * KB); + (BYTE *)(dest - 64 * KB), NULL, 64 * KB, NoDynOffset); } int LZ4_setStreamDecode(LZ4_streamDecode_t *LZ4_streamDecode,@@ -392,7 +412,7 @@ int LZ4_decompress_safe_continue(LZ4_streamDecode_t *LZ4_streamDecode, endOnInputSize, full, 0, usingExtDict, lz4sd->prefixEnd - lz4sd->prefixSize, lz4sd->externalDict, - lz4sd->extDictSize); + lz4sd->extDictSize, NoDynOffset); if (result <= 0) return result;@@ -406,7 +426,7 @@ int LZ4_decompress_safe_continue(LZ4_streamDecode_t *LZ4_streamDecode, compressedSize, maxOutputSize, endOnInputSize, full, 0, usingExtDict, (BYTE *)dest, - lz4sd->externalDict, lz4sd->extDictSize); + lz4sd->externalDict, lz4sd->extDictSize, NoDynOffset); if (result <= 0) return result; lz4sd->prefixSize = result;@@ -427,7 +447,7 @@ int LZ4_decompress_fast_continue(LZ4_streamDecode_t *LZ4_streamDecode, endOnOutputSize, full, 0, usingExtDict, lz4sd->prefixEnd - lz4sd->prefixSize, - lz4sd->externalDict, lz4sd->extDictSize); + lz4sd->externalDict, lz4sd->extDictSize, NoDynOffset); if (result <= 0) return result;@@ -440,7 +460,7 @@ int LZ4_decompress_fast_continue(LZ4_streamDecode_t *LZ4_streamDecode, result = LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, usingExtDict, (BYTE *)dest, - lz4sd->externalDict, lz4sd->extDictSize); + lz4sd->externalDict, lz4sd->extDictSize, NoDynOffset); if (result <= 0) return result; lz4sd->prefixSize = originalSize;@@ -463,19 +483,19 @@ static FORCE_INLINE int LZ4_decompress_usingDict_generic(const char *source, if (dictSize == 0) return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, - noDict, (BYTE *)dest, NULL, 0); + noDict, (BYTE *)dest, NULL, 0, NoDynOffset); if (dictStart + dictSize == dest) { if (dictSize >= (int)(64 * KB - 1)) return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, - withPrefix64k, (BYTE *)dest - 64 * KB, NULL, 0); + withPrefix64k, (BYTE *)dest - 64 * KB, NULL, 0, NoDynOffset); return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, noDict, - (BYTE *)dest - dictSize, NULL, 0); + (BYTE *)dest - dictSize, NULL, 0, NoDynOffset); } return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, usingExtDict, - (BYTE *)dest, (const BYTE *)dictStart, dictSize); + (BYTE *)dest, (const BYTE *)dictStart, dictSize, NoDynOffset); } int LZ4_decompress_safe_usingDict(const char *source, char *dest,diff --git a/lib/lz4/lz4defs.h b/lib/lz4/lz4defs.h index 00a0b58..9451a73 100644 --- a/lib/lz4/lz4defs.h +++ b/lib/lz4/lz4defs.h@@ -75,6 +75,7 @@ #define WILDCOPYLENGTH 8 #define LASTLITERALS 5 #define MFLIMIT (WILDCOPYLENGTH + MINMATCH) +#define DYN_BIT 0x1 /* Increase this value ==> compression run slower on incompressible data */ #define LZ4_SKIPTRIGGER 6@@ -87,6 +88,7 @@ #define MAXD_LOG 16 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1) +#define MAX_DISTANCE_DYN ((1 << (MAXD_LOG - 1)) - 1) #define STEPSIZE sizeof(size_t) #define ML_BITS 4@@ -147,6 +149,13 @@ static FORCE_INLINE void LZ4_copy8(void *dst, const void *src) #endif } +static FORCE_INLINE void LZ4_copy4(void *dst, const void *src) +{ + U32 a = get_unaligned((const U32 *)src); + + put_unaligned(a, (U32 *)dst); +} + /* * customized variant of memcpy, * which can overwrite up to 7 bytes beyond dstEnd@@ -224,4 +233,6 @@ static FORCE_INLINE unsigned int LZ4_count( typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive; typedef enum { full = 0, partial = 1 } earlyEnd_directive; +typedef enum { NoDynOffset = 0, DynOffset = 1 } Dynamic_Offset; + #endif --1.7.1