 
> Maurice:
> Sorry to bring bad news but it seems that the postgresql daemon is leaking
> memory when building indices.
> (When using electric fence it takes long enough to notice -:))
> 
> Anybody want to recommend a good freeware tool which helps to find memory
> leaks?
 
 
 
> Bruce:
> Yea, as I reported earlier, it is probably all from the same place.  I
> used a pginterface C file do show it.  I think we need Purify.
 
 

> Vadim:
> Chris Albertson wrote:
> > 
> > This is just one example.  ++Every time++ I do a SELECT where
> > the expected result is a large number of rows I get a
> > failure of some type.
> > 
> > testdb=> select count(*) from tassm16
> > testdb-> where 15.5 < b_mag::float4 - (0.375 * (b_mag -
> >          r_mag)::float4);
> > FATAL 1:  palloc failure: memory exhausted
> > testdb=>
> > 
> > I can make Postgresql 6.3 fail every time.  Just do a SELECT
> > where the number of rows returned is > a few million.  The
> 
> 0.375 above is float8 and so server uses two float8 funcs to
> calculate right op of '<' ==> 2 * palloc(8) for each row.
> palloc(8) eats more than 8 bytes of memmory (~ 24): 2 * 24 = 48,
> 48 * 1_million_of_rows = 48 Mb.
> 
> This is problem of all data types passed by ref !!!
> And this is old problem.
 

I have been doing some thought about memory allocation in postgresql
so the above messages are very timely (at least to me).

I would like to discuss the idea of replacing the current scheme of
explicit memory allocation and and deallocation from separate
"MemoryDuration" pools with a conservative garbage collector.

For more information about garbage collection in general and about the
specific collector I am proposing see these urls:

  GC FAQ and links
	http://www.iecc.com/gclist/GC-faq.html

  Boehm-Weiser Collector
	http://reality.sgi.com/employees/boehm_mti/gc.html

Rationale:

>From my experience, I think that this is a stone cold win for postgresql. I
have of course, no before and afternumbers (yet) to back this up, but the
following are I think true:

- MemoryDuration is really "poor mans garbage collection" anyway. The idea
  being that it is either a) hard, or b) impossible to arrange to free your
  memory at the right time. Some objects need to last for a session, some
  for a transaction, some for a statement, some for a function, and some
  for other indeterminate durations. The duration mechanism is meant to
  help free things at the right time. Arguably it almost but not quite
  works.

- MemoryDuration adds complexity to the code. A quick skim of the code base
  will show that duration gets switched all over the place often for not
  very obvious reasons. An example is a function allocateing working memory
  (per function duration) and returning an allocated result (per statement
  duration). This makes writing both server code and extension code much
  harder than need be.


- MemoryDuration is very costly in terms of space:

a)  A function returning an allocated object returns memory that cannot be
    freed until the end of the statement. But as observed, often this memory
    is really needed only "per row". When millions of rows are involved, this
    gets pretty piggy (they just don't make swap partitions big enough...).

b)  Each chunk of allocated memory has overhead of 8 to 16 bytes of
    bookkeeping overhead to link it to the MemoryContext structure that
    controls the duration. This is in addition to whatever overhead (often
    8 bytes) imposed by the underlying malloc() for boundary tags or size
    and arena information. Each allocation then has 16 to 24 bytes of
    overhead.

    The statistics I have seen for a derivative of postgres say that 86% of
    all allocations are 64 bytes or less. 75% are 32 bytes or less, and 43%
    are less than 16 bytes. This suggests that allocator overhead about
    doubles the storage needed.

c)  But it is really quite a lot worse than this. As noted above, memory
    is not freed for reuse in a timely way but accumulated until the end
    of the memory duration (ie statement or transaction). This is the
    usual reason for running out of memory in a large query. Additionaly,
    the division of memory into separate pools creates extra fragmentation
    which can only make matters even worse.


- MemoryDuration is very costly in terms of speed:

