Garbage collection

[Bartc]

Re: Garbage collection


"Eligiusz Narutowicz" <eligiuszdotnar u@hotmail.comwr ote in message
news:fv24na$cqu $1@registered.m otzarella.org.. .

Flash Gordon <spam@flash-gordon.me.ukwri tes:
>

>jacob navia wrote, On 27/04/08 14:57:

>>George Peter Staplin wrote:
>>>Some people are content with a few false references and thus the
>>>Boehm GC works for them. I hope that their software isn't used for
>>>something involving human lives, and that the allocations retained
>>>aren't large.
>>>>
>>>
>>Incredible. And you will trust your life to the ability of a programmer
>>to avoid bugs in MANUALLY done memory management?
>>>
>>I would prefer GC at any time!

>>
>Actually, I would prefer safety critical software not use *any*
>allocated memory, no recursion, and the maximum call depth and memory
>usage calculated and *proved* to fit in the available memory. I've
>done a significant amount of non-safety critical work with these
>restrictions so for certain classes of application it is entirely
>possible.

>
Why? If you are able to be programming and testing properly your
seemingly random restrictions seem more tailored to a low quality C
programmer than to produce a sensible and reliable program. Mallocing
memory is not dangerous at all when its correctly handled.

Malloc can run out of memory.

Not using malloc can't! So the program can't fail for that reason.

--
Bartc

[santosh]

Re: Garbage collection

Eligiusz Narutowicz wrote:

Flash Gordon <spam@flash-gordon.me.ukwri tes:
>

>jacob navia wrote, On 27/04/08 14:57:

>>George Peter Staplin wrote:
>>>Some people are content with a few false references and thus the
>>>Boehm GC works for them. I hope that their software isn't used for
>>>something involving human lives, and that the allocations retained
>>>aren't large.
>>>>
>>>
>>Incredible. And you will trust your life to the ability of a
>>programmer to avoid bugs in MANUALLY done memory management?
>>>
>>I would prefer GC at any time!

>>
>Actually, I would prefer safety critical software not use *any*
>allocated memory, no recursion, and the maximum call depth and memory
>usage calculated and *proved* to fit in the available memory. I've
>done a significant amount of non-safety critical work with these
>restrictions so for certain classes of application it is entirely
>possible.

>
Why? If you are able to be programming and testing properly your
seemingly random restrictions seem more tailored to a low quality C
programmer than to produce a sensible and reliable program. Mallocing
memory is not dangerous at all when its correctly handled. The same
for recursion. I would suggest more rigour in your design and testing
than silly rules such as you mention.

I think the point that Flash is making is that malloc *can* fail. In a
fault-intolerant environment, you want to keep chances of failures to a
minimum. In a important section of code, what should be done if malloc
returns NULL due to some reason or the other, like say memory
fragmentation? The options open to desktop or general purpose programs
(like calling exit, abort etc.) may not be acceptable at in some
contexts. Recursion *can* be used safely, but again it simply opens up
the program to more chances of failure and consumes excessive resources
in a very likely resource constrained environment.

So I would say that for certain limited types of applications Flash's
recommendations are entirely sensible.

[Eligiusz Narutowicz]

Re: Garbage collection

"Bartc" <bc@freeuk.comw rites:

"Eligiusz Narutowicz" <eligiuszdotnar u@hotmail.comwr ote in message
news:fv24na$cqu $1@registered.m otzarella.org.. .

>Flash Gordon <spam@flash-gordon.me.ukwri tes:
>>

>>jacob navia wrote, On 27/04/08 14:57:
>>>George Peter Staplin wrote:
>>>>Some people are content with a few false references and thus the
>>>>Boehm GC works for them. I hope that their software isn't used for
>>>>something involving human lives, and that the allocations retained
>>>>aren't large.
>>>>>
>>>>
>>>Incredible . And you will trust your life to the ability of a programmer
>>>to avoid bugs in MANUALLY done memory management?
>>>>
>>>I would prefer GC at any time!
>>>
>>Actually, I would prefer safety critical software not use *any*
>>allocated memory, no recursion, and the maximum call depth and memory
>>usage calculated and *proved* to fit in the available memory. I've
>>done a significant amount of non-safety critical work with these
>>restriction s so for certain classes of application it is entirely
>>possible.

