[a-priori]

While the "Metronome" has very predictable behaviour that makes it probably the best GC collector for real-time purposes, it still has a maximum GC load before it gets backed up. If it gets backed up too far... forget about timing guarantees because the system will fail. The "Metronome" collector can guarantee a known and tunable GC capacity over time (in terms of objects collected/sec), which is good. But the flip side is that you need to be able to guarantee that your application will never exceed that capacity, at least not for any sustained period of time.

In order to provide hard real-time guarantees in a garbage collected system, you need to know that there is no situation in which the system produce more garbage faster than the collector can collect. With manual deallocation, you can prove that with static analysis. With garbage collection you have to demonstrate it empirically using dynamic analysis. That requires exhaustive testing to make sure you've covered the worst-case scenario.

[dllthomas]

I don't see why you could not, in principle, prove it statically.

[a-priori]

Maybe there are tools that will do that. My knowledge of the industry is about 5 years out of date, and I was no expert even then. But we had no such solution and, in fact, didn't use dynamic memory allocation at all nevermind newfangled gizmos like garbage collection.

In principle, yes I think it's possible... at least, I don't think it reduces to the halting problem. But it would be tricky. It would be relatively simple to reason statically about the rate of memory allocation (iterate through all paths leading to a 'new' operator), but for this purpose you care about cases where an object becomes garbage and can be deallocated. That occurs when the last reference to the object is overwritten or goes out of scope, which is not so easy to determine in the presence of aliasing.

[dllthomas]

In principle it reduces to the halting problem, but given that the domain we're discussing is real-time systems, you'd better already be dealing with programs that you know will halt (in the sense of producing an answer) in not just a finite amount of time but even below some particular bound! Once you've constrained yourself to those programs, you may well be able to get a general result... but as others have noted, really what we want is results about specific programs, and the halting problem has nothing to say there.

I don't know that there exists tooling to construct these proofs, beyond general proof-constructing support, but I'm not working in hard-realtime environments so I'm sure I'm not aware of everything going on either.

[Dylan16807]

>It would be relatively simple to reason statically about the rate of memory allocation (iterate through all paths leading to a 'new' operator), but for this purpose you care about cases where an object becomes garbage and can be deallocated.

No I don't. All I care about is having enough free memory to make new allocations. I don't care how much garbage there is, I just care that when there's garbage it's being freed fast enough to support my allocations.

[moomin]

Just to state the obvious, in practice over the long term, you've got to be deallocating faster than you're allocating, or something nasty that will at the very least violate your performance constraints will happen.

[Dylan16807]

Right. And my point is that the deallocation vs. allocation ratio is the only metric you really need. How fast garbage is made is completely irrelevant because over the long term it's bounded by the allocation rate. You don't have to solve the hard problem of figuring out how fast garbage can be made, you can solve the much easier problem of bounding allocation. And of course in either scenario you have to show that there are no leaks.

[eru]

> [...] at least, I don't think it reduces to the halting problem [...]

It does. But the halting problem is solvable for specific instances, e.g. if you are writing the programmes.

[hga]

Manual deallocation of a heap???

[a-priori]

Sorry, I don't follow.

[hga]

Are you allocating from and deallocating to a heap?

If so, I've heard that can result in non-optimal results, that would also require dynamic analysis to avoid unacceptable worst cases.

[a-priori]

By 'non-optimal results' do you mean heap fragmentation?

If so then yes that's a major concern with dynamic memory allocation in real-time environments. These systems must be designed to run continuously for years at a time and have limited memory, so any allocator that causes non-zero heap fragmentation is right out.

There are allocators that don't do that. One way is to use a pool allocator which allocates fixed-size blocks. Since all blocks are the same size, fragmentation can't occur.