rsync - May 2020 - [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

On 2020-05-18 17:55:58 [+0200], Jorrit Jongma via rsync
wrote:
> 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.
Still. You claim in your patch that

| Benchmarks                   C           SSE2        SSSE3
| - Intel i7-7700hq            1850 MB/s   2550 MB/s   4050 MB/s

while xxhash [0] claims on a Core i5-3340M @2.7GHz that:

|Version	Speed on 64-bit	Speed on 32-bit
|XXH64		13.8 GB/s	1.9 GB/s

so using xxhash64 for that work would also boost !x86 platforms.

However your patch has the benefit that no changes are required on the
remote side. I like that.

[0] https://github.com/Cyan4973/xxHash#benchmarks

Sebastian

That is the goal, a drop-in optimization.

I don't know if xxhash has the required properties to be able to
replace the rolling checksum (bytes need to be able to easily be
shifted on/off at boths ends, see match.c).

However, as there's also talk of replacing the MD5 checksum with
xxhash (again, the rolling checksum isn't the MD5 checksum, they're
two different checksums used at different times for different
reasons), and that would lead to a much larger performance benefit
than replacing the rolling checksum, I suggest we keep xxhash over
there. xxhash isn't a cryptographic checksum, and if we replace MD5
with xxhash we still have two different checksums being verified when
blocks are replaced, which should increase their total strength
(decrease the odds of a collision).

You could argue xxhash is fast enough to replace both checksums even
if the rolling checksum has to be recalculated for every shifted byte,
but that would require extensive testing and some study into how to
refactor the double checksum into a single one while maintaining
backward compatibility (could be easy, could be hard).
> Still. You claim in your patch that
>
> | Benchmarks                   C           SSE2        SSSE3
> | - Intel i7-7700hq            1850 MB/s   2550 MB/s   4050 MB/s
>
> while xxhash [0] claims on a Core i5-3340M @2.7GHz that:
>
> |Version        Speed on 64-bit Speed on 32-bit
> |XXH64          13.8 GB/s       1.9 GB/s
>
> so using xxhash64 for that work would also boost !x86 platforms.
>
> However your patch has the benefit that no changes are required on the
> remote side. I like that.
>
> [0] https://github.com/Cyan4973/xxHash#benchmarks