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              
 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Thu, 28 Jan 1999 12:06:25 +0100
"Ulrich Voss" <voss@vocalweb.de>
new heap manager mmalloc

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, USA
 Everyone is permitted to copy and distribute verbatim copies
 of this license document, but changing it is not allowed.

[This is the first released version of the library GPL.  It is
 numbered 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 


Thu, 28 Jan 1999 08:41:49 -0400 (AST)
The Hermit Hacker <scrappy@hub.org>
Re: [HACKERS] new heap manager mmalloc
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

Thu, 28 Jan 1999 10:50:04 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: [HACKERS] new heap manager mmalloc 
> 
> 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, Pennsylvania 19026

Thu, 28 Jan 1999 12:46:52 -0500 (EST)
Bruce Momjian <maillist@candle.pha.pa.us>
Re: [HACKERS] new heap manager mmalloc
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

Thu, 28 Jan 1999 13:57:32 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: [HACKERS] new heap manager mmalloc 
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) #



Fri, 29 Jan 1999 15:02:26 +0100 (MET)
jwieck@debis.com (Jan Wieck)
Re: [HACKERS] new heap manager mmalloc
>     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, Pennsylvania 19026

Sat, 30 Jan 1999 00:22:35 -0500 (EST)
Bruce Momjian <maillist@candle.pha.pa.us>
Re: [HACKERS] new heap manager mmalloc
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 set aside an amount of memory for exclusive
     use by the resource pool owner.  This can be used by applications to
     guarantee the availability of a minimum amount of memory needed to con���
     tinue operation independent of the memory resources currently available
     from the system-wide memory allocator (malloc(9)).  The pool manager can
     optionally obtain temporary memory by calling the palloc() function
     passed to pool_create(), for extra pool items in case the number of allo���
     cations exceeds the nominal number of pool items managed by a pool re���
     source.  This temporary memory will 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

Sat, 30 Jan 1999 15:08:33 +0000 (GMT)
"Patrick Welche" <prlw1@newn.cam.ac.uk>
Re: [HACKERS] new heap manager mmalloc

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, Pennsylvania 19026

Tue, 6 Jul 1999 21:25:12 -0400 (EDT)
Bruce Momjian <maillist@candle.pha.pa.us>
Re: [HACKERS] new heap manager mmalloc