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

Question

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?

You should not care *when* Java objects get actually deleted. It is an implementation detail. — Basile Starynkevitch, May 08 '18 at 06:10
@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 08 '18 at 07:34
What does Objective C do when there are circular references? I assume it just leaks them? — user541686, May 08 '18 at 07:34
@ArturBiesiadowksi: No, the Java specification does not tell *when* an object is deleted (and likewise, for [R5RS](http://www.schemers.org/Documents/Standards/R5RS/)). You could and probably should develop your Java program [as-if](https://en.wikipedia.org/wiki/As-if_rule) 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 08 '18 at 07:36
@BasileStarynkevitch How is caring about memory consumption a different story from caring whether these objects are ever deleted? — Nacht, May 08 '18 at 09:12
You could prove that a given program execution don't allocate more than a gigabyte of memory. You then don't care about object deletion (which might and is likely to never happen) — Basile Starynkevitch, May 08 '18 at 09:14
@Mehrdad yep, as with C++ smart pointers, ObjC will leak on strong cycles — OrangeDog, May 08 '18 at 11:51
Both Obj-C and Java are languages, both of which can be (and have been) implemented with various kinds of memory management. — OrangeDog, May 08 '18 at 12:09
If it was deleted immediately, it would basically be a reference-counted GC strategy. You are right that this "implementation detail" being undefined is a bit of a problem, because if you want something close to real-time behavior or fitting into a well known amount of space, it's not ideal behavior. It is what it is, and it's one reason why GC environments can be memory hogs; particularly JVM. — Rob, May 08 '18 at 14:45
Related: https://blogs.msdn.microsoft.com/oldnewthing/20100809-00/?p=13203/ — Matteo Italia, May 08 '18 at 15:02
@Mehrdad If they two objects reference each other using strong references, yes. The solution to this is to have at least one of the two references be weak, which can be used to access the object if it's still alive (because it's being kept alive but another strong reference), but the weak reference itself won't keep the object alive — Alexander, May 08 '18 at 16:12
@Basile In real life, if you're writing software that cares about performance and other non-functional requirements and where you know the environment in which your application is running (all very sensible requirements for server software), caring about "implementation details" is perfectly acceptable and can give you great benefits. — Voo, May 09 '18 at 08:21
@Voo I think Basile's point was misunderstood - he's not saying you shouldn't care how things work, just that certain implementation details are hidden/abstracted away for a reason, and relying on them being a certain way is risky. In the case of Java's GC, understand how it works for sure, but don't write code that relies on that assumption, because it is subject to change beyond your control. — GoatInTheMachine, May 09 '18 at 11:58
"Why isn't this the case in Java?" Because Java is not Objective-C. The questioner could motivate more on why he thinks Java should be like Objective-C in this regard to make this a useful question. — NoDataDumpNoContribution, May 09 '18 at 12:01
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 09 '18 at 14:07
I just thought of an analogy: Suppose we are designing a program that airlines will use to create a passenger manifest that identifies passengers based on where they sit. Suppose the airline will also use it to order drinks within the plane, which requires knowledge of each passenger's seat. This program will thus use two objects: Seats and Passengers. For the first purpose, the program can use a list of Seats, each of which has their own Passenger. For the second purpose, the program can use a list of Passengers, each of which has their own Seat. — moonman239, May 09 '18 at 18:15
Since the program doesn't need to know both things at once, giving each Passenger a reference to their Seat - and vice-versa - allows the program to construct either list on an as-needed basis. — moonman239, May 09 '18 at 18:18
There is such a thing as a "leaky abstraction". You *generally* should not care about implementation details. *Generally*... — Panzercrisis, May 11 '18 at 15:58
The expression "deleted immediately" in the question is also somewhat misleading, since C++ and Objective-C don't decrement the reference count until scope exit. In a tracing GC, it's possible for an object to be collected while a variable that refers to it is still in (lexical) scope, so long as the value of that variable is never read again. This means that not only can a GC run a finalizer "too late", it can also run it "too soon". — Daniel Pryden, May 11 '18 at 16:33
@BasileStarynkevitch Woah there. It may not be guaranteed *when* garbage collection happens, but that absolutely **does not** mean you should just ignore garbage collection altogether by programming as if it does not happen. That's a road that leads straight to memory leaks. — Kröw, Jun 30 '19 at 16:03

score 86 · Answer 1 · answered May 08 '18 at 00:32

86

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.

answered May 08 '18 at 00:32

whatsisname

27,463
14
73
93

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? – user541686 May 08 '18 at 07: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 08 '18 at 07:39
@Josef Why would it be slower? It should reduce the frequency with with the GC needs to be invoked at all. (Python has the part that scans for circular references completely disabled by default and discourages circular references in general.) That should eliminate the overhead of scanning all references to count them and look for loops. – jpmc26 May 08 '18 at 11:14
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 08 '18 at 11:53
33

@Josef: proper reference counting isn't free either; reference count update requires atomic increments/decrements, which [are surprisingly costly](https://stackoverflow.com/a/2783981/214671), 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 08 '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 08 '18 at 13:49
3

@Josef: *That's* your evidence? – user541686 May 08 '18 at 14:03
4

@Mehrdad As for example MatteoItalia mentioned, there are VMs which switch away from reference counting because it is to slow. As far as I know there was never a full blown GC implementation using reference counting for a JVM, so no one know how it actually performs until you implement it. There are reasons why it has never been implemented, some of them I mentioned. – Josef May 08 '18 at 14:18
6

Another thing to add is that one of the observations the JVM team had is that the great majority of objects are short-lived. You create a Set in a method, do a bit of processing on it, and then discard it. (I can't find a reference right now, but I've seen them write about it.) As such, the cost of finding a few still-live objects is smaller than constantly discovering which objects are now eligible for GC. But the relevant point isn't actually which is faster: it's that from a language/contract perspective, making the GC time undefined gives you the _option_ of doing either approach. – yshavit May 08 '18 at 14:57
1

@Mehrdad Using both together does give you the advantages of both like in python (deterministic destruction AND automatic clean up of strong ref cycles), but it also hits you with both techniques downsides. Reference counting incurs some overhead on every reference creation/deletion, and GC incurs overhead from having to place safepoints in your code (even in hot loops!), and pausing the world when cleaning up. – Alexander May 08 '18 at 16:18
@MatteoItalia Amazingly, Rust has two reference counting "boxes": `Rc` and `Arc`. The former has non-atomic inc/decs (faster), and the latter has atomic inc/decs (thread safe). The borrow checker can guarantee that `Rc` isn't under contention, and it won't let you give rise to race conditions! So if you have references that only need single threaded access, you can have lock-less reference counting! – Alexander May 08 '18 at 16:21
2

@Alexander: I agree, but static analysis could help them optimize away a lot of refcounting like w/ with heap allocations. Also, there's an important point you need to consider: in a GC, live objects that are traversed but not actually garbage-collected result in *wasted* work, and the amount of this waste can be *arbitrarily large*, because the highest-generation GC can kick in any number of times on an arbitrarily large graph. By contrast, in a reference-counting scheme, there is *no* wasted work: the amount of work done is *bounded* by the number of times references are created & destroyed. – user541686 May 08 '18 at 16:33
1

Although background GC certainly is/can be expensive in absolute terms, lots of effort has gone into making it work in the background. ARC happens by definition on the hot/fast path of your application. Whether the occasional background (and even less frequent stop-the-world) collections are actually better or worse than the up-front cost of ARC is, of course, application dependent. – Useless May 08 '18 at 17:33
6

@Mehrdad AFAIK it's folk wisdom in the memory management community that for typical workloads, manual management is faster than decent GC is faster than refcounting. In a concurrent world, refcounting introduces memory barriers. In a cached world, refcounting has poor locality. There are benchmarks in [Myths and Realities: The Performance Impact of Garbage Collection](https://www.cs.utexas.edu/users/mckinley/papers/mmtk-sigmetrics-2004.pdf) §5.4.3. Refcounting also [suffers from pauses](http://www.hpl.hp.com/techreports/2003/HPL-2003-215.pdf) like tracing GC. – Gilles 'SO- stop being evil' May 08 '18 at 20:54
@Gilles: Nice paper. A couple points it didn't touch on much: (1) Going from one generation to two is an improvement; it might have been helpful to see whether going to three or four would help further; (2) Some platforms may offer different ways of tracking writes, with varying balances between cost and precision. Some, for example, may be able to mark 4K pages holding older-generation objects as read-only, but quickly change them to read-write the first time they are written, incurring at most one penalty per page per GC cycle. Writing a page would make it necessary... – supercat May 08 '18 at 21:24
...to trace all references contained within that page, but in many cases the vast majority of references held by older objects would be in pages that don't get written, meaning that the GC could safely ignore those references unless it's processing the generation in which they are contained. – supercat May 08 '18 at 21:26
1

@Gilles: The latest reference you have for this is folk wisdom from... *2004*? I can't really speak to what it was like back then. CPUs, memory, etc. have evolved a lot since then. I'm just talking about my experience in the past ~10 years. And not theoretical justifications people enjoy repeating to each other -- but actual experience with actual code. And yes, nobody claimed refcounting eliminates pauses entirely... but there are 'pauses' in refcounting, and then there are *paaaaaaaaauuuuuuuses* in GC... – user541686 May 08 '18 at 21:34
1

@Mehrdad That's what I found in two minutes with Google. If you want a thorough literature survey, you do it. It isn't theoretical justifications, it's benchmarks. The factors that make refcounting costly have rather increased in the past decade, so I don't expect the situation to have become inverted. And if you think there are “paaaaaaaaauuuuuuuses in GC”, then your experience is not from the past 10 years, it's from 50 years ago. – Gilles 'SO- stop being evil' May 08 '18 at 22:27
5

@Gilles: 50 years ago? The latest instance was 1 week ago.. – user541686 May 08 '18 at 23:04
2

@MatteoItalia Atomic updates are not "surprisingly costly on modern multicore architectures;" they're actually quite cheap the vast majority of the time. I think you're misreading the linked answer. *Unless you hit the worst-case behavior,* where the same cache line is in L1 cache on two different cores, (which is not common at all,) the "price" of an atomic increment or decrement over an ordinary increment/decrement is virtually nil these days. What you're claiming used to be true, but hasn't been for several processor generations now. – Mason Wheeler May 09 '18 at 00:36
You say what if two objects are referencing each other- I feel like that problem could be solved by having one object hold its reference in such a way that it isn't factored into the ref count. – moonman239 May 09 '18 at 05:38
@moonman239 So you have a weak reference in B that points to A. A loses all strong references, is collected... and B no longer has the A it needs. The main objective of any automatic memory management system isn't to make sure there are no memory leaks (that's impossible anyway) - it's to make sure things aren't released *too soon* (remember access violations and reading/writing pretty much random memory? That's what a GC protects you against - though usually not null references). In fact, a GC for the CLR can legally do *nothing* (and it can be useful, e.g. for batch processing). – Luaan May 09 '18 at 07:37
"Because properly knowing something is no longer referenced isn't easy. Not even close to easy." According to the question, Objective-C can do it. If this is true, then it cannot be that difficult either. – NoDataDumpNoContribution May 09 '18 at 12:02
@Luaan: The idea being: If we have a running class, that class has a strong reference to A and B, whether directly or via a strong reference to another object that in turn has a strong reference to A or B, and that neither A nor B are needed when the object holding the strong reference gets deallocated. – moonman239 May 09 '18 at 15:00
@moonman239 ... and that's how the typical mark & sweep garbage collector works, not how a reference counting one does. You walk through all the objects in the heap (in the simplest implementation), and check if they are *rooted* - that their references can be traced all the way to e.g. a static field, a CPU register, a stack value... This is a lot of effort. How do you know who refers to your C? Either you need to keep bi-directional references *everywhere* (ouch), or you need to walk the heap. Walking the heap takes time, so you don't want to do it every time a reference is lost. – Luaan May 09 '18 at 15:18
2

@moonman239 You have to keep in mind that reference counting adds the bare minimum extra tracking on top of normal program operation, and it's already so much effort that a "stop the world" GC can be *faster*. Reference counting through *hierarchies* is much more complex, and likely to suffer heavily from performance issues related to things like data locality, and don't even get me started on multi-threading. There are solutions to these problems, and some languages and environments use them pretty successfully with some limitations; for example, you can only allow *one* owner of a resource. – Luaan May 09 '18 at 15:24

score 79 · Accepted Answer · answered May 08 '18 at 05:25

79

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.

answered May 08 '18 at 05:25

Karl Bielefeldt

146,727
38
279
479

60

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 08 '18 at 07: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 08 '18 at 07:39
66

@Neil shouldn't that be 13 loaves? – JAD May 08 '18 at 08:18
69

"Off by one error on aisle 7" – joeytwiddle May 08 '18 at 10:53
13

@JAD I would have said 13, but most don't tend to get that. ;) – Neil May 08 '18 at 11:39
2

It has been found to be more efficient to GC as many objects in one go as possible. – Thorbjørn Ravn Andersen May 08 '18 at 21:08
2

@joeytwiddle I thought the bread was on aisle 6... – Mason Wheeler May 09 '18 at 00:37
2

@ArturBiesiadowski I'm not sure which is the more common approach, but compacting the heaps is also done in some GCs (notably .NET's). This is more expensive than zeroing the memory, but has a huge advantage in allocations (no need to find free space - just increment a pointer) and sometimes in data locality (GC survivors cluster together in memory - especially handy in a multi-threaded environment with many disposable worker threads). Oracle's JVM also does compaction, but only as the fragmentation gets high (though of course different GCs are available). – Luaan May 09 '18 at 07:42
2

