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