Thread: new heap manager mmalloc
Hi, FYI regarding the recent performance issues. This lib is ported to win32. I don't know, how many unixes are supported. Perhaps it's better to reuse something and not to reimplementit from scratch. But you are to decide. forwarded from comp.os.linux.announce --- mmalloc is a heap manager. It is written from a scratch. Main goals were accurate RAM consuming and performance. Goals achieved using relatively new virtual memory mapping techniques (known in UNIX wolrd as mmap ;-) and AVL trees. Major advantages of this heap manager:* Trimming and "no commit". mmalloc immediately (not in Windows world) releasesall deallocated pages to the system. Also all allocated pages are not commited, because new areas are just mapped in, still not commited and only user program could commit memory. So the following rule is real true: "NOUNUSED MEMORY WILL BE CONSUMED". * Best-fit. Best-fit strategy was used. As shown in real world experiments, best-fit proven to be more accurate than first-fit. * AVL Trees. Primary internal structure used for controlling large blocks (>256 bytes, tunable). So the time consumed byallocating new block is proportional to O(log N), where N is the number of memory fragments. Implementation is in pureC and optimized. * Small blocks grouped. Small blocks are grouped within pages. This provides more accurate memory consuming. When doing100000 times mmalloc(1) only ~130k of real memory will be allocated. * Smart alignment. Blocks smaller than MALLOC_ALIGN (tunable) are not aligned. (typical for i386 are blocks <4 bytes).Other blocks are aligned by MALLOC_ALIGN. * Small overhead. For blocks large blocks overhead is 32 bytes. It is approximately 12.5% for 256 bytes long block. Forlarger blocks size of this control structure is ever less noticed. Small blocks are grouped within one page and resultingoverhead is less than 0.2% (8/4096*100). * Pure ANSI-C. Pure ANSI-C without any extensions was used. So library should be portable. Only vmm functions are not portable,other library parts should be. Visit homepage: http://www.geocities.com/SiliconValley/Circuit/5426/index.html Valery ---- Ciao Ulrich -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- Ulrich Vo"3 uvo@uvo.do.eunet.de " As a human being I claim the right to be widely inconsistent " John Peel -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Two things against it...
First, its a Linux-ism...he's got it ported to Win and Linux, that's it...
Second:
GNU LIBRARY GENERAL PUBLIC LICENSE Version 2, June 1991
Copyright (C) 1991 Free Software Foundation, Inc.59 Temple Place - Suite 330, Boston, MA 02111-1307, USAEveryone is
permittedto copy and distribute verbatim copiesof this license document, but changing it is not allowed.
[This is the first released version of the library GPL. It isnumbered 2 because it goes with version 2 of the ordinary
GPL.]
On Thu, 28 Jan 1999, Ulrich Voss wrote:
> Hi,
>
> FYI regarding the recent performance issues.
>
> This lib is ported to win32. I don't know, how many unixes are
> supported. Perhaps it's better to reuse something and not to
> reimplementit from scratch. But you are to decide.
>
> forwarded from comp.os.linux.announce
>
> ---
>
> mmalloc is a heap manager. It is written from a scratch. Main goals were
> accurate RAM consuming and performance. Goals achieved using relatively
> new virtual memory mapping techniques (known in UNIX wolrd as mmap ;-) and
> AVL trees.
>
> Major advantages of this heap manager:
> * Trimming and "no commit". mmalloc immediately (not in Windows
> world) releases all deallocated pages to the system. Also all
> allocated pages are not commited, because new areas are just mapped
> in, still not commited and only user program could commit memory. So
> the following rule is real true:
> "NO UNUSED MEMORY WILL BE CONSUMED".
>
> * Best-fit. Best-fit strategy was used. As shown in real world
> experiments, best-fit proven to be more accurate than first-fit.
>
> * AVL Trees. Primary internal structure used for controlling large
> blocks (>256 bytes, tunable). So the time consumed by allocating
> new block is proportional to O(log N), where N is the number of memory
> fragments. Implementation is in pure C and optimized.
>
> * Small blocks grouped. Small blocks are grouped within pages. This
> provides more accurate memory consuming. When doing 100000 times
> mmalloc(1) only ~130k of real memory will be allocated.
>
> * Smart alignment. Blocks smaller than MALLOC_ALIGN (tunable)
> are not aligned. (typical for i386 are blocks <4 bytes). Other
> blocks are aligned by MALLOC_ALIGN.
>
> * Small overhead. For blocks large blocks overhead is 32 bytes. It is
> approximately 12.5% for 256 bytes long block. For larger blocks size
> of this control structure is ever less noticed. Small blocks are
> grouped within one page and resulting overhead is less than
> 0.2% (8/4096*100).
>
> * Pure ANSI-C. Pure ANSI-C without any extensions was used. So library
> should be portable. Only vmm functions are not portable, other library
> parts should be.
>
> Visit homepage:
>
> http://www.geocities.com/SiliconValley/Circuit/5426/index.html
>
> Valery
>
> ----
>
> Ciao
>
> Ulrich
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
> Ulrich Vo"3 uvo@uvo.do.eunet.de
>
> " As a human being I claim the right
> to be widely inconsistent " John Peel
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>
Marc G. Fournier
Systems Administrator @ hub.org
primary: scrappy@hub.org secondary: scrappy@{freebsd|postgresql}.org
The Hermit Hacker <scrappy@hub.org> writes:
> Two things against it...
> First, its a Linux-ism...he's got it ported to Win and Linux, that's it...
If it depends on mmap(), porting may not be trivial, either.
Still, if it's a drop-in replacement for malloc, I see no reason that
a particular installation couldn't use it with Postgres --- and we could
even recommend that, if it's a big win. The license conflict would
preclude actually including it with Postgres, but pointing to it is
no problem.
Anyone want to try it and see if it provides a noticeable speed
improvement?
regards, tom lane
> > Two things against it... > > First, its a Linux-ism...he's got it ported to Win and Linux, that's it... Actually, our problem is not malloc itself. Most Unix OS's have pretty good malloc's, tuned to their OS. The problem is the number of times we call it. Massimo's idea of having several alloc contexts, some of which supply memory from a backend-managed pool is a good idea. When I was working on a SQL backend design, I thought this would be a very good way to go. SQL databases have a nice end-of-transaction free-it-all point that can make use of such a give-me-the-memory and don't worry about freeing it until I am done with the transaction model. -- Bruce Momjian | http://www.op.net/~candle maillist@candle.pha.pa.us | (610) 853-3000+ If your life is a hard drive, | 830 Blythe Avenue + Christ can be your backup. | Drexel Hill, Pennsylvania19026
Bruce Momjian <maillist@candle.pha.pa.us> writes:
> Actually, our problem is not malloc itself. Most Unix OS's have pretty
> good malloc's, tuned to their OS. The problem is the number of times we
> call it.
Well, some malloc libs are noticeably better than others, but as long
as the operating assumption is that any allocated block can be freed
independently of any other one, it's hard to do a *lot* better than
a standard malloc library. You have to keep track of each allocated
chunk and each free area, individually, to meet malloc/free's API.
What we need to do is exploit the notion of pooled allocation
(contexts), wherein the memory management apparatus doesn't keep track
of each allocation individually, but just takes it from a pool of space
that will all be freed at the same time. End of statement, end of
transaction, etc, are good pool lifetimes for Postgres.
We currently have the worst of both worlds: we pay malloc's overhead,
and we have a *separate* bookkeeping layer on top of malloc that links
allocated blocks together to allow everything to be freed at end-of-
context. We should be able to do this more cheaply than malloc, not
more expensively.
BTW, I already did something similar in the frontend libpq, and it
was a considerable win for reading large SELECT results.
regards, tom lane
Tom Lane wrote:
>
> Bruce Momjian <maillist@candle.pha.pa.us> writes:
> > Actually, our problem is not malloc itself. Most Unix OS's have pretty
> > good malloc's, tuned to their OS. The problem is the number of times we
> > call it.
>
> [...]
>
> What we need to do is exploit the notion of pooled allocation
> (contexts), wherein the memory management apparatus doesn't keep track
> of each allocation individually, but just takes it from a pool of space
> that will all be freed at the same time. End of statement, end of
> transaction, etc, are good pool lifetimes for Postgres.
>
> We currently have the worst of both worlds: we pay malloc's overhead,
> and we have a *separate* bookkeeping layer on top of malloc that links
> allocated blocks together to allow everything to be freed at end-of-
> context. We should be able to do this more cheaply than malloc, not
> more expensively.
Right right right! Pooled allocation will gain performance
and the separate bookkeeping should be more useful.
I did some little hacking and placed a silly pool into
palloc() and friends. It simply uses bigger blocks of memory
for small allocations and keeps only a refcount in the block
to see when all allocations are pfree()'d. No chunks inside a
block are reused, instead it waits until the entire block is
free to throw it away (what doesn't happen as often as it
should). The blocks are allocated in the same memory context
the chunks should have been, so transaction ends
AllocSetReset() cleans them out anyway.
It is a poor, simple way to reduce the number of palloc()'d
segments, so it saves calls to malloc()/free() and reduces
the bookkeeping overhead in AllocSet...().
The performance win on the regression test is about 10%. So
it demonstrates that it's a good place for optimization.
For now, it noticably raises the memory consumption of the
backend. I think there are many small palloc()'d chunks not
free'd, that cause my entier blocks to stay in memory. And
since there is no reuse in a block, this summarizes up. This
kind of pool is useful for things that should stay until
transaction end.
But I can think of another thing that might help. A temporary
allocation pool stack.
The functions to manage it are:
void tmppalloc_push(void);
void tmppalloc_pop(void);
void *tmppalloc(Size size);
void *tmpuppalloc(Size size, int levels_up);
The stack does also handle the allocations in bigger blocks.
But no individual free's are necessary, because the closing
pop will throw away the innermost memory context. And since
there are no free and realloc functions, it must not remember
any information about the individual chunks. Could be a much
bigger win for all our little allocs (I've seen thousands of
2-16 byte allocations when hacking in the above - with the
old palloc(), every such has an additional overhead of 16
bytes in the AllocSet).
Well, it requires us to revise the entire backend code,
module per module, to look which palloc()'s could be changed
into temp ones. But we'll find MANY places where memory
isn't pfree()'d that nobody wants until transaction end.
Jan
--
#======================================================================#
# It's easier to get forgiveness for being wrong than for being right. #
# Let's break this rule - forgive me. #
#======================================== jwieck@debis.com (Jan Wieck) #
> The functions to manage it are: > > void tmppalloc_push(void); > void tmppalloc_pop(void); > void *tmppalloc(Size size); > void *tmpuppalloc(Size size, int levels_up); This is a nice interface that I think would work. Let's map out the *alloc options after 6.5, pick one, and go for it. -- Bruce Momjian | http://www.op.net/~candle maillist@candle.pha.pa.us | (610) 853-3000+ If your life is a hard drive, | 830 Blythe Avenue + Christ can be your backup. | Drexel Hill, Pennsylvania19026
Jan Wieck wrote: > > Right right right! Pooled allocation will gain performance > and the separate bookkeeping should be more useful. ... > But I can think of another thing that might help. A temporary > allocation pool stack. > > The functions to manage it are: > > void tmppalloc_push(void); > void tmppalloc_pop(void); > void *tmppalloc(Size size); > void *tmpuppalloc(Size size, int levels_up); You might be interested in: POOL(9) NetBSD Kernel Manual POOL(9) NAME pool_create, pool_destroy, pool_get, pool_put, pool_prime - resource-pool manager ... DESCRIPTION These utility routines provide management of pools of fixed-sized areas of memory. Resource pools setaside an amount of memory for exclusive use by the resource pool owner. This can be used by applications to guaranteethe availability of a minimum amount of memory needed to con� tinue operation independent of the memory resourcescurrently available from the system-wide memory allocator (malloc(9)). The pool manager can optionally obtaintemporary memory by calling the palloc() function passed to pool_create(), for extra pool items in case the numberof allo� cations exceeds the nominal number of pool items managed by a pool re� source. This temporary memorywill be automatically returned to the sys� tem at a later time. ... CODE REFERENCES The pool manager is implemented in the file sys/kern/subr_pool.c. eg. ftp://ftp.NetBSD.org/pub/NetBSD-current/src/sys/kern/subr_pool.c Cheers, Patrick
I have added this to the TODO list: * improve dynamic memory allocation by introducing tuple-context memory allocation * add pooled memory allocation where allocations are freed only as a group > Bruce Momjian <maillist@candle.pha.pa.us> writes: > > Actually, our problem is not malloc itself. Most Unix OS's have pretty > > good malloc's, tuned to their OS. The problem is the number of times we > > call it. > > Well, some malloc libs are noticeably better than others, but as long > as the operating assumption is that any allocated block can be freed > independently of any other one, it's hard to do a *lot* better than > a standard malloc library. You have to keep track of each allocated > chunk and each free area, individually, to meet malloc/free's API. > > What we need to do is exploit the notion of pooled allocation > (contexts), wherein the memory management apparatus doesn't keep track > of each allocation individually, but just takes it from a pool of space > that will all be freed at the same time. End of statement, end of > transaction, etc, are good pool lifetimes for Postgres. > > We currently have the worst of both worlds: we pay malloc's overhead, > and we have a *separate* bookkeeping layer on top of malloc that links > allocated blocks together to allow everything to be freed at end-of- > context. We should be able to do this more cheaply than malloc, not > more expensively. > > BTW, I already did something similar in the frontend libpq, and it > was a considerable win for reading large SELECT results. > > regards, tom lane > -- Bruce Momjian | http://www.op.net/~candle maillist@candle.pha.pa.us | (610) 853-3000+ If your life is a hard drive, | 830 Blythe Avenue + Christ can be your backup. | Drexel Hill, Pennsylvania19026