View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0005289 | unreal | ircd | public | 2019-05-19 08:22 | 2019-08-18 15:17 |
| Reporter | syzop | Assigned To | syzop | ||
| Priority | normal | Severity | tweak | Reproducibility | N/A |
| Status | resolved | Resolution | fixed | ||
| Fixed in Version | 5.0.0-alpha1 | ||||
| Summary | 0005289: U5: Optimize hash table | ||||
| Description | When testing the hash table code with 3701 realistic nicks I found the collision rate with current nick hash table is 23%. Using the hybrid hash table code it's 20%, so very similar. There are several reasons but one of them is that our hash table size is 16k entries and 64k entries may be a better choice. With 64k entries the hybrid hash table collision rate drops to 5.8%, and I also tested DJB2 which gives 6.5%. | ||||
| Tags | No tags attached. | ||||
| 3rd party modules | |||||
|
|
My main interest would be SIPHASH https://en.wikipedia.org/wiki/SipHash which I already researched a few years back. With -O2: Current algo: 6.7 nanoseconds Siphash algo: 16.1 nanoseconds In other words: Current algo: 149,253,731 hashes per second Siphash algo: 62,111,801 hashes per second That speed is very acceptable. |
|
|
Make this something generic, so we can use the same function (with different arguments, presumably) for nick, channel, etc.... everything. And get rid of the old hash stuff. |
|
|
Done :) New generic functions are siphash() / siphash_nocase(). See src/hash.c for various usage examples. |
| Date Modified | Username | Field | Change |
|---|---|---|---|
| 2019-05-19 08:22 | syzop | New Issue | |
| 2019-05-19 08:22 | syzop | Status | new => acknowledged |
| 2019-05-19 08:30 | syzop | Note Added: 0020684 | |
| 2019-06-12 19:45 | syzop | Relationship added | child of 0005290 |
| 2019-06-12 19:45 | syzop | Relationship deleted | child of 0005290 |
| 2019-06-12 19:46 | syzop | Relationship added | child of 0005279 |
| 2019-06-12 19:47 | syzop | Note Added: 0020733 | |
| 2019-06-26 17:31 | syzop | Assigned To | => syzop |
| 2019-06-26 17:31 | syzop | Status | acknowledged => resolved |
| 2019-06-26 17:31 | syzop | Resolution | open => fixed |
| 2019-06-26 17:31 | syzop | Fixed in Version | => 5.0.0-alpha1 |
| 2019-06-26 17:31 | syzop | Note Added: 0020742 | |
| 2019-06-26 17:32 | syzop | Note Edited: 0020742 | |
| 2019-08-18 15:17 | syzop | View Status | private => public |
