77

In Java, as soon as an object no longer has any references, it becomes eligible for deletion, but the JVM decides when the object is actually deleted. To use Objective-C terminology, all Java references are inherently "strong". However, in Objective-C, if an object no longer has any strong references, the object is deleted immediately. Why isn't this the case in Java?

  • 46
    You should not care when Java objects get actually deleted. It is an implementation detail. – Basile Starynkevitch May 8 '18 at 6:10
  • 152
    @BasileStarynkevitch You should absolutely care and challenge how your system/platform works. Asking questions 'how' and 'why' is one of best ways to become better programmer (and, in more general sense, smarter person). – Artur Biesiadowski May 8 '18 at 7:34
  • 6
    What does Objective C do when there are circular references? I assume it just leaks them? – Mehrdad May 8 '18 at 7:34
  • 45
    @ArturBiesiadowksi: No, the Java specification does not tell when an object is deleted (and likewise, for R5RS). You could and probably should develop your Java program as-if that deletion never happens (and for short lived processes like a Java hello world, it indeed does not happen). You may care about the set of living objects (or the memory consumption), which is a different story. – Basile Starynkevitch May 8 '18 at 7:36
  • 28
    One day the novice said to the master "I have a solution to our allocation problem. We will give every allocation a reference count, and when it reaches zero, we can delete the object". The master replied "One day the novice said to the master "I have a solution... – Eric Lippert May 9 '18 at 14:07

11 Answers 11

78

First of all, Java has weak references and another best-effort category called soft references. Weak vs. strong references is a completely separate issue from reference counting vs. garbage collection.

Second, there are patterns in memory usage that can make garbage collection more efficient in time by sacrificing space. For example, newer objects are much more likely to be deleted than older objects. So if you wait a bit between sweeps, you can delete most of the new generation of memory, while moving the few survivors to longer-term storage. That longer term storage can be scanned much less frequently. Immediate deletion via manual memory management or reference counting is much more prone to fragmentation.

It's sort of like the difference between going grocery shopping once per paycheck, and going every day to get just enough food for one day. Your one large trip will take a lot longer than an individual small trip, but overall you end up saving time and probably money.

  • 58
    A programmer's wife sends him to the supermarket. She tells him, "Buy a loaf of bread, and if you see some eggs, grab a dozen." The programmer later returns with a dozen loaves of bread under his arm. – Neil May 8 '18 at 7:10
  • 7
    I suggest mentioning that new generation gc time is generally proportional to amount of live objects, so having more deleted objects means their cost won't be paid at all in many cases. Delete is as simple as flipping survivor space pointer and optionally zeroing entire memory space in one big memset (not sure if it is done at end of gc or amortized during allocation of tlabs or objects themselves in current jvms) – Artur Biesiadowski May 8 '18 at 7:39
  • 62
    @Neil shouldn't that be 13 loaves? – JAD May 8 '18 at 8:18
  • 66
    "Off by one error on aisle 7" – joeytwiddle May 8 '18 at 10:53
  • 13
    @JAD I would have said 13, but most don't tend to get that. ;) – Neil May 8 '18 at 11:39
85

Because properly knowing something is no longer referenced isn't easy. Not even close to easy.

What if you have two objects referencing each other? Do they stay forever? Extending that line of thinking to resolving any arbitrary data structure, and you'll soon see why the JVM or other garbage collectors are forced to employ far more sophisticated methods of determining what's still needed and what can go.

  • 7
    Or you could take a Python approach where you use refcounting as much as possible, resorting to a GC when you expect there are circular dependencies leaking memory. I don't see why they couldn't have refcounting in addition to GC? – Mehrdad May 8 '18 at 7:35
  • 27
    @Mehrdad They could. But probably it would be slower. Nothing stops you from implementing this, but don't expect to beat any of the GCs in Hotspot or OpenJ9. – Josef May 8 '18 at 7:39
  • 21
    @jpmc26 because if you delete objects as soon as they are not used anymore, the probability is high you delete them in a high load situation which increases load even more. GC can run when there is less load. Reference counting itself is a small overhead for every reference. Also with a GC you can often discard a large portion of memory with no references without handling the single objects. – Josef May 8 '18 at 11:53
  • 33
    @Josef: proper reference counting isn't free either; reference count update requires atomic increments/decrements, which are surprisingly costly, especially on modern multicore architectures. In CPython it isn't much of a problem (CPython is extremely slow on its own, and the GIL limits its multithread performance to single-core levels), but on a faster language which also supports parallelism it can be a problem. It's not a chance that PyPy gets rid of reference counting completely and just uses GC. – Matteo Italia May 8 '18 at 12:51
  • 10
    @Mehrdad once you have implemented your reference counting GC for Java I will gladly test it to find a case where it performs worse than any other GC implementation. – Josef May 8 '18 at 13:49
