Subject: Re: delete command weirdness
From: (Rob Warnock)
Date: Tue, 13 May 2008 23:04:47 -0500
Newsgroups: comp.lang.lisp
Message-ID: <>
<> wrote:
| > I understand that DELETE's (and destructive functions in general) main
| > purpose is to reduce consing by means of reuse. Am I wrong?
| That is not wrong, only conceptually dangerous.
| The EXCLUSIVE purpose of destructive functions is SPEED.
| The fact that reducing consing increases speed in practically every
| known case is in principle a different question altogether.

And just to keep the pedantry going, there are definitely situations
where re-use of conses *is* slower than new allocation/initialization.
For a specific example, consider a system with a generational garbage
collector (with Ungar-style "nursery"), when the list being DELETE'd
is already in a higher-generation GC area. Stores into that list structure
might be *very* expensive, due to the necessity of implementing the
write barrier required for a generational collector. In fact, if one
is using the operating system's page protections to implement the
write barrier [e.g., as CMUCL currently does for x86], then doing a
DELETE of a small but "old" list could be *much* more expensive than
allocating fresh conses for all of the non-deleted elements (a la REMOVE),
since it would require an O/S trap for each memory page modified during


Rob Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607