From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.lisp.guile.devel Subject: Re: Imporved cons representatoin in guile Date: Fri, 10 Jul 2015 13:31:02 -0400 Message-ID: References: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1436549492 15791 80.91.229.3 (10 Jul 2015 17:31:32 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 10 Jul 2015 17:31:32 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Fri Jul 10 19:31:26 2015 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1ZDc8z-0002jc-3G for guile-devel@m.gmane.org; Fri, 10 Jul 2015 19:31:25 +0200 Original-Received: from localhost ([::1]:45586 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZDc8y-0002mK-CH for guile-devel@m.gmane.org; Fri, 10 Jul 2015 13:31:24 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:41636) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZDc8v-0002mE-O5 for guile-devel@gnu.org; Fri, 10 Jul 2015 13:31:22 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZDc8p-00026W-Sl for guile-devel@gnu.org; Fri, 10 Jul 2015 13:31:21 -0400 Original-Received: from plane.gmane.org ([80.91.229.3]:43112) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZDc8p-00026H-MO for guile-devel@gnu.org; Fri, 10 Jul 2015 13:31:15 -0400 Original-Received: from list by plane.gmane.org with local (Exim 4.69) (envelope-from ) id 1ZDc8l-0002bR-O1 for guile-devel@gnu.org; Fri, 10 Jul 2015 19:31:12 +0200 Original-Received: from 157-52-6-103.cpe.teksavvy.com ([157.52.6.103]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 10 Jul 2015 19:31:11 +0200 Original-Received: from monnier by 157-52-6-103.cpe.teksavvy.com with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 10 Jul 2015 19:31:11 +0200 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 36 Original-X-Complaints-To: usenet@ger.gmane.org X-Gmane-NNTP-Posting-Host: 157-52-6-103.cpe.teksavvy.com User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.0.50 (gnu/linux) Cancel-Lock: sha1:KBrnCFc0TF5lEEJo/t06qVKCYwM= X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 80.91.229.3 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:17759 Archived-At: > To compress even further we need a way to could use > x ->[SCM/2/SCM/2], witt SCM/2 the same tagging half the size as the normal Note that this is not specific to cons-cells. I've been meaning to try and experiment with such a box-compression scheme for several years, but it never got high enough on the todo list (tho I did get a student to look at it, but he gave up his MSc before getting far enough). Note that because of set-car! and set-cdr! you need those SCM/2 fields to be able to hold *any* value. So an SCM/2 field can hold 3 different things: - an immediate value. - a compressed reference, typically using relative addressing, where you'll want the GC to know about them, so it tries to keep/bring related objects near each other. - a "proxy reference", which identifies a full SCM cell which contains the actual value. It can be a relative pointer or an index in some table. I imagined it working by dividing the heap into zones whose size corresponds to the "reachability" of an SCM/2 relative pointer (so an SCM/2 field can point to any other object within the same zone without going through a proxy), and have each zone come with an array of proxies. I was thinking about this mostly in the context of 64bit boxes where the SCM/2 references would basically only ever need to go through proxies once the process size passes the 4GB limit. But for small-memory systems using 32bit pointers, the same idea might work as well. Interestingly, this split into zones+proxies would also allow the GC to operate on each zone independently (you don't need to trace the objects in the other zones, only their proxies). Stefan