From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Andy Wingo Newsgroups: gmane.lisp.guile.devel Subject: weak hash tables Date: Mon, 24 Oct 2011 19:19:21 +0200 Message-ID: <878voaqpd2.fsf@pobox.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1319476776 11338 80.91.229.12 (24 Oct 2011 17:19:36 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Mon, 24 Oct 2011 17:19:36 +0000 (UTC) To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Mon Oct 24 19:19:32 2011 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([140.186.70.17]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1RIOBQ-0001RR-Dw for guile-devel@m.gmane.org; Mon, 24 Oct 2011 19:19:32 +0200 Original-Received: from localhost ([::1]:58451 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RIOBP-00009V-QR for guile-devel@m.gmane.org; Mon, 24 Oct 2011 13:19:31 -0400 Original-Received: from eggs.gnu.org ([140.186.70.92]:43252) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RIOBM-00009Q-6W for guile-devel@gnu.org; Mon, 24 Oct 2011 13:19:29 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1RIOBK-0008UX-D4 for guile-devel@gnu.org; Mon, 24 Oct 2011 13:19:28 -0400 Original-Received: from a-pb-sasl-sd.pobox.com ([74.115.168.62]:43968 helo=sasl.smtp.pobox.com) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RIOBK-0008UT-AQ for guile-devel@gnu.org; Mon, 24 Oct 2011 13:19:26 -0400 Original-Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTP id 1DA2F5E92 for ; Mon, 24 Oct 2011 13:19:26 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=from:to :subject:date:message-id:mime-version:content-type; s=sasl; bh=J VEPID/ExphtoyKf0KqFVlasFzY=; b=O2uVJSu+a1wfyR/DHZmq01WOAb4jRN8vv 4WuNbX/IFmZFhKJzEvYRynuaSGo+O762/MVb+Hx1qNpW5VEFC+OF1g7qUYmVjsGs mkvesX9aV9/MsDBP604whOzKs3qiVbnajxJjhQJal17Y03PQKhFS1b+yLNX7VuTE EUtbyYZbWU= DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:subject :date:message-id:mime-version:content-type; q=dns; s=sasl; b=ie0 rm/d42dl7e0IfRgvgUc/gTtP2+a7KBcv0heOdIGoREGTZZjkO8H/thtBR6HLiJVd iB1sKh6ecVA92dS1bmg1O1XMJ8FEmx7VxufTKfyCCjVbwo3Pp2+YsvlY6z9pXF83 4MOuoY8Un8+6LaAI0T36SrWvDaKA7V/H9lYoN1y8= Original-Received: from a-pb-sasl-sd.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTP id 14C5B5E91 for ; Mon, 24 Oct 2011 13:19:26 -0400 (EDT) Original-Received: from badger (unknown [90.164.198.39]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTPSA id 66A855E90 for ; Mon, 24 Oct 2011 13:19:25 -0400 (EDT) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux) X-Pobox-Relay-ID: 52838528-FE64-11E0-A1A8-65B1DE995924-02397024!a-pb-sasl-sd.pobox.com X-detected-operating-system: by eggs.gnu.org: Solaris 10 (beta) X-Received-From: 74.115.168.62 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 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 Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:12857 Archived-At: Hi, While doing the recent retagging work I realized that I really wanted to kill weak pairs. They look like pairs but you can't actually access their fields using car and cdr -- terrible things. To do that I had to reimplement the weak hash tables, to make them not use them. I did that, reimplementing them as open-addressed hash tables, with robin hood linear probing on collision. It seems to work well. Besides the performance improvement you get with just scanning linearly through memory, open-addressed hash tables aren't structurally perturbed by the disappearing links. It's a lot less messy, and uses less memory, and we have space to encode the actual hash values in the table. (However I don't think our current hash functions are very good.) The one nasty thing there was adapting to the old interfaces. In particular the hashx interface expects to be able to assoc down a list, but there are no assoc lists in the new weak tables. Guess what I do? That's right, for weak hashx tables I make new association lists in the equal? handler, then pass that alist to the user's assoc function. Gross. Currently the new weak tables are only accessible under the old API. I don't know whether to publicise the new API, or make a different API, or what. If we hadn't coded the handle API into our hash tables I would replace the regular (strong) hash table implementation too. I might still do that but it's not pressing. Anyway, thoughts on the API are welcome. Regards, Andy ps. The new weak tables are thread-safe. Yay. -- http://wingolog.org/