home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / windows / x / 19261 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  4.1 KB
  1. Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!bu.edu!news.bbn.com!noc.near.net!news.centerline.com!jimf
  2. From: jimf@centerline.com (Jim Frost)
  3. Newsgroups: comp.windows.x
  4. Subject: Re: FLAME, FLAME ON X!!!
  5. Message-ID: <1ebs7rINNp9k@armory.centerline.com>
  6. Date: 17 Nov 92 22:37:47 GMT
  7. References: <1683@igd.fhg.de> <1992Nov9.235741.25166@dsd.es.com> <RJC.92Nov13144522@daiches.cogsci.ed.ac.uk> <1992Nov16.162457.2923@osf.org>
  8. Organization: CenterLine Software, Inc.
  9. Lines: 70
  10. NNTP-Posting-Host: 140.239.3.202
  11.  
  12. drand@spinner.osf.org (Douglas S. Rand) writes:
  13. >|> The word is `Fragmentation'. 
  14.  
  15. >There are a number of reasonable solutions to memory fragmentation.  It really
  16. >is up to a decent malloc implementation to attempt to avoid fragmentation.
  17. >I'll illustrate with a well known method which we used on Prime's EMACS and
  18. >which I believe libg++ uses.  
  19.  
  20. >Allocate all memory in set size chunks.  Sizes can be on powers of two, for
  21. >example.  Freeing a block places it on a free list for that size.  Allocation
  22. >requests first go to the most natural next size block and progress upward in
  23. >size.  Optionally break larger blocks if no smaller blocks are available.
  24. >Optionally run the block lists on occation and join smaller contiguous
  25. >blocks into larger blocks.  
  26.  
  27. Unfortunately power-of-two allocation is remarkably wasteful of
  28. virtual memory (which means wasteful of real live swap space on many
  29. systems).  It works fine for very tiny allocations but once you start
  30. allocating those "unusual" sizes like 80-byte segments you start
  31. seeing major memory waste as well as relatively slow free-element
  32. location compared to several other techniques.
  33.  
  34. The two best generic allocation systems I've run into are
  35. limited-cluster (usually just called cluster) and a nifty tree system
  36. done by a research guy at IBM.
  37.  
  38. Limited-cluster systems predict that most programs do a lot of little
  39. allocations of the same size (up to, say, 128 bytes) but fewer large
  40. ones of widely varying sizes, and therefore allocate a lot of little
  41. allocations up front.  Managing allocations and frees of the little
  42. allocations is dirt cheap and you get very little fragmentation (and a
  43. lot of locality to boot).  Some systems I've seen use power-of-two
  44. fitting for the clustered allocations, but I personally believe that
  45. you get better overall behavior by using linear increases since they
  46. are far less wasteful after the first few power steps (and in fact
  47. most linear fitting schemes are practically the same as power fitting
  48. for the first few power steps).  Large allocations are done as
  49. necessary and fitted as exactly as possible.  The big win is keeping
  50. the many small allocations in most programs away from the few big
  51. ones, which keeps fragmentation down.
  52.  
  53. Limited-cluster allocation systems are commonly used when memory is
  54. not a major issue but heap maintenance overhead is.
  55.  
  56. The tree allocation system done at IBM is more complicated, ordering a
  57. tree of memory fragments by both address and size.  Address ordering
  58. makes defragmentation a snap since adjacent allocations will always
  59. share adjacent nodes, and size ordering makes finding a good fit easy.
  60.  
  61. It's an interesting system -- interesting enough that IBM shifted from
  62. a power-of-two allocation system to their research system between
  63. release 3.1 and 3.2 of AIX, largely due to customer complaints about
  64. overwhelming memory waste in the 3.1 malloc(*).  There's an article in
  65. the IBM Journal of Research and Development on the topic but I don't
  66. have the issue handy.
  67.  
  68. Informationally yours,
  69.  
  70. jim frost
  71. jimf@centerline.com
  72.  
  73. (*) Many of the observed performance problems may have been due to
  74. their technique of recycling allocations when the available heap is
  75. exhausted rather than using a more aggressive system.  Long recycle
  76. times lead to poor heap locality and much-higher-than-necessary paging
  77. rates.  A power-of-two allocator that aggressively reuses allocations
  78. would have fewer problems in this regard although locality would still
  79. be hurt for multiple allocations which were not particularly well
  80. fitted to a power-of-two.  The AIX 3.2 system is far more aggressive
  81. at reuse.
  82.