9

A lot of languages like Java and C# have garbage collectors that free memory when that memory no longer has any reference. Yet they don't immediately free it after the reference counter hits zero but instead every once in a while they check on all the memory to see if that memory has any reference and delete it if it doesn't. What is the benefit of doing that way?

The downside to doing it that way is that you lose the destructor as you can't guarantee when it will be called.

I would imagine that it is done that way because of performance, but has there been any study that shows that a garbage collector that works like that has a better performance then std::shared_ptr found in C++?

Improve this question
7
  • because then you'd need to keep a reference counter and that can cascade down heavily
    – ratchet freak
    Dec 9, 2013 at 23:47
  • 3
    std::shared_ptr cannot properly detect when some data needs to be freed. Example: Cyclic references. Functional languages often need the full power of a non-reference counting collector to deal with closures and such. The alternative (counted pointers) is too messy for users to be a real option.
    – Thomas Eding
    Dec 9, 2013 at 23:55
  • 1
    Strongly related: programmers.stackexchange.com/questions/113209/…
    – Robert Harvey
    Dec 10, 2013 at 4:11
  • 5
    Answer could be very simple: "Yet they don't immediately free it after the reference counter hits zero" : there is no reference counter to hit 0.
    – Pieter B
    Dec 10, 2013 at 9:13
  • 1
    say A refers to B and B refers to A, but nothing refers to either of them. They both have a reference count of 1.
    – Peter Lawrey
    Dec 10, 2013 at 10:26

4 Answers 4

Reset to default
24

Because in order to free memory as soon as the reference counter hits zero, you have to keep a reference counter. And that doesn't come for free. Typically, it limits your throughput.

There are generally two major strategies for implementing garbage collectors: tracing collectors and reference counting collectors. (There are others, but those are the ones in use by most mainstream automatic memory management systems.)

Typically, reference counting GCs tend to have worse throughput but better (and more predictable) latency than tracing collectors whereas tracing collectors have better throughput but higher and less predictable latency. Another big problem with (at least with simple implementations of) reference counting garbage collectors is that they can't garbage collect cycles. You typically need to run a tracing collector in conjunction with a reference counting collector anyway (that's what CPython does, for example).

Practically speaking, all modern industrial-strength high-performance automatic memory management systems (all of the collectors in Oracle JDK, Oracle JRockit and most other JVMs, Microsoft CLR, Mono, most ECMAScript implementations, all Ruby implementations, almost all Python implementations, all Smalltalk implementations, all Lisp implementations etc.) are tracing collectors, so there is a bit of a self-reinforcing feedback loop here: more money gets put into research on tracing GCs because they are popular, and they become more popular because they get better because of the money spent on their research … and so on.

Improve this answer
13
  • Perl (see perlref) and objective C (SO ... even with ARC (static code analysis to generate retain/release)) use a reference count system. The later (clang & Apple) is certainly not without its own research being done. In particular, iOS had a trade off on how garbage collection worked for cpu/battery being a premium.
    – user40980
    Dec 10, 2013 at 1:51
  • 1
    @MichaelT: I think the iphone is a pretty special case here, though. The majority of modern systems are not heavily RAM constrained computers with limited scope for concurrency. Reference counting really shines under that sort of environment, but it isn't representative of, say, your average desktop computer. (Nor will it necessarily be representative of mobile devices for long, I'd be willing to bet iOS will move to a tracing GC within the next decade or so)
    – Phoshi
    Dec 10, 2013 at 10:49
  • 1
    @Phoshi : The majority of computers sold ARE memory contrained: smartphone sales have already in 2011 overtaken traditional computer sales and tablets are projected to overtake traditional computer sales end of this year.
    – Pieter B
    Dec 10, 2013 at 10:54
  • 1
    @Steve314: It works for me, now, too. Must have been a temporary glitch. Yes, that's the Recycler paper, I'm well aware of that. PHP has adopted the non-concurrent version of that algorithm as of PHP 5.3. Interestingly, the same authors have also developed a tracing GC which has even lower pause times than their reference counting GC: Metronome, whose pause times are lower than thread context switching times of typical modern OSs (~250 µs as opposed to 6 ms for the Recycler). It is sold as part of IBM WebSphere RealTime.
    – Jörg W Mittag
    Dec 10, 2013 at 13:19
  • 1
    @PieterB is correct, smartphones and tablets dominate computer sales and all of them have heavily constrained memory. See sealedabstract.com/rants/why-mobile-web-apps-are-slow for a great overview of how garbage collection issues are very real in the mobile/tablet world.
    – Michael Shopsin
    Dec 11, 2013 at 16:07