>>
>Why? If you are able to be programming and testing properly your
>seemingly random restrictions seem more tailored to a low quality C
>programmer than to produce a sensible and reliable program. Mallocing
>memory is not dangerous at all when its correctly handled.

>
Malloc can run out of memory.
>
Not using malloc can't! So the program can't fail for that reason.

Malloc can also break down when the power goes off too. In a well
designed program on a properly specced piece of HW it does not run out
of memory. So the natural extension of your reply is "do not use malloc
as it may run out of memory". I wonder if C is being for you?

[santosh]

Re: Garbage collection

Bartc wrote:

>
"Eligiusz Narutowicz" <eligiuszdotnar u@hotmail.comwr ote in message
news:fv24na$cqu $1@registered.m otzarella.org.. .

>Flash Gordon <spam@flash-gordon.me.ukwri tes:
>>

>>jacob navia wrote, On 27/04/08 14:57:
>>>George Peter Staplin wrote:
>>>>Some people are content with a few false references and thus the
>>>>Boehm GC works for them. I hope that their software isn't used
>>>>for something involving human lives, and that the allocations
>>>>retained aren't large.
>>>>>
>>>>
>>>Incredible . And you will trust your life to the ability of a
>>>programmer to avoid bugs in MANUALLY done memory management?
>>>>
>>>I would prefer GC at any time!
>>>
>>Actually, I would prefer safety critical software not use *any*
>>allocated memory, no recursion, and the maximum call depth and
>>memory usage calculated and *proved* to fit in the available memory.
>>I've done a significant amount of non-safety critical work with
>>these restrictions so for certain classes of application it is
>>entirely possible.

>>
>Why? If you are able to be programming and testing properly your
>seemingly random restrictions seem more tailored to a low quality C
>programmer than to produce a sensible and reliable program. Mallocing
>memory is not dangerous at all when its correctly handled.

>
Malloc can run out of memory.
>
Not using malloc can't! So the program can't fail for that reason.

In a really safety critical program sufficient memory for maximum
expected usage must be present as part of system design. Otherwise,
instead of malloc failing, we will simply get the even more
unmanageable stack memory exhaustion.

[jacob navia]

Re: Garbage collection

Eligiusz Narutowicz wrote:

In a well
designed program on a properly specced piece of HW it does not run out
of memory. So the natural extension of your reply is "do not use malloc
as it may run out of memory". I wonder if C is being for you?

Of course it may run out of memory if for some reason (BUG) there is
a memory leak.

Of course this never happens to you, Mr Superman. (Unless you run into
Kryptonite)

What people like you fail to understand is that a moderately complex
piece of software can't be tested exhaustively since the exponential
growth of the combinations of input parameters, interrupts, timing
considerations, possible paths through the software etc makes exhaustive
testing impossible.

What can be done is to test each module as far as the budget goes,
test all the modules in simulated real life conditions, etc.

But no amount of testing will make bugs go away, specially in C,
and SPECIALLY using manually garbage collection!!!

In manual GC (malloc/free) each allocation/release becomes a point of
failure. Using a GC, the GC can be the point of failure but when the GC
is certified, all other points of failures disappear.

Obviously you haven't read the abundant literature about software
testing, and apparently you are ignorant of all the problems associated
with manual GC. It is therefore with the usual ARROGANCE of the people
that think that know everything that you dare to ask:

<< I wonder if C is for you >>

as if you were some kind of demigod, that never makes mistakes.

You know nothing about the subject matter guy!


--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique

http://www.cs.virginia.edu/~lcc-win32

[Bartc]

Re: Garbage collection


"Eligiusz Narutowicz" <eligiuszdotnar u@hotmail.comwr ote in message
news:fv26m3$ob8 $3@registered.m otzarella.org.. .

"Bartc" <bc@freeuk.comw rites:
>

>"Eligiusz Narutowicz" <eligiuszdotnar u@hotmail.comwr ote in message
>news:fv24na$cq u$1@registered. motzarella.org. ..

