Re: C is too old? opinions?

Logan Shaw wrote:
Ed Prochak wrote:
Logan Shaw wrote:
Phlip wrote:

Making a garbage collector deterministic would defeat the point of a
garbage collector - trading programming time for run time.

I think what is meant is making the running time of the garbage collector
deterministic. If you could ensure that a garbage collection system
would increase the running time of any arbitrary section of code by no
more than a constant (and known) factor, then you retain the ability
to predict the running time of your code either through theory or through
testing. You could, for example, use every other clock cycle for
garbage collection (to make a gross oversimplification of what the
algorithm would really be like).

Assuming the alternate clock cycle (or a second CPU), the garbage
collector algorithm then would have to deal with pointers changing
while it is running. That makes the process more complex.

A deterministic garbage collector has to be very carefully written. I
haven't seen algorithms for this, but there are a lot of factors to
consider. I'd have to pull out some old text books to see what approach
would work, but merely allocating arbitrary CPU cycles is not going to
solve the problem of making a deterministic GC.

Well, and just to be clear, I wasn't trying to say it was. I was just
saying that if garbage collection overhead can be reduced to a fixed
factor times regular execution time, then that makes real-time
programming with garbage collection basically no more difficult than
without it. The hypothetical garbage collector that runs in every
other clock cycle (or every other instruction, maybe) was just an
illustration to show how easy it would be to work with such a garbage
collector if it did (or could) exist.

Anyway, the point was to illustrate what one possible deterministic
running time for a garbage collector might look like. It may well
be that such a garbage collector is theoretically impossible for all
I know.

They're possible. I've referred to a paper giving one possible way to
do it. Oliver Wong referred to another more modern paper.

With this problem the thing to remember is that allocations are what
matter, not other work. When an allocation occurs the GC must be able
to collect an amount of garbage at least as large as amount of space
that's just been allocated.

One way of doing this is to use a Baker 2-space GC. When some pointers
are allocated then GC performs the same number of moves at the same
time, probably somewhere else in the heap, and if necessary flips.

(I think that explaination is correct but I may be slightly off, its a
while since I looked at this).

.

Relevant Pages

  • Re: C is too old? opinions?
    ... garbage collector - trading programming time for run time. ... to predict the running time of your code either through theory or through ... algorithm would really be like). ... A deterministic garbage collector has to be very carefully written. ...
    (comp.programming)
  • Re: garbage collector and slowdown (guillaume weymeskirch)
    ... To test the python 2.5 garbage collector, ... But I've noticed a near linear slowdown of the execution: ... there have been past threads reporting that ... allocating and freeing increasingly long arrays, ...
    (comp.lang.python)
  • Re: garbage collector and slowdown (guillaume weymeskirch)
    ... The garbage collector seems working well, ... But I've noticed a near linear slowdown of the execution: ... On a related note, there have been past threads reporting that allocating and freeing increasingly long arrays, especially of tuples can take more than linearly increasing time. ...
    (comp.lang.python)
  • Re: Memory leak
    ... but in your test you are allocating a lot of large arrays ... > implicit vmt pointer) and storing them in an array. ... up until a certain memory load. ... This does not happen in applications without a garbage collector ...
    (microsoft.public.dotnet.languages.csharp)