home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / windows / x / 19399 < prev    next >
Encoding:
Internet Message Format  |  1992-11-20  |  2.7 KB
  1. Path: sparky!uunet!news.centerline.com!jimf
  2. From: jimf@centerline.com (Jim Frost)
  3. Newsgroups: comp.windows.x
  4. Subject: Re: FLAME, FLAME ON X!!!
  5. Date: 20 Nov 1992 19:32:56 GMT
  6. Organization: CenterLine Software, Inc.
  7. Lines: 47
  8. Message-ID: <1ejeh8INN1jq@armory.centerline.com>
  9. References: <RJC.92Nov13144522@daiches.cogsci.ed.ac.uk> <1992Nov16.162457.2923@osf.org> <1ebs7rINNp9k@armory.centerline.com> <1992Nov19.040434.12181@osf.org>
  10. NNTP-Posting-Host: 140.239.3.202
  11.  
  12. dbrooks@osf.org (David Brooks) writes:
  13. >jimf@centerline.com (Jim Frost) writes:
  14.  
  15. >>Unfortunately power-of-two allocation is remarkably wasteful of
  16. >>virtual memory (which means wasteful of real live swap space on many
  17. >>systems).
  18.  
  19. >Then why have I heard people recommend using gnu malloc with X, people who
  20. >I thought would be in the know?  The only gnu mallocs I've seen use
  21. >exclusively power-of-two allocation, and don't attempt to split a larger
  22. >block or merge blocks on free.
  23.  
  24. Look at it this way -- if you do all allocations in a power of two
  25. then to have a list for every possible different sized allocation you
  26. need only thirty-two lists (actually 28 or 29 depending on the minimum
  27. allocation size, or even fewer if you consider that you can't really
  28. allocate a 4 gig area).  That's real convenient -- you can basically
  29. find an empty space (if there is one) immediately, making your
  30. allocator REALLY fast.  It's my assumption that that's what the GNU
  31. malloc does, although I've never looked it the code.
  32.  
  33. The downside is that it's wasteful for allocations that don't fit
  34. well.  An 65-byte allocation will return 128 bytes.  No big deal, at
  35. least as long as you're not doing a lot of those allocations.  As the
  36. sizes get larger, however, it becomes a really big deal -- a 1.1
  37. megabyte allocation will return 2 megabytes, for instance.  Once you
  38. have a few of those you're starting to really waste memory.
  39.  
  40. Most small programs -- and even a lot of large ones -- do few large
  41. allocations but a lot of small ones.  For small allocations the
  42. lossage isn't too bad, so you get the performance win of finding free
  43. elements of the right size quickly without any real degredation.
  44.  
  45. Things fall apart quickly for any application that actually needs to
  46. do many large allocations of odd sizes, though -- if the allocation
  47. doesn't fit well you start to loose megabytes.  Thus for applications
  48. that do lots of large allocations it really pays to use something that
  49. fits allocations better.  Further, it's really not that hard to make
  50. an algorithm that's just as fast as the power-of-two algorithm -- at
  51. least for a fair number of different small sizes.  It's just harder
  52. than doing a power-of-two algorithm.
  53.  
  54. Anyway this has gone off pretty far from X.  If you want more
  55. discussion send me email.
  56.  
  57. jim frost
  58. jimf@centerline.com
  59.