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

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

I agreed with Maurice.
Using GC instead of MemoryDuration everywhere isn't good idea for
database server.

But we could implement additional GC-like allocation mode and use it
where is appropriate!

One example - using float8 (etc) in WHERE. We could switch to GC-allocation
in the beginnig of ExecQual () and destroy all allocations made in GC-mode
before return().

Another example - psort.c! With -S 8192 I see that server uses ~ 30M
of memory - due to malloc/palloc overhead in palloc() for each tuple.
No one of these allocations will be freed untill psort_end() <-
good place for GC-destroyer.

Comments ?

Vadim

Vadim:
> I agreed with Maurice.
> Using GC instead of MemoryDuration everywhere isn't good idea for
> database server.

Why? Please state your reasons for this claim.

> But we could implement additional GC-like allocation mode and use it
> where is appropriate!

This assumes that there is a "where it is not appropriate". My contention
is that it is generally appropriate. So my question must be, where is it
not appropriate and why?

> One example - using float8 (etc) in WHERE. We could switch to GC-allocation
> in the beginnig of ExecQual () and destroy all allocations made in GC-mode
> before return().
>
> Another example - psort.c! With -S 8192 I see that server uses ~ 30M
> of memory - due to malloc/palloc overhead in palloc() for each tuple.
> No one of these allocations will be freed untill psort_end() <-
> good place for GC-destroyer.

The examples you give are certainly places where a GC would be very very
useful.  But, I think restricting the GC to cover only some allocations
would lose most of the benifit of using a GC altogether.

First, the entire heap and stack have to be scanned as part of the root
set in either case. However your proposal only lets the collector free
some of the garbage identified in that scan. This has the effect of making
the cost of each bit of reclaimed storage higher than it would be in the
general case. That is, the cost of a collection remains the same, but less
storage would be freed by each collection.

Second, one of the reasons a GC can be faster that explicit allocation /
deallocation is that it frees the rest of the system from doing bookeeping
work. A half-and-half system does not get this benifit.

PostgreSQL is I think an especially good candidate to use a GC as the overall
complexity of the system makes it very hard to determine the real lifetime of
any particular allocation. This is why we have the complex MemoryDuration
system that we currently have. This is also why we have the leaks and vast
storage requirements that we have.

Finally, my main reason for suggesting GC is stabilty and correctness. With
an effective GC, many many bugs simply never get the chance to exist at all.

A GC would likewise make the business of writing loadable functions for new
types etc much simpler and less error prone.

Did you have a chance to review the links I sent in the earlier posting?
Some of the papers referenced there are quite interesting, particularly
the Zorn papers on the real cost of explicit storage allocation.

-dg


David Gould            dg@illustra.com           510.628.3783 or 510.305.9468
Informix Software  (No, really)         300 Lakeside Drive  Oakland, CA 94612
If simplicity worked, the world would be overrun with insects.

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

This is exactly the problem memoryduration is meant to solve. It trys to
guarantee that everything will be freed when it is no longer needed. It does
this by keeping a list of all allocations and then freeing them when the
duration ends. However we have existance proofs (by the truckload) that
this does not solve the problem.


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

Perhaps. Why then does it not work?


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

To write extention function to make some application domain calculation
and return a (allocated) double, I now have to understand the whole
executor? I hope not.

In any case, there is no mechanism in the current code to allow a function
author to control this accurately.

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

This is again exactly what MemoryDuration is intended to do. My argument is
that it a) doesn't work, b) wastes memory, c) is slow.


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

Why should this overhead be part of a collector? As nearly as I can tell from
a quick skim of the Boehm collector code, allocated objects have ZERO space
overhead.

As for time, considering the time we currently lavish on the allocator, almost
anything would be an improvement.


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

I did not measure lifetimes. It would take full tracing to really understand
the behavior in detail and I simply have not done it. However the common
uncontrolled growth case we see is that the objects may have short lifetimes
but they are not freed until end of statement so the server just gets bigger
and bigger and bigger...


> So I would expect (and this is _my_ experience) that for any but the most
> cosmetic of applications GC's use more memory.

