home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / lisp / 2938 < prev    next >
Encoding:
Internet Message Format  |  1992-11-23  |  4.3 KB
  1. Xref: sparky comp.lang.lisp:2938 comp.lang.lisp.mcl:1658
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!rpi!ghost.dsi.unimi.it!univ-lyon1.fr!chx400!sicsun!disuns2!disuns2.epfl.ch!simon
  3. From: simon@lia.di.epfl.ch (Simon Leinen)
  4. Newsgroups: comp.lang.lisp,comp.lang.lisp.mcl
  5. Subject: Re: remove
  6. Message-ID: <SIMON.92Nov23130108@liasg2.epfl.ch>
  7. Date: 23 Nov 92 12:01:08 GMT
  8. References: <HALTRAET.92Nov20091121@monsun.si.no> <1eq7anINNejt@coli-gate.coli.uni-sb.de>
  9. Sender: news@disuns2.epfl.ch
  10. Followup-To: comp.lang.lisp
  11. Organization: DI-LIA -- Ecole Polytechnique Federale de Lausanne
  12. Lines: 67
  13. Nntp-Posting-Host: liasg2.epfl.ch
  14. In-reply-to: espen@coli.uni-sb.de's message of 23 Nov 92 09:12:55 GMT
  15. X-Md4-Signature: 418c3ba46e8c3692468e8a0041c2448b
  16.  
  17. Espen is correct in that Hallvard's REMOVE variant isn't
  18. tail-recursive and may therefore cause problems with long lists.  One
  19. could code an iterative tail-preserving version (which might be slower).
  20.  
  21. But I did some benchmarking on Sun-4s under Allegro and CMU CL, and even
  22. on longish lists (like 1000 elements or so), Hallvard's FASTER-REMOVE
  23. performed better on the whole than the system-provided REMOVE versions.
  24. I would bet that at least 90% of the uses of REMOVE would benefit from
  25. using FASTER-REMOVE.
  26.  
  27. Let me just point out that is a bit unfair to compare FASTER-REMOVE
  28. against CL REMOVE implementations because REMOVE allows :TEST/:TEST-NOT
  29. and :KEY arguments to be provided, which makes it more difficult to
  30. inline the test - FASTER-REMOVE uses EQ directly, which is usually
  31. inlined.  REMOVE also has to cope with :START, :END, :COUNT and
  32. :FROM-END arguments, although these are usually not provided.
  33.  
  34. On the other hand, the implementors probably thought that REMOVE would s
  35. usually be called only in casewhere it would actually remove
  36. something, so sharing structure with the original sequence (list)
  37. wouldn't be worth the effort.  But since REMOVE often leaves a
  38. significant tail portion intact, this assumption could have been wrong.
  39.  
  40. The moral is probably:
  41.  
  42. 0. Don't use any CL functions other than EQ, ATOM, CAR, CDR, CONS(?),
  43.    defstruct accessors and the fixnum and float operations in
  44.    time-critical code :-)
  45.  
  46. 1. Even for basic functions like REMOVE, it can be a good idea to define
  47.    your own specialized versions that are tuned for application-specific
  48.    performance.  Common Lisp's abundance of useful `generic' (not in the
  49.    CLOS sense) functions is in part responsible for the reputation of CL
  50.    as being `slow': If I want to remove an item from a list structure in
  51.    C, I usually write the loop myself, with the appropriate testing
  52.    inline.  Usually I will also write it to work destructively.  In CL I
  53.    simply call REMOVE---this is guaranteed to work but is also guaranteed
  54.    to scan the whole list (unless I say :COUNT which is often possible),
  55.    and usually reconses the whole list even if nothing or just the first
  56.    or second element has to be removed.
  57.  
  58. 3. There is still some optimization potential for Lisp implementations.
  59.    Consider REMOVE: in 90% of all cases it is called with the second
  60.    argument being a list(*), with no :START/:END, :COUNT (and therefore
  61.    no :FROM-END) and the :TEST argument being either the default (#'EQL)
  62.    or #'EQ.  So by transforming these two cases into calls to specialized
  63.    functions like SIMPLE-LIST-EQ-REMOVE and SIMPLE-LIST-EQL-REMOVE, a lot
  64.    could be gained.  I was a bit surprised that I managed neither Allegro
  65.    nor CMU CL to inline any call to REMOVE (well in CMU CL I finally
  66.    defined the transformer), even in presence of a LIST type definition
  67.    of the sequence argument.
  68.  
  69.    The sad thing about these possible optimizations is that they have a
  70.    cost in terms of overall size of the system and the corresponding
  71.    locality problems.  So the implementor has to find a good compromise
  72.    between the extreme solutions (on one end of the spectrum: provide one
  73.    single generic REMOVE function that handles lists, vectors, :TEST,
  74.    :KEY, :COUNT, :FROM-END, and on the other end: provide inline dispatch
  75.    to SIMPLE-LIST-EQ-REMOVE, SIMPLE-VECTOR-EQ-REMOVE,
  76.    SIMPLE-LIST-TEST-NO-KEY-REMOVE, SIMPLE-LIST-EQ-COUNT=1-REMOVE,
  77.    SIMPLE-LIST-EQL-COUNT=1-REMOVE,LIST-TEST-KEY-WITH-COUNT-FROM-END-REMOVE
  78.    and so on, the same for DELETE, FIND, REMOVE-IF, DELETE-IF etc.).
  79.    Clever "lazy" compilation schemes could help here.
  80. -- 
  81. Simon.
  82.  
  83. *) This is usually difficult for the compiler to prove.
  84.