46

AFAIK, the JVM specification (written in English) does not mention when exactly an object (or a value) should be deleted, and leaves that to the implementation (likewise for R5RS). It somehow requires or suggests a garbage collector but leaves the details to the implementation. And likewise for Java specification.

Remember that programming languages are specifications (of syntax, semantics, etc...), not software implementations. A language like Java (or its JVM) has many implementations. Its specification is published, downloadable (so you can study it) and written in English. §2.5.3 Heap of the JVM spec mentions a garbage collector:

Heap storage for objects is reclaimed by an automatic storage management system (known as a garbage collector); objects are never explicitly deallocated. The Java Virtual Machine assumes no particular type of automatic storage management system

(emphasis is mine; BTW finalization is mentioned in §12.6 of Java spec, and a memory model is in §17.4 of Java spec)

So (in Java) you should not care when an object gets deleted, and you could code as-if it does not happen (by reasoning in an abstraction where you ignore that). Of course you need to care about memory consumption and set of living objects, which is a different question. In several simple cases (think of a "hello world" program) you are able to prove -or to convince yourself- that the allocated memory is rather small (e.g. less than a gigabyte), and then you don't care at all about deletion of individual objects. In more cases, you can convince yourself that the living objects (or reachable ones, which is a superset -easier to reason about- of living ones) never exceed a reasonable limit (and then you do rely on GC, but you don't care how and when the garbage collection happens). Read about space complexity.

I guess that on several JVM implementations running a short-lived Java program like a hello world one, the garbage collector is not triggered at all and no deletion occurs. AFAIU, such a behavior is conforming to the numerous Java specs.

Most JVM implementations use generational copying techniques (at least for most Java objects, those not using finalization or weak references; and finalization is not guaranteed to happen in a short time and could be postponed, so is just a helpful feature that your code should not depend much on) in which the notion of deleting an individual object does not make any sense (since a large block of memory -containing memory zones for many objects-, perhaps several megabytes at once, get released at once).

If the JVM specification required each object to be deleted exactly as soon as possible (or simply put more constraints on object deletion), efficient generational GC techniques would be forbidden, and the designers of Java and of the JVM have been wise in avoiding that.

BTW, it could be possible that a naive JVM which never deletes objects and don't release memory might be conforming to the specs (the letter, not the spirit) and certainly is able to run a hello world thing in practice (notice that most tiny and short lived Java programs probably don't allocate more than a few gigabytes of memory). Of course such a JVM is not worth mentioning and is just a toy thing (like is this implementation of malloc for C). See the Epsilon NoOp GC for more. Real-life JVMs are very complex pieces of software and mix several garbage collection techniques.

Also, Java is not the same as the JVM, and you do have Java implementations running without the JVM (e.g. ahead-of-time Java compilers, Android runtime). In some cases (mostly academic ones), you might imagine (so called "compilation-time garbage collection" techniques) that a Java program don't allocate or delete at runtime (e.g. because the optimizing compiler has been clever enough to only use the call stack and automatic variables).

Why aren't Java objects deleted immediately after they are no longer referenced?

Because the Java and JVM specs don't require that.


Read the GC handbook for more (and the JVM spec). Notice that being alive (or useful to future computation) for an object is a whole-program (non-modular) property.

