Thread

1. Its not my fault. Its SEG's FAULT!

   David Gould <dg@illustra.com> — 1998-04-02T08:44:48Z

    
   > 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."
   
   

2. Re: [HACKERS] Its not my fault. Its SEG's FAULT!

   Tom Ivar Helbekkmo <tih@hamartun.priv.no> — 1998-04-02T18:01:30Z

   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"
   
   

3. Re: [HACKERS] Its not my fault. Its SEG's FAULT!

   David Gould <dg@illustra.com> — 1998-04-03T07:25:16Z

   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."