[vlc-devel] [PATCH] vlc_arrays: force hash table sizes to prime numbers
remi at remlab.net
Tue Aug 11 21:08:12 CEST 2020
Le tiistaina 11. elokuuta 2020, 22.00.58 EEST Francois Cartegnie a écrit :
> Our performance is really bad on hash collision/realloc.
In the first place, you should probably not use the VLC dictionary for large
datasets where performance actually matters. We have search trees for this,
which don't do realloc at all and don't rely on avoiding hash collisions.
> Sizing with prime numbers has the property of creating a
> better distribution (as well as not being close to 2^n).
But heap (re)allocator typically work optimally on power of two sizes (or
multiple of large powers of two).
More information about the vlc-devel