Objective-C favors a reference counting approach to memory management. And that also has pitfalls (e.g. the Objective-C programmer has to care about circular references by expliciting weak references, but a JVM handles circular references nicely in practice without requiring attention from the Java programmer).

There is No Silver Bullet in programming and programming language design (be aware of the Halting Problem; being a useful living object is undecidable in general).

You might also read SICP, Programming Language Pragmatics, the Dragon Book, Lisp In Small Pieces and Operating Systems: Three Easy Pieces. They are not about Java, but they will open your mind and should help to understand what a JVM should do and how it might practically work (with other pieces) on your computer. You could also spend many months (or several years) in studying the complex source code of existing open source JVM implementations (like OpenJDK, which has several millions of source code lines).

  • 20
    "it could be possible that a naive JVM which never deletes objects and don't release memory might be conforming to the specs" It most certainly does conform to the spec! Java 11 is actually adding a no-op garbage collector for, among other things, very short-lived programs. – Michael May 8 '18 at 11:07
  • 6
    "you should not care when an object gets deleted" Disagree. For one, you should know that RAII is not a feasible pattern anymore, and that you can't depend on finalize for any resource management (of filehandles, db connections, gpu resources, etc.). – Alexander May 8 '18 at 16:23
  • 4
    @Michael It makes perfect sense for batch processing with a used memory ceiling. The OS can just say "all the memory used by this program is now gone!" after all, which is rather fast. Indeed, many programs in C were written that way, especially in the early Unix world. Pascal had the beautifully horrible "reset the stack/heap pointer to a pre-saved checkpoint" that allowed you to do much the same thing, though it was quite unsafe - mark, start sub-task, reset. – Luaan May 9 '18 at 7:46
  • 6
    @Alexander in general outside of C++ (and a few languages that intentionally derive from it), assuming RAII will work based on finalizers alone is an anti-pattern, one that should be warned against and replaced with an explicit resource control block. The whole point of GC is that lifetime and resource are decoupled, after all. – Leushenko May 9 '18 at 9:13
  • 3
    @Leushenko I would strongly disagree that "lifetime and resource are decoupled" is the "whole point" of GC. It's the negative price you pay for the main point of GC: easy, safe memory management. "assuming RAII will work based on finalizers alone is an anti-pattern" In Java? Perhaps. But not in CPython, Rust, Swift, or Objective C. "warned against and replaced with an explicit resource control block" Nope, these are strictly more limited. An object that manages a resource through RAII gives you a handle to pass the scoped life around. A try-with-resource block is limited to a single scope. – Alexander May 9 '18 at 15:51
23

To use Objective-C terminology, all Java references are inherently "strong".

That's not correct - Java does have both weak and soft references, though these are implemented at the object level rather than as language keywords.

In Objective-C, if an object no longer has any strong references, the object is deleted immediately.

That's also not necessarily correct - some versions of Objective C indeed used a generational garbage collector. Other versions had no garbage collection at all.

It is true that newer versions of Objective C use automatic reference counting (ARC) rather than a trace based GC, and this (often) results in the object being "deleted" when that reference count hits zero. However, note that a JVM implementation could also be compliant and work exactly this way (heck, it could be compliant and have no GC at all.)

So why don't most JVM implementations do this, and instead use trace based GC algorithms?

Simply put, ARC is not as utopian as it first seems:

  • You have to increment or decrement a counter every time a reference is copied, modified, or goes out of scope, which brings an obvious performance overhead.
  • ARC can't easily clear out cyclical references, as they all have a reference to each other, thus their reference count never hits zero.

