home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / lang / lisp / 2344 < prev    next >
Encoding:
Internet Message Format  |  1992-08-31  |  2.9 KB
  1. Path: sparky!uunet!think.com!barmar
  2. From: barmar@think.com (Barry Margolin)
  3. Newsgroups: comp.lang.lisp
  4. Subject: Re: What do compilers optimize?
  5. Date: 31 Aug 1992 20:33:05 GMT
  6. Organization: Thinking Machines Corporation, Cambridge MA, USA
  7. Lines: 69
  8. Message-ID: <17tvm1INNqdc@early-bird.think.com>
  9. References: <7398@skye.ed.ac.uk>
  10. NNTP-Posting-Host: telecaster.think.com
  11.  
  12. In article <7398@skye.ed.ac.uk> jeff@aiai.ed.ac.uk (Jeff Dalton) writes:
  13. >(Do any Lisp implementors read this newsgroup?)
  14.  
  15. KMP of Symbolics has been participating quite a bit lately.  I know some
  16. Lucid people read it but don't post much.
  17.  
  18. >Are there any implementations that do any of the following (or
  19. >something similar):
  20. >
  21. >  * Turn a CASE in which the alternatives are integers into
  22. >    an indirect transfer?
  23.  
  24. Symbolics and Lucid do this.  My gripe with the Symbolics implementation is
  25. that it won't do the optimization if the case values are a dense set not
  26. near 0 -- it doesn't want to create a sparse jump table, and it doesn't try
  27. to offset the value to the base of the set.
  28.  
  29. Surprisingly, CMUCL doesn't do this optimization at all.
  30.  
  31. An interesting enhancement to this optimization would be to recognize when
  32. the case values are a sparse set of dense sets, e.g.
  33.  
  34. (case x
  35.   ((0 1 2 3 4 5 6) ...)
  36.   ((7 9 11) ...)
  37.   ((30 31 32) ...)
  38.   ((33 34 35) ...)
  39.   ((95 97 99 101) ...))
  40.  
  41. and transform this into
  42.  
  43. (cond ((<= 0 x 11)
  44.        (case x ((0 1 2 3 4 5 6) ...)
  45.            ((7 9 11) ...)))
  46.       ((<= 30 35)
  47.        (case x ((30 31 32) ...)
  48.            ((33 34 35) ...)))
  49.       (t (case x ((95 97 99 101) ...))))
  50.  
  51. I could imagine the above style of code being in the implementation of a
  52. byte code interpreter.  A processor emulator might be similar, although the
  53. dense sets would likely be found clustered above power-of-two values,
  54. allowing for further optimization; instead of the outer level being a COND,
  55. it could be another CASE that indexes off the high-order bits of the
  56. opcode, which is likely to be a dense set that can be turned into a jump
  57. table.
  58.  
  59. >  * Use hashing for a CASE with many alternatives?
  60.  
  61. Neither Symbolics, Lucid, nor CMUCL appear to do this.
  62.  
  63. >  * Allow fixnums (or floats) to be passed between procedures without
  64. >    any heap allocations (maybe just for local procedures in the same
  65. >    top-level form)?
  66.  
  67. Most implementations implement fixnums as immediate values, so they are
  68. never allocated on the heap.  Symbolics also implements single floats as
  69. immediate types.  I don't expect any implementations for conventional
  70. 32-bit processors to do this, though, since single floats take 32 bits, and
  71. that doesn't leave any room for tags.  I believe this was the original
  72. intent of the small-float type, but apparently it's not useful enough (most
  73. FP hardware only supports 32 and 64 bit floats, and the limited precision
  74. of smaller floats probably makes them pretty useless).
  75.  
  76. -- 
  77. Barry Margolin
  78. System Manager, Thinking Machines Corp.
  79.  
  80. barmar@think.com          {uunet,harvard}!think!barmar
  81.