I am interested. What experience have you had with collection? Also, what
applications have you seen use more memory collected than they would have
otherwise?

In any case, the usual number is that a collected system will have a virtual
size somewhere from the same to 50% larger than an explicitly allocated
system. The higher number tends to be found with copying collectors as they
need both the "from" and "to" spaces. Boehm is not a copying collector. Even
so, I expect it will make us use more memory that the theoretical optimum.
But I also expect it to be better then the current implementation.


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

No. There is no requirement for this. The Boehm collector has incremental
collection.


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

It is pretty fatal to database systems with more than one active thread/process
to page at all. Think about what happens when someone holding a spinlock
gets paged out, it is not pretty. Fortunately there is no requirement with
a modern collector to wait until pages are swapped out.


> I think it was you who suggested a good solution to this problem which would
> also guaranteed 8 byte alignment for palloced objects.
...
> 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.

This was my initial thought. I expect a good improvement could be made on
the current system. I think collection would serve us even better.


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

There are papers (by I believe Appel) that show that collection can be
faster than stack allocation. I admit to being surprised by this, and have
not yet read the papers, but they are taken seriously, it is not just
smoke and sunshine.


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

As it happens, the Boehm collector can be used as a leak detector too.
In this mode you just use your conventional allocation scheme and run the
collector in "purify" mode. It does its collection scan at each malloc and
then reports all the allocated but unreachable (hence leake) memory.


> I recall the MySql guys boasting "No memory errors as reported by

I suspect they are exagerating. On Solaris, the resolver libc routines
leak so anything linked with libc leaks (just a little).

> Purify" This confirms what I allready know: "All memory errors can be
> detected
> can be squashed".

I believe that the Space Shuttle onboard code is leak free... maybe.


> Especially if the programming team disciplines it's self
> by consistently using good tools.

Exactly why I am proposing this. The Boehm collector is a good tool. It
eliminates a large class of errors. They just "cease to be".

> We are professionals.

We are volunteers. I don't happen to think chasing leaks is what
I want to do with my free time, I get to do more than enough of that at work.

> We can do that, can't we? In my experience memory errors are a result of
> "tired fingers" and  being a newbie.

Even if this was true, and we can write perfect code, we are working with
postgresql, a great big piece of code written mostly by grad students. Who
are almost guaranteed to be either newbies or to have "tired fingers".


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

Please share your experience here, I am very interested.

While I am taking an advocacy position on this topic, I am sincere about
wanting a discussion and more information. If there is real evidence that
applies to our case that suggest GC is not the right thing to do, we need
to know about it.


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

The Boehm collector is aware of most of this and in practice almost
any ANSI conforming C program can be collected correctly. The only real
restriction is that you can't use 'xor' to store both a prev and next field
in one pointer as it hides the pointer. However, there is not an ANSI
conforming way to do this anyway.... (you can cast (ptr to int), but the
result of casting back after the xor is unspecified).


[code examples deleted]

> Yes and there are programming idioms which invalidate the need to do the
> above without introducing the overhead of Garbage Collectors.

Yes? How can we apply them to postgres? I hate the kind of code I placed
in the example, but it is ubiquitous. If you have a better way (that can
be applied here), please please tell us.

> So such code is only needed if the designed of a system didn't design
> a memory management subsystem which properly solved the problem.

A succinct description of the system we are working on.


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

This is known as "finalization". The Boehm collecter supports it by allowing
you to register a function to be called when an object is collected. I do
not think we need to take advantage of this now though.

> So what is the fundamental difference between opening/closing a file and
> mallocing/freeing memory?

Hmmm, what is the difference between a file and memory? Conceptually nothing.
In practice, real implementations posit a number of differences (size,
persistance etc). Real systems provide different mechanism to access
files vs memory. And, I suspect, most of us find this comforting.


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

There is a point to what you say here and some interesting research is being
done in this area, but what we have in postgreSQL is a big pile of 'C'.

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

