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