ARC does have advantages of course - its simple to implement and collection is deterministic. But the disadvantages above, amongst others, are the reason the majority of JVM implementations will use a generational, trace based GC.

  • 1
    The funny thing is that Apple switched to ARC precisely because they saw that, in practice, it vastly outperforms other GCs (in particular generational ones). To be fair, this is mostly true on memory-constrained platforms (iPhone). But I’d counter your statement that “ ARC is not as utopian as it first seems” by saying that generational (and other non-deterministic) GCs aren’t as utopian as they first seem: Deterministic destruction is probably a better option in the vast majority of scenarios. – Konrad Rudolph May 9 '18 at 10:39
  • 3
    @KonradRudolph though I'm rather a fan of deterministic destruction too, I don't think “better option in the vast majority of scenarios” holds up. It is certainly a better option when latency or memory is more important than average throughput, and in particular when the logic is reasonably simple. But it's not like there aren't many complex applications that require lots of cyclic references etc. and require fast average operation, but don't really care about latency and have plenty of memory available. For these, it is doubtful if ARC is a good idea. – leftaroundabout May 9 '18 at 12:53
  • 1
    @leftaroundabout In “most scenarios”, neither throughput nor memory pressure are a bottleneck so it doesn’t matter either way. Your example is one specific scenario. Granted, it’s not extremely uncommon but I wouldn’t go so as far as claiming that it’s more common than other scenarios where ARC is better suited. Furthermore, ARC can deal with cycles just fine. It just requires some simple, manual intervention by the programmer. This makes it less ideal but hardly a deal breaker. I contend that deterministic finalisation is a much more important characteristic than you pretend. – Konrad Rudolph May 9 '18 at 16:15
  • 3
    @KonradRudolph If ARC requires some simple manual intervention by the programmer, then it doesn't deal with cycles. If you start using doubly-linked lists heavily, then ARC devolves into manual memory allocation. If you have large arbitrary graphs, ARC forces you to write a garbage collector. The GC argument would be that resources that need destruction aren't the job of the memory subsystem, and to track the relatively few of them, they should be deterministically finalized through some simple manual intervention by the programmer. – prosfilaes May 10 '18 at 1:58
  • 2
    @KonradRudolph ARC and cycles fundamentally leads to memory leaks if they are not manually handled. In complex enough systems, major leaks can happen if e.g. some object stored in a map stores a reference to that map, a change that could be made by a programmer not in charge of the sections of code creating and destroying that map. Large arbitrary graphs does not mean that the internal pointers aren't strong, that it's okay for the items linked to to disappear. Whether dealing with some memory leaks is less of a problem than having to manually close files, I won't say, but it is real. – prosfilaes May 11 '18 at 6:20
5

Java doesn't specify precisely when the object gets collected because that gives implementations the freedom to choose how to handle garbage collection.

There are many different garbage collection mechanisms, but those that guarantee that you can collect an object immediately are almost entirely based on reference counting (I am unaware of any algorithm that breaks this trend). Reference counting is a powerful tool, but it comes at a cost of maintaining the reference count. In singlethreaded code, that's nothing more than a increment and decrement, so assigning a pointer can cost cost on the order of 3x as much in reference counted code than it does in non-reference counted code (if the compiler can bake everything down to machine code).

In multithreaded code, the cost is higher. It either calls for atomic increments/decrements or locks, both of which can be expensive. On a modern processor, an atomic operation can be on the order of 20x more expensive than a simple register operation (obviously varies from processor to processor). This can increase the cost.

So with this, we can consider the tradeoffs made by several models.

  • Objective-C focuses on ARC - automated reference counting. Their approach is to use reference counting for everything. There is no cycle detection (that I know of), so programmers are expected to prevent cycles from occurring, which costs development time. Their theory is that pointers are not assigned all that often, and their compiler can identify situations where incrementing/decrementing reference counts cannot cause an object to die, and elide those increments/decrements completely. Thus they minimize the cost of reference counting.

  • CPython uses a hybrid mechanism. They use reference counts, but they also have a garbage collector that identifies cycles and releases them. This provides the benefits of both worlds, at the cost of both approaches. CPython must both maintain reference counts and do the book keeping to detect cycles. CPython gets away with this in two ways. The fist is that CPython is really not fully multithreaded. It has a lock known as the GIL which limits multithreading. This means CPython can use normal increments/decrements rather than atomic ones, which is much faster. CPython also is interpreted, which means operations like assignment to a variable already take a handful of instructions rather than just 1. The extra cost of doing the increments/decrements, which is done quickly in C code, is less of an issue because we've already paid this cost.

  • Java goes down the approach of not guaranteeing a reference counted system at all. Indeed the specification does not say anything about how objects are managed other than that there will be an automatic storage management system. However, the specification also strongly hints to the assumption that this will be garbage collected in a way that handles cycles. By not specifying when objects expire, java gains the freedom to use collectors which do not waste time incrementing/decrementing. Indeed, clever algortihms such as generational garbage collectors can even handle many simple cases without even looking at the data that is being reclaimed (they only have to look at data that is still being referenced).

