Jorrit Jongma
2020-May-18 15:06 UTC
[PATCH] SSE2/SSSE3 optimized version of get_checksum1() for x86-64
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 2001From: Jorrit Jongma <git at 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
Ben RUBSON
2020-May-18 15:17 UTC
[PATCH] SSE2/SSSE3 optimized version of get_checksum1() for x86-64
> On 18 May 2020, at 17:06, Jorrit Jongma via rsync <rsync at lists.samba.org> wrote: > > This drop-in patch increases the performance of the get_checksum1() > function on x86-64.As ref, rather related to this : https://bugzilla.samba.org/show_bug.cgi?id=13082 <https://bugzilla.samba.org/show_bug.cgi?id=13082> Thank you Jorrit ! -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.samba.org/pipermail/rsync/attachments/20200518/878ac93b/attachment.htm>
Filipe Maia
2020-May-18 15:42 UTC
[PATCH] SSE2/SSSE3 optimized version of get_checksum1() for x86-64
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 at 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 <git at 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 >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.samba.org/pipermail/rsync/attachments/20200518/26ecd0f0/attachment.htm>
Jorrit Jongma
2020-May-18 15:55 UTC
[PATCH] SSE2/SSSE3 optimized version of get_checksum1() for x86-64
I don't disagree that MD5 could (or even should) be replaced so it is no longer the bottleneck in several real-world cases (including mine). However this patch is not for MD5 performance, rather for the rolling checksum rsync uses to match blocks on existing files on both ends to reduce transfer size. On Mon, May 18, 2020 at 5:44 PM Filipe Maia via rsync <rsync at lists.samba.org> wrote:> > 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 at 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 <git at 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
Jorrit Jongma
2020-May-18 15:58 UTC
[PATCH] SSE2/SSSE3 optimized version of get_checksum1() for x86-64
Well, don't get too excited, get_checksum1() (the function optimized here) is not the great performance limiter in this case, it's get_checksum2() and sum_update(), which will be using MD5. You can force using MD4, but on the slower CPU's I've tested in practice that is slower rather than faster, contrary to what would be expected. While this patch will improve things a little, to improve things a lot we need to tackle or replace MD5. Unfortunately, single stream MD5 cannot be effectively optimized with SSE, at least I've not seen an SSE version faster than pure C, and I've looked into it. What we _can_ do is parallelize multiple streams using SSE, which may double to triple the throughput at the same CPU load under ideal circumstances. However, this cannot be applied to rsync as-is as it doesn't process multiple files simultaneously (and it is questionable if that is something we should even want). The single-file stream could still be parallelized this way but it would require a slight change in checksum generation that would in turn require a protocol change - both ends need to support it. At that point we might as well swap MD5 out completely, though I will still be digging deeper into this case. The good news is that this parallelization _is_ possible in a drop-in fashion for the case where rsync is comparing the chunks on both ends, the same case where the get_checksum1() patch shows its benefits. I estimate performance improvements could reach about 30% for that specific case (re-transferring large yet slightly modified files), but that does nothing for the performance of whole file checksumming or the transfer of new files. Depending on your use-case you may never or rarely even see that performance improvement in action. It applies for my use-case though, so I am looking into this. On Mon, May 18, 2020 at 5:18 PM Ben RUBSON via rsync <rsync at lists.samba.org> wrote:> > On 18 May 2020, at 17:06, Jorrit Jongma via rsync <rsync at lists.samba.org> wrote: > > This drop-in patch increases the performance of the get_checksum1() > function on x86-64. > > > As ref, rather related to this : https://bugzilla.samba.org/show_bug.cgi?id=13082 > > Thank you Jorrit ! > -- > 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
Sebastian Andrzej Siewior
2020-May-18 19:15 UTC
[PATCH] SSE2/SSSE3 optimized version of get_checksum1() for x86-64
On 2020-05-18 17:06:51 [+0200], Jorrit Jongma via rsync wrote:> 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); > } > +#endifYou can't replace the code like that with SSE2+. You need runtime detection for this. Otherwise it can't be enabled by distros becuase it would fail on CPUs without SSE2+. Only SSE is part of generic x86-64. Sebastian
Jorrit Jongma
2020-May-18 19:55 UTC
[PATCH] SSE2/SSSE3 optimized version of get_checksum1() for x86-64
What do you base this on? Per https://gcc.gnu.org/onlinedocs/gcc/x86-Options.html : "For the x86-32 compiler, you must use -march=cpu-type, -msse or -msse2 switches to enable SSE extensions and make this option effective. For the x86-64 compiler, these extensions are enabled by default." That reads to me like we're fine for SSE2. As stated in my comments, SSSE3 support must be manually enabled at build time. Your comment would imply that SSSE3 is enabled out of the box on builds on machines that support it, this is not the case (it certainly isn't on my Ubuntu box). It would be preferred to detect this at runtime but getting that to work on GCC is (apparently) a mess, and would probably require modifications to configure/Makefile/etc that I'm not comfortable doing, as my lack of expertise on those would probably lead me to break the build for somebody else. If someone knowledgable enough in that area wants to fix it, though... The only reason there's an SSE2 backport (you'll find SSSE3 support on most CPUs up to nearly a decade old) in the first place is because by my understanding SSE2 is supported on all x86-64 CPUs out of the box.> You can't replace the code like that with SSE2+. You need runtime > detection for this. Otherwise it can't be enabled by distros becuase it > would fail on CPUs without SSE2+. Only SSE is part of generic x86-64.