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

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