NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/fj/maillis/xwindow/17588

Internet Message Format | 1992-11-18 | 4.2 KB

Path: sparky!uunet!stanford.edu!sun-barr!sh.wide!wnoc-tyo-news!scslwide!wsgw!wsservra!daemon
From: [e-mail] (Jim Frost)
Newsgroups: fj.mail-lists.x-window
Subject: Re: FLAME, FLAME ON X!!!
Message-ID: <[e-mail]>
Date: 18 Nov 92 12:13:38 GMT
Sender: [e-mail] (The devil himself)
Distribution: fj
Organization: CenterLine Software, Inc.
Lines: 76
Approved: [e-mail]

Date: 17 Nov 92 22:37:47 GMT
Message-Id: <[e-mail]>
Newsgroups: comp.windows.x
References: <[e-mail]>, <[e-mail]>, <[e-mail]>
Sender: [e-mail]

[e-mail] (Douglas S. Rand) writes:
>|> The word is `Fragmentation'.

>There are a number of reasonable solutions to memory fragmentation.  It really
>is up to a decent malloc implementation to attempt to avoid fragmentation.
>I'll illustrate with a well known method which we used on Prime's EMACS and
>which I believe libg++ uses.

>Allocate all memory in set size chunks.  Sizes can be on powers of two, for
>example.  Freeing a block places it on a free list for that size.  Allocation
>requests first go to the most natural next size block and progress upward in
>size.  Optionally break larger blocks if no smaller blocks are available.
>Optionally run the block lists on occation and join smaller contiguous
>blocks into larger blocks.

Unfortunately power-of-two allocation is remarkably wasteful of
virtual memory (which means wasteful of real live swap space on many
systems).  It works fine for very tiny allocations but once you start
allocating those "unusual" sizes like 80-byte segments you start
seeing major memory waste as well as relatively slow free-element
location compared to several other techniques.

The two best generic allocation systems I've run into are
limited-cluster (usually just called cluster) and a nifty tree system
done by a research guy at IBM.

Limited-cluster systems predict that most programs do a lot of little
allocations of the same size (up to, say, 128 bytes) but fewer large
ones of widely varying sizes, and therefore allocate a lot of little
allocations up front.  Managing allocations and frees of the little
allocations is dirt cheap and you get very little fragmentation (and a
lot of locality to boot).  Some systems I've seen use power-of-two
fitting for the clustered allocations, but I personally believe that
you get better overall behavior by using linear increases since they
are far less wasteful after the first few power steps (and in fact
most linear fitting schemes are practically the same as power fitting
for the first few power steps).  Large allocations are done as
necessary and fitted as exactly as possible.  The big win is keeping
the many small allocations in most programs away from the few big
ones, which keeps fragmentation down.

Limited-cluster allocation systems are commonly used when memory is
not a major issue but heap maintenance overhead is.

The tree allocation system done at IBM is more complicated, ordering a
tree of memory fragments by both address and size.  Address ordering
makes defragmentation a snap since adjacent allocations will always
share adjacent nodes, and size ordering makes finding a good fit easy.

It's an interesting system -- interesting enough that IBM shifted from
a power-of-two allocation system to their research system between
release 3.1 and 3.2 of AIX, largely due to customer complaints about
overwhelming memory waste in the 3.1 malloc(*).  There's an article in
the IBM Journal of Research and Development on the topic but I don't
have the issue handy.

Informationally yours,

jim frost
[e-mail]

(*) Many of the observed performance problems may have been due to
their technique of recycling allocations when the available heap is
exhausted rather than using a more aggressive system.  Long recycle
times lead to poor heap locality and much-higher-than-necessary paging
rates.  A power-of-two allocator that aggressively reuses allocations
would have fewer problems in this regard although locality would still
be hurt for multiple allocations which were not particularly well
fitted to a power-of-two.  The AIX 3.2 system is far more aggressive
at reuse.