Everybody thinks about garbage collection the wrong way (2010)

http://blogs.msdn.com/b/oldnewthing/archive/2010/08/09/10047586.aspx

by derefr • 13 years ago

73 43 13 years ago

blogs.msdn.com

rdtsc• 13 years ago

In case someone missed it, this is more about releasing external resources than GC per se. (There is an interesting analogy of how GC simulates a machine with infinite memory).

but there are things you can do even if you have infinite memory that have visible effects on other programs

Moreover there are things you can do even without having these external resources that will mess up your program and that is just running the GC in a highly concurrent application. Except for systems with separate per/thread/actor heaps, when memory is allocated vigorously GC runs will start to affect your latency and parts of the program will get blocked and frozen.

As for releasing resources. In vital systems it is important to run watchdogs that release resources on behalf of a the main applications. Sometimes processes crash hard, segfault, and may not run their own finalizes. So these resource lists might have to be sent to a watchdog process whose only job is to monitor for the original program crashing and then releasing these resources.

rational_indian2• 13 years ago

Garbage collection is simulating a computer with an infinite amount of memory

I think he means "infinite amount of virtual memory". Virtual memory already tries to "simulate a computer with an infinite amount of (random access) memory". This makes me wonder if virtual memory can be used as a poor man's garbage collector?

knz42• 13 years ago

Virtual memory can be used as "poor man's GC" only with languages with a variable number of bits in pointers (references). If you have a fixed number of bits in your pointers, like in C & C++, then you will run out of addresses eventually, even with virtual memory.

rational_indian2• 13 years ago

Yup! Virtual memory as a poor man's GC seems to be viable for short lived programs with modest virtual memory requirements. I seem to recall Walter Bright using something along the same lines to replace malloc/free in the D compiler code. It lead to a significant improvement in performance.

hannibal5• 13 years ago

Copying garbage collectors benefit from virtual memory.

Copying GC needs two same sized memory pools. One is used and one is empty. If you have same amount of virtual memory as ram, the empty unused one can reside in the virtual memory. When GC happens live data is copied (and compacted) from live pool to empty pool and the roles switched. With virtual memory, you can use as much ram as there is without affecting performance significantly.

If you do manual memory management, long running programs cause memory fragmentation. If allocated memory sizes are very variable in size, available memory can be half of the actual memory in the long run.

In theory, moving and compacting GC with virtual memory can almost double the available ram compared to manual memory management.

nostrademons3• 13 years ago

BTW, it's not unheard of for short-lived command line utilities or multiprocess apps to literally run with the null garbage collector. They just never free memory and deliberately leak it until they exit, at which point the OS cleans it up. If you expect total RAM requirements to be a few hundred K on a multi-G system, this is completely reasonable, and faster than either manual or automatic memory management to boot.

The analog in a long-running program is an arena: it keeps allocating memory indefinitely, and then frees it all in one clump when the program is done with that phase of operation.

Multi-process languages like Erlang sometimes use this approach as a degenerate case of a stop & copy garbage collector. They start a process with a young generation heap sized large enough to contain all the memory the process will ever allocate (you can get reasonable estimates on this from previous runs), and so the GC never triggers and all the memory is freed in one block when the process terminates.

joe_the_user4• 13 years ago

The QT C++ framework consciously decides to not deallocate the stuff that only get allocated once. The result is that running leaking catching tools is very hard. Not necessarily the greatest outcome despite being a logically defensible move.

lmm2• 13 years ago

QT is big and popular enough that I would expect tools to have support for it.

gngeal• 13 years ago

Wouldn't a creation of the equivalent of a permspace and instructing said tools to ignore it mitigate the problem?

icefox• 13 years ago

Can you be more specific? The common case in Qt (not QT) is that a QObject has a parent and when the parent is destroyed all of the children are too.

rcthompson2• 13 years ago

There was an article on HN a few days ago about how the Digital Mars D compiler was using the null garbage collector and modified its allocation strategy to take advantage of this to yield a major speedup.

alcari• 13 years ago

Here's the referenced article. It's quite interesting: http://www.drdobbs.com/cpp/increasing-compiler-speed-by-over...

derleth• 13 years ago

They just never free memory and deliberately leak it until they exit

Which is a great way to kill that process, or arbitrary processes, when a previously well-behaved program is run on a system that's a bit strapped for RAM at the moment, or run on a somewhat larger-than-usual input, or both.

That, or bring the system to a standstill as the swapping subsystem flogs the disk nonstop.

