home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / pop / 170 < prev    next >
Encoding:
Internet Message Format  |  1992-12-22  |  2.1 KB
  1. From: sfk@otter.hpl.hp.com (Steve Knight)
  2. Date: Tue, 22 Dec 1992 14:55:12 GMT
  3. Subject: Dynamic List Implementation
  4. Message-ID: <116670038@otter.hpl.hp.com>
  5. Organization: Hewlett-Packard Laboratories, Bristol, UK.
  6. Path: sparky!uunet!zaphod.mps.ohio-state.edu!sdd.hp.com!hpscit.sc.hp.com!hplextra!otter.hpl.hp.com!otter!sfk
  7. Newsgroups: comp.lang.pop
  8. Lines: 49
  9.  
  10. I've always been puzzled why POPLOG implements dynamic lists using
  11. pairs rather than a separate dpair key.  In fact, a dynamic list
  12. is represented using a pair whose back is a procedure and whose
  13. front is true.
  14.  
  15. Because POPLOG uses this representation, many simple operators go
  16. slower in the common case of non-dynamic lists.  For example, the
  17. operator -null-, which is almost always applied to non-dynamic pairs, 
  18. determines the speed of -for- loops.  But it has to be coded like 
  19. this
  20.  
  21.     define null( x ); lvars x;
  22.         if ispair( x ) then
  23.             isprocedure( fast_back( x ) ) and 
  24.             dnull( x )    ;;; you can imagine the code for this.
  25.         else
  26.             x == [] or mishap( 'LIST NEEDED', [^x] )
  27.         endif
  28.     enddefine;
  29.  
  30.  
  31. In the common case, this version of null is obliged not only to inspect
  32. the key of -x- but also the fast_back(x) for being a procedure.  If we
  33. compare with the version which uses dpairs to indicate dynamic pairs.
  34.  
  35.     define null( x ); lvars x;
  36.         not( ispair( x ) ) and
  37.         (    
  38.             x == [] or
  39.             isdpair( x ) and dnull( x )
  40.         )
  41.     endefine;
  42.  
  43. Now the common case is significantly quicker -- only inspecting the key
  44. of -x- to return a result.
  45.  
  46. As far as I can tell, the same analysis follows through for all the 
  47. list operators.  The dynamic list operations are slightly worsened in
  48. performance, it is true, but looking at the statistics there it is
  49. a very small amount indeed.  
  50.  
  51. Is there some subtle detail about dynamic lists that I am overlooking?
  52. I would be grateful for any facts or insights into this aspect of
  53. POP.  What motivates me is that I love having dynamic lists around
  54. but I hate having to pay -any- performance penalty for them if there is
  55. no necessity for it.  So my question boils down to, where is the 
  56. necessity?
  57.  
  58. Steve
  59.