home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / pop / 173 < prev    next >
Encoding:
Internet Message Format  |  1992-12-23  |  2.3 KB
  1. Path: sparky!uunet!pipex!bnr.co.uk!uknet!bhamcs!axs
  2. From: axs@cs.bham.ac.uk (Aaron Sloman)
  3. Newsgroups: comp.lang.pop
  4. Subject: Re: Dynamic List Implementation
  5. Message-ID: <Bzq1Du.HxF@cs.bham.ac.uk>
  6. Date: 23 Dec 92 16:49:05 GMT
  7. References: <116670038@otter.hpl.hp.com>
  8. Sender: news@cs.bham.ac.uk
  9. Organization: School of Computer Science, University of Birmingham, UK
  10. Lines: 46
  11. Nntp-Posting-Host: emotsun
  12.  
  13. Following on from my previous comment on Steve Knight's message.
  14.  
  15. > sfk@otter.hpl.hp.com (Steve Knight)
  16. > Date: 22 Dec 92 14:55:12 GMT
  17. > Organization: Hewlett-Packard Laboratories, Bristol, UK
  18.  
  19. Steve considered a change to use a special data-type for dynamic
  20. lists, saying
  21.  
  22. > Now the common case is significantly quicker -- only inspecting the key
  23. > of -x- to return a result.
  24. >
  25. > As far as I can tell, the same analysis follows through for all the
  26. > list operators.  The dynamic list operations are slightly worsened in
  27. > performance, it is true, but looking at the statistics there it is
  28. > a very small amount indeed.
  29. >
  30. > Is there some subtle detail about dynamic lists that I am overlooking?
  31. > I would be grateful for any facts or insights into this aspect of
  32. > POP.  What motivates me is that I love having dynamic lists around
  33. > but I hate having to pay -any- performance penalty for them if there is
  34. > no necessity for it.  So my question boils down to, where is the
  35. > necessity?
  36.  
  37. I asked John Gibson about the possible advantage of using a new kind
  38. of link and he commented:
  39. | Checking whether the back is a procedure is merely 1 memory access
  40. | slower than checking the key of the pair (ie, utterly insignificant).
  41. | Once you know it's dynamic, checking the front for true/false is
  42. | insignificant compared to the time taken the run the dynamic procedure,
  43. | etc.
  44.  
  45. So maybe the efficiency issue is not worth worrying about, given
  46. that you can already use front and back (or the fast_versions) for
  47. speed when you know you are not using dynamic lists.
  48.  
  49. But I have not done any tests to check the difference it would make
  50. to procedures like hd, tl, null, etc. on non-dynamic lists, if there
  51. were a special datatype for dynamic lists.
  52.  
  53. aaron
  54. -- 
  55. Aaron Sloman, School of Computer Science,
  56. The University of Birmingham, B15 2TT, England
  57. EMAIL   A.Sloman@cs.bham.ac.uk  OR A.Sloman@bham.ac.uk
  58. Phone: +44-(0)21-414-3711       Fax:   +44-(0)21-414-4281
  59.