From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.emacs.devel Subject: Re: van Emde Boas hash. Date: Mon, 23 Nov 2009 17:57:27 +0100 Organization: Organization?!? Message-ID: <87ocmt2n7s.fsf@lola.goethe.zz> References: <24616604.12772711258985081474.JavaMail.www@wwinf4633> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1258995506 25675 80.91.229.12 (23 Nov 2009 16:58:26 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 23 Nov 2009 16:58:26 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Nov 23 17:58:20 2009 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1NCcEz-0008U5-S8 for ged-emacs-devel@m.gmane.org; Mon, 23 Nov 2009 17:58:18 +0100 Original-Received: from localhost ([127.0.0.1]:59010 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NCcEz-0001C8-EX for ged-emacs-devel@m.gmane.org; Mon, 23 Nov 2009 11:58:17 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1NCcEu-0001Bz-7p for emacs-devel@gnu.org; Mon, 23 Nov 2009 11:58:12 -0500 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1NCcEo-0001B3-Od for emacs-devel@gnu.org; Mon, 23 Nov 2009 11:58:10 -0500 Original-Received: from [199.232.76.173] (port=60009 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NCcEo-0001B0-LA for emacs-devel@gnu.org; Mon, 23 Nov 2009 11:58:06 -0500 Original-Received: from lo.gmane.org ([80.91.229.12]:47501) by monty-python.gnu.org with esmtps (TLS-1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1NCcEo-0002RG-6a for emacs-devel@gnu.org; Mon, 23 Nov 2009 11:58:06 -0500 Original-Received: from list by lo.gmane.org with local (Exim 4.50) id 1NCcEh-0008L3-MJ for emacs-devel@gnu.org; Mon, 23 Nov 2009 17:57:59 +0100 Original-Received: from p5b2c257e.dip.t-dialin.net ([91.44.37.126]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Mon, 23 Nov 2009 17:57:59 +0100 Original-Received: from dak by p5b2c257e.dip.t-dialin.net with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Mon, 23 Nov 2009 17:57:59 +0100 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 30 Original-X-Complaints-To: usenet@ger.gmane.org X-Gmane-NNTP-Posting-Host: p5b2c257e.dip.t-dialin.net X-Face: 2FEFf>]>q>2iw=B6, xrUubRI>pR&Ml9=ao@P@i)L:\urd*t9M~y1^:+Y]'C0~{mAl`oQuAl \!3KEIp?*w`|bL5qr,H)LFO6Q=qx~iH4DN; i"; /yuIsqbLLCh/!U#X[S~(5eZ41to5f%E@'ELIi$t^ Vc\LWP@J5p^rst0+('>Er0=^1{]M9!p?&:\z]|;&=NP3AhB!B_bi^]Pfkw User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1.50 (gnu/linux) Cancel-Lock: sha1:a7oRId3UQrI7fC22wG438XeW79I= X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6 (newer, 3) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:117598 Archived-At: Stefan Monnier writes: >> As far as I understand, the algorthm is so: > >> oblookup ( obarray, sym ) > >> ;; hash is an integer, the index of a bucket that may contain sym >> hash = hash_string (sym) >> ;; bucket is a vector. obarray is a vector of many buckets >> bucket = obarray [hash] >> ;; search sym in its bucket using a naive search >> FOR every symbol S in bucket, check whether S has the same name >> as sym. If so, return S. If no symbol matches, returns the hash. > > >> Even if it is very unlikely that we can find many symbols into >> a bucket, the algorithm does not require constant time for >> every search. > > Yes, it's a very simple hashing algorithm. I'm sure we can come up > with something more efficient. Then again, I haven't seen any > indication that this is a performance problem. I should think that it makes up a sizeable portion of byte-recompiling and autoloading, both of which are not often benchmarked. But it isn't something which you commonly do on data sets in a loop. Scanning files is done just once usually. -- David Kastrup