From f910d27f87419e17cc59034265f6795db5247dfa Mon Sep 17 00:00:00 2001
From: Ulrik Sverdrup <bluss@users.noreply.github.com>
Date: Sat, 25 Jul 2015 11:55:26 +0200
Subject: siphash: Use ptr::copy_nonoverlapping for efficient data loading

Use `ptr::copy_nonoverlapping` (aka memcpy) to load an u64 from the
byte stream. This is correct for any alignment, and the compiler will
use the appropriate instruction to load the data.

Use unchecked indexing.

This results in a large improvement of throughput (hashed bytes
/ second) for long data. Maximum improvement benches at a 70% increase
in throughput for large values (> 256 bytes) but already values of 16
bytes or larger improve.

Introducing unchecked indexing is motivated to reach as good throughput
as possible. Using ptr::copy_nonoverlapping without unchecked indexing
would land the improvement some 20-30 pct units lower.

We use a debug assertion so that the test suite checks our use of
unchecked indexing.
---
 src/libcore/hash/sip.rs | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)

(limited to 'src/libcore')

diff --git a/src/libcore/hash/sip.rs b/src/libcore/hash/sip.rs
index d26e9ab7072..fae14da22c4 100644
--- a/src/libcore/hash/sip.rs
+++ b/src/libcore/hash/sip.rs
@@ -10,6 +10,7 @@
 
 //! An implementation of SipHash 2-4.
 
+use ptr;
 use prelude::*;
 use super::Hasher;
 
@@ -65,6 +66,20 @@ macro_rules! u8to64_le {
     });
 }
 
+/// Load a full u64 word from a byte stream, in LE order. Use
+/// `copy_nonoverlapping` to let the compiler generate the most efficient way
+/// to load u64 from a possibly unaligned address.
+///
+/// Unsafe because: unchecked indexing at i..i+8
+#[inline]
+unsafe fn load_u64_le(buf: &[u8], i: usize) -> u64 {
+    debug_assert!(i + 8 <= buf.len());
+    let mut data = 0u64;
+    ptr::copy_nonoverlapping(buf.get_unchecked(i),
+                             &mut data as *mut _ as *mut u8, 8);
+    data.to_le()
+}
+
 macro_rules! rotl {
     ($x:expr, $b:expr) =>
     (($x << $b) | ($x >> (64_i32.wrapping_sub($b))))
@@ -151,7 +166,7 @@ impl SipHasher {
 
         let mut i = needed;
         while i < end {
-            let mi = u8to64_le!(msg, i);
+            let mi = unsafe { load_u64_le(msg, i) };
 
             self.v3 ^= mi;
             compress!(self.v0, self.v1, self.v2, self.v3);
-- 
cgit 1.4.1-3-g733a5


From 5f6a61e16524025a690ac5512669583145db94b1 Mon Sep 17 00:00:00 2001
From: Ulrik Sverdrup <bluss@users.noreply.github.com>
Date: Sat, 25 Jul 2015 11:57:02 +0200
Subject: siphash: Remove one variable

Without this temporary variable, codegen improves slightly and less
registers are spilled to the stack in SipHash::write.
---
 src/libcore/hash/sip.rs | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

(limited to 'src/libcore')

diff --git a/src/libcore/hash/sip.rs b/src/libcore/hash/sip.rs
index fae14da22c4..5b6fd46f677 100644
--- a/src/libcore/hash/sip.rs
+++ b/src/libcore/hash/sip.rs
@@ -161,11 +161,10 @@ impl SipHasher {
 
         // Buffered tail is now flushed, process new input.
         let len = length - needed;
-        let end = len & (!0x7);
         let left = len & 0x7;
 
         let mut i = needed;
-        while i < end {
+        while i < len - left {
             let mi = unsafe { load_u64_le(msg, i) };
 
             self.v3 ^= mi;
-- 
cgit 1.4.1-3-g733a5


From 27c44ce9c3be36d49b829e3dfbdcc983bddd727d Mon Sep 17 00:00:00 2001
From: Ulrik Sverdrup <bluss@users.noreply.github.com>
Date: Sat, 25 Jul 2015 11:59:06 +0200
Subject: siphash: Reorder hash state in the struct

If they are ordered v0, v2, v1, v3, the compiler can find just a few
simd optimizations itself.

The new optimization I could observe on x86-64 was using 128 bit
registers for the v = key ^ constant operations in new / reset.
---
 src/libcore/hash/sip.rs | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

(limited to 'src/libcore')

diff --git a/src/libcore/hash/sip.rs b/src/libcore/hash/sip.rs
index 5b6fd46f677..93bdadff549 100644
--- a/src/libcore/hash/sip.rs
+++ b/src/libcore/hash/sip.rs
@@ -32,9 +32,13 @@ pub struct SipHasher {
     k0: u64,
     k1: u64,
     length: usize, // how many bytes we've processed
+    // v0, v2 and v1, v3 show up in pairs in the algorithm,
+    // and simd implementations of SipHash will use vectors
+    // of v02 and v13. By placing them in this order in the struct,
+    // the compiler can pick up on just a few simd optimizations by itself.
     v0: u64,      // hash state
-    v1: u64,
     v2: u64,
+    v1: u64,
     v3: u64,
     tail: u64, // unprocessed bytes le
     ntail: usize,  // how many bytes in tail are valid
-- 
cgit 1.4.1-3-g733a5