View Issue Details

IDProjectCategoryView StatusLast Update
0005289unrealircdpublic2019-08-18 15:17
ReportersyzopAssigned Tosyzop 
PrioritynormalSeveritytweakReproducibilityN/A
Status resolvedResolutionfixed 
Product Version 
Target VersionFixed in Version5.0.0-alpha1 
Summary0005289: U5: Optimize hash table
DescriptionWhen 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%.
TagsNo tags attached.
3rd party modules

Relationships

child of 0005279 acknowledged UnrealIRCd 5 master tracking issue 

Activities

syzop

2019-05-19 08:30

administrator   ~0020684

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.

syzop

2019-06-12 19:47

administrator   ~0020733

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.

syzop

2019-06-26 17:31

administrator   ~0020742

Last edited: 2019-06-26 17:32

View 2 revisions

Done :)

New generic functions are siphash() / siphash_nocase(). See src/hash.c for various usage examples.

Issue History

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 View Revisions
2019-08-18 15:17 syzop View Status private => public