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.

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"

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.

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

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

David, you state this is a fact. Ok I am willing to accept that as a fact if
you
can provide "real world applications" which use GC's which
get the job done more efficiently that a comparable system without the
GC.
Please David, not just assertions facts. And I don't consider statements
like "proferssor X says so" to be a factual.

Yes I am aware of "academic experiments" where some claim
that GC's are actually good _general_ purpose solutions. But
everytime I've taken the time to dig into this (and I have taken the time)
it turns out that they seem to massage the results based on (what seems to
be)
some pro GC bias.

And after my personal search I have concluded that GC's are based on
a bad principle. Thisis the principle as I have identified it.

"Pospone until you can pospone no longer".

IMO this principle is not a good principle in _general_.

Again I will state that a GC does not solve any _general_ problem.

1. Can you identify the fundamental difference between allocating/freeing
memory
and opening/closing files?

2. Have you also been reading those so called "optimisation hints" for
Java programs that Sun sends around to Java developers?

3. Have you noticed that these "hints" are supposted to help the GC
implementation not make a fool of it's self?

4. Have you noticed that the finalize method in Java in useless in general
because you never know if it will be called?
So if you put any code in it, the code is quite useless, because
maybe it wont be called. (I'm sorry I'm getting to Java specific).

5. Isn't it true that a GC's performance is a function of the number of
active objects in the runtime system?
So adding some new subsystem actually in _general_ decreases
your systems performance (larger memory footprint) _and_ your GC's
performance?
(Assuming the subsystem also uses the GC).

6. Are algorithms to detected circular references? O(n) or event worse?
Last time I checked they where not linear time. I'm certain you
can envision a graph for which it would take some effort on the part of the
GC to determine if a node is freeable.

And sure, I too am able to think up some cases in which this will not be
true.
But in the _general_ case it will, because the GC's performance _is_
a function of the number of objects to be collected. No amount of
prayer is going to change that.

I'm sorry but as far as I am concerned these are facts. Please
supply me with some facts about the merits of these GC's.
I'd also prefer you don't refer me to some researcher who is
obviously biased because he probably spent a few years of his life
researching a lost case.

I prefer you give me results comparing similar systems implemented
with and without GC's.

I have yet to see any "non cosmetic" case where the GC systems wins
in _general_. Many poeple can massage the input of a system
as to show the "merit" of their pet algorithm but it doesn't change the fact
that the _principle_ GC's are based on is a poor one.
If it were not so, GC's would solve general problems (including situations
like opening and closing files.) )Yes those researchers recognize this as
well.)

Isn't it true that good principles are applicable to the general case?
If this is so then GC's just don't pull it.
But maybe you can design a GC based on some better principle?
I certainly would use it if it would prove to work better in general.

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.

Yes, we make mistakes. I make mistakes too. But I am certain that some
of the subsystems I've written are leak free. And I am certain some of them
are not. I just don't know which ones are and which ones are not.

I know you are not trying to say that using GC's will insure that no
programming
error are made. So I'll conclude that with or without GC's we will have
will have errors in our systems.
The challenge/solution is then to design systems which work inspite of the
fact
that we make mistakes.

This leads to _general_ techniques such as using (precondition and
postconditions)
to help us cope with the fact that we are not perfect.

There is a good principle. It works all the time, in any situation
(considering the
context of our discussion.)

Ok, I'll stop now.

Please understand that I have no personal grudge against anyone.

With regards from Maurice.

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

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.

This seems like an effective strategy too me. It also provides a solution
to the 8 byte alignment problem.

With regards from Maurice.

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

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

...

I'll try to find time to find out about these particular garbage collectors.
It's just that I've never seen/heard of one kept it's promises yet.

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.

No. we don't. The "implementation of a concept" is not "the concept".
Poorly implementing any algorithm is hardly a proof.

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?

It works. It simply does not yet meet our standards.
I for one, don't fully appreciate mm in postgresql as yet. But if I were to
understand
it (and this is a matter of time) it would meet at least my standards if I
were
to so choose.

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.

No, you don't have to understand the whole executor.
You would read the documentation on how to write extention functions.
This would tell you how to allocated memory for your purposes.

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

This can however be fixed.

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.

Yes. The MemoryDuration sceem as it's implemented now could have been
better. But that doesn't mean the _concept_ of MemoryDuration is bad
it only means that it is poorly implemented.

I'm certain you know it is logically incorrect to assume that the
implementation of a concept _is_ the concept.

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.

Don't you consider wasted execution time to be overhead David?

As for time, considering the time we currently lavish on the allocator,

almost

anything would be an improvement.

Let's make some of the main resources we are concerned with explicite.
- program execution time
- runtime program memory usage
- time spent programming/debugging etc.

Lets assume that we have 10 developers and 1000 users and that
these users have 5 connection to the database at any given time.
Poor execution time and poor memory management affects 5050 processes
running on different machines.
The time spent programming costs a lot for those 10 developers.

Which resource we want to conserve most depends on situation as usual.

I prefer to make the programmer go through hell so that the users
don't have to go through a similar hell.

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

And the lifetimes are usually short so GC's are not the answer IMO.
Please don't confuse a bad implementation a concept with the concept.

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?

I have experience with collection. And I don't think it's wise for me
to speak about it, sorry.

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.

Come on, we should measure space _and_ time.
This is what the GC is costing us.

Let's consider an object M which has a life time which equals the life time
of
the program. How many times will it be checked for possible collection
before the program ends? Consider we have N objects with
a similar life time as M. Now the GC is considering N*M objects for
collections which won't be collected until the program ends.

This is _wasted_ resources. And the waste is a function of
the number of objects in the system multiplied with the amount of time
the program is running. It is _impossible_ that a GC will use
the same amount of resources as any sane non GC implementation
of a pratical system if we consider both space _and_ time.

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.

Which simply means that instead of wasting more space it wastes more
CPU cycles. Please, don't be fooled by nice talk.

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.

No, but a GC visits allocated objects. These objects
are scattered all over the memory space, so the working set of
the program using the GC increases and as a result the perfomance
decreases. This has allways been this way an probably always will.

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.

They are taken seriosly by whom? I love it when poeple use careful wordings.

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.

Wow, that must take quite some bookkeeping. You mean they actually
have some kind of a table which keeps track of the pointers?
This sound pretty conventional to me.

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.

As I said, I choose not to.

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.

I would suggest measuring practical implementations.
GC's always lose. When they win there are cheating in my experience.
(They don't chart the runtime overhead etc. or some other relevant
resource.)

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.

And it can all be fixed. Remember that the original developers of
our system probably had different goals than we do. Do you know what
our goals are? I don't, I'm simply learning about the system right now.

Anyway, as I've said if you prove me wrong I will be happy, because certain
programming tasks will be simpler. It is just that I've never seen
anyone backup the GC promise with real world facts.

Thanks again, with regards from Maurice.