I'm not sure. If you start using smart pointers in C++, you can get the same problem: instead of a GC pause, you get a cascading delete pause. To eliminate it, you have to devise a smarter memory scheme, at which point you probably don't underestimate the determinism cap.

Also don't forget that garbage collectors can often be tuned. Granted, many of them suck, but a generational, incremental collector whose parameters can be tweaked? Much less room for pauses.

A cascading delete pause may be undesirable, but is it nondeterministic?

In the same way that GC is, yes. Technically both are probably fully deterministic, just not readily determinable by casual examination of the code at compile time.

I guess I didn't mean nondeterministic in the philosophical indeterminism sense, but in the sense that different runs might produce different behavior.

http://en.wikipedia.org/wiki/Nondeterministic_algorithm

Well, you can get there if you lag enough to drop a few frames in a competitive FPS game: while the game is still deterministic, the game/players system will diverge: a few dropped frames can get you fragged.

Also, some naive simulations will adapt the length of their steps with the time it takes to compute them. Any performance variation gives you full blown unpredictability.

Even a single delete/free is nondeterministic. How long it takes depends on the state of the heap (true of new/malloc as well).

Very good point. Performance folds in latency (determinism) and throughput. There is usually a trade-off between the two. GC might handle throughput reasonably, latency is a bit tougher. You are sort of left tweaking knobs on a black box hoping to get good results in the end.