>>Flash Gordon <spam@flash-gordon.me.ukwri tes:
>>>
>>>jacob navia wrote, On 27/04/08 14:57:
>>>>George Peter Staplin wrote:
>>>>>Some people are content with a few false references and thus the
>>>>>Boehm GC works for them. I hope that their software isn't used for
>>>>>somethin g involving human lives, and that the allocations retained
>>>>>aren't large.
>>>>>>
>>>>>
>>>>Incredibl e. And you will trust your life to the ability of a
>>>>programme r
>>>>to avoid bugs in MANUALLY done memory management?
>>>>>
>>>>I would prefer GC at any time!
>>>>
>>>Actually, I would prefer safety critical software not use *any*
>>>allocated memory, no recursion, and the maximum call depth and memory
>>>usage calculated and *proved* to fit in the available memory. I've
>>>done a significant amount of non-safety critical work with these
>>>restrictio ns so for certain classes of application it is entirely
>>>possible.
>>>
>>Why? If you are able to be programming and testing properly your
>>seemingly random restrictions seem more tailored to a low quality C
>>programmer than to produce a sensible and reliable program. Mallocing
>>memory is not dangerous at all when its correctly handled.

>>
>Malloc can run out of memory.
>>
>Not using malloc can't! So the program can't fail for that reason.

>
Malloc can also break down when the power goes off too. In a well
designed program on a properly specced piece of HW it does not run out
of memory. So the natural extension of your reply is "do not use malloc
as it may run out of memory". I wonder if C is being for you?

What difference will changing language make? If dynamic memory is being used
in a complex way then it is conceivable that memory can become full whatever
the language. At least in C there is some choice.

Imagine a graph showing heap memory usage from 0% to 100% over runtime.
There will be peaks and troughs. Some peaks can be near 100%. But can you
prove that it will not hit 100%? Ever? On any combination of programs that
might be sharing the memory?

If you take dynamic memory out of the equation (or get the dynamic
allocations out of the way right at the start, in a proven setup) then you
forcing other techniques to be used so that you can avoid that problem.

Malloc can also break down when the power goes off too.

Where it's important, then there are ways of taking care of that.

--
Bartc

[santosh]

Re: Garbage collection

jacob navia wrote:

<snip>

In manual GC (malloc/free) each allocation/release becomes a point of
failure. Using a GC, the GC can be the point of failure but when the
GC is certified, all other points of failures disappear.

<snip>

What exactly do you mean by a "failure" in a GC? Is failing to collect
storage for which all references have been lost a failure? If this is
so, and in due course the program fails to run because of an
out-of-memory situation due to the GC failing to collect blocks that it
should have, would you still say that such software can be reliably
used in safety or performance critical contexts?

Also how exactly do you propose to certify a GC? Just because it works
for some set of programs doesn't mean that it will work for all
possible programs.

[Flash Gordon]

Re: Garbage collection

santosh wrote, On 27/04/08 16:37:

Eligiusz Narutowicz wrote:
>

>Flash Gordon <spam@flash-gordon.me.ukwri tes:
>>

>>jacob navia wrote, On 27/04/08 14:57:
>>>George Peter Staplin wrote:
>>>>Some people are content with a few false references and thus the
>>>>Boehm GC works for them. I hope that their software isn't used for
>>>>something involving human lives, and that the allocations retained
>>>>aren't large.
>>>>>
>>>Incredible . And you will trust your life to the ability of a
>>>programmer to avoid bugs in MANUALLY done memory management?
>>>>
>>>I would prefer GC at any time!
>>Actually, I would prefer safety critical software not use *any*
>>allocated memory, no recursion, and the maximum call depth and memory
>>usage calculated and *proved* to fit in the available memory. I've
>>done a significant amount of non-safety critical work with these
>>restriction s so for certain classes of application it is entirely
>>possible.

>Why? If you are able to be programming and testing properly your
>seemingly random restrictions seem more tailored to a low quality C
>programmer than to produce a sensible and reliable program. Mallocing
>memory is not dangerous at all when its correctly handled. The same
>for recursion. I would suggest more rigour in your design and testing
>than silly rules such as you mention.

>
I think the point that Flash is making is that malloc *can* fail. In a
fault-intolerant environment, you want to keep chances of failures to a
minimum.

You also need to be able to prove with a certain degree of rigour (which
varies depending on how safety critical the SW is and what else there is
to prevent injury or loss of life).

In a important section of code, what should be done if malloc
returns NULL due to some reason or the other, like say memory
fragmentation?

