home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3414 < prev    next >
Encoding:
Text File  |  1993-01-05  |  4.7 KB  |  91 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!usc!howland.reston.ans.net!sol.ctr.columbia.edu!eff!world!jhallen
  3. From: jhallen@world.std.com (Joseph H Allen)
  4. Subject: Re: Memory management models (plus new malloc library described)
  5. Message-ID: <C0DDr7.3rw@world.std.com>
  6. Organization: The World Public Access UNIX, Brookline, MA
  7. References: <1ia6tqINNaps@uwm.edu>
  8. Date: Tue, 5 Jan 1993 07:21:06 GMT
  9. Lines: 80
  10.  
  11. In article <1ia6tqINNaps@uwm.edu> markh@csd4.csd.uwm.edu (Mark) writes:
  12. >   I'm looking for efficient models for source-level memory management that
  13. >resolve fragmentation and allows contiguous segments of arbitrary size to be
  14. >allocated.  They should be compared to the model which I presently use:
  15. >
  16. >        * Free lists maintained for blocks of size 2^N for each N < 32,
  17. >
  18. >        * Allocated segment are fit into the smallest available block of
  19. >          size 2^N, using the Nth free-list if it's non-empty.
  20. >
  21. >Default malloc is insufficient because it doesn't normally protect against
  22. >external fragmentation,
  23.  
  24. >   The model above guarantees that fragmentation will always lie under 50%,
  25. >that allocation will usually be a constant-time operation and that deallocation
  26. >will always be constant time.
  27.  
  28. I've found that fragmentation (I think you mean the tendancy for free blocks
  29. to get more numerous on the small end) is not really that much of a problem
  30. compared to other things.  In your algorithm for example:  although what you
  31. call fragmentation will be less than 50%, the amount of memory you waste is
  32. large since you also have to count what's left in the free list.
  33.  
  34. In any case, GNU Malloc works the same as your method for blocks smaller
  35. than 4K, except that it will combine free blocks together into other powers
  36. of 2, and works as a simple first-fit singly-linked free-list allocator for
  37. blocks larger than 4K.  It's quite fast, wastes a bit less space than your
  38. method, but sill wastes quite a bit compared with other slower algorithms.
  39.  
  40. The most space-effecient non-garbage collecting algorithm I've found (for
  41. flat random distributions of mallocs, frees and reallocs) is best-fit.  This
  42. is when you pick the smallest free block which will fit the malloc request
  43. and always return the balance of the block back to the free list.  Also free
  44. blocks always get coalesced when they can.  Usually I try to give back space
  45. to the OS by calling sbrk when the last block is freed.  This helps only a
  46. little, but it does help.
  47.  
  48. Although I usually use flat random numbers for testing malloc schemes, I've
  49. found that less random tests only amplify the differences between schemes. 
  50. So in the real world, best-fit is much better than GNU malloc.
  51.  
  52. The problem with best fit is that since you have to do a linear search
  53. through a linked list, it's really slow (like hundreds or thousands of times
  54. slower than GNU malloc).
  55.  
  56. I found that this can be fixed by using a database.  The best database I
  57. found is the 'skip-list' scheme described in this newsgroup some time ago. 
  58. It's best because the constant time cost is extremely small.
  59.  
  60. Anyway I made a new memory allocator using this (it's included as part of my
  61. JOE editor.  Get it from anonymous ftp from world.std.com, file
  62. src/editors/joe1.0.7.tar.Z.  The allocator is in heap.c/heap.h and requires
  63. blocks.c/blocks.h, random.c/random.h and config.h).
  64.  
  65. I compared it with GNU malloc for 100,000 random mallocs, reallocs and
  66. frees.  It ended up wasting 50% less memory.  I don't remember the exact
  67. test results, but I think GNU malloc had 4 MB of core allocated of which 2MB
  68. was actually requested, where mine had 3 MB of core allocated.
  69.  
  70. It used only 50% more CPU time than GNU malloc.  This is really astounding
  71. considering how fast GNU malloc is.  That a best fit scheme is even in the
  72. same order of magnitude is really amazing.  Skip-lists are really cool.  :-)
  73. one neat thing is that in the paper that described skip-lists, the inventor
  74. suggests that you use 1/2 or 1/4 as easy approximations of 1/e for the
  75. random number distribution.  It turned out that using 1/e instead of 1/2 or
  76. 1/4 translated into significant CPU-time differences, so that was used
  77. instead.
  78.  
  79. >and source-level paging is insufficient because it
  80. >doesn't resolve the need for contiguity.
  81.  
  82. I started out as a microprocessor assembly langauge programmer.  I have to
  83. remind myself time and time again that using malloc on UNIX is ok and that I
  84. don't have to make up some difficult page allocation scheme.  But I still
  85. have this feeling that I'm cheating :-)
  86. -- 
  87. /*  jhallen@world.std.com (192.74.137.5) */               /* Joseph H. Allen */
  88. int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
  89. +r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2
  90. ]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}
  91.