From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "Pascal J. Bourguignon" Newsgroups: gmane.emacs.help Subject: Re: why are there [v e c t o r s] in Lisp? Date: Fri, 16 Oct 2015 05:57:29 +0200 Organization: Informatimago Message-ID: <87a8rjea8m.fsf@kuiper.lan.informatimago.com> References: <87mvvjeg29.fsf@kuiper.lan.informatimago.com> <87io67pmr7.fsf@debian.uxu> <87mvvjzgup.fsf@fastmail.com> <87d1wfplu5.fsf@debian.uxu> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: ger.gmane.org 1444968025 4480 80.91.229.3 (16 Oct 2015 04:00:25 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 16 Oct 2015 04:00:25 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Fri Oct 16 06:00:20 2015 Return-path: Envelope-to: geh-help-gnu-emacs@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 1ZmwBl-00085S-HS for geh-help-gnu-emacs@m.gmane.org; Fri, 16 Oct 2015 06:00:17 +0200 Original-Received: from localhost ([::1]:50722 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZmwBl-0007CB-2Z for geh-help-gnu-emacs@m.gmane.org; Fri, 16 Oct 2015 00:00:17 -0400 Original-Path: usenet.stanford.edu!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail Original-Newsgroups: gnu.emacs.help Original-Lines: 127 Original-X-Trace: individual.net 1x681hDYTReWcPnVTi7GtgVO2seY00bBGfZJmXfI4KfXvmOEBQ Cancel-Lock: sha1:ZTg1MzE0OTFkMGUxNjU4NTAxN2I4ZWMwYmI0MWRlZWE3ZjU1YjM5Zg== sha1:oflPROVsS0yTMIsbykTg7byUt0k= Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwAQMAAABtzGvEAAAABlBMVEUAAAD///+l2Z/dAAAA oElEQVR4nK3OsRHCMAwF0O8YQufUNIQRGIAja9CxSA55AxZgFO4coMgYrEDDQZWPIlNAjwq9 033pbOBPtbXuB6PKNBn5gZkhGa86Z4x2wE67O+06WxGD/HCOGR0deY3f9Ijwwt7rNGNf6Oac l/GuZTF1wFGKiYYHKSFAkjIo1b6sCYS1sVmFhhhahKQssRjRT90ITWUk6vvK3RsPGs+M1RuR mV+hO/VvFAAAAABJRU5ErkJggg== X-Accept-Language: fr, es, en User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) Original-Xref: usenet.stanford.edu gnu.emacs.help:215387 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:107671 Archived-At: Random832 writes: > Emanuel Berg writes: >> If a list just contains say a bunch of known integers >> that don't need to be computed, is there anything that >> stops this list from being stored in "contiguous >> memory" with the list functions as well as the >> constant access time "vector" functions available? Emanuel, notice that in some implementations of lisp in the 1980s, there was an optimization for lists called cdr-coding which stored the list when it was copied as a vector of consecutive elements (eliminating thus the cdr, which basically was reduced to a bit in tag of the slot). This still allowed to call cdr (instead of derefencing that slot, we'd just increment the address in the vector). But if you used rplacd, then it had to "split" the cdr-coded vector, creating a new cons cell where to store the new cdr pointer. (copy-list '(1 2 3 4 5)) would create a vector of CARs and point to the first one. The slot would have a bit set indicating that the CDR has been eliminated, and the CAR of the next cell is stored in the next address: +-----------------------------------------------------------+ | list = (1 2 3 4 5) +----------------------------f | | | | | | v v | | +-----+-----+-----+-----+-----+-----+ | | | * '| * '| * '| * '| * | NIL | | | +-----+-----+-----+-----+-----+-----+ | | | | | | | | | v v v v v | | +---+ +---+ +---+ +---+ +---+ | | | 1 | | 2 | | 3 | | 4 | | 5 | | | +---+ +---+ +---+ +---+ +---+ | +-----------------------------------------------------------+ The last cell would be a CDR (so the preceeding slot doesn't have the bit in the tag set), pointing to a following cons cell or cdr vector, or the atom in the dotted list (here, NIL, to indicate the end of the list). Now the problem occurs when you use rplacd in the middle of the list: (let* ((list (list 1 2 3 4 5)) (f (nthcdr 3 list))) (rplacd (cddr list) (list* 4.0 4.2 (cddddr list))) (list list f)) --> ((1 2 3 4.0 4.2 . #1=(5)) (4 . #1#)) To do that in the presence of cdr-coding, we have to introduce a new cons cell for 4, and more problematic, we have to scan the whole memory for references to this cell, and update them (in this case, the variable f must now point to a new cons cell, instead of in the middle of the cdr-vector): +-----------------------------------------------------------+ | list = (1 2 3 4 5) | | | | | | +-----+-----+-----+ | | | +-->| * '| * | * | | | | | +-----+-----+-----+ | | | | | | | | | | | v v | | | | | +---+ +---+ | | | | | |4.0| |4.2| | | | | | +---+ +---+ | | | | | | | | | | +------------+<-----------+ | | | | | f-------+ | | | | | | | | | | v v v v | | | +-----+-----+-----+-----+-----+-----+ +---+---+ | | | | * '| * '| * | * | * '| NIL | | * | * |--+ | | +-----+-----+-----+-----+-----+-----+ +---+---+ | | | | | | | | | v v v v v | | +---+ +---+ +---+ +---+ +---+ | | | 1 | | 2 | | 3 | | 5 | | 4 | | | +---+ +---+ +---+ +---+ +---+ | +-----------------------------------------------------------+ > Well, what happens if you cdr that list? Does it make a > copy? cdr'ing is no problem you just increment your pointer. > Wasted memory, wasted time, won't track if you change > the original. Yeah, yeah, in platonic ideal lisp you *can't* > change lists, but this is the real world, where even scheme > lets you do it. Does it keep a reference to the original > list? Then what if you take the cd^{4000}r of a list of > 5000, then throw away the original? Wasted memory > again. Java used to have this issue with strings. I suppose > you could have the underlying array somehow know what the > earliest index that a reference actually exists for is, and > magically throw away everything before it during garbage > collection, if there's too much wasted space. But that seems > rather a lot of work. > >> By the way: in my previous post strings were mentioned >> and it sounded like they were sugar for lists of chars >> - this isn't the case (you can't `car' a string) but >> it could have been and it isn't harmful (I think) to >> think of strings that way. > > The thing is, if you can car a string people will wonder why > you can't cdr it. And with mutable objects it's hard to make > cdr work right. (fsvo "right") It's rplacd which becomes much more complex. Also, when you program with such a system, you might be afraid that rplacd leads to fragmented chains, and will have a tendency to call copy-list to compact them. But indeed, copy-list means that less structure is shared, and therefore would waste time and memory. This is what they do in C++ and why they believe lists are costly. -- __Pascal Bourguignon__ http://www.informatimago.com/ “The factory of the future will have only two employees, a man and a dog. The man will be there to feed the dog. The dog will be there to keep the man from touching the equipment.” -- Carl Bass CEO Autodesk