@Luaan Oracle JVM is also compacting memory in new GC, as it copies live objects between survivor spaces. After compaction you are left with memory ready for allocations with simple pointer increment as you say (well, TLABs complicate it a bit), but you still need to zero the memory at some point before handing over newly allocated object to user. You can do it after evacuation for entire space, you can do it during TLAB allocation or you can do it directly when object is initialized. This is unrelated to compaction, compaction just gives you more places in lifecycle when you can do it. – Artur Biesiadowski May 09 '18 at 08:08
1

@JAD no, you `buy(1)` and `grab(12)`. Those are different operations. – Chaos Monkey May 09 '18 at 21:53
1

I assume it's possible to grab the one you've already bought. – Dawood ibn Kareem May 09 '18 at 22:04
1

@Renan that's the point, you `buy(1)` **and** `if(eggs.AreSeen())` you then `grab(12)`. – JAD May 10 '18 at 07:52
3

@Neil So, the programmer in the story ends up _buying_ one out of the 13 loafs of bread, but just _grabbing_ (i.e. stealing) the other 12. The programmer in our story never makes it back to the wife; he ends up arrested by police :c – code_dredd May 10 '18 at 21:13
What if you miss on some sales for your items which come around after you've done your monthly trip to the supermarket? – Milan Velebit May 11 '18 at 09:04
@MasonWheeler C'mon, what supermarket indexes its aisles from zero? – David Richerby May 11 '18 at 13:06
@DavidRicherby • Everyzero knows why indexing from 1 is bad. – Eljay May 11 '18 at 13:39

