hash table freeze is useless


I was just noticing that g_hash_table_insert() performs a hash lookup.  
This means that if you freeze the hash table, then insert a lot of items,
the performance of g_hash_table_insert() will be degenerating into O(n)
over time, so your insert-items loop will have O(n^2) performance. Without
the freeze, it is basically O(n) (with the hash resizes amortized, and
each insertion constant time).

For small values of n, it's probably a toss-up; for large values of n,
freeze() almost certainly causes a performance hit.

Unless I'm wrong of course, please comment. ;-)

Recommended solution would be to make freeze/thaw no-ops and say in the
docs that they are deprecated.

A better solution than freeze/thaw might be a way to set the expected
number of items, g_hash_table_resize_for(hash, n_items) which would resize
the table in advance to accomodate that number of additional items, saving 
n_items re-insertions and perhaps reducing the total number of resizes.


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]