I think this is a great patch but, in my view, an even better way to tackle the fundamental problem (the performance limitations) is to use a much faster checksum like xxhash, as has been suggested before: https://lists.samba.org/archive/rsync/2019-October/031975.html
Cheers, Filipe On Mon, 18 May 2020 at 17:08, Jorrit Jongma via rsync <rsync@lists.samba.org> wrote: > This drop-in patch increases the performance of the get_checksum1() > function on x86-64. > > On the target slow CPU performance of the function increased by nearly > 50% in the x86-64 default SSE2 mode, and by nearly 100% if the > compiler was told to enable SSSE3 support. The increase was over 200% > on the fastest CPU tested in SSSE3 mode. > > Transfer time improvement with large files existing on both ends but > with some bits flipped was measured as 5-10%, with the target machine > being CPU limited (still so due to MD5). > > This same patch on (my) GitHub for easier reading: > > https://github.com/Chainfire/rsync/commit/f5d0b32df869a23a74b8b8295e4983b0943866df > > > From f5d0b32df869a23a74b8b8295e4983b0943866df Mon Sep 17 00:00:00 2001 > From: Jorrit Jongma <g...@jongma.org> > Date: Mon, 18 May 2020 00:21:39 +0200 > Subject: [PATCH 1/1] SSE2/SSSE3 optimized version of get_checksum1() for > x86-64 > > --- > Makefile.in | 2 +- > checksum.c | 2 + > checksum_sse2.c | 243 ++++++++++++++++++++++++++++++++++++++++++++++++ > 3 files changed, 246 insertions(+), 1 deletion(-) > create mode 100644 checksum_sse2.c > > diff --git a/Makefile.in b/Makefile.in > index 59649562..e4202336 100644 > --- a/Makefile.in > +++ b/Makefile.in > @@ -40,7 +40,7 @@ OBJS1=flist.o rsync.o generator.o receiver.o > cleanup.o sender.o exclude.o \ > util.o util2.o main.o checksum.o match.o syscall.o log.o backup.o > delete.o > OBJS2=options.o io.o compat.o hlink.o token.o uidlist.o socket.o > hashtable.o \ > fileio.o batch.o clientname.o chmod.o acls.o xattrs.o > -OBJS3=progress.o pipe.o > +OBJS3=progress.o pipe.o checksum_sse2.o > DAEMON_OBJ = params.o loadparm.o clientserver.o access.o connection.o > authenticate.o > popt_OBJS=popt/findme.o popt/popt.o popt/poptconfig.o \ > popt/popthelp.o popt/poptparse.o > diff --git a/checksum.c b/checksum.c > index cd234038..4e696f3d 100644 > --- a/checksum.c > +++ b/checksum.c > @@ -99,6 +99,7 @@ int canonical_checksum(int csum_type) > return csum_type >= CSUM_MD4 ? 1 : 0; > } > > +#ifndef __SSE2__ // see checksum_sse2.c for SSE2/SSSE3 version > /* > a simple 32 bit checksum that can be updated from either end > (inspired by Mark Adler's Adler-32 checksum) > @@ -119,6 +120,7 @@ uint32 get_checksum1(char *buf1, int32 len) > } > return (s1 & 0xffff) + (s2 << 16); > } > +#endif > > void get_checksum2(char *buf, int32 len, char *sum) > { > diff --git a/checksum_sse2.c b/checksum_sse2.c > new file mode 100644 > index 00000000..51662833 > --- /dev/null > +++ b/checksum_sse2.c > @@ -0,0 +1,243 @@ > +/* > + * SSE2/SSSE3-optimized routines to support checksumming of bytes. > + * > + * Copyright (C) 1996 Andrew Tridgell > + * Copyright (C) 1996 Paul Mackerras > + * Copyright (C) 2004-2020 Wayne Davison > + * Copyright (C) 2020 Jorrit Jongma > + * > + * This program is free software; you can redistribute it and/or modify > + * it under the terms of the GNU General Public License as published by > + * the Free Software Foundation; either version 3 of the License, or > + * (at your option) any later version. > + * > + * This program is distributed in the hope that it will be useful, > + * but WITHOUT ANY WARRANTY; without even the implied warranty of > + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the > + * GNU General Public License for more details. > + * > + * You should have received a copy of the GNU General Public License along > + * with this program; if not, visit the http://fsf.org website. > + */ > +/* > + * Optimization target for get_checksum1 was the Intel Atom D2700, the > + * slowest CPU in the test set and the most likely to be CPU limited > during > + * transfers. The combination of intrinsics was chosen specifically for > the > + * most gain on that CPU, other combinations were occasionally slightly > + * faster on the others. > + * > + * While on more modern CPUs transfers are less likely to be CPU limited, > + * lower CPU usage is always better. Improvements may still be seen when > + * matching chunks from NVMe storage even on newer CPUs. > + * > + * Benchmarks C SSE2 SSSE3 > + * - Intel Atom D2700 550 MB/s 750 MB/s 1000 MB/s > + * - Intel i7-7700hq 1850 MB/s 2550 MB/s 4050 MB/s > + * - AMD ThreadRipper 2950x 2900 MB/s 5600 MB/s 8950 MB/s > + * > + * This optimization for get_checksum1 is intentionally limited to x86-64 > as > + * no 32-bit CPU was available for testing. As 32-bit CPUs only have half > the > + * available xmm registers, this optimized version may not be faster than > the > + * pure C version anyway. > + * > + * GCC automatically enables SSE2 support on x86-64 builds. The SSSE3 code > + * path must be enabled manually: ./configure CFLAGS="-mssse3 -O2" > + */ > + > +#ifdef __x86_64__ > +#ifdef __SSE2__ > + > +#include "rsync.h" > + > +#ifdef __SSSE3__ > +#include <immintrin.h> > +#else > +#include <tmmintrin.h> > +#endif > + > +/* Compatibility functions to let our SSSE3 algorithm run on SSE2 */ > + > +static inline __m128i sse_load_si128(void const* buf) { > +#ifdef __SSSE3__ > + return _mm_lddqu_si128(buf); // same as loadu on all but the > oldest SSSE3 CPUs > +#else > + return _mm_loadu_si128(buf); > +#endif > +} > + > +#ifndef __SSSE3__ > +static inline __m128i sse_interleave_odd_epi16(__m128i a, __m128i b) { > + return _mm_packs_epi32( > + _mm_srai_epi32(a, 16), > + _mm_srai_epi32(b, 16) > + ); > +} > + > +static inline __m128i sse_interleave_even_epi16(__m128i a, __m128i b) { > + return sse_interleave_odd_epi16( > + _mm_slli_si128(a, 2), > + _mm_slli_si128(b, 2) > + ); > +} > + > +static inline __m128i sse_mulu_odd_epi8(__m128i a, __m128i b) { > + return _mm_mullo_epi16( > + _mm_srli_epi16(a, 8), > + _mm_srai_epi16(b, 8) > + ); > +} > + > +static inline __m128i sse_mulu_even_epi8(__m128i a, __m128i b) { > + return _mm_mullo_epi16( > + _mm_and_si128(a, _mm_set1_epi16(0xFF)), > + _mm_srai_epi16(_mm_slli_si128(b, 1), 8) > + ); > +} > +#endif > + > +static inline __m128i sse_hadds_epi16(__m128i a, __m128i b) { > +#ifdef __SSSE3__ > + return _mm_hadds_epi16(a, b); > +#else > + return _mm_adds_epi16( > + sse_interleave_even_epi16(a, b), > + sse_interleave_odd_epi16(a, b) > + ); > +#endif > +} > + > +static inline __m128i sse_maddubs_epi16(__m128i a, __m128i b) { > +#ifdef __SSSE3__ > + return _mm_maddubs_epi16(a, b); > +#else > + return _mm_adds_epi16( > + sse_mulu_even_epi8(a, b), > + sse_mulu_odd_epi8(a, b) > + ); > +#endif > +} > + > +/* > + a simple 32 bit checksum that can be updated from either end > + (inspired by Mark Adler's Adler-32 checksum) > + */ > +/* > + Original loop per 4 bytes: > + s2 += 4*(s1 + buf[i]) + 3*buf[i+1] + 2*buf[i+2] + buf[i+3] + > 10*CHAR_OFFSET; > + s1 += buf[i] + buf[i+1] + buf[i+2] + buf[i+3] + 4*CHAR_OFFSET; > + > + SSE2/SSSE3 loop per 32 bytes: > + int16 t1[8]; > + int16 t2[8]; > + for (int j = 0; j < 8; j++) { > + t1[j] = buf[j*4 + i] + buf[j*4 + i+1] + buf[j*4 + i+2] + buf[j*4 + > i+3]; > + t2[j] = 4*buf[j*4 + i] + 3*buf[j*4 + i+1] + 2*buf[j*4 + i+2] + > buf[j*4 + i+3]; > + } > + s2 += 32*s1 + > + 28*t1[0] + 24*t1[1] + 20*t1[2] + 16*t1[3] + 12*t1[4] + > 8*t1[5] + 4*t1[6] + > + t2[0] + t2[1] + t2[2] + t2[3] + t2[4] + t2[5] + t2[6] + t2[7] + > + ((16+32+48+64+80+96) + 8)*CHAR_OFFSET; > + s1 += t1[0] + t1[1] + t1[2] + t1[3] + t1[4] + t1[5] + t1[6] + t1[7] + > + 32*CHAR_OFFSET; > + */ > +uint32 get_checksum1(char *buf1, int32 len) > +{ > + int32 i; > + uint32 s1, s2; > + schar *buf = (schar *)buf1; > + > + i = s1 = s2 = 0; > + if (len > 32) { > + const char mul_t1_buf[16] = {28, 0, 24, 0, 20, 0, 16, 0, 12, > 0, 8, 0, 4, 0, 0, 0}; > + __m128i mul_t1 = sse_load_si128((void const*)mul_t1_buf); > + __m128i ss1 = _mm_setzero_si128(); > + __m128i ss2 = _mm_setzero_si128(); > + > + for (i = 0; i < (len-32); i+=32) { > + // Load ... 2*[int8*16] > + __m128i in8_1 = sse_load_si128((void const*)&buf[i]); > + __m128i in8_2 = sse_load_si128((void const*)&buf[i + 16]); > + > + // (1*buf[i] + 1*buf[i+1]), (1*buf[i+2], 1*buf[i+3]), ... > 2*[int16*8] > + // Fastest, even though multiply by 1 > + __m128i mul_one = _mm_set1_epi8(1); > + __m128i add16_1 = sse_maddubs_epi16(mul_one, in8_1); > + __m128i add16_2 = sse_maddubs_epi16(mul_one, in8_2); > + > + // (4*buf[i] + 3*buf[i+1]), (2*buf[i+2], buf[i+3]), ... > 2*[int16*8] > + __m128i mul_const = _mm_set1_epi32(4 + (3 << 8) + (2 << > 16) + (1 << 24)); > + __m128i mul_add16_1 = sse_maddubs_epi16(mul_const, in8_1); > + __m128i mul_add16_2 = sse_maddubs_epi16(mul_const, in8_2); > + > + // s2 += 32*s1 > + ss2 = _mm_add_epi32(ss2, _mm_slli_epi32(ss1, 5)); > + > + // [sum(t1[0]..t1[6]), X, X, X] [int32*4]; faster than > multiple _mm_hadds_epi16 > + // Shifting left, then shifting right again and shuffling > (rather than just > + // shifting right as with mul32 below) to cheaply end up > with the correct sign > + // extension as we go from int16 to int32. > + __m128i sum_add32 = _mm_add_epi16(add16_1, add16_2); > + sum_add32 = _mm_add_epi16(sum_add32, > _mm_slli_si128(sum_add32, 2)); > + sum_add32 = _mm_add_epi16(sum_add32, > _mm_slli_si128(sum_add32, 4)); > + sum_add32 = _mm_add_epi16(sum_add32, > _mm_slli_si128(sum_add32, 8)); > + sum_add32 = _mm_srai_epi32(sum_add32, 16); > + sum_add32 = _mm_shuffle_epi32(sum_add32, 3); > + > + // [sum(t2[0]..t2[6]), X, X, X] [int32*4]; faster than > multiple _mm_hadds_epi16 > + __m128i sum_mul_add32 = _mm_add_epi16(mul_add16_1, > mul_add16_2); > + sum_mul_add32 = _mm_add_epi16(sum_mul_add32, > _mm_slli_si128(sum_mul_add32, 2)); > + sum_mul_add32 = _mm_add_epi16(sum_mul_add32, > _mm_slli_si128(sum_mul_add32, 4)); > + sum_mul_add32 = _mm_add_epi16(sum_mul_add32, > _mm_slli_si128(sum_mul_add32, 8)); > + sum_mul_add32 = _mm_srai_epi32(sum_mul_add32, 16); > + sum_mul_add32 = _mm_shuffle_epi32(sum_mul_add32, 3); > + > + // s1 += t1[0] + t1[1] + t1[2] + t1[3] + t1[4] + t1[5] + > t1[6] + t1[7] > + ss1 = _mm_add_epi32(ss1, sum_add32); > + > + // s2 += t2[0] + t2[1] + t2[2] + t2[3] + t2[4] + t2[5] + > t2[6] + t2[7] > + ss2 = _mm_add_epi32(ss2, sum_mul_add32); > + > + // [t1[0], t1[1], ...] [int16*8] > + // We could've combined this with generating sum_add32 > above and save one _mm_add_epi16, > + // but benchmarking shows that as being slower > + __m128i add16 = sse_hadds_epi16(add16_1, add16_2); > + > + // [t1[0], t1[1], ...] -> [t1[0]*28 + t1[1]*24, ...] [int32*4] > + __m128i mul32 = _mm_madd_epi16(add16, mul_t1); > + > + // [sum(mul32), X, X, X] [int32*4]; faster than multiple > _mm_hadd_epi32 > + mul32 = _mm_add_epi32(mul32, _mm_srli_si128(mul32, 4)); > + mul32 = _mm_add_epi32(mul32, _mm_srli_si128(mul32, 8)); > + > + // s2 += 28*t1[0] + 24*t1[1] + 20*t1[2] + 16*t1[3] + > 12*t1[4] + 8*t1[5] + 4*t1[6] > + ss2 = _mm_add_epi32(ss2, mul32); > + > +#if CHAR_OFFSET != 0 > + // s1 += 32*CHAR_OFFSET > + __m128i char_offset_multiplier = _mm_set1_epi32(32 * > CHAR_OFFSET); > + ss1 = _mm_add_epi32(ss1, char_offset_multiplier); > + > + // s2 += 528*CHAR_OFFSET > + char_offset_multiplier = _mm_set1_epi32(528 * CHAR_OFFSET); > + ss2 = _mm_add_epi32(ss2, char_offset_multiplier); > +#endif > + } > + > + int32 x[4] = {0}; > + _mm_store_si128((void*)x, ss1); > + s1 = x[0]; > + _mm_store_si128((void*)x, ss2); > + s2 = x[0]; > + } > + for (; i < (len-4); i+=4) { > + s2 += 4*(s1 + buf[i]) + 3*buf[i+1] + 2*buf[i+2] + buf[i+3] + > 10*CHAR_OFFSET; > + s1 += (buf[i] + buf[i+1] + buf[i+2] + buf[i+3] + 4*CHAR_OFFSET); > + } > + for (; i < len; i++) { > + s1 += (buf[i]+CHAR_OFFSET); s2 += s1; > + } > + return (s1 & 0xffff) + (s2 << 16); > +} > + > +#endif > +#endif > -- > 2.25.2 > > -- > Please use reply-all for most replies to avoid omitting the mailing list. > To unsubscribe or change options: > https://lists.samba.org/mailman/listinfo/rsync > Before posting, read: http://www.catb.org/~esr/faqs/smart-questions.html >
-- Please use reply-all for most replies to avoid omitting the mailing list. To unsubscribe or change options: https://lists.samba.org/mailman/listinfo/rsync Before posting, read: http://www.catb.org/~esr/faqs/smart-questions.html