14

Because it would be too expensive to do it continuously.

"Mark and sweep" garbage collectors periodically sweep the memory space for objects that have been dereferenced. Generational garbage collectors sweep those objects first that are most likely to have been disposed of recently (which turns out statistically to be the objects most recently created). Objects that have been around for awhile get put into a second or third generation for sweeping later.

Garbage collection works very much like your trash bin: your trash man does not check your can every minute for trash, or even every day, although you might check the cans inside your house every day. Checking every minute or every hour would be too inefficient, for both you and the trash man.

Improve this answer
10
  • You don't need to do it continuously, just when the object has been dereferenced. The same way std::shared_ptr does in C++.
    – Caesar
    Dec 9, 2013 at 23:46
  • 7
    @Caesar but you'd need to increment the counter when you add a reference, and that needs to happen in a thread-safe manner, plus the freeing can cascade down
    – ratchet freak
    Dec 9, 2013 at 23:48
  • @ratchetfreak nothing prevents you from doing it asynchronously, or in steps, so it's not an issue.
    – Ismael Luceno
    Dec 10, 2013 at 1:22
  • 1
    @Ismael you still need a thread safe counter with atomic increment/decrement. These things don't grow on trees. At the very least, you prevent two threads from referencing/unreferencing the same object at the very same clock cycle and you cause a lot of cache stalling because the cache page ownership jumps around the cores like crazy, for pretty much every memory page. Cache stalling hurts.
    – John Dvorak
    Dec 10, 2013 at 6:08
  • @JanDvorak if it's atomic, it's thread-safe, and you have at least atomic exchange in most architectures.
    – Ismael Luceno
    Dec 26, 2013 at 20:00
2

A reference in a 64-bit JVM typically use 4-bytes of memory (using compressed oops) This means using a reference count will increase the size of memory per object, but also increase complexity of passing references around. Every time a thread anywhere has to obtain a reference to an object it need to increment and later decrement the counter, something a GC basis system doesn't need to to do.

BTW in C++ a shared pointer has two pointers (each 64-bit) one to the object and one to the reference counter. On many systems this reference counter uses 32-bytes as this is the minimum allocation cost. In total shared pointers replace a 4-byte reference with a 16 bytes shared pointer and a 32 byte reference. That doesn't sound very CPU cache friendly.

The problem with JVM GCs is the stop-the-world collections which are fine for throughput processing but a real pain for low latency systems. One way around this is to use a concurrent collector, the best being Azul's Zing which is pause less (though not pauseless ;)

Improve this answer
2

Garbage collection based on reference counting is much slower than tracing garbage collectors (Boost shared_ptr vs other solutions, or you can find links to more scientific comparisons at the Boehm GC's website). In addition, reference counting alone is insatisfactory, because it cannot deal with reference cycles.

C++ programmers tend to think about memory as just a resource, since C++ manages memory and other resources the same way. Garbage collection is special approach that can only manage memory, which is in fact the most often used resource.

This often confuses C++ programmers - they tend to think of finalizers as a poor substitute for C++ destructors, which they are not. To release sparse resources (not memory) in a deterministic manner, use finally blocks.

Improve this answer
2
  • Can you please add a comment briefly stating the reason of the downvote?
    – user99541
    Dec 10, 2013 at 15:05
  • I assume they didn't like the idea C++ developers get confused... I find its the GC devs that think finalisers are an equivalent of C++ destructors, not realising that GCs require manually managing object lifetimes, like C. Have a +1 for pointing that out though.
    – gbjbaanb
    Dec 10, 2013 at 16:35

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