Or simply a bug in the malloc/free implementation. So you would have to
either get the library provider to get their library tested to the
relevant standards (such testing is expensive, even more so if it was
not designed to meet those standards in the first place) or you have to
take responsibility for it and prove the library.

The options open to desktop or general purpose programs
(like calling exit, abort etc.) may not be acceptable at in some
contexts.

Indeed. How do you fancy being in (or under) a military jet flying at
night 30 feet above the ground when the pilots night vision system
decides to reboot? You could be dead in under a second.

Recursion *can* be used safely, but again it simply opens up
the program to more chances of failure and consumes excessive resources
in a very likely resource constrained environment.

Even if it is not tightly constrained (where I worked there was a
standard requirement of 50% free resources to allow for future
enhancements) it still makes it harder to *prove* that it is safe.

So I would say that for certain limited types of applications Flash's
recommendations are entirely sensible.

There are a lot of applications where it makes sense, and a lot more
where it doesn't make sense. Safety critical (and it was someone else
who mentioned "life depending on it") would be at the top of my list of
things where it makes sense.

I would be interested to here what the MISRA standard said about
allocated memory and recursion, I suspect it might be forbidden or at
least highly constrained there too.

Oh, and when I worked in the defence industry we had these restrictions.
For the type of applications I worked on it was not a problem and even
without the restrictions there was only one application in 15 years
where I might have considered using malloc, and I can't think of any
where recursion would have been appropriate.

For "normal" applications (like those I work on now) I will happily use
malloc/realloc/free, I might consider garbage collection if it was part
of the standard, and I think nothing of mutually recursive functions (we
have very good reason for a() calls b() calls c() calls a() and even
more complex things).
--
Flash Gordon

[jacob navia]

Re: Garbage collection

santosh wrote:

jacob navia wrote:
>
<snip>
>

>In manual GC (malloc/free) each allocation/release becomes a point of
>failure. Using a GC, the GC can be the point of failure but when the
>GC is certified, all other points of failures disappear.

>
<snip>
>
What exactly do you mean by a "failure" in a GC?

1) Failing to collect an unused block
2) Failure to realize that a released block was actually in use
3) Failure to compact memory

Is failing to collect
storage for which all references have been lost a failure?

Yes.

If this is
so, and in due course the program fails to run because of an
out-of-memory situation due to the GC failing to collect blocks that it
should have, would you still say that such software can be reliably
used in safety or performance critical contexts?
>

Of course not. And I am not proposing that a conservative GC
that is OK for desktop applications be used in an airplane software.

But a GC can be built into the compiler, or programmed specifically
for the application, etc.

Also how exactly do you propose to certify a GC?

As all other certifications process for complex software go.

Just because it works
for some set of programs doesn't mean that it will work for all
possible programs.
>

Exactly. It is very difficult!


--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique

http://www.cs.virginia.edu/~lcc-win32

[Hallvard B Furuseth]

Re: Garbage collection

George Peter Staplin wrote:

>Hallvard B Furuseth wrote:

>Sure it could. p might have representation 0x6f726c64, which is the
>same as the ASCII representation of "orld", from the program's output
>text "Hello, world!". Very often that's OK. Sometimes it's not.
>(...)

>
That's how C works with a conservative GC, such as the Boehm GC. With
an accurate GC there are no such limitations. (...) Unfortunately
making an accurate GC for C would require compiler support, and even
then it would break in some cases due to the design of C.

True, I should have mentioned that I was talking about GC in C (or a
normal C implementation anyway), which doesn't store enough type
information for the collector to know what is a pointer and what isn't.

--
Hallvard

[CBFalconer]

Re: Garbage collection

jacob navia wrote:

George Peter Staplin wrote:
>

>Some people are content with a few false references and thus the
>Boehm GC works for them. I hope that their software isn't used
>for something involving human lives, and that the allocations
>retained aren't large.

>
Incredible. And you will trust your life to the ability of a
programmer to avoid bugs in MANUALLY done memory management?

Definitely yes. I pay attention to these things, and have produced
lots of software, embedded and otherwise, that accurately handles
memory with malloc and equivalents. I know what is happening. And
the lives of others depended on that software.

I prefer to trust my own judgment than that of some unknown.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.


** Posted from http://www.teranews.com **

[Eligiusz Narutowicz]

Re: Garbage collection

