[SERVER-12157] Replace implementation of StringMapDefaultHash::operator() with Murmur3. Created: 18/Dec/13  Updated: 11/Jul/16  Resolved: 04/Jan/14

Status: Closed
Project: Core Server
Component/s: Internal Code, Performance
Affects Version/s: 2.5.4
Fix Version/s: 2.5.5

Type: Improvement Priority: Major - P3
Reporter: Andy Schwerin Assignee: Davide Italiano
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Participants:

 Description   

The existing hash function used for StringMap has a very high collision rate for text names that vary by only a few characters; particularly suffixes. Running the Smhasher benchmark's text and performance tests shows that Murmur3 is superior in terms of collisions and comparable in terms of performance for short keys (and superior for long keys).

So, the task of this ticket is to replace the current implementation with Murmur3. I recommend doing this by making StringDataDefaultHash a typedef of StringData::Hasher, and changing the implementation of SD::Hasher::operator() as follows:

On platforms where size_t is 32-bit, we should use MurmurHash3_x86_32. Where it is 64 bits, we should use MurmurHash3_x64_128 and keep the low order 64 bits.



 Comments   
Comment by Githook User [ 05/Jan/14 ]

Author:

{u'username': u'dcci', u'name': u'Davide Italiano', u'email': u'davide.italiano@10gen.com'}

Message: SERVER-12157: fix build on Linux 32-bit and old version(s) of g++.
Branch: master
https://github.com/mongodb/mongo/commit/4cd551544a4f25dcb5c2447b9ee14cf0591a3cfe

Comment by Githook User [ 04/Jan/14 ]

Author:

{u'username': u'erh', u'name': u'Eliot Horowitz', u'email': u'eliot@10gen.com'}

Message: SERVER-12157: fix 32-bit compile
Branch: master
https://github.com/mongodb/mongo/commit/06851f4859a61019a17147ea96c4e6d9462f354b

Comment by Githook User [ 04/Jan/14 ]

Author:

{u'username': u'dcci', u'name': u'Davide Italiano', u'email': u'davide.italiano@10gen.com'}

Message: SERVER-12157 Replace implementation of StringMapDefaultHash::operator()
with Murmur3. This has proven to be more effective in terms of speed
and collision rates.
Branch: master
https://github.com/mongodb/mongo/commit/22424987d2f0df32671998f0c7574adcfa07bf32

Comment by Andy Schwerin [ 18/Dec/13 ]

FYI, MurmurHash3 functions are available by including "murmurhash3/MurmurHash3.h".

Generated at Thu Feb 08 03:27:46 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.