From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Han-Wen Newsgroups: gmane.lisp.guile.devel Subject: Re: GUILE GC -- Write barrier for vectors Date: Tue, 16 Jul 2002 01:02:28 +0200 Sender: guile-devel-admin@gnu.org Message-ID: <15667.21636.174313.24740@blauw.xs4all.nl> References: <15667.4827.763060.19585@meddo.cs.uu.nl> Reply-To: hanwen@cs.uu.nl NNTP-Posting-Host: localhost.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: main.gmane.org 1026774026 21635 127.0.0.1 (15 Jul 2002 23:00:26 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Mon, 15 Jul 2002 23:00:26 +0000 (UTC) Cc: guile-devel@gnu.org, jantien@xs4all.nl Return-path: Original-Received: from fencepost.gnu.org ([199.232.76.164]) by main.gmane.org with esmtp (Exim 3.33 #1 (Debian)) id 17UEpL-0005ci-00 for ; Tue, 16 Jul 2002 01:00:23 +0200 Original-Received: from localhost ([127.0.0.1] helo=fencepost.gnu.org) by fencepost.gnu.org with esmtp (Exim 3.35 #1 (Debian)) id 17UEp8-0004b3-00; Mon, 15 Jul 2002 19:00:11 -0400 Original-Received: from smtpzilla3.xs4all.nl ([194.109.127.139]) by fencepost.gnu.org with esmtp (Exim 3.35 #1 (Debian)) id 17UEoS-0004ZX-00 for ; Mon, 15 Jul 2002 18:59:28 -0400 Original-Received: from blauw.xs4all.nl (blauw.xs4all.nl [213.84.26.127]) by smtpzilla3.xs4all.nl (8.12.0/8.12.0) with ESMTP id g6FMxRXN097551; Tue, 16 Jul 2002 00:59:27 +0200 (CEST) Original-To: Dirk Herrmann In-Reply-To: X-Mailer: VM 7.05 under Emacs 21.2.1 Errors-To: guile-devel-admin@gnu.org X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.0.11 Precedence: bulk List-Help: List-Post: List-Subscribe: , List-Id: Developers list for Guile, the GNU extensibility library List-Unsubscribe: , List-Archive: Xref: main.gmane.org gmane.lisp.guile.devel:808 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.devel:808 dirk@sallust.ida.ing.tu-bs.de writes: > > SCM scm_changing_cell() > > SCM scm_changing_vector() > > > > They would be allocated from a separate memory pool. Also if we > > redefine the GC engine to use a different function internally > > (i.e. scm_gc_internal_mark), then we can distinguish between data > > cells that may be moved (only pointed to from within the heap), and > > other cells (marked by scm_gc_mark: conservatively marked entries, > > pointed to from smobs, etc.). > > > > The copiable cells could be subjected to copying GC, although it would > > require another scan of the entire heap. > > It's a good idea - unfortunately it is patented. Don't ask me who has > this patented, but I also suggested this idea some time ago. That's the > bad thing about patents: Whenever there's a good idea, you can't be sure > it is patented. > > But, it may make sense to investigate this patent issue again. Maybe the > information above is outdated and the idea can actually be used in free > software? > > In this case, I wouldn't like to have the API extended as you suggest > above: Then it would be easy to re-arrange cells in cards such that > untouched cells are moved into common cards - no need to extend the API. I don't know. Some form of the idea seems to be patented, but I can't access the text of the patent, so I'm not sure (it's no. 251554). (and even if I could -- you never know: the only person qualified to judge wether a patent is applicable are IP lawyers and IP judges. With those millions and millions of patents it is unlikely that none of them are covering GUILE as it is). Interestingly, his techreport (ftp://gatekeeper.dec.com/pub/DEC/WRL/research-reports/WRL-TR-88.2.ps) contains C source code for the garbage collector -- but that's no permission to use it, right, and the "patents" page at DEC doesn't mention the patent. (some time later I dug it up anyway: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=/netahtml/search-bool.html&r=1&f=G&l=50&co1=AND&d=ft90&s1='digital+equipment'.ASNM.&s2=bartlett.INZZ.&OS=AN/%22digital+equipment%22+AND+IN/bartlett&RS=AN/%22digital+equipment%22+AND+IN/bartlett ) I'm reading the patent (gosh, what verbosity) -- but interestingly, the claim is only made for not copying entire pages (cards in Scheme terms), that are marked conservatively. If you one uses a second set of mark bits, you could leave alone exactly those objects that are marked conservatively (iso. the whole page). The price is that you have another mark-bit vector (1.5 % memory overhead), that the free space in the conservatively marked pages is fragmented, and that there is more overhead (checking the marked-conservatively-bit) during the copy phase. > This is true if there is code. As long as there is just a > conceptual phase, there is no code to comment on. And, the current > situation is a counterexample to your suggestion: If we had started > the workbook idea sooner, we would not have to go around asking for > things about gc that others have already thought about. Ok. So how do I go about adding to the workbook? Do I send simply send patches? > > > Hmmm? Where should this be necessary? Do you want to modify the vector > > > cell itself, or are you using this for "speed ups"? In the "speed-up" > > > case: wouldn't SCM_VECTOR_SET do as well, given that the compiler can > > > extract constant expressions from within loops? > > > > In some cases no (GC manipulations of weak vectors), and in some cases > > yes, but it would introduce lots of redtape: long lists of > > SCM_VECTOR_SET calls. I'll review the cases once more. > > GC manipulations of weak vectors? These shouldn't require any write > barrier. And, even if so, there's already SCM_SET_WVECT_GC_CHAIN. No, exactly my point. If you add some kind of GC related code that writes header from SCM_VECTOR_SET() (to flag object writes), then you shouldn't use it in code that is related to the GC. Also flagging object writes is overhead, so you typically want to move it out of loops if possible. -- Han-Wen Nienhuys | hanwen@cs.uu.nl | http://www.cs.uu.nl/~hanwen _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel