3

I was reading R. Read's How to be a programmer, and I came accross something I didn't understand:

...even with garbage collection, you can fill up all memory with garbage. A classic mistake is to use a hash table as a cache and forget to remove the references in the hash table. Since the reference remains, the referent is noncollectable but useless. This is called a memory leak. You should look for and fix memory leaks early. If you have long running systems memory may never be exhausted in testing but will be exhausted by the user.

So let's say I have a dictionary structure in python, indexed on md5 hashes (is this the kind of hashtable he's referring to?). Eg:

x = {}
x['c4ca4238a0b923820dcc509a6f75849b'] = 1
x['c81e728d9d4c2f636f067f89cc14862c'] = 2

Can someone now walk me through his example? What do I have to do now concretely to cause a memory leak?

  • 1
    A memory leak is memory that is unreachable but not returned to the free store. That only happens in non-GC languages. Sometimes the term is also used to refer to memory that is still referenced but never used in practice which is applicable to GC and non-GC languages. This is often due to large temporary variables or large quantities of temporary variables that remain in scope too long. – user22815 Jan 26 '15 at 21:13
  • No, memory leaks can occur in garbage collected languages, because a GC could keep some useless data (because that data stays reachable) – Basile Starynkevitch Jan 26 '15 at 21:14
  • So ... what's the relevance of screwing up the scope of your variable declarations to the hash table example? – Escher Jan 26 '15 at 21:29
  • 2
    It is very clear that even with a GC language, programming errors can result in memory usage growing until the machine becomes unusable. You can certainly say that this is caused by programmers who stupidly forgot to ensure that the references went away, but is this really different from the C++ programmer who forgot to call delete? – Steven Burnap Jan 26 '15 at 21:44
  • It's not technically a leak of memory because it's still being managed correctly and never fell through a crack to get somewhere it didn't belong. It's semantically a leak of memory because it's memory space being wasted on values you never plan to look up again. If you never remove entries from a dictionary regardless of them being totally unnecessary, that memory will never be reclaimed or used-> Managed and maintained but wasted. Semantically a leak, just not one due to technical failures. – Jimmy Hoffa Jan 26 '15 at 23:50
5

It's pretty basic. Walk through the code:

x = {}

Memory reserved for overhead

x['c4ca4238a0b923820dcc509a6f75849b'] = 1

Memory for one key/value pair allocated

x['c81e728d9d4c2f636f067f89cc14862c'] = 2

Memory for two key/value pairs allocated

Now imagine we do this 10,000 times. We will have allocated space for 10,000 key/value pairs. Each hash added increases memory usage. If these values will indeed never be used again, they are "useless", but since you've told python to save them, they will not be collected. You'd need to remove the reference like this:

del x['c4ca4238a0b923820dcc509a6f75849b']

You have to do this because in general, the garbage collector can't know that you are never going to look this value up.

The case talked about here is using a dictionary as a cache, and presumably you don't really know if you will need a particular value. Also, presumably, there's no real limit to the number of values. So with a long-running app, you could conceivably exhaust memory. You'd need to have some scheme to delete elements from the cache when they are no longer needed, presumably by testing recency of use.

GC can't help you here any more than it can help you if you attempt to allocate a 100 gigabyte array. You've told it explicitly through referencing not to discard any of the data.

  • And so the significance to Robert Read's hashtable example is that you have a giant hash table whose keys don't refer to anything important that you'll ever look up anymore? – Escher Jan 27 '15 at 7:48
  • In a cache, you are saving data not because it is required, but to speed things up. Also, often when you cache, the behavior is to need to grab the data a bunch of times in a limited timeframe, usually backing a user session. – Steven Burnap Jan 27 '15 at 13:23
0

To me the semantics don't matter. A program is leaky if it starts using up a boatload of memory and running slower and slower the longer you run it, like a video game which requires you to restart every 30 minutes because the frame rates keep dropping the longer you play it while it goes from taking megabytes to gigabytes of memory. Most games that exhibit these leaky symptoms use garbage collection and for a good reason: garbage collection tends to exchange immediately reproducible crashes for leaks that fly under the radar.

In that sense above, it can actually be easier to introduce leaks into a program built using a language with GC, since all you have to do to root a resource and prevent it from being freed is store a reference to it.

As a simple example, let's say you have a video game which has a physics system to move particles around and a renderer to render a list of particles it references as well. When a particle dies, it fades off the screen and stops being visible, at which point the physics system removes it from the list of particles to process.

Voila, now you have a leak because you didn't remove the particle reference from the renderer. However, it won't be obvious in game because the dead particles have an opacity of zero. Nevertheless, the game would be creating a bigger and bigger list of particles that are never freed until the game is shut down, and spending more and more time in increasingly larger loops in the renderer as the particle list grows larger and larger. This might fly under the radar of the developers indefinitely to the point where they actually suggest to users to restart the game from time to time if it gets slow while bumping up the system requirements to beefy machines even for a simple 2D game.

Meanwhile in C, this would have simply lead to an immediately detectable crash since the physics system would have manually destroyed the particle when it died. The renderer would then try to access a particle which was destroyed and most likely come crashing down during the first play test which is arguably more preferable in this case than having game-halting leaks which go unsolved indefinitely.

A very firm way to avoid this problem is to rely on concepts like weak and phantom references and decide who actually manages the particles. If it's the physics system, then the renderer should keep weak references to particles so that it doesn't prolong their lifespan and can detect when they are destroyed and hopefully even run into a game-halting error if the renderer tries to access a particle that no longer exists.

In general GC doesn't protect you against having to think about resource management and who owns a resource and having to manually free resources (assigning them as none/nil/null) to avoid logical leaks. Its primary usefulness in my opinion is in the context of areas like multithreading where you want to ensure that an object is not destroyed until a thread is finished processing the object.

The ideal solution to me if a language could ever provide it at the native language level (C++ is the closest I can think with shared_ptr, but it's a library concept and can't detect cycles since it uses basic ref counting) is one that could let you opt into garbage collection per object. For example, perhaps the object is normally destroyed when it either goes out of scope or is assigned a null, and everything that references it outside of its immediate scope effectively acts as a pointer to it, not preventing the object from being destroyed. However, something that wants to share ownership of that object, like a thread, could call a ref method to increase its reference count and deref to decrement it to prevent it from being destroyed until the thread is finished using it, or it could use some kind of shared reference concept that avoids the need for an explicit deref in the thread's scope, with a "pay as you use it" cost.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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