jacob navia <jacob@nospam.c omwrites:

Eligiusz Narutowicz wrote:

>In a well
>designed program on a properly specced piece of HW it does not run out
>of memory. So the natural extension of your reply is "do not use malloc
>as it may run out of memory". I wonder if C is being for you?

>
Of course it may run out of memory if for some reason (BUG) there is
a memory leak.

Yes - this is true of all programs in all languages.

>
Of course this never happens to you, Mr Superman. (Unless you run into
Kryptonite)

I'm not sure what you are being aggressive for. I am just saying that a
well tested and debugged program does not lose memory - do yours?
Certainly using GC to cover sloppy programming is no remedy I think.

>
What people like you fail to understand is that a moderately complex
piece of software can't be tested exhaustively since the exponential
growth of the combinations of input parameters, interrupts, timing
considerations, possible paths through the software etc makes exhaustive
testing impossible.

What can be tested and checked is a well marshalled malloc/free
access. God knows I have worked on enough C progrms which are large and
do not leak memory. Have I made bugs? Of course.

>
What can be done is to test each module as far as the budget goes,
test all the modules in simulated real life conditions, etc.
>
But no amount of testing will make bugs go away, specially in C,
and SPECIALLY using manually garbage collection!!!

I think - sorry, I know, you are wrong. You are basically saying you
can not make a bug free program using malloc. This is clearly not the
truth.

>
In manual GC (malloc/free) each allocation/release becomes a point of
failure. Using a GC, the GC can be the point of failure but when the
GC
is certified, all other points of failures disappear.
>
Obviously you haven't read the abundant literature about software
testing, and apparently you are ignorant of all the problems associated
with manual GC. It is therefore with the usual ARROGANCE of the people
that think that know everything that you dare to ask:
>
<< I wonder if C is for you >>
>
as if you were some kind of demigod, that never makes mistakes.
>
You know nothing about the subject matter guy!

Actually I have been a professional C programmer for approximately 20
years. I am acutely aware of the issues and pitfalls involedv in C
programming.

I think you have misunderstood me.

I am saying this - one does not "not use malloc" because its possible to
use it badly. Do you not drive a car because its possibly to crash it if
you make a mistake?

[Eligiusz Narutowicz]

Re: Garbage collection

CBFalconer <cbfalconer@yah oo.comwrites:

jacob navia wrote:

>George Peter Staplin wrote:
>>

>>Some people are content with a few false references and thus the
>>Boehm GC works for them. I hope that their software isn't used
>>for something involving human lives, and that the allocations
>>retained aren't large.

>>
>Incredible. And you will trust your life to the ability of a
>programmer to avoid bugs in MANUALLY done memory management?

>
Definitely yes. I pay attention to these things, and have produced
lots of software, embedded and otherwise, that accurately handles
memory with malloc and equivalents. I know what is happening. And
the lives of others depended on that software.
>
I prefer to trust my own judgment than that of some unknown.

I too am confused why Jacob thinks it is not possible to use malloc/free
in a proven, tested and bug free manner. it is a surprise to me and I
wonder how all these C programs over the years are still working so well
- including Gnome and the Linux kernel.

Personally I do not like GC - I think it encourages lazy thinking and if
you then go back to a non GC C environment then possibly this lazy
thinkings will be causing bugs.

[santosh]

Re: Garbage collection

CBFalconer wrote:

[ ... ]

I prefer to trust my own judgment than that of some unknown.

Now if everybody said the same...

[santosh]

Re: Garbage collection

Eligiusz Narutowicz wrote:

<snip>

Personally I do not like GC - I think it encourages lazy thinking and
if you then go back to a non GC C environment then possibly this lazy
thinkings will be causing bugs.

I would be interested to hear your views on what you mean by "lazy
thinking" in this context.

Personally I consider it lazy programming (in a manual malloc -free
context) to free some memory but not others. With a GC of course you
don't free anything at all. However a poor GC which fails to pick up
eligible objects may itself be called "lazy" I suppose. :-)

Also (at least in the context of C programming) even if one uses a GC
other resources like file streams, file descriptors, mmap'ed objects
still need to be freed manually. Typically they are much scarcer than
memory too! So it pays (IMHO) to get into the practise of closely
tracking all your program resources early on, if you ever want to be a
good C or C++ programmer.