Possibly first one, and then the other.

xyzzy123• 13 years ago

Well, you never have guarantees that this won't happen even if you free().

Reasonable resource consumption is an engineering decision based on context (target, expected problem size, etc).

Deliberate leaking is IMHO a totally viable engineering strategy. If anything, behaviour is actually more reliable and predictable than the alternatives apart from "upfront static allocation".

If you ran into problems and want the entire system to behave predictably, you could on Linux disable vm overcommit, set oom_adj (so leaker proc gets killed preferentially), set strict ulimits and ensure abort() on malloc failure. However if you have to go to these lengths, leaking might not be appropriate ;)

nostrademons3• 13 years ago

For a lot of these simple command-line utilities, it wouldn't matter anyway. They often work by building up some data structure that's then used to process the rest of the input line-by-line, and then the program exits. If the data structure is never freed, so what? It's needed until the end of execution anyway.

Think of compiled regular expressions for grep, or total counts for wc, or a rotating line buffer for tail, or the previous line for uniq.

It's quite possible to get pathological behavior even with GC or careful RAII, as anyone who's ever leaked memory in a Java program could tell you. Simulating a computer with infinite memory breaks down when the working set you're touching exceeds the physical RAM of the machine. Actually, leaking memory is the least of your concerns in that case, as leaked memory just gets paged out and doesn't cause any problems unless it exceeds the computer's address space.

Retric• 13 years ago

If your five orders of magnatude below system RAM and the OS runs out of memory then it's someone else's problem. Granted the system might runout of swap space due to say the 100kb you allocated but reolistically other things that take up ~100,000 times as much space collectively are the actual problem.

mikeash3• 13 years ago

What kind of systems are you running where a few hundred kilobytes of allocation on a machine with gigabytes of memory can "bring the system to a standstill"?

lucian1900• 13 years ago

Erlang processes are green threads, not system processes. It is true that they each have their own heap, but the heaps are GC-ed.

nostrademons3• 13 years ago

I know that they're green threads. I thought the implementation was that the heap itself is malloc'd from the OS and then freed when the process terminates. Within the heap, of course, it uses GC, but if you set the heap size at process creation > the total memory allocated, then the GC never runs and the heap essentially becomes an arena.

coldtea• 13 years ago

BTW, it's not unheard of for short-lived command line utilities or multiprocess apps to literally run with the null garbage collector.

If I am not mistaken, PHP scripts use precisely that.

And they can get away with it, because they are short-lived.

anonymous4• 13 years ago

The apache http server uses that allocation strategy, actually. For each request you have a separate memory pool and you allocate out of that. There's no function to free memory you've got from a pool and the entire pool is destroyed/released after the request has been served.

mikeash3• 13 years ago

This sounds great if it's just a switch you can pull to turn off the garbage collector, but I wanted to pipe up to strongly recommend against this approach if you're working in an environment with manual memory management. It can be tempting to write code that calls malloc but never calls free, because you know that the process is short-lived and it's pointless. The problem comes when your requirements change or you reuse some code, and suddenly that memory needs to be cleaned up. It's far more painful to go back and insert the cleanup calls after the fact than it is to get them in the right place when you write the code. I did this once, and never again.

joe_the_user4• 13 years ago

The argument seems logical as far as it goes. But having a piece of code which may or not run seems to introduce inherently greater mental complications into the programming process.

lmm2• 13 years ago

Finalizers are almost inherently a bad idea in garbage-collected languages; the best practice is simply not to use them. If you're trying to do C++-style RAII (a very good idea!) you want something like Java 7's try-with-resources.

salmonellaeater• 13 years ago

The key point is that finalize() is not reliable, so you shouldn't depend on it. The correct idiom is more or less

  myResource = foo();
  try {
     ...
  } finally {
     myResource.release();
  }