So we can see each of these three had to make tradeoffs. Which tradeoff is best depends greatly on the nature of how the language is intended to be used.

4

Although finalize was piggy-backed onto Java's GC, garbage collection at its core isn't interested in dead objects, but live ones. On some GC systems (possibly including some implementations of Java), the only thing distinguishing a bunch of bits that represents an object from a bunch of storage that isn't used for anything may be the existence of references to the former. While objects with finalizers get added to a special list, other objects may not have anything anywhere in the universe that says their storage is associated with an object except for references held in user code. When the last such reference is overwritten, the bit pattern in memory will immediately cease to be recognizable as an object, whether or not anything in the universe is aware of that.

The purpose of garbage collection isn't to destroy objects to which no references exist, but rather to accomplish three things:

  1. Invalidate weak references that identify objects which don't have any strongly-reachable references associated with them.

  2. Search the system's list of objects with finalizers to see if any of those don't have any strongly-reachable references associated with them.

  3. Identify and consolidate regions of storage which aren't being used by any objects.

Note that the primary goal of the GC is #3, and the longer one waits before doing it, the more opportunities at consolidation one is likely to have. It makes sense to do #3 in cases where one would have an immediate use for the storage, but otherwise it makes more sense to defer it.

  • 5
    Actually, gc only has one goal: Simulating infinite memory. Everything you named as a goal is either an imperfection in the abstraction or an implementation-detail. – Deduplicator May 8 '18 at 19:46
  • @Deduplicator: Weak references offer useful semantics that can't be achieved without GC assistance. – supercat May 8 '18 at 20:16
  • Sure, weak references have useful semantics. But would those semantics be needed if the simulation was better? – Deduplicator May 8 '18 at 20:19
  • @Deduplicator: Yes. Consider a collection which defines how updates will interact with enumeration. Such a collection may need to hold weak references to any live enumerators. In an unlimited-memory system, a collection that was iterated repeatedly would have its list of interested enumerators grow without bound. The memory required for that list wouldn't be a problem, but the time required to iterate through it would degrade system performance. Adding GC can mean the difference between an O(N) and O(N^2) algorithm. – supercat May 8 '18 at 20:32
  • 2
    Why would you want to notify the enumerators, instead of appending to a list and letting them look for themselves when they are used? And any program depending on garbage being processed in a timely manner instead of depending on memory pressure is living in a state of sin anyway, if it moves at all. – Deduplicator May 8 '18 at 20:46
4

Let me suggest a rewording and generalization of your question:

Why doesn't Java make strong guarantees about its GC process?

With that in mind, take a quick scroll through the answers here. There are seven so far (not counting this one), with quite a few comment threads.

That's your answer.

GC is hard. There are lots of considerations, lots of different tradeoffs, and, ultimately, lots of very different approaches. Some of those approaches make it feasible to GC an object as soon as it's not needed; others don't. By keeping the contract loose, Java gives its implementers more options.

There is a tradeoff even in that decision, of course: by keeping the contract loose, Java mostly* takes away the ability for programmers to rely on destructors. This is something that C++ programmers in particular often miss ([citation needed] ;) ), so it's not an insignificant tradeoff. I haven't seen a discussion of that particular meta-decision, but presumably the Java folks decided that the benefits of having more GC options outweighed the benefits of being able to tell programmers exactly when an object will be destroyed.


* There is the finalize method, but for various reasons that are out of scope for this answer, it's hard and not a good idea to rely on it.

3