A fine plan. I will make sure to ask for your help on the performance
testing. If you have particular test cases to suggest, start collecting
them, otherwise I am going to time a full regression suite run as the
benchmark.

> If it can compare performance wise with a "purified" version of postgresql
> I'll be totally for it -:).

Fair enough.

> With regards from Maurice.
>
> PS: Sorry to disagree.

Someone had to ;-)

-dg

David Gould            dg@illustra.com           510.628.3783 or 510.305.9468
Informix Software  (No, really)         300 Lakeside Drive  Oakland, CA 94612
"Of course, someone who knows more about this will correct me if I'm wrong,
 and someone who knows less will correct me if I'm right."
               --David Palmer (palmer@tybalt.caltech.edu)

David Gould wrote:
>
> Vadim:
> > I agreed with Maurice.
> > Using GC instead of MemoryDuration everywhere isn't good idea for
> > database server.
>
> Why? Please state your reasons for this claim.
>
> > But we could implement additional GC-like allocation mode and use it
> > where is appropriate!
>
> This assumes that there is a "where it is not appropriate". My contention
> is that it is generally appropriate. So my question must be, where is it
> not appropriate and why?

Where would you put call to collector in Executor ?

> The examples you give are certainly places where a GC would be very very
> useful.  But, I think restricting the GC to cover only some allocations
> would lose most of the benifit of using a GC altogether.
>
> First, the entire heap and stack have to be scanned as part of the root
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> set in either case. However your proposal only lets the collector free
  ^^^^^^^^^^^^^^^^^^
> some of the garbage identified in that scan. This has the effect of making
> the cost of each bit of reclaimed storage higher than it would be in the
> general case. That is, the cost of a collection remains the same, but less
> storage would be freed by each collection.

No! In GC-like allocation mode I meant to use malloc to allocate
memory in big chunks (> 8K) and use Last_Allocated_Byte counter for
each chunk in palloc() to "allocate" memory. pfree will do nothing.
GC-destroyer will just free a few chunks - without any scans.
Many GC-storages will be available simultaneously (GC_Storage_Identifier
will be returned by StartGCAllocation() call and used by EndGCAllocation()
to free memory in given storage). GC-allocations will be made in current memory
context (in term of postgres) ==> code using special memory contexts
(relation cache etc) will not be affected at all (switching to another
context will stop GC-allocation untill first context restored)
as well elog(ERROR) clean up feature.

> Second, one of the reasons a GC can be faster that explicit allocation /
> deallocation is that it frees the rest of the system from doing bookeeping
> work. A half-and-half system does not get this benifit.
>
> PostgreSQL is I think an especially good candidate to use a GC as the overall
> complexity of the system makes it very hard to determine the real lifetime of
> any particular allocation. This is why we have the complex MemoryDuration
> system that we currently have. This is also why we have the leaks and vast
> storage requirements that we have.

Sure - it's not so hard to determine lifetime of any allocation.
Please, don't forget that postgres was _academic_ research project
for very long time and so there were no big efforts against leaks etc.

> Did you have a chance to review the links I sent in the earlier posting?
> Some of the papers referenced there are quite interesting, particularly
> the Zorn papers on the real cost of explicit storage allocation.

Sorry - I just started and will continue...

Vadim

David Gould wrote:
>
> > 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.
>
> Perhaps. Why then does it not work?

There was no proper attention to this issue!

> > 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.
>
> To write extention function to make some application domain calculation
> and return a (allocated) double, I now have to understand the whole
> executor? I hope not.
>
> In any case, there is no mechanism in the current code to allow a function
> author to control this accurately.

And he shouldn't care! He have to make allocation in current context
and let us take care about anything else.

> > >    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.)
>
> I did not measure lifetimes. It would take full tracing to really understand
> the behavior in detail and I simply have not done it. However the common
> uncontrolled growth case we see is that the objects may have short lifetimes
> but they are not freed until end of statement so the server just gets bigger
           ^^^^^^^^^^^^^
So we have to fix this!

> > >    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
>
> No. There is no requirement for this. The Boehm collector has incremental
> collection.

This is interest - I see I have to read more...

Vadim