[vlc-devel] [PATCH] vlc_arrays: force hash table sizes to prime numbers

[Francois Cartegnie]

Our performance is really bad on hash collision/realloc.

Sizing with prime numbers has the property of creating a 
better distribution (as well as not being close to 2^n).

We also can increase the chained list depth.

This had limited testing and will need unit tests.

Francois


---
 include/vlc_arrays.h | 38 +++++++++++++++++++++++++++++++++-----
 1 file changed, 33 insertions(+), 5 deletions(-)

diff --git a/include/vlc_arrays.h b/include/vlc_arrays.h
index b558422f93..acc940f32f 100644
--- a/include/vlc_arrays.h
+++ b/include/vlc_arrays.h
@@ -411,10 +411,32 @@ typedef struct vlc_dictionary_t
 
 static void * const kVLCDictionaryNotFound = NULL;
 
-static inline void vlc_dictionary_init( vlc_dictionary_t * p_dict, int i_size )
+/* try to have prime numbers to avoid collisions */
+static const int vlc_dictionary_sizes[12] = { 0, 3, 7, 17, 29, 61, 113, 173, 233, 331, 491, 757 };
+
+static inline int vlc_dictionary_alignsize( int i_size )
 {
-    p_dict->p_entries = NULL;
+    for( int i=0 ; i<12; i++ )
+    {
+        if(i_size <= vlc_dictionary_sizes[i])
+            return vlc_dictionary_sizes[i];
+    }
+    return i_size;
+}
 
+static inline int vlc_dictionary_growsize( int i_oldsize )
+{
+    for( int i=0 ; i<11; i++ )
+    {
+        if(i_oldsize == vlc_dictionary_sizes[i])
+            return vlc_dictionary_sizes[i+1];
+    }
+    return (i_oldsize + 2) * 3 / 2;
+}
+
+static inline void vlc_dictionary_init_impl_( vlc_dictionary_t * p_dict, int i_size )
+{
+    p_dict->p_entries = NULL;
     if( i_size > 0 )
     {
         p_dict->p_entries = (vlc_dictionary_entry_t **)calloc( i_size, sizeof(*p_dict->p_entries) );
@@ -424,6 +446,12 @@ static inline void vlc_dictionary_init( vlc_dictionary_t * p_dict, int i_size )
     p_dict->i_size = i_size;
 }
 
+static inline void vlc_dictionary_init( vlc_dictionary_t * p_dict, int i_size )
+{
+    i_size = vlc_dictionary_alignsize( i_size );
+    vlc_dictionary_init_impl_( p_dict, i_size );
+}
+
 static inline void vlc_dictionary_clear( vlc_dictionary_t * p_dict,
                                          void ( * pf_free )( void * p_data, void * p_obj ),
                                          void * p_obj )
@@ -540,7 +568,7 @@ vlc_dictionary_insert_impl_( vlc_dictionary_t * p_dict, const char * psz_key,
                              void * p_value, bool rebuild )
 {
     if( !p_dict->p_entries )
-        vlc_dictionary_init( p_dict, 1 );
+        vlc_dictionary_init( p_dict, 3 );
 
     int i_pos = DictHash( psz_key, p_dict->i_size );
     vlc_dictionary_entry_t * p_entry;
@@ -560,9 +588,9 @@ vlc_dictionary_insert_impl_( vlc_dictionary_t * p_dict, const char * psz_key,
         {
             /* Here it starts to be not good, rebuild a bigger dictionary */
             struct vlc_dictionary_t new_dict;
-            int i_new_size = ( (p_dict->i_size+2) * 3) / 2; /* XXX: this need tuning */
+            int i_new_size = vlc_dictionary_growsize( p_dict->i_size );
             int i;
-            vlc_dictionary_init( &new_dict, i_new_size );
+            vlc_dictionary_init_impl_( &new_dict, i_new_size );
             for( i = 0; i < p_dict->i_size; i++ )
             {
                 p_entry = p_dict->p_entries[i];
-- 
2.25.4