[RHEL7,COMMIT] ms/xxHash: create arch dependent 32/64-bit xxhash()

Submitted by Konstantin Khorenko on Nov. 24, 2018, 3:12 p.m.

Details

Message ID 201811241512.wAOFCBnS030374@finist-ce7.sw.ru
State New
Series "ksm: Switch to xxhash hash algorithm"
Headers show

Commit Message

Konstantin Khorenko Nov. 24, 2018, 3:12 p.m.
The commit is pushed to "branch-rh7-3.10.0-862.20.2.vz7.73.x-ovz" and will appear at https://src.openvz.org/scm/ovz/vzkernel.git
after rh7-3.10.0-862.20.2.vz7.73.8
------>
commit 4d54c1ca1c908f02912f9d8ae2bc6d18ba8c2237
Author: Timofey Titovets <nefelim4ag@gmail.com>
Date:   Sat Nov 24 18:12:11 2018 +0300

    ms/xxHash: create arch dependent 32/64-bit xxhash()
    
    Patch series "Currently used jhash are slow enough and replace it allow as
    to make KSM", v8.
    
    Speed (in kernel):
            ksm: crc32c   hash() 12081 MB/s
            ksm: xxh64    hash()  8770 MB/s
            ksm: xxh32    hash()  4529 MB/s
            ksm: jhash2   hash()  1569 MB/s
    
    Sioh Lee's testing (copy from other mail):
    
    Test platform: openstack cloud platform (NEWTON version)
    Experiment node: openstack based cloud compute node (CPU: xeon E5-2620 v3, memory 64gb)
    VM: (2 VCPU, RAM 4GB, DISK 20GB) * 4
    Linux kernel: 4.14 (latest version)
    KSM setup - sleep_millisecs: 200ms, pages_to_scan: 200
    
    Experiment process:
    Firstly, we turn off KSM and launch 4 VMs.  Then we turn on the KSM and
    measure the checksum computation time until full_scans become two.
    
    The experimental results (the experimental value is the average of the measured values)
    crc32c_intel: 1084.10ns
    crc32c (no hardware acceleration): 7012.51ns
    xxhash32: 2227.75ns
    xxhash64: 1413.16ns
    jhash2: 5128.30ns
    
    In summary, the result shows that crc32c_intel has advantages over all of
    the hash function used in the experiment.  (decreased by 84.54% compared
    to crc32c, 78.86% compared to jhash2, 51.33% xxhash32, 23.28% compared to
    xxhash64) the results are similar to those of Timofey.
    
    But, use only xxhash for now, because for using crc32c, cryptoapi must be
    initialized first - that require some tricky solution to work good in all
    situations.
    
    So:
    
    - First patch implement compile time pickup of fastest implementation of
      xxhash for target platform.
    
    - The second patch replaces jhash2 with xxhash
    
    This patch (of 2):
    
    xxh32() - fast on both 32/64-bit platforms
    xxh64() - fast only on 64-bit platform
    
    Create xxhash() which will pick up the fastest version at compile time.
    
    Link: http://lkml.kernel.org/r/20181023182554.23464-2-nefelim4ag@gmail.com
    Signed-off-by: Timofey Titovets <nefelim4ag@gmail.com>
    Reviewed-by: Pavel Tatashin <pavel.tatashin@microsoft.com>
    Reviewed-by: Mike Rapoport <rppt@linux.vnet.ibm.com>
    Reviewed-by: Andrew Morton <akpm@linux-foundation.org>
    Cc: Andrea Arcangeli <aarcange@redhat.com>
    Cc: leesioh <solee@os.korea.ac.kr>
    Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
    Signed-off-by: Kirill Tkhai <ktkhai@virtuozzo.com>
    
    =====================
    Patchset description:
    
    ksm: Switch to xxhash hash algorithm
    
    xxhash shows better performance in comparison to currently
    used jhash2:
    
            ksm: xxh64 hash() 8770 MB/s
            ksm: xxh32 hash() 4529 MB/s
            ksm: jhash2 hash() 1569 MB/s
    
    Note, that algorithm module lib/xxhash.c is already in ms kernel [1/3],
    while [2-3/3] just make ksm to use it (but they also already in akpm tree).
    
    This should improve ksm performance in some way.
    
    Nick Terrell (1):
          lib: Add xxhash module
    
    Timofey Titovets (2):
          xxHash: create arch dependent 32/64-bit xxhash()
          ksm: replace jhash2 with xxhash
    
    https://jira.sw.ru/browse/PSBM-90044
---
 include/linux/xxhash.h | 23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

Patch hide | download patch | download mbox

diff --git a/include/linux/xxhash.h b/include/linux/xxhash.h
index 9e1f42cb57e9..52b073fea17f 100644
--- a/include/linux/xxhash.h
+++ b/include/linux/xxhash.h
@@ -107,6 +107,29 @@  uint32_t xxh32(const void *input, size_t length, uint32_t seed);
  */
 uint64_t xxh64(const void *input, size_t length, uint64_t seed);
 
+/**
+ * xxhash() - calculate wordsize hash of the input with a given seed
+ * @input:  The data to hash.
+ * @length: The length of the data to hash.
+ * @seed:   The seed can be used to alter the result predictably.
+ *
+ * If the hash does not need to be comparable between machines with
+ * different word sizes, this function will call whichever of xxh32()
+ * or xxh64() is faster.
+ *
+ * Return:  wordsize hash of the data.
+ */
+
+static inline unsigned long xxhash(const void *input, size_t length,
+				   uint64_t seed)
+{
+#if BITS_PER_LONG == 64
+       return xxh64(input, length, seed);
+#else
+       return xxh32(input, length, seed);
+#endif
+}
+
 /*-****************************
  * Streaming Hash Functions
  *****************************/