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