Skip to content
  • Ben Pfaff's avatar
    hash: Replace primary hash functions by murmurhash. · c49d1dd1
    Ben Pfaff authored
    
    
    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: default avatarBen Pfaff <blp@nicira.com>
    Acked-by: default avatarEthan Jackson <ethan@nicira.com>
    c49d1dd1