Re: [HACKERS] Its not my fault. Its SEG's FAULT! - Mailing list pgsql-hackers

>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.
I'm afraid I don't follow this argument.
Different objects have different lifetimes. It is a matter of design to
ensure that
it is known what the lifetime of an object is when it is created.
What you are describing is similar to the problem of lifetime of objects in
a parse tree.
If you don't know/understand the grammar being parsed it is very difficult
do manage
memory correctly. However if you do understand the grammar it's becomes
almost trivial.

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

I'm sorry I don't agree. If the programmer doesn't know what the lifetimes
of the objects creates should be, he probably should first find out. IMO
this is
one the most import parts of understanding a system.

I like to see the backend of a system like postgres as a parser for some
formal language. No, not only the SQL part but all of the system.
The life times of objects within a system also obey certain "grammar rules"
as you have indirectly suggested above. (Sessions containing a list of
transactions,
which contain a list of statements ... etc).
Make these rules explicite and the "when to free an object" problem goes
away.
>
>
>- 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...).
This seems to imply that we need a per row MemoryDuration pool.
>
>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.
This overhead and more is also present in any garbage collector. The
garbage collector wastes CPU cycles figuring out if a memory block
is still referenced as well.
>
>    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.
Did you also measure the lifetime of the objects. I would expect this to be
relatively short (as compared to the lifetime these objects might have with
a garbage collector.)
So I would expect (and this is _my_ experience) that for any but the most
cosmetic
of applications GC's use more memory.
>
>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.
Don't GC's accumulate memory until "garbage collect" time? At
GC time memory pages are revisited which may have been swapped out
ages ago. This isn't good for performance. And much more is accumulated than
in the case where palloc and pfree are used.
>
>
>- 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.
Right, but the GC is constantly "chasing a bug list of pointers" when it
tries to
determine if a memory block is still in use. Sure everybody gives the
list of pointers a different name but it all boils down to the same thing.

I think it was you who suggested a good solution to this problem which would
also guaranteed 8 byte alignment for palloced objects.
Such an implementation would be very efficient indeed. (According to some
sources
(Bjarn Stroustrup C++ book?)).
Also if we pre allocate big chuncks of memory (as you suggested I think) we
can in many cases avoid "chasing a big list of pointers" because the
like time of most objects is likely to me small for many applications.
>
>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).
My reading of the principle of procrastination is:

    Do now what you _must_ do anyway. (Considering priorities of course)
    Postpone until tomorrow all things which you are _certain_ you
    might not have to do at all.

According to me garbage collectors follow a principle as in the following:

    Pospone everything until It can't be posponed anymore.

I don't think this is good reasoning in any context. Because you tend to
make the problem more difficult than it needed to be in the general case.
The GC has to find out that which in general was allready known at somepoint
in time.

Consider the case where all objects have a lifespan similar to the stack
frame
of the functions in which they are used. GC give provably bad perforrmance
in
such cases (which for many applications is the common case).
>
>
>- 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.
Yes and if we use good tools to help we can squash them all.
I recall the MySql guys boasting "No memory errors as reported by
Purify" This confirms what I allready know: "All memory errors can be
detected
can be squashed".

Especially if the programming team disciplines it's self
by consistently using good tools. We are professionals.
We can do that, can't we? In my experience memory errors are a result of
"tired fingers" and  being a newbie.
 >
>  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.
No I don't agree. Have you ever been hired to "fix" large systems using
garbage collectors which refused to perform well (memory hogs)?
Thank God for malloc and free.

Another point is using a GC in languages with pointers. You get the
most terrible bugs because us C and C++ programmers tend to use tricks
(like pointer arithmetic) a times. These (in general) are always
incompatible
(in one way or the other) with the GC implementation.
Combine this with "smart" compilers doing "helpful" optimizations and
you get very very obscure bugs.

>
>
>- 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.
I agree in a sense. This is equal to saying: It costs more to build a system
of
good quality as compared to the same system of less quality.

Obtaining a high measure of "quality" implies "care" has to be taken.
In our context "care" translates to:

- Good design (Using formal techiques where possible)
- proper use of profiling tools
- proper use of memory usage debuggers
- Configuration managment
- etc.

So it is possible to _measure_ how good as system is performing and why.

So having high goals is more dificult than having less exacting goals.
>
>  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.


Yes and there are programming idioms which invalidate the need to do the
above without introducing the overhead of Garbage Collectors.
So such code is only needed if the designed of a system didn't design
a memory management subsystem which properly solved the problem.

On a side note IMO GC's don't solve any _general_ problem at all.
And I'll try to explain why.
Consider a language like Java were there is no equivalent of the
free() function.

Now you create some resource like some window object (which allocates memory
and other system resources).
These languages introduce function like "dispose" (and other such names)
which
are supposed to free the resources used by such objects.

When you open a file you still _must_ close the thing. So you must know
_when_
you are allowed to close it. So you must know the lifetime of the object
before
you can properly use it.

So what is the fundamental difference between opening/closing a file and
mallocing/freeing memory?
If a GC solved a general problem it would also figure out when to close the
file.
Because both memory and files are system resources.

So what implementors do is they pretend that memory is a special resource
as aposed to windows/files/sockets/cryptographic contexts/ etc.

I don't agree with them.
>
>
>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.
>


Ok, I'll try to keep an open mind. I suggest you make a garbage collecting
version
of postgresql and I'll be willing to profile for you -:).
If it can compare performance wise with a "purified" version of postgresql
I'll
be totally for it -:).

With regards from Maurice.

PS: Sorry to disagree.