From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Marius Vollmer Newsgroups: gmane.lisp.guile.devel,gmane.lisp.guile.user Subject: Re: Does anyone have a better scm_string_hash ? Date: Mon, 17 Nov 2003 17:02:43 +0100 Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Message-ID: <87u153q8yk.fsf@zagadka.ping.de> References: <8765hnf308.fsf@zagadka.ping.de> <1068823738.13123.54.camel@localhost> <20031114155148.GI16650@powergnu.laas.fr> <1069058032.1638.21.camel@localhost> <874qx3rogk.fsf@zagadka.ping.de> NNTP-Posting-Host: deer.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: sea.gmane.org 1069085219 15247 80.91.224.253 (17 Nov 2003 16:06:59 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Mon, 17 Nov 2003 16:06:59 +0000 (UTC) Cc: guile-user@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Mon Nov 17 17:06:56 2003 Return-path: Original-Received: from monty-python.gnu.org ([199.232.76.173]) by deer.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 1ALltw-0001MM-00 for ; Mon, 17 Nov 2003 17:06:56 +0100 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.24) id 1ALmoS-0005mC-72 for guile-devel@m.gmane.org; Mon, 17 Nov 2003 12:05:20 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.24) id 1ALmns-0005k6-GK for guile-devel@gnu.org; Mon, 17 Nov 2003 12:04:44 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.24) id 1ALmnM-0005Uy-8Q for guile-devel@gnu.org; Mon, 17 Nov 2003 12:04:43 -0500 Original-Received: from [195.253.8.218] (helo=mail.dokom.net) by monty-python.gnu.org with esmtp (Exim 4.24) id 1ALmnL-0005Ub-Sr for guile-devel@gnu.org; Mon, 17 Nov 2003 12:04:12 -0500 Original-Received: from dialin.speedway42.dip10.dokom.de ([195.138.42.10] helo=zagadka.ping.de) by mail.dokom.net with smtp (Exim 3.36 #3) id 1ALlsg-0002Tx-00 for guile-devel@gnu.org; Mon, 17 Nov 2003 17:05:38 +0100 Original-Received: (qmail 17181 invoked by uid 1000); 17 Nov 2003 16:02:43 -0000 Original-To: guile-devel@gnu.org In-Reply-To: <874qx3rogk.fsf@zagadka.ping.de> (Marius Vollmer's message of "Mon, 17 Nov 2003 16:42:35 +0100") User-Agent: Gnus/5.1002 (Gnus v5.10.2) Emacs/21.3 (gnu/linux) X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.2 Precedence: list List-Id: Developers list for Guile, the GNU extensibility library List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: main.gmane.org gmane.lisp.guile.devel:3042 gmane.lisp.guile.user:2399 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.user:2399 Marius Vollmer writes: > Both should be much better than the one we have right now and I'm > going to install the one from Roland without the hash_mask. Ok, I have installed the following hash function into 1.7. As a nice side effect, guile seems to start a bit faster now. (Although the new function does more work than the old. Talk about being too clever.) unsigned long scm_string_hash (const unsigned char *str, size_t len) { /* from suggestion at: */ /* http://srfi.schemers.org/srfi-13/mail-archive/msg00112.html */ unsigned long h = 0; while (len-- > 0) { /* h = (str[i] + h*37) % 2^bits_per_long; */ h = *str++ + (h<<5) + (h<<2) + h; } return h; } I removed 'i' from the calculation since neither the glib function nor the one from Java uses it and I'm wary of heuristical magic when it comes to random number generation and hash functions. Permutations of the input will still lead to different hash values since, for example str[0]+str[1]*37 is different from str[1]+str[0]*37. Just for kicks, I'm now going to see what kind of code GCC generates for h*37 as compared to (h<<5) + (h<<2) + h... -- GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3 331E FAF8 226A D5D4 E405 _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel