Re: g_str_hash
- From: Karl Nelson <kenelson ece ucdavis edu>
- To: gtk-devel-list redhat com
- cc: kenelson sequoia ece ucdavis edu
- Subject: Re: g_str_hash
- Date: Fri, 11 Feb 2000 11:01:51 -0800
>
> Hi,
>
> g_str_hash is really slow. The Tcl string hash function is twice as
> fast, literally. Here's a test program, and it also shows you the Tcl
> function. Any objections to the Tcl version?
Instead of switching how about just optimizing the one we have a
bit?
guint
copy_of_g_str_hash (gconstpointer v)
{
const char *s = (char*)v;
const char *p;
guint h=0, g;
for(p = s; *p != '\0'; p += 1) {
h = ( h << 4 ) + *p;
if ( ( g = h & 0xf0000000 ) ) {
h = h ^ (g >> 24);
h = h ^ g;
}
}
return h /* % M */;
}
=>
guint
copy_of_g_str_hash (gconstpointer v)
{
const char *s = (char*)v;
const char *p;
guint32 h=0;
for(p = s; *p != '\0' && !(h&0xf0000000); p += 1) {
h = ( h << 4 ) + *p;
}
for(; *p != '\0'; p += 1) {
h = h ^ ((h >> 24)&0xf0);
h = ( h << 4 ) + *p;
}
return h /* % M */;
}
This is the exact same hash except operations have been moved to
enhance speed. The difference being the new one keeps the upper bits
and thus has less collisions and operates somewhere between the TCL and
GLib on.
Also I suggest the << 4 go to << 3 so that you don't create the case
annomally where Aaaaaaaaaaaaa and aaaaaaAaaaaaa are equivent. (The
shift should be prime to the representation system.
-O0 -O3
Original system: 0.54 0.31
Proposed system: 0.48 0.22
TCL system: 0.31 0.12
Is that enough improvement?
--Karl
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]