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.
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.
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.]
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.
I'm not saying a fast GC can reduce the cost of allocation. I'm saying a fast GC can reduce GC overhead. I think that's an uncontroversial statement. I can only insist so many times that Java's GC doesn't touch dead objects at any time during its scan. If you want to disagree with me, that is your prerogative.
I agree that a GC walk can thrash cache when it happens. However, a copying GC can also rearrange object layout to improve locality. Which effect is more significant depends on the workload.
I didn't mention the number of cores because it didn't occur to me that it was significant to you. GCs can scale just fine to many cores. No core has to "check" other cores: each core can check its own local data, depending on the tactics employed to deal with NUMA. There are always challenges in scaling any parallel workload, of course, and there are always solutions.
Our GC (in IBM's J9 JVM) uses 8 bits in each object. With classes aligned to 256 bytes, there are eight free bits in each object's class pointer. Hence, J9's object model has one word of overhead on top of the user's data, which is what malloc/free typically needs to track each object's size anyway. No disadvantage there.
[These are my personal opinions, not those of my employer.]
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.
I agree that limited RAM environments are important. Asymptotic complexity only matters when you're effectively operating at the asymptote.
http://en.wikipedia.org/wiki/Smart_pointer#C.2B.2B_smart_poi...
My personal experience with similar such systems was that even when performance was not a concern the cost of having to untangle and document my reference structure was well worth the time.
Has any language ever gotten the balance of tradeoffs for finalizers right for strong GC?
Why is that? I would have thought they would work really well together - if an object such as a file stream doesn't escape you could inline and run the finaliser after the last use of the object goes out of scope.
Or do you mean they defeat current implementations of escape analysis?
To make this work, the JIT would need to perform escape analysis on the finalizer too (since the finalizer can make an object escape). If that analysis succeeds, then I suppose the object could be stack-allocated and the finalizer called directly. Even then, though, you would have to think carefully about all the subtle ramifications, like the consequences running a finalizer on an application thread instead of the finalizer thread. (What if the finalizer grabs a lock in an attempt to protect itself from the application code? Now this becomes a recursive lock by one thread, and so both the application code and the finalizer can enter it at the same time!)
If this ever became important enough, it's possible the JIT developers could get this right in every case with enough effort invested. I wouldn't count on that happening any time soon.
[These are my personal opinions, not those of my employer.]
I didn't say synchronization can prevent EA. I said that calling a finalizer on an application thread can defeat the mutual exclusion that would usually be guaranteed by Java's locking. If the app thread holds a monitor when the finalizer is called, that would usually make the finalizer block until the app exits the monitor. If they're on the same thread, that becomes a recursive monitor enter on the same thread, which doesn't block.
Even if you and I solve this particular problem, these are only the problems that occurred to me off the top of my head. With these kinds of subtle, thorny issues lurking around every corner, I wouldn't expect JIT development teams to give this any real attention unless there's some workload where it matters.
[These are my personal opinions, not those of my employer.]
"If (this stuff isn't escaping) then (the JIT can prove that it isn't using a lock)."
That is logically equivalent to:
"If not (the JIT can prove that it isn't using a lock) then not (this stuff isn't escaping)."
Hence, I was explaining that using a lock doesn't count as an escape. But apparently I just misunderstood your meaning?
Wow. Overreact much? :-)
Garbage collection works great for one use case: managing heap memory. Please, let's not return to a universe where you need to free each chunk of memory piecewise. That makes freeing memory O(n) in the number of chunks freed, where modern collectors can free unlimited numbers of objects in O(1) time. Compared to this, malloc and free are a little like keeping score in soccer by tracking every action that does not result in a ball entering a net.
The trouble is finalizers. Finalizers suck. They tie the management of one resource (say native memory or file handles) to an unrelated resource (heap memory). This has the terrible consequences highlighted by this story, plus others. It keeps the native resource tied up until the collector decides to run, for one thing. It also harms performance in secondary ways even when the finalizer isn't running. For example, finalizers typically defeat escape analysis, meaning objects with finalizers can't be stack-allocated.
It's a good idea to use finalizers mostly for detecting invalid final states of objects (like leaking resources), as long as you stay aware that finalizers can slow down your program in unexpected ways.
[These are my personal opinions, not those of my employer.]