Re: Bob Jenkins' hashing implementation in Ruby
From:
Mauricio Fern疣dez <batsman.geo@...>
Date:
2003-03-01 18:05:36 UTC
List:
ruby-core #897
On Sat, Mar 01, 2003 at 10:10:35PM +0900, ts wrote:
> >>>>> "M" == Mauricio Fern疣dez <Mauricio> writes:
>
> M> With what function, Jenkins or "one-at-a-time"?
>
> one-at-a-time
Yes, much slower. Jenkins is obviously even worse :(
I thought it would compensate by having fewer collisions but the current
hash is already good enough to use num_bins == 2^n...
What about the following?
I get a speed increase of 3% (compared to the non-inlined version)
with the second test of the GCLS.
I eliminate 2 instructions per iteration (on x86) out of 10 in the loop.
It's OK to use compiler extensions if we detect them in configure, isn't
it?
--- ruby.jenkins.orig/string.c 2003-02-28 17:16:14.000000000 +0100
+++ ruby.jenkins/string.c 2003-03-01 18:40:22.000000000 +0100
@@ -27,6 +27,7 @@
VALUE rb_cString;
+#define HAVE_COMPUTED_GOTO 1 /* this should be detected by configure */
#define STR_ASSOC FL_USER3
#define RESIZE_CAPA(str,capacity) do {\
@@ -727,6 +728,84 @@
key = key*33 + *p++;
}
key = key + (key>>5);
+#elif HAVE_COMPUTED_GOTO
+ static void* unrolled_addr[] = {
+ &&PC_0,
+ &&PC_1,
+ &&PC_2,
+ &&PC_3,
+ &&PC_4,
+ &&PC_5,
+ &&PC_6,
+ &&PC_7,
+ &&PC_8,
+ &&PC_9,
+ &&PC_10,
+ &&PC_11,
+ &&PC_12,
+ &&PC_13,
+ &&PC_14,
+ &&PC_15,
+ &&PC_16,
+ &&PC_17,
+ &&PC_18,
+ &&PC_19,
+ &&PC_20,
+ &&PC_21,
+ &&PC_22,
+ &&PC_23,
+ &&PC_24,
+ &&PC_25,
+ &&PC_26,
+ &&PC_27,
+ &&PC_28,
+ &&PC_29,
+ &&PC_30,
+ &&PC_31,
+ &&PC_LOOP
+ };
+ if (len < 32 )
+ goto *unrolled_addr[len];
+ PC_LOOP:
+ while (len--) {
+ key = key*65599 + *p;
+ p++;
+ }
+ goto PC_0;
+ PC_32: key = key*65599 + *p++;
+ PC_31: key = key*65599 + *p++;
+ PC_30: key = key*65599 + *p++;
+ PC_29: key = key*65599 + *p++;
+ PC_28: key = key*65599 + *p++;
+ PC_27: key = key*65599 + *p++;
+ PC_26: key = key*65599 + *p++;
+ PC_25: key = key*65599 + *p++;
+ PC_24: key = key*65599 + *p++;
+ PC_23: key = key*65599 + *p++;
+ PC_22: key = key*65599 + *p++;
+ PC_21: key = key*65599 + *p++;
+ PC_20: key = key*65599 + *p++;
+ PC_19: key = key*65599 + *p++;
+ PC_18: key = key*65599 + *p++;
+ PC_17: key = key*65599 + *p++;
+ PC_16: key = key*65599 + *p++;
+ PC_15: key = key*65599 + *p++;
+ PC_14: key = key*65599 + *p++;
+ PC_13: key = key*65599 + *p++;
+ PC_12: key = key*65599 + *p++;
+ PC_11: key = key*65599 + *p++;
+ PC_10: key = key*65599 + *p++;
+ PC_9: key = key*65599 + *p++;
+ PC_8: key = key*65599 + *p++;
+ PC_7: key = key*65599 + *p++;
+ PC_6: key = key*65599 + *p++;
+ PC_5: key = key*65599 + *p++;
+ PC_4: key = key*65599 + *p++;
+ PC_3: key = key*65599 + *p++;
+ PC_2: key = key*65599 + *p++;
+ PC_1: key = key*65599 + *p++;
+ PC_0:
+ key = key + (key>>5);
#else
while (len--) {
key = key*65599 + *p;
--
_ _
| |__ __ _| |_ ___ _ __ ___ __ _ _ __
| '_ \ / _` | __/ __| '_ ` _ \ / _` | '_ \
| |_) | (_| | |_\__ \ | | | | | (_| | | | |
|_.__/ \__,_|\__|___/_| |_| |_|\__,_|_| |_|
Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com
<igor> Hah! we have 2 Johnie Ingrams in the channel :)
<igor> Hey all btw :)