Basile Starynkevitch · Answer 3 · 2018-05-08T17:44:45.787

45

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).

edited May 08 '18 at 17:44

answered May 08 '18 at 07:56

Basile Starynkevitch

32,434
6
84
125

Different, but related. – glglgl May 08 '18 at 08:02
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](http://openjdk.java.net/jeps/318) for, among other things, very short-lived programs. – Michael May 08 '18 at 11:07
1

I think JavaCard still defines garbage collection as never happening ever. There are cases where it really does happen never. – Rob May 08 '18 at 14:48
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 08 '18 at 16:23
@Alexander: Then give your answer, quoting the JVM or the Java standard, explaining why. My point is that you *may* care (with finalizers) about deletion, but you *should not* because according to the specs it is an implementation detail (and the Java specs permit various implementations of the GC) – Basile Starynkevitch May 08 '18 at 16:50
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 09 '18 at 07: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. – Alex Celeste May 09 '18 at 09:13
@Luaan Interesting point. Of course, it's possible to use that kind of deallocate-the-whole-lot-when-we're-done strategy in ways other than short-lived processes. 'Region-based memory management'. Not something that gets much attention these days. – Max Barraclough May 09 '18 at 09:47
@MaxBarraclough It's trickier said than done. .NET has AppDomains that can do this, but they're pretty much being deprecated. The main benefit of using processes is that they already exist, are well tested and decently well understood. In general, a lot of programming still relies on spreading references/pointers all over the memory, which makes any partial approach tricky - it's all too easy to miss a tiny thing that shouldn't have been allocated/referenced/deallocated... – Luaan May 09 '18 at 13:26
@Michael That's pretty interesting. I would like to have an option to only have a young collector but a no-op old/tenured collector. This is useful in a clustered container-based application. Since instances can come and go at any point, the time it takes to do mark-sweep-compact isn't worth it. You can just spin up a new instance and trash the old one. – JimmyJames May 09 '18 at 13:48
1

@Luaan I'm sure you're right on all points. Java and .Net don't have, or need, an 'Obstack' library like GNU C/C++ (not that anyone uses it afaik, but it's still neat) – Max Barraclough May 09 '18 at 15:23
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 09 '18 at 15:51
3