There are two different strategies of handling memory without explicit code written by the developer: Garbage collection, and reference counting.

Garbage collection has the advantage that it "works" unless the developer does something stupid. With reference counting, you can have reference cycles, which means that it "works" but the developer sometimes has to be clever. So that's a plus for garbage collection.

With reference counting, the object goes away immediately when the reference count goes down to zero. That's an advantage for reference counting.

Speedwise, garbage collection is faster if you believe the fans of garbage collection, and reference counting is faster if you believe the fans of reference counting.

It's just two different methods to achieve the same goal, Java picked one method, Objective-C picked another (and added lots of compiler support to change it from a pain-in-the-arse to something that is little work for developers).

Changing Java from garbage collection to reference counting would be a major undertaking, because lots of code changes would be needed.

In theory, Java could have implemented a mixture of garbage collection and reference counting: If the reference count is 0, then the object is unreachable, but not necessarily the other way round. So you could keep reference counts and delete objects when their reference count is zero (and then run garbage collection from time to time to catch objects within unreachable reference cycles). I think the world is split 50/50 in people who think that adding reference counting to garbage collection is a bad idea, and people who think that adding garbage collection to reference counting is a bad idea. So this isn't going to happen.

So Java could delete objects immediately if their reference count becomes zero, and delete objects within unreachable cycles later. But that's a design decision, and Java decided against it.

  • With reference-counting, finalizing is trivial, as the programmer took care of cycles. With gc, cycles are trivial, but the programmer has to be careful with finalizing. – Deduplicator May 8 '18 at 16:33
  • @Deduplicator In Java, it's also possible to create strong references to objects being finalised... In Objective-C and Swift, once the reference count is zero, the object will disappear (unless you put an infinite loop into dealloc / deist). – gnasher729 May 8 '18 at 17:42
  • Just noticed stupid spelling checker replacing deinit with deist... – gnasher729 May 8 '18 at 19:07
  • 1
    There is a reason most programmers hate automatic spelling correction... ;-) – Deduplicator May 8 '18 at 19:44
  • lol... I think the world is split 0.1/0.1/99.8 between people who think that adding reference counting to garbage collection is a bad idea, and people who think that adding garbage collection to reference counting is a bad idea, and people who keep counting days until garbage collection arrives because that ton is already getting smelly again... – leftaroundabout May 9 '18 at 18:49
1

All of the other performance arguments and discussions about the difficulty of understanding when there are no longer references to an object are correct though one other idea that I think is worth mentioning is that there is at least one JVM (azul) that considers something like this in that it implements parallel gc that essentially has a vm thread constantly checking references to attempt to delete them which will act not entirely dis-similarly from what you are talking about. Basically it will constant look around at the heap and try to reclaim any memory that is not being referenced. This does incur a very slight performance cost but it leads to essentially zero or very short GC times. (That is unless the constantly expanding heap size exceeds system RAM and then Azul gets confused and then there be dragons)

TLDR Something like that kinda exists for the JVM it just is a special jvm and it has drawbacks like any other engineering compromise.

Disclaimer: I have no ties to Azul we just used it at a previous job.

1

Maximizing sustained throughput or minimizing gc latency are in dynamic tension, which is probably the most common reason why GC doesn't occur immediately. In some system's, like 911 emergency apps, not meeting a specific latency threshold can start triggering site fail-over processes. In others, like a banking and/or arbitrage site, it's far more important to maximize throughput.

0

Speed

Why all of this is going on is ultimately because of speed. If processors were infinitely fast, or (to be practical) close to it, e.g. 1,000,000,000,000,000,000,000,000,000,000,000 operations per second then you can have insanely long and complicated things happen between each operator, such as making sure de-referenced objects are deleted. As that number of operations per second is not currently true and, as most of the other answers explain it is actually complicated and resource intensive to figure this out, garbage collection exists so that programs can focus on what they are actually trying to achieve in a speedy manner.

  • Well, I'm sure we would find more interesting ways to use up the extra cycles than that. – Deduplicator May 13 '18 at 15:29

protected by gnat May 9 '18 at 3:43

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.