Hi, I'm profiling some code and found out that it's consing much more
than it should. I found that the following is true of MCL 2.0:
(let ((a '(1 2 3))) (eq a (remove 0 a))) => nil, while of course
(let ((a '(1 2 3))) (equal a (remove 0 a))) => t
Remove conses up a new list even though it doesn't remove anything!
It shouldn't be difficult to write one that kept the biggest unchanged
tail of the original list, returning the whole unmodified list if it
didn't contain the first argument. It only requires an eq-test on the
result from a recursive call:
(defun faster-remove (elt list)
(if (atom list)
(values list)
(let* ((cons (cdr list))
(cons-result (faster-remove elt (cdr list))))
(if (eq (car list) elt)
(values cons-result)
(if (eq cons cons-result)
(values list)
(cons (car list) cons-result))))))
Time-ing shows a big difference:
(DOTIMES (A 1000) (DOTIMES (B 8) (FASTER-REMOVE B '(1 2 3 4 5 1 2 3 4
5)))) took 2421 milliseconds (2.421 seconds) to run.
Of that, 117 milliseconds (0.117 seconds) were spent in The
Cooperative Multitasking Experience.
240000 bytes of memory allocated.
NIL
?
(DOTIMES (A 1000) (DOTIMES (B 8) (REMOVE B '(1 2 3 4 5 1 2 3 4 5))))
took 6966 milliseconds (6.966 seconds) to run.
Of that, 376 milliseconds (0.376 seconds) were spent in The
Cooperative Multitasking Experience.
640000 bytes of memory allocated.
NIL
I know my function isn't as general as remove since it only works on
lists and doesn't take all those arguments. But I feel remove should
be optimized for the simplest cases and also should try to cons as
little as possible. As the results show, faster-remove (or should it
be called low-consing-remove) is far better when it comes to consing.
--
Hallvard Traetteberg
Dept. of Knowledge Based Systems
Center for Industrial Research
Box 124 Blindern, 0314 Oslo 3
NORWAY
Tlf: +47 2 45 29 83 or +47 2 45 20 10
Fax: +47 2 45 20 40
Email: ···················@si.no
In article <······················@monsun.si.no> Hallvard Tr{tteberg,
········@monsun.si.no writes:
>Time-ing shows a big difference:
>
>(DOTIMES (A 1000) (DOTIMES (B 8) (FASTER-REMOVE B '(1 2 3 4 5 1 2 3 4
>5)))) took 2421 milliseconds (2.421 seconds) to run.
>Of that, 117 milliseconds (0.117 seconds) were spent in The
>Cooperative Multitasking Experience.
> 240000 bytes of memory allocated.
>NIL
>?
>(DOTIMES (A 1000) (DOTIMES (B 8) (REMOVE B '(1 2 3 4 5 1 2 3 4 5))))
>took 6966 milliseconds (6.966 seconds) to run.
>Of that, 376 milliseconds (0.376 seconds) were spent in The
>Cooperative Multitasking Experience.
> 640000 bytes of memory allocated.
>NIL
>
>I know my function isn't as general as remove since it only works on
>lists and doesn't take all those arguments. But I feel remove should
>be optimized for the simplest cases and also should try to cons as
>little as possible. As the results show, faster-remove (or should it
>be called low-consing-remove) is far better when it comes to consing.
>
[hei Hallvard, hyggelig aa se at det fortsatt programmeres i MCL paa SI!]
Hallvard,
Your function can definitely be faster for several purposes, but because
it isn't tail-recursive, it's not as general in its applicability as
REMOVE: It doesn't work for large lists.
In the following example, the value of TSTLIST is the list
(10000 9999 ... 2 1):
? (room)
There are at least 12185032 bytes of available RAM.
Total Size Free Used
Mac Heap: 972552 (949K) 361152 (352K) 611400 (598K)
Lisp Heap: 12607488 (12312K) 11823880 (11546K) 788320 (769K)
(Static): 528384 (516K)
Stacks: 208952 (204K)
? (progn (time (remove 5000 tstlist)) t)
(REMOVE 5000 TSTLIST) took 69 milliseconds (0.069 seconds) to run.
80016 bytes of memory allocated.
T
? (progn (time (faster-remove 5000 tstlist)) t)
> Error: Stack overflow.
> While executing: FASTER-REMOVE
> Type Command-. to abort.
See the RestartsU menu item for further choices.
1 >
For shorter lists, but larger than in your example, your function shows a
memory, but no time gain (egc is not used, btw). The following example
is your own example scaled by a factor of 100, i.e., TSTLIST is set to (1
... 500 1 ... 500):
? (time (dotimes (X 800) (remove X tstlist)))
(DOTIMES (X 800) (REMOVE X TSTLIST)) took 6078 milliseconds (6.078
seconds) to run.
Of that, 191 milliseconds (0.191 seconds) were spent in The Cooperative
Multitasking Experience.
6400080 bytes of memory allocated.
NIL
? (gc)
NIL
? (time (dotimes (X 800) (faster-remove X tstlist)))
(DOTIMES (X 800) (FASTER-REMOVE X TSTLIST)) took 6280 milliseconds (6.280
seconds) to run.
Of that, 200 milliseconds (0.200 seconds) were spent in The Cooperative
Multitasking Experience.
2994000 bytes of memory allocated.
NIL
--------------------------------------------------------------
Espen J. Vestre, ·····@coli.uni-sb.de
Universitaet des Saarlandes,
Computerlinguistik, Gebaeude 17.2
Im Stadtwald, tel. +49 (681) 302 4501
D-6600 SAARBRUECKEN, Germany fax. +49 (681) 302 4351
--------------------------------------------------------------
In article <······················@monsun.si.no> Hallvard Tr{tteberg,
········@monsun.si.no writes:
>Time-ing shows a big difference:
>
>(DOTIMES (A 1000) (DOTIMES (B 8) (FASTER-REMOVE B '(1 2 3 4 5 1 2 3 4
>5)))) took 2421 milliseconds (2.421 seconds) to run.
>Of that, 117 milliseconds (0.117 seconds) were spent in The
>Cooperative Multitasking Experience.
> 240000 bytes of memory allocated.
>NIL
>?
>(DOTIMES (A 1000) (DOTIMES (B 8) (REMOVE B '(1 2 3 4 5 1 2 3 4 5))))
>took 6966 milliseconds (6.966 seconds) to run.
>Of that, 376 milliseconds (0.376 seconds) were spent in The
>Cooperative Multitasking Experience.
> 640000 bytes of memory allocated.
>NIL
>
>I know my function isn't as general as remove since it only works on
>lists and doesn't take all those arguments. But I feel remove should
>be optimized for the simplest cases and also should try to cons as
>little as possible. As the results show, faster-remove (or should it
>be called low-consing-remove) is far better when it comes to consing.
>
[hei Hallvard, hyggelig aa se at det fortsatt programmeres i MCL paa SI!]
Hallvard,
Your function can definitely be faster for several purposes, but because
it isn't tail-recursive, it's not as general in its applicability as
REMOVE: It doesn't work for large lists.
In the following example, the value of TSTLIST is the list
(10000 9999 ... 2 1):
? (room)
There are at least 12185032 bytes of available RAM.
Total Size Free Used
Mac Heap: 972552 (949K) 361152 (352K) 611400 (598K)
Lisp Heap: 12607488 (12312K) 11823880 (11546K) 788320 (769K)
(Static): 528384 (516K)
Stacks: 208952 (204K)
? (progn (time (remove 5000 tstlist)) t)
(REMOVE 5000 TSTLIST) took 69 milliseconds (0.069 seconds) to run.
80016 bytes of memory allocated.
T
? (progn (time (faster-remove 5000 tstlist)) t)
> Error: Stack overflow.
> While executing: FASTER-REMOVE
> Type Command-. to abort.
See the RestartsU menu item for further choices.
1 >
For shorter lists, but larger than in your example, your function shows a
memory, but no time gain (egc is not used, btw). The following example
is your own example scaled by a factor of 100, i.e., TSTLIST is set to (1
... 500 1 ... 500):
? (time (dotimes (X 800) (remove X tstlist)))
(DOTIMES (X 800) (REMOVE X TSTLIST)) took 6078 milliseconds (6.078
seconds) to run.
Of that, 191 milliseconds (0.191 seconds) were spent in The Cooperative
Multitasking Experience.
6400080 bytes of memory allocated.
NIL
? (gc)
NIL
? (time (dotimes (X 800) (faster-remove X tstlist)))
(DOTIMES (X 800) (FASTER-REMOVE X TSTLIST)) took 6280 milliseconds (6.280
seconds) to run.
Of that, 200 milliseconds (0.200 seconds) were spent in The Cooperative
Multitasking Experience.
2994000 bytes of memory allocated.
NIL
--------------------------------------------------------------
Espen J. Vestre, ·····@coli.uni-sb.de
Universitaet des Saarlandes,
Computerlinguistik, Gebaeude 17.2
Im Stadtwald, tel. +49 (681) 302 4501
D-6600 SAARBRUECKEN, Germany fax. +49 (681) 302 4351
--------------------------------------------------------------
Espen is correct in that Hallvard's REMOVE variant isn't
tail-recursive and may therefore cause problems with long lists. One
could code an iterative tail-preserving version (which might be slower).
But I did some benchmarking on Sun-4s under Allegro and CMU CL, and even
on longish lists (like 1000 elements or so), Hallvard's FASTER-REMOVE
performed better on the whole than the system-provided REMOVE versions.
I would bet that at least 90% of the uses of REMOVE would benefit from
using FASTER-REMOVE.
Let me just point out that is a bit unfair to compare FASTER-REMOVE
against CL REMOVE implementations because REMOVE allows :TEST/:TEST-NOT
and :KEY arguments to be provided, which makes it more difficult to
inline the test - FASTER-REMOVE uses EQ directly, which is usually
inlined. REMOVE also has to cope with :START, :END, :COUNT and
:FROM-END arguments, although these are usually not provided.
On the other hand, the implementors probably thought that REMOVE would s
usually be called only in casewhere it would actually remove
something, so sharing structure with the original sequence (list)
wouldn't be worth the effort. But since REMOVE often leaves a
significant tail portion intact, this assumption could have been wrong.
The moral is probably:
0. Don't use any CL functions other than EQ, ATOM, CAR, CDR, CONS(?),
defstruct accessors and the fixnum and float operations in
time-critical code :-)
1. Even for basic functions like REMOVE, it can be a good idea to define
your own specialized versions that are tuned for application-specific
performance. Common Lisp's abundance of useful `generic' (not in the
CLOS sense) functions is in part responsible for the reputation of CL
as being `slow': If I want to remove an item from a list structure in
C, I usually write the loop myself, with the appropriate testing
inline. Usually I will also write it to work destructively. In CL I
simply call REMOVE---this is guaranteed to work but is also guaranteed
to scan the whole list (unless I say :COUNT which is often possible),
and usually reconses the whole list even if nothing or just the first
or second element has to be removed.
3. There is still some optimization potential for Lisp implementations.
Consider REMOVE: in 90% of all cases it is called with the second
argument being a list(*), with no :START/:END, :COUNT (and therefore
no :FROM-END) and the :TEST argument being either the default (#'EQL)
or #'EQ. So by transforming these two cases into calls to specialized
functions like SIMPLE-LIST-EQ-REMOVE and SIMPLE-LIST-EQL-REMOVE, a lot
could be gained. I was a bit surprised that I managed neither Allegro
nor CMU CL to inline any call to REMOVE (well in CMU CL I finally
defined the transformer), even in presence of a LIST type definition
of the sequence argument.
The sad thing about these possible optimizations is that they have a
cost in terms of overall size of the system and the corresponding
locality problems. So the implementor has to find a good compromise
between the extreme solutions (on one end of the spectrum: provide one
single generic REMOVE function that handles lists, vectors, :TEST,
:KEY, :COUNT, :FROM-END, and on the other end: provide inline dispatch
to SIMPLE-LIST-EQ-REMOVE, SIMPLE-VECTOR-EQ-REMOVE,
SIMPLE-LIST-TEST-NO-KEY-REMOVE, SIMPLE-LIST-EQ-COUNT=1-REMOVE,
SIMPLE-LIST-EQL-COUNT=1-REMOVE,LIST-TEST-KEY-WITH-COUNT-FROM-END-REMOVE
and so on, the same for DELETE, FIND, REMOVE-IF, DELETE-IF etc.).
Clever "lazy" compilation schemes could help here.
--
Simon.
*) This is usually difficult for the compiler to prove.
Espen is correct in that Hallvard's REMOVE variant isn't
tail-recursive and may therefore cause problems with long lists. One
could code an iterative tail-preserving version (which might be slower).
But I did some benchmarking on Sun-4s under Allegro and CMU CL, and even
on longish lists (like 1000 elements or so), Hallvard's FASTER-REMOVE
performed better on the whole than the system-provided REMOVE versions.
I would bet that at least 90% of the uses of REMOVE would benefit from
using FASTER-REMOVE.
Let me just point out that is a bit unfair to compare FASTER-REMOVE
against CL REMOVE implementations because REMOVE allows :TEST/:TEST-NOT
and :KEY arguments to be provided, which makes it more difficult to
inline the test - FASTER-REMOVE uses EQ directly, which is usually
inlined. REMOVE also has to cope with :START, :END, :COUNT and
:FROM-END arguments, although these are usually not provided.
On the other hand, the implementors probably thought that REMOVE would s
usually be called only in casewhere it would actually remove
something, so sharing structure with the original sequence (list)
wouldn't be worth the effort. But since REMOVE often leaves a
significant tail portion intact, this assumption could have been wrong.
The moral is probably:
0. Don't use any CL functions other than EQ, ATOM, CAR, CDR, CONS(?),
defstruct accessors and the fixnum and float operations in
time-critical code :-)
1. Even for basic functions like REMOVE, it can be a good idea to define
your own specialized versions that are tuned for application-specific
performance. Common Lisp's abundance of useful `generic' (not in the
CLOS sense) functions is in part responsible for the reputation of CL
as being `slow': If I want to remove an item from a list structure in
C, I usually write the loop myself, with the appropriate testing
inline. Usually I will also write it to work destructively. In CL I
simply call REMOVE---this is guaranteed to work but is also guaranteed
to scan the whole list (unless I say :COUNT which is often possible),
and usually reconses the whole list even if nothing or just the first
or second element has to be removed.
3. There is still some optimization potential for Lisp implementations.
Consider REMOVE: in 90% of all cases it is called with the second
argument being a list(*), with no :START/:END, :COUNT (and therefore
no :FROM-END) and the :TEST argument being either the default (#'EQL)
or #'EQ. So by transforming these two cases into calls to specialized
functions like SIMPLE-LIST-EQ-REMOVE and SIMPLE-LIST-EQL-REMOVE, a lot
could be gained. I was a bit surprised that I managed neither Allegro
nor CMU CL to inline any call to REMOVE (well in CMU CL I finally
defined the transformer), even in presence of a LIST type definition
of the sequence argument.
The sad thing about these possible optimizations is that they have a
cost in terms of overall size of the system and the corresponding
locality problems. So the implementor has to find a good compromise
between the extreme solutions (on one end of the spectrum: provide one
single generic REMOVE function that handles lists, vectors, :TEST,
:KEY, :COUNT, :FROM-END, and on the other end: provide inline dispatch
to SIMPLE-LIST-EQ-REMOVE, SIMPLE-VECTOR-EQ-REMOVE,
SIMPLE-LIST-TEST-NO-KEY-REMOVE, SIMPLE-LIST-EQ-COUNT=1-REMOVE,
SIMPLE-LIST-EQL-COUNT=1-REMOVE,LIST-TEST-KEY-WITH-COUNT-FROM-END-REMOVE
and so on, the same for DELETE, FIND, REMOVE-IF, DELETE-IF etc.).
Clever "lazy" compilation schemes could help here.
--
Simon.
*) This is usually difficult for the compiler to prove.
Regarding the discussion about REMOVE. I ran the test functions (10
element list, 8000 removals) under lucid common lisp, and found that
REMOVE was considerably faster than FASTER-REMOVE.
Full optimization Unoptimized Consing
remove .22 sec .23 sec 280kb
faster .35 sec .44 sec 240kb
Except for the marginal increase in consing, the system provided
version of remove is considerably faster. The lesson that I've drawn
from this is that a good quality lisp should be expected to provide
reasonable optimizations for the commonly used functions in the
language.
>Let me just point out that is a bit unfair to compare FASTER-REMOVE
>against CL REMOVE implementations because REMOVE allows :TEST/:TEST-NOT
>and :KEY arguments to be provided, which makes it more difficult to
>inline the test
This is not at all an unfair comparison. The keywords should provide
flexibility, but little or no runtime cost when they are known at
compile time.
>1. Even for basic functions like REMOVE, it can be a good idea to define
> your own specialized versions that are tuned for application-specific
> performance.
I'm happy to disagree with this. I try to do this only after a system
provided function turns out to be a real bottleneck. It's probably
better for all concerned to complain to the vendor if basic functions
are not adequately coded.
Cheers,
Adam Farquhar.
········@cs.utexas.edu
Date: Mon, 23 Nov 1992 23:51 EST
From: Adam Farquhar <········@cs.utexas.edu>
Regarding the discussion about REMOVE. I ran the test functions (10
element list, 8000 removals) under lucid common lisp, and found that
REMOVE was considerably faster than FASTER-REMOVE.
Full optimization Unoptimized Consing
remove .22 sec .23 sec 280kb
faster .35 sec .44 sec 240kb
Except for the marginal increase in consing, the system provided
version of remove is considerably faster. The lesson that I've drawn
from this is that a good quality lisp should be expected to provide
reasonable optimizations for the commonly used functions in the
language.
Actually, you learned another lesson as well. The second lesson is,
always meter your optimizations to make sure that you really optimized
things. I have seen plenty of "optimizations" that actually make things
much worse. Everybody should pay careful attention to your experiences.
>1. Even for basic functions like REMOVE, it can be a good idea to define
> your own specialized versions that are tuned for application-specific
> performance.
I'm happy to disagree with this. I try to do this only after a system
provided function turns out to be a real bottleneck. It's probably
better for all concerned to complain to the vendor if basic functions
are not adequately coded.
As a Lisp implementor, I completely agree with this. If, as users, you
have good reason to believe that some basic functionality of the Lisp
implementation is too slow, you should tell your vendor.
In article <············@cascade.cs.utexas.edu> ········@cs.utexas.edu (Adam Farquhar) writes:
>Regarding the discussion about REMOVE. I ran the test functions (10
>element list, 8000 removals) under lucid common lisp, and found that
>REMOVE was considerably faster than FASTER-REMOVE.
>
> Full optimization Unoptimized Consing
>remove .22 sec .23 sec 280kb
>faster .35 sec .44 sec 240kb
>
>Except for the marginal increase in consing, the system provided
>version of remove is considerably faster. The lesson that I've drawn
>from this is that a good quality lisp should be expected to provide
>reasonable optimizations for the commonly used functions in the
>language.
As some have pointed out, faster-remove is not tail-recursive.
It is certainy not the fastest faster-remove that can be written.
Moreover, there are almost bound to be optimizations the system
doesn't provide. (Suppose you know the list contains fixnums in
increasing order. You can't even easily say a list is a list of
fixnums. You have to do something like this:
(remove (the fixnum i)
list ; N.B. can't say (list fixnum)
:test #'(lambda (i j)
(declare (fixnum i j))
(= i j)))
)
In any case, if the system has a good compiler, your functions
shouldn't be much, if any, slower than the system ones.
>>Let me just point out that is a bit unfair to compare FASTER-REMOVE
>>against CL REMOVE implementations because REMOVE allows :TEST/:TEST-NOT
>>and :KEY arguments to be provided, which makes it more difficult to
>>inline the test
>
>This is not at all an unfair comparison. The keywords should provide
>flexibility, but little or no runtime cost when they are known at
>compile time.
Right. But not all implementations will handle all the possibilities.
>>1. Even for basic functions like REMOVE, it can be a good idea to define
>> your own specialized versions that are tuned for application-specific
>> performance.
>
>I'm happy to disagree with this. I try to do this only after a system
>provided function turns out to be a real bottleneck.
Actually, you're agreeing: it _can be_ a good idea.
>It's probably better for all concerned to complain to the vendor if
>basic functions are not adequately coded.
That might work in cases where the vendor has _most_ of the
optimizations and just happens to be missing this one.
-- jd
In article <············@coli-gate.coli.uni-sb.de> ·····@coli.uni-sb.de (Espen J. Vestre) writes:
>Your function can definitely be faster for several purposes, but because
>it isn't tail-recursive, it's not as general in its applicability as
>REMOVE: It doesn't work for large lists.
Don't be so sure that REMOVE works for large lists. Sure, it does
in _some_ implementations.
In article <······················@monsun.si.no> Hallvard Tr{tteberg,
········@monsun.si.no writes:
>It shouldn't be difficult to write one that kept the biggest unchanged
>tail of the original list, returning the whole unmodified list if it
>didn't contain the first argument.
On the other hand, Common Lisp, the Manual, states that "the result [of
remove] is a copy of the input sequence." If you return part of the
original list, then you change the contract of the function. Sometimes
one uses remove and requires a totally new list. One must be careful
about "efficiency".
Tim Larkin
Federal Nutrition Laboratory
Tower Road
Ithaca, New York
····@cornell.edu
607-255-7008
In <······················@mail.cornell.edu> Tim Larkin <····@cornell.edu> writes:
> On the other hand, Common Lisp, the Manual, states that "the result [of
> remove] is a copy of the input sequence." If you return part of the
> original list, then you change the contract of the function. Sometimes
> one uses remove and requires a totally new list. One must be careful
> about "efficiency".
I was just about to post exactly this response until, in a stunning
(for me) display of scholarship, I read a page further in the
reference and discovered what seems to me like an inconsistency in the
defined semantics of the function. (CLtL2, pg 400):
"The result of REMOVE may share with the argument; a list result may
share a tail with an input list, and the result may be eq to the
input sequence if no elements need to be removed."
In <······················@mail.cornell.edu> Tim Larkin <····@cornell.edu> writes:
> On the other hand, Common Lisp, the Manual, states that "the result [of
> remove] is a copy of the input sequence." If you return part of the
> original list, then you change the contract of the function. Sometimes
> one uses remove and requires a totally new list. One must be careful
> about "efficiency".
I was just about to post exactly this response until, in a stunning
(for me) display of scholarship, I read a page further in the
reference and discovered what seems to me like an inconsistency in the
defined semantics of the function. (CLtL2, pg 400):
"The result of REMOVE may share with the argument; a list result may
share a tail with an input list, and the result may be eq to the
input sequence if no elements need to be removed."
In article <······················@mail.cornell.edu> ····@cornell.edu (Tim Larkin) writes:
>In article <······················@monsun.si.no> Hallvard Tr{tteberg,
>········@monsun.si.no writes:
>>It shouldn't be difficult to write one that kept the biggest unchanged
>>tail of the original list, returning the whole unmodified list if it
>>didn't contain the first argument.
>
>On the other hand, Common Lisp, the Manual, states that "the result [of
>remove] is a copy of the input sequence." If you return part of the
>original list, then you change the contract of the function.
Well, ... no.
Common Lisp, The Language, says what you quote above but then
goes on to say "The result of REMOVE may share with the argument
sequence; ...". See page 400 of CLtL II.
>Sometimes one uses remove and requires a totally new list.
You can lose if you rely on REMOVE returning a new list.
-- jd
In article <······················@mail.cornell.edu> ····@cornell.edu (Tim Larkin) writes:
>In article <······················@monsun.si.no> Hallvard Tr{tteberg,
>········@monsun.si.no writes:
>>It shouldn't be difficult to write one that kept the biggest unchanged
>>tail of the original list, returning the whole unmodified list if it
>>didn't contain the first argument.
>
>On the other hand, Common Lisp, the Manual, states that "the result [of
>remove] is a copy of the input sequence." If you return part of the
>original list, then you change the contract of the function.
Well, ... no.
Common Lisp, The Language, says what you quote above but then
goes on to say "The result of REMOVE may share with the argument
sequence; ...". See page 400 of CLtL II.
>Sometimes one uses remove and requires a totally new list.
You can lose if you rely on REMOVE returning a new list.
-- jd
In article <······················@monsun.si.no> Hallvard Tr{tteberg,
········@monsun.si.no writes:
>It shouldn't be difficult to write one that kept the biggest unchanged
>tail of the original list, returning the whole unmodified list if it
>didn't contain the first argument.
On the other hand, Common Lisp, the Manual, states that "the result [of
remove] is a copy of the input sequence." If you return part of the
original list, then you change the contract of the function. Sometimes
one uses remove and requires a totally new list. One must be careful
about "efficiency".
Tim Larkin
Federal Nutrition Laboratory
Tower Road
Ithaca, New York
····@cornell.edu
607-255-7008
In article <···················@liasg2.epfl.ch> Simon Leinen,
·····@lia.di.epfl.ch writes:
>Espen is correct in that Hallvard's REMOVE variant isn't
>tail-recursive and may therefore cause problems with long lists. One
>could code an iterative tail-preserving version (which might be slower).
>
>But I did some benchmarking on Sun-4s under Allegro and CMU CL, and even
>on longish lists (like 1000 elements or so), Hallvard's FASTER-REMOVE
>performed better on the whole than the system-provided REMOVE versions.
>I would bet that at least 90% of the uses of REMOVE would benefit from
>using FASTER-REMOVE.
Yes, especially if you take into account that if you're using very long
lists as your data structures, you are probably using the wrong kind of
data structure.
I guess a lot of programs might benefit even more from _memoizing_ the
remove function, i.e. if the program is using remove to filter the same
list again and again, it would benefit from knowing that, e.g., a given
value isn't present in that list at all.
--------------------------------------------------------------
Espen J. Vestre, ·····@coli.uni-sb.de
Universitaet des Saarlandes,
Computerlinguistik, Gebaeude 17.2
Im Stadtwald, tel. +49 (681) 302 4501
D-6600 SAARBRUECKEN, Germany fax. +49 (681) 302 4351
--------------------------------------------------------------
In article <···················@liasg2.epfl.ch> Simon Leinen,
·····@lia.di.epfl.ch writes:
>Espen is correct in that Hallvard's REMOVE variant isn't
>tail-recursive and may therefore cause problems with long lists. One
>could code an iterative tail-preserving version (which might be slower).
>
>But I did some benchmarking on Sun-4s under Allegro and CMU CL, and even
>on longish lists (like 1000 elements or so), Hallvard's FASTER-REMOVE
>performed better on the whole than the system-provided REMOVE versions.
>I would bet that at least 90% of the uses of REMOVE would benefit from
>using FASTER-REMOVE.
Yes, especially if you take into account that if you're using very long
lists as your data structures, you are probably using the wrong kind of
data structure.
I guess a lot of programs might benefit even more from _memoizing_ the
remove function, i.e. if the program is using remove to filter the same
list again and again, it would benefit from knowing that, e.g., a given
value isn't present in that list at all.
--------------------------------------------------------------
Espen J. Vestre, ·····@coli.uni-sb.de
Universitaet des Saarlandes,
Computerlinguistik, Gebaeude 17.2
Im Stadtwald, tel. +49 (681) 302 4501
D-6600 SAARBRUECKEN, Germany fax. +49 (681) 302 4351
--------------------------------------------------------------
In article <······················@monsun.si.no> ········@monsun.si.no (Hallvard Tr{tteberg) writes:
>Remove conses up a new list even though it doesn't remove anything!
This is true in some implementations, but remove is allowed to
return a result that "shares structure" with the list it was given.
Indeed, people often don't realize this and rely on remove making
a copy.
Since implementations don't always perform the optimizations
you need, it often turns out that a hand-written version that
does do what you want will be faster.
-- jeff
In article <······················@monsun.si.no> ········@monsun.si.no (Hallvard Tr{tteberg) writes:
>Remove conses up a new list even though it doesn't remove anything!
This is true in some implementations, but remove is allowed to
return a result that "shares structure" with the list it was given.
Indeed, people often don't realize this and rely on remove making
a copy.
Since implementations don't always perform the optimizations
you need, it often turns out that a hand-written version that
does do what you want will be faster.
-- jeff