mORMot Open Source

TPrami

Member

Registered: 2010-07-06

Posts: 119

What or are benefits of using Daniel Lemire's method for Dicti

Has it been measured yet? Memory usage/Speed etc? Is there clear measurable menefit?

-Tee-

ab

Administrator

From: France

Registered: 2010-06-21

Posts: 14,649

Website

Re: What or are benefits of using Daniel Lemire's method for Dicti

From the regression tests timing of mORMot and our private apps, when number of items increases, it is as fast as "and (PowerOfTwoSize-1)" and noticeably faster than "mod BigSize".
In conjunction with a prime size, it enhances distribution.
And using less memory than power of two, since our increasing _PRIMES[] list has more linear increments.

Note: I discovered that Delphi's TDictionary not only store the hashcode in the table (which we did, but don't anymore since it was not mandatory and saves 32-bit per slot), but it stores the value in the hash table, which is usually much bigger than the items count (typically twice), so is actually wasting a lot of memory if the value is some big record...
Of course, storing the data allows to bypass the indexes adjustment after deletion - as we must do within our hash table. But with our branchless AVX2 code - see DynArrayHashTableAdjust - maintaining the indexes is not a bottleneck anymore. So best of both worlds, I hope.

TPrami

Member

Registered: 2010-07-06

Posts: 119

Re: What or are benefits of using Daniel Lemire's method for Dicti

thanks for info`?