[ovs-git] Open vSwitch: hash: Replace primary hash functions by murmurhash. (master)

[dev at openvswitch.org]

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "Open vSwitch".

The branch, master has been updated
       via  c49d1dd1686277277cb742ec0fc93749214de391 (commit)
       via  cb8ca8156749d07c94b92249a49c1c6aa7c74934 (commit)
       via  b2a52eedaa406bacfa53d2b2a3d4236e46042bcd (commit)
       via  432fca235c375c1d56bd6d3049b0b24ce2cb2958 (commit)
      from  7aac03bd99c6a8133587853c4e24335ad159d53f (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
commit c49d1dd1686277277cb742ec0fc93749214de391
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=c49d1dd1686277277cb742ec0fc93749214de391
Author: Ben Pfaff <blp at nicira.com>
		
hash: Replace primary hash functions by murmurhash.
		
murmurhash is faster than Jenkins and slightly higher quality, so switch to
it for hashing words.

The best timings I got for hashing for data lengths of the following
numbers of 32-bit words, in seconds per 1,000,000,000 hashes, were:

words     murmurhash      Jenkins hash
-----     ----------      ------------
   1           8.4              10.4
   2          10.3              10.3
   3          11.2              10.7
   4          12.6              18.0
   5          13.9              18.3
   6          15.2              18.7

In other words, murmurhash outperforms Jenkins for all input lengths other
than exactly 3 32-bit words (12 bytes).  (It's understandable that Jenkins
would have a best case at 12 bytes, because Jenkins works in 12-byte
chunks.)  Even in the case where Jenkins is faster, it's only by 5%.  On
average within this data set, murmurhash is 15% faster, and for 4-word
input it is 30% faster.

We retain Jenkins for flow_hash_symmetric_l4() and flow_hash_fields(),
which are cases where the hash value is exposed externally.

This commit appears to improve "ovs-benchmark rate" results slightly by
a few hundred connections per second (under 1%), when used with an NVP
controller.

Signed-off-by: Ben Pfaff <blp at nicira.com>
Acked-by: Ethan Jackson <ethan at nicira.com>


commit cb8ca8156749d07c94b92249a49c1c6aa7c74934
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=cb8ca8156749d07c94b92249a49c1c6aa7c74934
Author: Ben Pfaff <blp at nicira.com>
		
hash: Change mhash_finish() data measurement from words to bytes.
		
murmurhash includes an xor with the number of bytes hashed in its finishing
step.  Until now, we've only had murmurhash for full words, but an upcoming
commit adds murmurhash for bytes, so the finishing function will need to
take a count of bytes instead.

Signed-off-by: Ben Pfaff <blp at nicira.com>


commit b2a52eedaa406bacfa53d2b2a3d4236e46042bcd
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=b2a52eedaa406bacfa53d2b2a3d4236e46042bcd
Author: Ben Pfaff <blp at nicira.com>
		
hash: Correct implementation of mhash_finish().
		
With rotates instead of shifts, the upper and lower 16 bits of the returned
hash are always the same.

I noticed this while working on replacing Jenkins hash by murmurhash,
because some of the database unit tests started failing, e.g. "row
hashing (scalars)".

Signed-off-by: Ben Pfaff <blp at nicira.com>
Acked-by: Ethan Jackson <ethan at nicira.com>


commit 432fca235c375c1d56bd6d3049b0b24ce2cb2958
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=432fca235c375c1d56bd6d3049b0b24ce2cb2958
Author: Ben Pfaff <blp at nicira.com>
		
tests: Fix dependencies on hash function in ofproto-dpif tests.
		
These tests relied on luck to ensure that OpenFlow ports received the
expected OpenFlow port numbers.  With a different hash function, or (I
expect) on a big-endian architecture, the port numbers were assigned
differently and the tests failed.

This commit fixes the problem by requesting the specific expected port
numbers explicitly.

Signed-off-by: Ben Pfaff <blp at nicira.com>
Acked-by: Ethan Jackson <ethan at nicira.com>


-----------------------------------------------------------------------

Summary of changes:
 lib/automake.mk           |    2 +
 lib/flow.c                |    9 ++-
 lib/hash.c                |   93 ++++++++-----------------------
 lib/hash.h                |  134 +++++++++++++++-----------------------------
 lib/jhash.c               |  125 ++++++++++++++++++++++++++++++++++++++++++
 lib/{random.h => jhash.h} |   33 +++++++----
 tests/ofproto-dpif.at     |  104 +++++++++++++----------------------
 tests/test-hash.c         |   27 +++++----
 8 files changed, 278 insertions(+), 249 deletions(-)
 create mode 100644 lib/jhash.c
 copy lib/{random.h => jhash.h} (51%)


hooks/post-receive
-- 
Open vSwitch