Everybody thinks about garbage collection the wrong way (2010)(blogs.msdn.com)
blogs.msdn.com
Everybody thinks about garbage collection the wrong way (2010)
http://blogs.msdn.com/b/oldnewthing/archive/2010/08/09/10047586.aspx
8 comments
>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.
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.
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.
You program as if you don't have finalizers. Finalizers really are just a safety net.
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.
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();
}
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.
> 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.
>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?
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?
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.
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.
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.
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.
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.
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.
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.
Here's the referenced article. It's quite interesting: http://www.drdobbs.com/cpp/increasing-compiler-speed-by-over...
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.
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.
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.
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.
See: http://stackoverflow.com/questions/1593717/is-anyone-using-v...
When I googled that, I found QT apparent has created some suppression files to help with using Valgrind. But I'm pretty sure that's recent and users struggled for a while with QT's approach.
http://developer.nokia.com/Community/Wiki/Using_valgrind_wit...
When I googled that, I found QT apparent has created some suppression files to help with using Valgrind. But I'm pretty sure that's recent and users struggled for a while with QT's approach.
http://developer.nokia.com/Community/Wiki/Using_valgrind_wit...
QT is big and popular enough that I would expect tools to have support for it.
Wouldn't a creation of the equivalent of a permspace and instructing said tools to ignore it mitigate the problem?
It might but that would be a matter for whoever is now developing QT itself.
>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.
If I am not mistaken, PHP scripts use precisely that.
And they can get away with it, because they are short-lived.
Erlang processes are green threads, not system processes. It is true that they each have their own heap, but the heaps are GC-ed.
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.
> 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.
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.
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.
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.
Actually, with tail -f that could become a problem.
I don't see how it could. Tail doesn't use more memory as it reads more lines. It sets up a fixed-size buffer and then continually re-uses it. Yes, "tail -f" could be a long-running process, but its memory usage should remain constant over its entire lifetime.
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 ;)
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 ;)
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.
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"?
Question to people who have used finalizers in GC languages: can you describe what you used them for?
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.
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.
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".
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".
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.
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?
The only difficulty I can see is persuading the C++ constructor to run on an arbitrary address?
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;
thing->~MyClass();
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.
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.
If you want to learn more, I'd suggest at first reading (or at least skimming) Bjarne Stroustrup's "The C++ programming language".
Also, the C++ FAQ http://www.parashift.com/c++-faq/ is useful for getting an overview on the corner cases of C++.
After which you should visit its inverse, the C++ FQA (frequently questioned answers, i.e. an anti-C++ answer to the FAQ) http://www.yosefk.com/c++fqa/ to learn why no-one in their right mind would ever use C++.
That won't teach you C++ per se, but would give you a useful look at the breadth of the language and how and why things happen the way they do.
Also, the C++ FAQ http://www.parashift.com/c++-faq/ is useful for getting an overview on the corner cases of C++.
After which you should visit its inverse, the C++ FQA (frequently questioned answers, i.e. an anti-C++ answer to the FAQ) http://www.yosefk.com/c++fqa/ to learn why no-one in their right mind would ever use C++.
That won't teach you C++ per se, but would give you a useful look at the breadth of the language and how and why things happen the way they do.
Thanks. I have got a copy of a Stroustrup on my shelf (I think it's a standard library reference, not the language definition) and I've been developing in "C with classes" for a while, so I've discovered quite a few of the pitfalls. I prefer to let clang++ point out when I stumble across something insane, like:
There is one OSS project I know that I never want to emulate: the code literally fails to compile via the python installer until you have run the makefile at least once, by which time it's finished generating all the header files. Whiskey Tango Foxtrot!
[1] https://github.com/orangeduck/libCello
vector<vector<T>> // wrong, uses a >> operator?!
vector<vector<T> > // compiles correctly.
There is one OSS project I know that I never want to emulate: the code literally fails to compile via the python installer until you have run the makefile at least once, by which time it's finished generating all the header files. Whiskey Tango Foxtrot!
[1] https://github.com/orangeduck/libCello
I'd like to mention that, while the FQA pulls no punches and is often sarcastic or worse, it's still a great read and will teach you a lot about C++ even if you disagree with the idea that nobody should use the language. Don't be scared off by that "no-one in their right mind" thing.
Although, if you read through it and subsequently decide that C++ is not the best language to use, I wouldn't call that the worst outcome....
Although, if you read through it and subsequently decide that C++ is not the best language to use, I wouldn't call that the worst outcome....
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.
>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.