a)  Some profiling (with Quantify) I have done on a derivative of postgres
    show that for even simple queries return only one row like
       "select * from table where key = <unique_value>;"
    spend about 25% to 30% of their total execution time in malloc(), free(),
    or one of the MemoryContext routines. This probably understates the case
    since it is based on instruction counting, not actual time and the
    "chase a big list of pointers" operation in MemoryContextDestroy() is
    almost guaranteed to have nasty cache behavior.

b)  There is quite a bit of bookeeping code all over the system (to support
    releaseing memory after an error etc). This is in heavily trafficced
    paths. Since is so widely distributed it is very hard to measure the
    slowdown, but there certainly is some. This could all be removed if we
    had garbage collection (although this in itself would be a big job).


- MemoryDuration is very costly in terms of correctness and stability:

  I am not going to say much here except to point out the number of
  freed pointer errors and memory leaks that have been found in the code
  to date. And that there are new ones in every release. And that I have
  spent a good part of the last three years chasing leaks out of a
  similar system, and no, I am not done yet.

  The very existance of companies and products like Purify should be a
  tipoff. There is no practical way to write large C programs with
  dynamic storage without significant storage management problems.


- MemoryDuration is very costly in terms of development cost:

  First, there are huge testing and debugging costs associated with
  manual storage management. This is basically all waste motion and a
  royal pain.

  Even more importantly, code written knowing that there is garbage
  collection tends to have about substantially fewer source statements.
  A typical case is a routine that allocates several things and operates
  on them and checks for failures:

/* non garbage collected example
*/
dothing(...)
{
    if ((p1 = malloc(...)) == NULL)
        return ERR;
    ...
    if ((p2 = malloc(...)) == NULL) {
        free(p1);
        return ERR;
    }
    ...
    if ((p3 = malloc(...)) == NULL) {
        free(p2);
        free(p1);
        return ERR;
    }
    ...
    if ((p4 = malloc(...)) == NULL) {
        free(p3);
        free(p2);
        free(p1);
        return ERR;
    }
    if ((info = do_the_wild_thing(p1, p2,p3, p4)) == ERR) {
        free(p4)
        free(p3);
        free(p2);
        free(p1);
        return ERR;
    }
    ...
    free(info)
    free(p4)
    free(p3);
    free(p2);
    free(p1);
    return OK;
}



/* same example only this time with garbage collection
 */
dothing(...)
{
    if ((p1 = malloc(...)) == NULL)
        return ERR;
    ...
    if ((p2 = malloc(...)) == NULL)
        return ERR;
    ...
    if ((p3 = malloc(...)) == NULL)
        return ERR;
    ...
    if ((p4 = malloc(...)) == NULL)
        return ERR;
    ...
    if ((info = do_the_wild_thing(p1, p2,p3, p4)) == ERR) 
        return ERR;
    ...
    return OK;
}


I know which one I would rather write! And it is fairly obvious which one
is more likely to work.


This is probably to long for one post, so I will stop now.

I would very much like comments and suggestions on this topic, especially if
this is something you have thought about or have experience with.

Unsupported assertions to the effect "GC is too slow ... only works with
lisp ..." etc are ok too, but will be eligible to win valuable prizes.

-dg

David Gould            dg@illustra.com           510.628.3783 or 510.305.9468 
Informix Software  (No, really)         300 Lakeside Drive  Oakland, CA 94612
"A week of coding can sometimes save an hour of thought."

Thu, 2 Apr 1998 00:44:48 -0800 (PST)
dg@illustra.com (David Gould)
Its not my fault. Its SEG's FAULT!
dg@illustra.com (David Gould) writes:

> I would like to discuss the idea of replacing the current scheme of
> explicit memory allocation and and deallocation from separate
> "MemoryDuration" pools with a conservative garbage collector.

