From 029c7e18fb4435c29ef31a14d5d3040cb1a0dca1 Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Thu, 16 Mar 2017 10:43:36 -0500 Subject: [PATCH] inflate: improve performance of memory copy operations When memory copy operations happen byte by byte, the processors are unable to fuse the loads and stores together because of aliasing issues. This patch clusters some of the memory copy operations in chunks of 16 and 8 bytes. For byte memset, the compiler knows how to prepare the chunk to be stored. When the memset pattern is larger than a byte, this patch builds the pattern for chunk memset using the same technique as in Simon Hosie's patch https://codereview.chromium.org/2722063002 This patch improves by 50% the performance of zlib decompression of a 50K PNG on aarch64-linux and x86_64-linux when compiled with gcc-7 or llvm-5. The number of executed instructions reported by valgrind --tool=cachegrind on the decompression of a 50K PNG file on aarch64-linux: - before the patch: I refs: 3,783,757,451 D refs: 1,574,572,882 (869,116,630 rd + 705,456,252 wr) - with the patch: I refs: 2,391,899,214 D refs: 899,359,836 (516,666,051 rd + 382,693,785 wr) The compression of a 260MB directory containing the code of llvm into a tar.gz of 35MB and decompressing that with minigzip -d on i7-4790K x86_64-linux, it takes 0.533s before the patch and 0.493s with the patch, on Juno-r0 aarch64-linux A57, it takes 2.796s before the patch and 2.467s with the patch, on Juno-r0 aarch64-linux A53, it takes 4.055s before the patch and 3.604s with the patch. --- Makefile.in | 10 +- inffast.c | 83 +++++------ inflate.c | 27 ++-- memcopy.h | 394 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 456 insertions(+), 58 deletions(-) create mode 100644 memcopy.h diff --git a/Makefile.in b/Makefile.in index c50e5126..5d8c95db 100644 --- a/Makefile.in +++ b/Makefile.in @@ -318,8 +318,9 @@ deflate.o: $(SRCDIR)/deflate.h $(SRCDIR)/deflate_p.h $(SRCDIR)/match.h $(SRCDIR) deflate_fast.o: $(SRCDIR)/deflate.h $(SRCDIR)/deflate_p.h $(SRCDIR)/match.h $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h deflate_medium.o: $(SRCDIR)/deflate.h $(SRCDIR)/deflate_p.h $(SRCDIR)/match.h $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h deflate_slow.o: $(SRCDIR)/deflate.h $(SRCDIR)/deflate_p.h $(SRCDIR)/match.h $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h -infback.o inflate.o: $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h $(SRCDIR)/inftrees.h $(SRCDIR)/inflate.h $(SRCDIR)/inffast.h $(SRCDIR)/inffixed.h -inffast.o: $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h $(SRCDIR)/inftrees.h $(SRCDIR)/inflate.h $(SRCDIR)/inffast.h +infback.o: $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h $(SRCDIR)/inftrees.h $(SRCDIR)/inflate.h $(SRCDIR)/inffast.h $(SRCDIR)/inffixed.h +inffast.o: $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h $(SRCDIR)/inftrees.h $(SRCDIR)/inflate.h $(SRCDIR)/inffast.h $(SRCDIR)/memcopy.h +inflate.o: $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h $(SRCDIR)/inftrees.h $(SRCDIR)/inflate.h $(SRCDIR)/inffast.h $(SRCDIR)/inffixed.h $(SRCDIR)/memcopy.h inftrees.o: $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h $(SRCDIR)/inftrees.h trees.o: $(SRCDIR)/deflate.h $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h $(SRCDIR)/trees.h zutil.o: $(SRCDIR)/zutil.h $(SRCDIR)/gzguts.h $(SRCDIR)/zlib.h zconf.h @@ -337,8 +338,9 @@ deflate.lo: $(SRCDIR)/deflate.h $(SRCDIR)/deflate_p.h $(SRCDIR)/match.h $(SRCDIR deflate_fast.lo: $(SRCDIR)/deflate.h $(SRCDIR)/deflate_p.h $(SRCDIR)/match.h $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h deflate_medium.lo: $(SRCDIR)/deflate.h $(SRCDIR)/deflate_p.h $(SRCDIR)/match.h $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h deflate_slow.lo: $(SRCDIR)/deflate.h $(SRCDIR)/deflate_p.h $(SRCDIR)/match.h $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h -infback.lo inflate.lo: $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h $(SRCDIR)/inftrees.h $(SRCDIR)/inflate.h $(SRCDIR)/inffast.h $(SRCDIR)/inffixed.h -inffast.lo: $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h $(SRCDIR)/inftrees.h $(SRCDIR)/inflate.h $(SRCDIR)/inffast.h +infback.lo: $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h $(SRCDIR)/inftrees.h $(SRCDIR)/inflate.h $(SRCDIR)/inffast.h $(SRCDIR)/inffixed.h +inffast.lo: $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h $(SRCDIR)/inftrees.h $(SRCDIR)/inflate.h $(SRCDIR)/inffast.h $(SRCDIR)/memcopy.h +inflate.lo: $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h $(SRCDIR)/inftrees.h $(SRCDIR)/inflate.h $(SRCDIR)/inffast.h $(SRCDIR)/inffixed.h $(SRCDIR)/memcopy.h inftrees.lo: $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h $(SRCDIR)/inftrees.h trees.lo: $(SRCDIR)/deflate.h $(SRCDIR)/zutil.h $(SRCDIR)/zlib.h zconf.h $(SRCDIR)/trees.h zutil.lo: $(SRCDIR)/zutil.h $(SRCDIR)/gzguts.h $(SRCDIR)/zlib.h zconf.h diff --git a/inffast.c b/inffast.c index 1e60b239..32bb4f34 100644 --- a/inffast.c +++ b/inffast.c @@ -7,6 +7,7 @@ #include "inftrees.h" #include "inflate.h" #include "inffast.h" +#include "memcopy.h" /* Return the low n bits of the bit accumulator (n < 16) */ #define BITS(n) \ @@ -195,10 +196,9 @@ void ZLIB_INTERNAL inflate_fast(z_stream *strm, unsigned long start) { input data or output space */ do { if (bits < 15) { - hold += (uint32_t)(*in++) << bits; - bits += 8; - hold += (uint32_t)(*in++) << bits; - bits += 8; + hold += load_short(in, bits); + in += 2; + bits += 16; } here = lcode[hold & lmask]; dolen: @@ -222,10 +222,9 @@ void ZLIB_INTERNAL inflate_fast(z_stream *strm, unsigned long start) { } Tracevv((stderr, "inflate: length %u\n", len)); if (bits < 15) { - hold += (uint32_t)(*in++) << bits; - bits += 8; - hold += (uint32_t)(*in++) << bits; - bits += 8; + hold += load_short(in, bits); + in += 2; + bits += 16; } here = dcode[hold & dmask]; dodist: @@ -303,10 +302,18 @@ void ZLIB_INTERNAL inflate_fast(z_stream *strm, unsigned long start) { if (op < len) { /* still need some from output */ len -= op; out = chunkcopysafe(out, from, op, safe); - out = chunkunroll(out, &dist, &len); - out = chunkcopysafe(out, out - dist, len, safe); + if (dist == 1) { + out = byte_memset(out, len); + } else { + out = chunkunroll(out, &dist, &len); + out = chunkcopysafe(out, out - dist, len, safe); + } } else { - out = chunkcopysafe(out, from, len, safe); + if (from - out == 1) { + out = byte_memset(out, len); + } else { + out = chunkcopysafe(out, from, len, safe); + } } #else from = window; @@ -347,46 +354,30 @@ void ZLIB_INTERNAL inflate_fast(z_stream *strm, unsigned long start) { from = out - dist; /* rest from output */ } } - while (len > 2) { - *out++ = *from++; - *out++ = *from++; - *out++ = *from++; - len -= 3; - } - if (len) { - *out++ = *from++; - if (len > 1) - *out++ = *from++; - } + + out = chunk_copy(out, from, (int) (out - from), len); #endif } else { #ifdef INFFAST_CHUNKSIZE - /* Whole reference is in range of current output. No - range checks are necessary because we start with room - for at least 258 bytes of output, so unroll and roundoff - operations can write beyond `out+len` so long as they - stay within 258 bytes of `out`. - */ - out = chunkunroll(out, &dist, &len); - out = chunkcopy(out, out - dist, len); -#else - from = out - dist; /* copy direct from output */ - if (dist == 1) { - memset (out, *from, len); - out += len; + if (dist == 1 && len >= sizeof(uint64_t)) { + out = byte_memset(out, len); } else { - do { /* minimum length is three */ - *out++ = *from++; - *out++ = *from++; - *out++ = *from++; - len -= 3; - } while (len > 2); - if (len) { - *out++ = *from++; - if (len > 1) - *out++ = *from++; - } + /* Whole reference is in range of current output. No + range checks are necessary because we start with room + for at least 258 bytes of output, so unroll and roundoff + operations can write beyond `out+len` so long as they + stay within 258 bytes of `out`. + */ + out = chunkunroll(out, &dist, &len); + out = chunkcopy(out, out - dist, len); } +#else + if (len < sizeof(uint64_t)) + out = set_bytes(out, out - dist, dist, len); + else if (dist == 1) + out = byte_memset(out, len); + else + out = chunk_memset(out, out - dist, dist, len); #endif } } else if ((op & 64) == 0) { /* 2nd level distance code */ diff --git a/inflate.c b/inflate.c index 8484bc32..cf0942c6 100644 --- a/inflate.c +++ b/inflate.c @@ -84,6 +84,7 @@ #include "inftrees.h" #include "inflate.h" #include "inffast.h" +#include "memcopy.h" #ifdef MAKEFIXED # ifndef BUILDFIXED @@ -1149,17 +1150,27 @@ int ZEXPORT inflate(z_stream *strm, int flush) { } if (copy > state->length) copy = state->length; + if (copy > left) + copy = left; + left -= copy; + state->length -= copy; + if (copy >= sizeof(uint64_t)) + put = chunk_memcpy(put, from, copy); + else + put = copy_bytes(put, from, copy); } else { /* copy from output */ - from = put - state->offset; + unsigned offset = state->offset; + from = put - offset; copy = state->length; + if (copy > left) + copy = left; + left -= copy; + state->length -= copy; + if (copy >= sizeof(uint64_t)) + put = chunk_memset(put, from, offset, copy); + else + put = set_bytes(put, from, offset, copy); } - if (copy > left) - copy = left; - left -= copy; - state->length -= copy; - do { - *put++ = *from++; - } while (--copy); if (state->length == 0) state->mode = LEN; break; diff --git a/memcopy.h b/memcopy.h new file mode 100644 index 00000000..eee8cd60 --- /dev/null +++ b/memcopy.h @@ -0,0 +1,394 @@ +/* memcopy.h -- inline functions to copy small data chunks. + * For conditions of distribution and use, see copyright notice in zlib.h + */ +#ifndef MEMCOPY_H_ +#define MEMCOPY_H_ + +#if (defined(__GNUC__) || defined(__clang__)) +#define MEMCPY __builtin_memcpy +#define MEMSET __builtin_memset +#else +#define MEMCPY memcpy +#define MEMSET memset +#endif + +/* Load a short from IN and place the bytes at offset BITS in the result. */ +static inline uint32_t load_short(const unsigned char *in, unsigned bits) { + union { + uint16_t a; + uint8_t b[2]; + } chunk; + MEMCPY(&chunk, in, sizeof(uint16_t)); + +#if BYTE_ORDER == LITTLE_ENDIAN + uint32_t res = chunk.a; + return res << bits; +#else + uint32_t c0 = chunk.b[0]; + uint32_t c1 = chunk.b[1]; + c0 <<= bits; + c1 <<= bits + 8; + return c0 + c1; +#endif +} + +static inline unsigned char *copy_1_bytes(unsigned char *out, unsigned char *from) { + *out++ = *from; + return out; +} + +static inline unsigned char *copy_2_bytes(unsigned char *out, unsigned char *from) { + uint16_t chunk; + unsigned sz = sizeof(chunk); + MEMCPY(&chunk, from, sz); + MEMCPY(out, &chunk, sz); + return out + sz; +} + +static inline unsigned char *copy_3_bytes(unsigned char *out, unsigned char *from) { + out = copy_1_bytes(out, from); + return copy_2_bytes(out, from + 1); +} + +static inline unsigned char *copy_4_bytes(unsigned char *out, unsigned char *from) { + uint32_t chunk; + unsigned sz = sizeof(chunk); + MEMCPY(&chunk, from, sz); + MEMCPY(out, &chunk, sz); + return out + sz; +} + +static inline unsigned char *copy_5_bytes(unsigned char *out, unsigned char *from) { + out = copy_1_bytes(out, from); + return copy_4_bytes(out, from + 1); +} + +static inline unsigned char *copy_6_bytes(unsigned char *out, unsigned char *from) { + out = copy_2_bytes(out, from); + return copy_4_bytes(out, from + 2); +} + +static inline unsigned char *copy_7_bytes(unsigned char *out, unsigned char *from) { + out = copy_3_bytes(out, from); + return copy_4_bytes(out, from + 3); +} + +static inline unsigned char *copy_8_bytes(unsigned char *out, unsigned char *from) { + uint64_t chunk; + unsigned sz = sizeof(chunk); + MEMCPY(&chunk, from, sz); + MEMCPY(out, &chunk, sz); + return out + sz; +} + +/* Copy LEN bytes (7 or fewer) from FROM into OUT. Return OUT + LEN. */ +static inline unsigned char *copy_bytes(unsigned char *out, unsigned char *from, unsigned len) { + Assert(len < 8, "copy_bytes should be called with less than 8 bytes"); + +#ifndef UNALIGNED_OK + while (len--) { + *out++ = *from++; + } + return out; +#else + switch (len) { + case 7: + return copy_7_bytes(out, from); + case 6: + return copy_6_bytes(out, from); + case 5: + return copy_5_bytes(out, from); + case 4: + return copy_4_bytes(out, from); + case 3: + return copy_3_bytes(out, from); + case 2: + return copy_2_bytes(out, from); + case 1: + return copy_1_bytes(out, from); + case 0: + return out; + default: + Assert(0, "should not happen"); + } + + return out; +#endif /* UNALIGNED_OK */ +} + +/* Copy LEN bytes (7 or fewer) from FROM into OUT. Return OUT + LEN. */ +static inline unsigned char *set_bytes(unsigned char *out, unsigned char *from, unsigned dist, unsigned len) { + Assert(len < 8, "set_bytes should be called with less than 8 bytes"); + +#ifndef UNALIGNED_OK + while (len--) { + *out++ = *from++; + } + return out; +#else + if (dist >= len) + return copy_bytes(out, from, len); + + switch (dist) { + case 6: + Assert(len == 7, "len should be exactly 7"); + out = copy_6_bytes(out, from); + return copy_1_bytes(out, from); + + case 5: + Assert(len == 6 || len == 7, "len should be either 6 or 7"); + out = copy_5_bytes(out, from); + return copy_bytes(out, from, len - 5); + + case 4: + Assert(len == 5 || len == 6 || len == 7, "len should be either 5, 6, or 7"); + out = copy_4_bytes(out, from); + return copy_bytes(out, from, len - 4); + + case 3: + Assert(4 <= len && len <= 7, "len should be between 4 and 7"); + out = copy_3_bytes(out, from); + switch (len) { + case 7: + return copy_4_bytes(out, from); + case 6: + return copy_3_bytes(out, from); + case 5: + return copy_2_bytes(out, from); + case 4: + return copy_1_bytes(out, from); + default: + Assert(0, "should not happen"); + break; + } + + case 2: + Assert(3 <= len && len <= 7, "len should be between 3 and 7"); + out = copy_2_bytes(out, from); + switch (len) { + case 7: + out = copy_4_bytes(out, from); + out = copy_1_bytes(out, from); + return out; + case 6: + out = copy_4_bytes(out, from); + return out; + case 5: + out = copy_2_bytes(out, from); + out = copy_1_bytes(out, from); + return out; + case 4: + out = copy_2_bytes(out, from); + return out; + case 3: + out = copy_1_bytes(out, from); + return out; + default: + Assert(0, "should not happen"); + break; + } + + case 1: + Assert(2 <= len && len <= 7, "len should be between 2 and 7"); + unsigned char c = *from; + switch (len) { + case 7: + MEMSET(out, c, 7); + return out + 7; + case 6: + MEMSET(out, c, 6); + return out + 6; + case 5: + MEMSET(out, c, 5); + return out + 5; + case 4: + MEMSET(out, c, 4); + return out + 4; + case 3: + MEMSET(out, c, 3); + return out + 3; + case 2: + MEMSET(out, c, 2); + return out + 2; + default: + Assert(0, "should not happen"); + break; + } + } + return out; +#endif /* UNALIGNED_OK */ +} + +/* Byte by byte semantics: copy LEN bytes from OUT + DIST and write them to OUT. Return OUT + LEN. */ +static inline unsigned char *chunk_memcpy(unsigned char *out, unsigned char *from, unsigned len) { + unsigned sz = sizeof(uint64_t); + Assert(len >= sz, "chunk_memcpy should be called on larger chunks"); + + /* Copy a few bytes to make sure the loop below has a multiple of SZ bytes to be copied. */ + copy_8_bytes(out, from); + + unsigned rem = len % sz; + len /= sz; + out += rem; + from += rem; + + unsigned by8 = len % sz; + len -= by8; + switch (by8) { + case 7: + out = copy_8_bytes(out, from); + from += sz; + case 6: + out = copy_8_bytes(out, from); + from += sz; + case 5: + out = copy_8_bytes(out, from); + from += sz; + case 4: + out = copy_8_bytes(out, from); + from += sz; + case 3: + out = copy_8_bytes(out, from); + from += sz; + case 2: + out = copy_8_bytes(out, from); + from += sz; + case 1: + out = copy_8_bytes(out, from); + from += sz; + } + + while (len) { + out = copy_8_bytes(out, from); + from += sz; + out = copy_8_bytes(out, from); + from += sz; + out = copy_8_bytes(out, from); + from += sz; + out = copy_8_bytes(out, from); + from += sz; + out = copy_8_bytes(out, from); + from += sz; + out = copy_8_bytes(out, from); + from += sz; + out = copy_8_bytes(out, from); + from += sz; + out = copy_8_bytes(out, from); + from += sz; + + len -= 8; + } + + return out; +} + +/* Memset LEN bytes in OUT with the value at OUT - 1. Return OUT + LEN. */ +static inline unsigned char *byte_memset(unsigned char *out, unsigned len) { + unsigned sz = sizeof(uint64_t); + Assert(len >= sz, "byte_memset should be called on larger chunks"); + + unsigned char *from = out - 1; + unsigned char c = *from; + + /* First, deal with the case when LEN is not a multiple of SZ. */ + MEMSET(out, c, sz); + unsigned rem = len % sz; + len /= sz; + out += rem; + from += rem; + + unsigned by8 = len % 8; + len -= by8; + switch (by8) { + case 7: + MEMSET(out, c, sz); + out += sz; + case 6: + MEMSET(out, c, sz); + out += sz; + case 5: + MEMSET(out, c, sz); + out += sz; + case 4: + MEMSET(out, c, sz); + out += sz; + case 3: + MEMSET(out, c, sz); + out += sz; + case 2: + MEMSET(out, c, sz); + out += sz; + case 1: + MEMSET(out, c, sz); + out += sz; + } + + while (len) { + /* When sz is a constant, the compiler replaces __builtin_memset with an + inline version that does not incur a function call overhead. */ + MEMSET(out, c, sz); + out += sz; + MEMSET(out, c, sz); + out += sz; + MEMSET(out, c, sz); + out += sz; + MEMSET(out, c, sz); + out += sz; + MEMSET(out, c, sz); + out += sz; + MEMSET(out, c, sz); + out += sz; + MEMSET(out, c, sz); + out += sz; + MEMSET(out, c, sz); + out += sz; + len -= 8; + } + + return out; +} + +/* Copy DIST bytes from OUT - DIST into OUT + DIST * k, for 0 <= k < LEN/DIST. Return OUT + LEN. */ +static inline unsigned char *chunk_memset(unsigned char *out, unsigned char *from, unsigned dist, unsigned len) { + if (dist >= len) + return chunk_memcpy(out, from, len); + + Assert(len >= sizeof(uint64_t), "chunk_memset should be called on larger chunks"); + + /* Double up the size of the memset pattern until reaching the largest pattern of size less than SZ. */ + unsigned sz = sizeof(uint64_t); + while (dist < len && dist < sz) { + copy_8_bytes(out, from); + + out += dist; + len -= dist; + dist += dist; + + /* Make sure the next memcpy has at least SZ bytes to be copied. */ + if (len < sz) + /* Finish up byte by byte when there are not enough bytes left. */ + return set_bytes(out, from, dist, len); + } + + return chunk_memcpy(out, from, len); +} + +/* Byte by byte semantics: copy LEN bytes from FROM and write them to OUT. Return OUT + LEN. */ +static inline unsigned char *chunk_copy(unsigned char *out, unsigned char *from, int dist, unsigned len) { + if (len < sizeof(uint64_t)) { + if (dist > 0) + return set_bytes(out, from, dist, len); + + return copy_bytes(out, from, len); + } + + if (dist == 1) + return byte_memset(out, len); + + if (dist > 0) + return chunk_memset(out, from, dist, len); + + return chunk_memcpy(out, from, len); +} + +#endif /* MEMCOPY_H_ */ -- 2.47.2