@Alexander It's ironic that people who insist that automatic memory management is better than manual one then tell "obviously, you manage all other resurces manually" without batting an eye. Memory is a boring resource, that's why it was relatively easy to automate, now let's automate more interesting ones! – Joker_vD May 09 '18 at 19:16
@Joker_vD Well by coupling object lifetime with the lifetimes of the resources it owns, reference counting lets you do both – Alexander May 09 '18 at 19:20
@Luaan Turbo Pascal had this memory hack. Probably because it was easier than implementing the standard. – Thorbjørn Ravn Andersen May 11 '18 at 09:29
@ThorbjørnRavnAndersen Yeah, it wasn't that awful there, since you rarely needed dynamically allocated memory; it mostly relied on scope-based memory management. Once in a while, the performance boost was worth the risk. – Luaan May 11 '18 at 14:04
@Alexander: Assuming that RAII-style (timely execution of `__del__` methods) works in CPython **is** an anti-pattern. That is not guaranteed and not a recommended style. That's the reason why the `with` statement was introduced into the Python syntax: it should be used instead. As far as I know, C++, Rust, Swift and Objective-C are the *only* languages which make guarantees about timely execution of arbitrary user-specified code in connection with scope exit, which actually makes them quite the minority. – Daniel Pryden May 11 '18 at 16:15
2

