[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: |
| Comment by Githook User [ 04/Jan/14 ] |
|
Author: {u'username': u'erh', u'name': u'Eliot Horowitz', u'email': u'eliot@10gen.com'}Message: |
| 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: |
| Comment by Andy Schwerin [ 18/Dec/13 ] |
|
FYI, MurmurHash3 functions are available by including "murmurhash3/MurmurHash3.h". |