Some programmers (although I've never met one) try to avoid this boilerplate by writing a finalize() method on myResource that releases it. It's an anti-pattern. C# and Java have syntactic sugar now that makes the boilerplate shorter, which should help.

barrkel• 13 years ago

You program as if you don't have finalizers. Finalizers really are just a safety net.

cousin_it• 13 years ago

Question to people who have used finalizers in GC languages: can you describe what you used them for?

anonymoushn• 13 years ago

I worked on some extremely filthy project that, among other things, sent data over the network in a constructor and finalizer so that a clone of a subset of the program's state could be maintained remotely. You just had to inherit from this class and suddenly you would have a clone all the time.

anonymous4• 13 years ago

Look at the FileInputStream and FileOutputStream classes in Java. The finalize method in them makes sure the file is closed when the object is reclaimed, to prevent file handle leaking.

It's not particularly effective a strategy for managing file handles unfortunately and if you forget to close your output streams, your program will crash with "too many open files".

bcoates• 13 years ago

If you call out to a C-style library through the FFI that's expecting a cleanup call, you should call it in both a user-accessible close() function and the finalizer.

I think the easiest way to think about it is, "finalizers don't prevent handle leaks, they sometimes clean up a handle leak that already happened".

I'm not sure if any debugger environments give a warning when a finalizer gets run due to GC but they ought to--it always indicates a programmer error.

tehwalrus3• 13 years ago

This article got me thinking - I use quite a lot of C/C++ python extensions, and I'm wondering if I could wrap some of my malloc calls (particularly the ones that store an "inner C++ object" on a python class) as python byte strings that are then pointer-cast to RAM for C++ to use, and then tidied up by the garbage collector rather than a manual delete call later.

The only difficulty I can see is persuading the C++ constructor to run on an arbitrary address?

WorksOnRobots• 13 years ago

Pass the address of the block of memory to the constructor along with your other arguments and perhaps the length of the memory block (to assert that sizeof(block) >= sizeof(object)). Then use a C-style cast to cast the block of memory to your class. Construct the object like normal and return the address.

anonymous4• 13 years ago

You can persuade the C++ constructor to run on an arbitrary address trivially with "placement-new". See here https://en.wikipedia.org/wiki/Placement_syntax . In short, you can do:

    void* mem;
    ... snip ...
    MyClass* thing = new (mem) MyClass;

And that doesn't allocate memory, but calls the constructor on the mem pointer. You are responsible for having allocated enough memory. You cannot call delete normally on this object though. You'll need to call the destructor manually as such:

    thing->~MyClass();

before the memory is deallocated. If the destructor doesn't actually do anything, you can safely skip this.

tehwalrus3• 13 years ago

Thanks, that's very helpful!

I am blissfully unaware of almost all C++ specific syntax beyond basic class definitions, as I use it to add the odd syntactic construct to C (like operator overloads for + etc for my math 2- and 3-vectors) so I had no idea of this.

Yhippa• 13 years ago

I didn't quite grok the concept of GC as simulating infinite memory. After some research I ended up at, what else, SICP (http://mitpress.mit.edu/sicp/full-text/sicp/book/node119.htm...) with an explanation. Hope this helps someone else.

The representation method outlined in section [http://mitpress.mit.edu/sicp/full-text/sicp/book/node118.htm...] solves the problem of implementing list structure, provided that we have an infinite amount of memory. With a real computer we will eventually run out of free space in which to construct new pairs.[http://mitpress.mit.edu/sicp/full-text/sicp/book/footnode.ht...] However, most of the pairs generated in a typical computation are used only to hold intermediate results. After these results are accessed, the pairs are no longer needed--they are garbage. For instance, the computation

(accumulate + 0 (filter odd? (enumerate-interval 0 n)))

constructs two lists: the enumeration and the result of filtering the enumeration. When the accumulation is complete, these lists are no longer needed, and the allocated memory can be reclaimed. If we can arrange to collect all the garbage periodically, and if this turns out to recycle memory at about the same rate at which we construct new pairs, we will have preserved the illusion that there is an infinite amount of memory.

twotwotwo• 13 years ago

If the amount of RAM available to the runtime is greater than the amount of memory required by a program, then a memory manager which employs the null garbage collector (which never collects anything) is a valid memory manager.

A bit of a tangent, but I wonder GC is one reason Android devices moved to larger RAM sizes faster than iOS did. (iPhone 5 == 1GB, GS3/N4/One == 2GB.)

Under manual memory management or refcounting, running with RAM 90% full isn't slower than 50% full. (Your app code isn't slower, at least; who knows it if has effects via OS having less for cache or whatever.) But under GC, if 90% of RAM is full of live objects, you'll be forced to GC several times as often as you would if only 50% of RAM were full. So that 1GB->2GB bump might actually _more_ than halve how often you have to collect.

There could be other reasons for the diff--maybe part of it is Android's more permissive multitasking model, maybe non-GC-related memory-use differences between Android/Java and iOS/ObjC, maybe greater focus on power consumption from Apple or greater focus on specs from Android handset makers.

Everybody thinks about garbage collection the wrong way (2010)

Related Stories