@BasileStarynkevitch: Worth mentioning that the "no particular type of automatic storage management system" clause also works the opposite way: the `new` keyword is not required to perform a heap allocation, or indeed to allocate any memory at all. If the JIT is able to inline all the methods ever invoked on an object, all the storage associated with the object can also be inlined into local variables and then can be allocated directly on the stack or possibly even only in registers, making the whole discussion of how soon the object gets destroyed effectively a moot point. – Daniel Pryden May 11 '18 at 16:19

berry120 · Answer 4 · 2018-05-09T07:58:39.400

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.

edited May 09 '18 at 07:58

answered May 08 '18 at 10:52

berry120

1,747
14
17

ARC already delays deletions for later to avoid stalling high-performance threads. Only using MRC can you choose whether to `release` or `autorelease`. – OrangeDog May 08 '18 at 12:05
You have a false dichotomy between Obj-C GC and ARC which omits all the manual memory management available. You are in fact free to mix `malloc/free`, `retain/release` and ARC (and `new/delete` for Obj-C++) in the same application. – OrangeDog May 08 '18 at 12:11
Please define ARC. – scai May 09 '18 at 07:49
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 09 '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 09 '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 09 '18 at 16:15
@leftaroundabout (cont’) In fact, in my experience, large systems that don’t have deterministic finalisation tend to become architecturally more complex because they need to work around that limitation to ensure resources are handled properly. Your comment simply ignores all non-memory considerations. This is why I insist that, in practice, deterministic destruction is probably the better option in the ***vast*** majority of scenarios. – Konrad Rudolph May 09 '18 at 16:18
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 01:58
@prosfilaes That’s purely arguing semantics. ARC can’t deal with cycles on its own but it’s false to suggest (as is often done) that ARC and cycles fundamentally leads to memory leaks. Your comment, like the previous ones, vastly overstate the complexity of solving this in practice, while at the same time understating the complexity of manually keeping track of non-memory resources. This leads to a bad trade-off in most cases (Java, C#). ARC, by contrast, is a good tradeoff more often than not (and that includes dealing with large, arbitrary graphs; look up weak pointers). – Konrad Rudolph May 10 '18 at 08:40
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 06:20

score 5 · Answer 5 · answered May 08 '18 at 18:13

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.

score 4 · Answer 6 · answered May 08 '18 at 17:02

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:

Invalidate weak references that identify objects which don't have any strongly-reachable references associated with them.
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.
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.

answered May 08 '18 at 17:02

supercat

8,335
22
28

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 08 '18 at 19:46
@Deduplicator: Weak references offer useful semantics that can't be achieved without GC assistance. – supercat May 08 '18 at 20:16
Sure, weak references have useful semantics. But would those semantics be needed if the simulation was better? – Deduplicator May 08 '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 08 '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 08 '18 at 20:46
@Deduplicator: Building a list of updates would result in unbounded memory growth if any code has a reference to an enumerator and just sits on it. I suppose if memory were unlimited that might not be a problem, but having the collection notify enumerators about updates gives them a chance to handle the updates and then forget about them. Further, unlike with code that relies upon `finalize` for fungible resources, failure to run the GC wouldn't result in incorrect behavior, but could cause useful performance to drop to a value that asymptotically approaches zero. – supercat May 08 '18 at 20:54
@supercat It's *exactly* not a problem because we are assuming a(n arbitrarily good simulation of a) machine with unbounded memory. – Caleth May 09 '18 at 11:27
@Caleth: For most purposes, an algorithm which would require bounded memory on a GC-based system will be preferable to one which would require unbounded memory on such a system. And weak references would sometimes be required to make such algorithms perform well even if memory weren't limited. – supercat May 09 '18 at 14:54

score 4 · Answer 7 · answered May 08 '18 at 18:17

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.

gnasher729 · Answer 8 · 2018-05-08T19:06:27.757

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 08 '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 08 '18 at 17:42
Just noticed stupid spelling checker replacing deinit with deist... — gnasher729, May 08 '18 at 19:07
There is a reason most programmers hate automatic spelling correction... ;-) — Deduplicator, May 08 '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 09 '18 at 18:49

score 1 · Answer 9 · answered May 08 '18 at 15:40

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.

score 1 · Answer 10 · answered May 08 '18 at 22:29

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.

score 0 · Answer 11 · answered May 13 '18 at 14:54

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

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

11 Answers11

Speed

Linked