Re: g_str_hash algorithm



On Fri, 2004-11-26 at 03:54 -0500, ANDREW MARLOW, BLOOMBERG/ LONDON OF
wrote:
> While measuring performance of my GTK app I noticed
> that alot of time is spent in g_str_hash.
> Google and a mail archive search tell me that this
> routine has not been looked at for a few years.
> I wonder what performance studies have been done.
> I realise that there is a tradeoff between ensuring
> the algorithm is fast and ensuring that few collisions result.
> The more complex the algorithms tend to result in fewer
> collisions but it takes longer to calculate.
> 
> I wonder if anyone has looked at the Pearson hash
> as an alternative to what is currently done.

The GLib string hash function is basically as fast as walking over the
memory. I'd be surprised to see anything significantly faster. 

And if collisions were a problem (*) you wouldn't see lots of time in
g_str_hash, you'd see lots of time in g_str_equal.

I haven't actually seen g_str_hash() show up in a GTK+ profile
for a long time... the main hash table culprit is is the param
spec pool, which uses a custom hash function.

Is the usage application specific?

Regards,
					Owen

(*) Testing has shown g_str_hash() to give very good distributions with
    the prime-sized hash tables used in GLib.

Attachment: signature.asc
Description: This is a digitally signed message part



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