Yes!  This is a great idea!  [scrambles, grinning, to finally get to
work on porting the Boehm-Weiser collector properly to NetBSD/* 1.3]

It seems, from recent discussion, reasonable to assume that this will
kill a number of bugs, reduce the memory footprint of the backend and
quite possibly even (judging by the profiling data you quote) give a
welcome performance boost.  Will you be doing some trial runs with
Boehm-Weiser simply linked in as a malloc/free replacement?  Is it a
big project to actually rip out the MemoryDuration allocator's guts to
get rid of some of that overhead?

> I know which one I would rather write! And it is fairly obvious
> which one is more likely to work.

Of course, this one [he said, grinning]:

(define (do-thing)
  (with-handler my-handler
                (do-the-wild-thing)))

> Unsupported assertions to the effect "GC is too slow ... only works
> with lisp ..." etc are ok too, but will be eligible to win valuable
> prizes.

...like a guide to documents on the net debunking these and other
favorite misconceptions about garbage collection?  You're hardly
likely to get too many of those assertions, though: by now, I would
assume that it's gotten through to most programmers that the handling
of memory in a large system can be done more reliably _and_ more
efficiently by a good garbage collector than by a C programmer.  The
fact that the Java designers got this right (no surprise, of course,
with Steele at the core), should by itself have convinced many.

Off-topic: as for Java, we now just have to wait for the byte-code
engine and entire run-time support system to be rewritten in Java, so
that we can get a stable deployment platform for Java on the web that
won't crash the user's browser every other time she loads an applet!

-tih
-- 
Popularity is the hallmark of mediocrity.  --Niles Crane, "Frasier"

02 Apr 1998 20:01:30 +0200
Tom Ivar Helbekkmo <tih@Hamartun.Priv.NO>
Re: [HACKERS] Its not my fault. Its SEG's FAULT!
Tom Ivar Helbekkmo writes: 
> dg@illustra.com (David Gould) writes:
> 
> > I would like to discuss the idea of replacing the current scheme of
> > explicit memory allocation and and deallocation from separate
> > "MemoryDuration" pools with a conservative garbage collector.
> 
> Yes!  This is a great idea!  [scrambles, grinning, to finally get to
> work on porting the Boehm-Weiser collector properly to NetBSD/* 1.3]

This is exactly the kind of thoughtful response I was looking for ;-)

> It seems, from recent discussion, reasonable to assume that this will
> kill a number of bugs, reduce the memory footprint of the backend and
> quite possibly even (judging by the profiling data you quote) give a
> welcome performance boost.  Will you be doing some trial runs with
> Boehm-Weiser simply linked in as a malloc/free replacement?  Is it a
> big project to actually rip out the MemoryDuration allocator's guts to
> get rid of some of that overhead?

Not too big, just redefine palloc and make the Context calls into no-ops.
A bit more trouble to track down all the 'malloc()' calls that shouldn't
have ever been there (but there are quite a few).

> Of course, this one [he said, grinning]:
> 
> (define (do-thing)
>   (with-handler my-handler
>                 (do-the-wild-thing)))

Sure, but right now we have some few hundred thousand lines of C...
 
> > Unsupported assertions to the effect "GC is too slow ... only works
> > with lisp ..." etc are ok too, but will be eligible to win valuable
> > prizes.
> 
> ...like a guide to documents on the net debunking these and other
> favorite misconceptions about garbage collection?  You're hardly

I had meant to say "not be eligible" but I like your idea better. Both
urls I posted have a bunch of very fine links to a lot of really good
information.

> likely to get too many of those assertions, though: by now, I would
> assume that it's gotten through to most programmers that the handling
> of memory in a large system can be done more reliably _and_ more
> efficiently by a good garbage collector than by a C programmer.  The

It is surprising, but this simple fact has not yet penetrated into
popular thought. I have seen large organizations full of very bright
people spend hundreds of man years chasing leaks without ever wondering
if there might be an alternative.

For some reason people cling to the belief that if they were just careful
enough and only let really good programmers touch the code and carried
a lucky rabbits foot that somehow they could write leak free software.

All this in the face of the observation that no-one ever actually _writes_
leak free software. Personally, I don't know anyone who can write leak
free software of any size, certainly not in a finite time.

-dg
> 
David Gould            dg@illustra.com           510.628.3783 or 510.305.9468 
Informix Software  (No, really)         300 Lakeside Drive  Oakland, CA 94612
"A week of coding can sometimes save an hour of thought."

Thu, 2 Apr 1998 23:25:16 -0800 (PST)
dg@illustra.com (David Gould)
Re: [HACKERS] Its not my fault. Its SEG's FAULT!