From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Roland Orre Newsgroups: gmane.lisp.guile.user Subject: Re: Efficiency and flexibility of hash-tables Date: 10 Feb 2003 16:00:42 +0100 Organization: Royal Institute of Technology Sender: guile-user-bounces+guile-user=m.gmane.org@gnu.org Message-ID: <1044889242.1033.310.camel@localhost> References: <87lm0o7951.fsf@alice.rotty.yi.org> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Trace: main.gmane.org 1044889313 25738 80.91.224.249 (10 Feb 2003 15:01:53 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Mon, 10 Feb 2003 15:01:53 +0000 (UTC) Cc: Joris van der Hoeven Return-path: Original-Received: from monty-python.gnu.org ([199.232.76.173]) by main.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 18iFRK-0006gR-00 for ; Mon, 10 Feb 2003 16:01:46 +0100 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 18iFSV-0006cq-09 for guile-user@m.gmane.org; Mon, 10 Feb 2003 10:02:59 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.10.13) id 18iFRi-0006GW-00 for guile-user@gnu.org; Mon, 10 Feb 2003 10:02:10 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.10.13) id 18iFR8-0005jk-00 for guile-user@gnu.org; Mon, 10 Feb 2003 10:01:39 -0500 Original-Received: from smtp0.nada.kth.se ([130.237.222.202] helo=smtp.nada.kth.se) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 18iFQa-00054L-00 for guile-user@gnu.org; Mon, 10 Feb 2003 10:01:00 -0500 X-Authentication-Info: Sender authentication was Original-Received: from [192.168.1.92] (bari.bacon.su.se [130.237.152.231]) (authenticated bits=0) by smtp.nada.kth.se (8.12.1/8.12.1) with ESMTP id h1AF12wV012733 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NO); Mon, 10 Feb 2003 16:01:08 +0100 (MET) Original-To: Greg Troxel In-Reply-To: X-Mailer: Ximian Evolution 1.2.1 Original-cc: Andreas Rottmann Original-cc: guile-user@gnu.org X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1b5 Precedence: list List-Id: General Guile related discussions List-Help: List-Post: List-Subscribe: , List-Archive: List-Unsubscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane.org@gnu.org Xref: main.gmane.org gmane.lisp.guile.user:1620 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.user:1620 On Mon, 2003-02-10 at 15:24, Greg Troxel wrote: > Maybe one could re-use the GLib code, they have resizing hash tables. > Wouldn't glib's implementation cause gc problems? Today there are three different types of hash tables: vectors, weak hash tables and double weak hash tables. The only real difference between them is how their content is handled by gc, "tag wise" they are close. My idea (which I haven't revealed yet) about resizing hash tables may be considered a little "dirty" but when thinking about it I don't really see a problem with it. My idea was to modify the routines scm_c_make_hash_table in hashtab.c, scm_make_weak_key_hash_table and scm_make_weak_value_hash_table in weaks.c so they allocate three extra items in the mallocated block but hides this to the gc by setting the actual vector length to the ordinary one. These extra items will contain the actual size in number of items stored in the table and current upper and lower thresholds for resizing the table. Then modify the routines: scm_hash_fn_create_handle_x and scm_hash_fn_remove_x in hashtab.c to do resizing when needed, using a table of prime numbers for next and previous size. The advantage with this solution is that it's minimalistic, i.e. all routines working with hash tables will behave exactly the same. Only the routines changing the number of items in the table will be affected. The reason why I don't see a problem with this solution is that the free() routine uses information which is independent from guile's view about the size of the allocated memory block. The only disadvantage I see is the risk that someone are not using the routine "make-hash-table" in their code. If they use "normal" vectors as hash tables it may cause segmentation fault, but this is not a serious one as I see it. Comments? Best regards Roland Orre > This prompted a few questions: > > Would it be reasonable for guile to depend on glib? > I wouldn't mind, but I suspect others would view this as a problem. > > If not, would a 'guile-glib' package that has interfaces to the glib > functions be appropriate. The new guile-gobject might support this > already. > > Didn't Jay Glascoe have auto-resizing hash tables implemented before? > > Using glib's implementation (in glib, not copying the code) really > seems preferable, either natively in guile or via (possibly enhanced) > guile-gobject. > > Greg Troxel _______________________________________________ Guile-user mailing list Guile-user@gnu.org http://mail.gnu.org/mailman/listinfo/guile-user