[xamuel]

>That makes freeing memory O(n) in the number of chunks freed

A GC can't outdo that. For everything the GC frees, it has to do some work to answer the question, "Should I free this or not?" Even if that question can magically be answered with a single CPU instruction, that's still O(n) answers in the number of chunks freed.

[Doradus]

I think you're referring to a mark and sweep collector. Java's garbage collector uses better algorithms. The collector never even looks at objects that are not referenced from the root set, and an allocation operation is nothing but a pointer bump. Even Cheney's algorithm from the early 1970s works this way, and collectors have only improved since then.

[TheLoneWolfling]

Except that the OS zeros memory when it's released...

[Doradus]

The JVM doesn't release the memory to the OS when garbage is collected; only when the heap shrinks. Any zeroing the OS might do is proportional to the size change in the heap, not to the number of objects freed.

[TheLoneWolfling]

Good point.

However, that brings up a related issue - namely that the JVM requires all (or close enough to all) object memory to be initialized. And given that the amount of memory required to be initialized is at minimum linear w.r.t. the number of objects required to be initialized...

Work done is still O(n) minimum w.r.t. the number of objects allocated regardless.

[Doradus]

Well, it's hard to deny that the work done by the program is O(n) (or even Ω(n)) in the number of objects created by the program. That's almost tautological.

The thing that is interesting about the asymptotic complexity of garbage collection, though, is that it gives you a peek into the future of GC overhead as heaps get larger.

Consider a program with some bounded steady-state memory consumption, and a GC that takes O(1) time to free unlimited amounts of memory. In such a system, you can reduce your GC overhead arbitrarily simply by enlarging the heap. A larger heap gives a larger time interval between collections, yet doesn't make the collections any slower. Don't like 6% overhead? Fine. Make the heap 10x larger and you have 0.6% overhead.

This time-space trade-off is always available to the end user of such a system. It's certainly not available with more primitive systems like malloc+free.

[These are my personal opinions, not those of my employer.]

[TheLoneWolfling]

It doesn't matter what the time to free memory is as long as it is O(n) w.r.t. the number of objects (or less), the limiting factor is allocation. As, in steady state (as you are assuming), all memory freed will be reused, and (effectively) all memory used will be written to at least once, and memory used by a group of objects is at least O(n) w.r.t. the number of objects.

So no, I don't see the advantage you say. I see that, in the best case, it's on par with non-GC'd systems, asymptotically speaking.

And yet, I see plenty of disadvantages. To start:

I have yet to see a GC that's O(1) w.r.t. the amount of memory to free. Best case? I'll grant you that, for an extremely naive copying collector. But the chance of that best case occurring is... not significant. Especially with the more sophisticated algorithms.

And again, as above, it doesn't matter how long it takes to free memory. As long as it's linear or sublinear, it'll be dominated, asymptotically speaking, by how long it takes to initialize that memory again. And in steady-state operation it will be reinitialized.

Not to mention the practical effects.

For instance: GC thrashes cache. Badly. It completely kills the concept of a working set. You can't work around that by making your heap larger - if anything it makes it worse. It makes the time period between thrashings longer, yes, but makes them worse when it does happen.

GC also doesn't scale well to large numbers of cores. In particular, your worst case "always" will be when the GC has to check with every core to see if it still has a reference to something. And given that processor numbers are where most of the performance improvements seem to be coming in... You mentioned memory size improvements but didn't mention increasing numbers of cores.

GC also (almost always) has field(s) per object. Minimum of O(1) overhead per object initialized.

Which means that, generally speaking, the overhead doesn't asymptote to zero. It asymptotes to a constant - and non-negligible, at least from what I've seen - amount of overhead.

[xamuel]

>and a GC that takes O(1) time to free unlimited amounts of memory

If the unlimited amounts of memory are all in one contiguous block and ALL of them are ready to be free'd (and determining that all of them are ready, takes O(1) time somehow) then what you say is plausible.

In any other case it's fantasy. Suppose I have n variables and I point each of them at a distinct new object (not pointed to from anywhere else). Then I re-set a random subset of them to null. Based on which ones I randomly set to null, there's 2^n possibilities for what the GC must do. If your claimed GC O(1) is long enough for the processor to take k conditional jumps, there are at most 2^k possible results of running it. For n>k, there are necessarily subsets in the above scenario which your GC fails to handle.

>This time-space trade-off is always available to the end user of such a system

People routinely run servers on virtual machines with very limited RAM.