13

If I have a garbage collector that tracks every object allocated and deallocates them as soon as they no longer have usable references to them can you still have a memory leak?

Considering a memory leak is allocations without any reference isn't that impossible or am I missing something?

Edit: So what I'm counting as a memory leak is allocations which you no longer have any reference to in the code. Large numbers of accumulating allocations which you still have references to aren't the leaks I'm considering here.

I'm also only talking about normal state of the art G.C., It's been a while but I know cases like cyclical references don't trip them up. I don't need a specific answer for any language, this is just coming from a conversation I was having with a friend. We were talking about Actionscript and Java but I don't care for answers specific to those.

Edit2: From the sounds of it, there doesn't seem to be any reason code can completely lose the ability to reference an allocation and not have a GC be able to pick it up, but I'm still waiting for more to weigh in.

5
  • The definition of "memory leak" is not at all the cut and dried. I suggest you tighten your definition, with references. May 14, 2012 at 4:37
  • Not downvoted yet, but since you have not provided your definition of "memory leak" and type of GC you have in mind it is not surprising. Also check if it is not related to homework of a kind and add "homework" tag if needed. May 14, 2012 at 4:38
  • Not homework at all, just was talking with a friend about actionscript and java and I don't know if leaks are a problem or not for them. May 14, 2012 at 4:40
  • I also was more specific about those other definitions thanks. But yeah I got downvoted in the very beginning but it went away.. May 14, 2012 at 4:46
  • I don't consider "memory leak" particularly ambiguous. Essentially, a program has a memory leak iff it would require an unbounded amount of memory to process a sequence of inputs that repeats an unbounded number of times after some point, even though those inputs would only put it into a bounded number of observable states. I suppose there are some cases where the term might be ambiguous (e.g. a program which determines whether the number of lines in a file is even or odd by buffering the file and then outputting the result). Arguably, such a program only has two observable states.
    – supercat
    May 14, 2012 at 17:01

4 Answers 4

19

If your question is really this:

Considering a memory leak is allocations without any reference isn't that impossible or am I missing something?

Then the answer is "yes, that's impossible" because a properly implemented garbage collector will reclaim all allocations that don't have active references.

However, you can definitely have a "memory leak" in (for example) Java. My definition of a "memory leak" is an allocation that still has an active reference (so that it won't be reclaimed by the garbage collector) but the programmer doesn't know that the object isn't reclaimable (ie: for the programmer, this object is dead and should be reclaimed). A simple example is something like this:

ObjectA -> ObjectB

In this example, ObjectA is an object in active use in the code. However, ObjectA contains a reference to ObjectB that is effectively dead (ie: ObjectB has been allocated and used and is now, from the programmer's perspective, dead) but the programmer forgot to set the reference in ObjectA to null. In this case, ObjectB has been "leaked".

Doesn't sound like a big problem, but there are situations where these leaks are cumulative. Let's imagine that ObjectA and ObjectB are actually instances of the same class. And this problem that the programmer forgot to set the reference to null happens every time such an instance is used. Eventually you end up with something like this:

ObjectA -> ObjectB -> ObjectC -> ObjectD -> ObjectE -> ObjectF -> ObjectG -> ObjectH -> etc...

Now ObjectB through ObjectH are all leaked. And problems like this will (eventually) cause your program to crash. Even with a properly implemented garbage collector.

7
  • This answer seems best, but the example is slightly unclear to me: are you saying the code does or doesn't still have a reference to ObjectA? Jun 15, 2012 at 17:48
  • There is still a reference to ObjectA. It is still in use. So it is a "live" object (both from the GC-perspective and from the programmer's perspective). However, there is a chain of dead objects that the GC is unable to reclaim because ObjectA still holds a reference to the head of the chain. The programmer just forget to null out that reference. For the programmer, these objects should be reclaimed, but due to his forgetfulness (or lazyness), the GC won't reclaim them. Jun 15, 2012 at 19:41
  • @RobotRocker: There is a difference between saying "Object A has a reference to Object B", and saying "Object A has a reference to Object B that it actually cares about". A memory leak exists in situations where the percentage of live objects that no rooted object actually cares about would asymptotically approach 100%, given enough time and memory.
    – supercat
    Aug 17, 2012 at 19:57
  • @supercat, I would argue that a memory leak does not have to crash the program, thus the percentage of live objects that no rooted object cars about would not have to approach 100%, given enough time and memory. Consider the situation where it asymptotically approaches 50%. The program is now using twice as much memory as it needs to. This is a leak if it can be avoided.
    – CaTalyst.X
    Apr 17, 2013 at 18:57
  • @CaTalyst.X: There are many things that could cause a program to require twice (or even 10x) as much memory as it "needs" to but would hardly be termed memory leaks. For example, a program which creates a lot of List<Guid> but ends up putting an average of two items in each would use only 1/8 of the space allocated to hold the GUIDs (if even that), but would hardly be "leaky". I would argue that there is a qualitative difference between a program which, given a certain infinite stream of input, could satisfy its memory needs with finite RAM, and one which cannot.
    – supercat
    Apr 17, 2013 at 19:08
3

To decide whether a program has a memory leak, one must first define what a leak is. I would define a program as having a memory leak if there exists some state S and series of inputs I such that:

  1. If the program is in state `S` and it receives inputs `I`, it will still be in state `S` (if it doesn't crash), but...
  2. The amount of memory required to repeat the above sequence `N` times will increase without bound.

It is definitely possible for programs that run entirely within garbage-collected frameworks to have memory leaks as defined above. A common way in which that can occur is with event subscriptions.

Suppose a thread-safe collection exposes a CollectionModified event, and the IEnumerator<T> returned by its IEnumerable<T>.GetEnumerator() method subscribes to that event on creation, and unsubscribes on Dispose; the event is used to allow enumeration to proceed sensibly even when the collection is modified (e.g. ensuring that objects are in the collection continuously throughout the enumeration will be returned exactly once; those that exist during part of it will be returned no more than once). Now suppose a long-lived instance of that collection class is created, and some particular input will cause it to be enumerated. If the CollectionModified event holds a strong reference to every non-disposed IEnumerator<T>, then repeatedly enumerating the collection will create and subscribe an unbounded number of enumerator objects. Memory leak.

1

Memory leaks don't just depend how efficient a garbage collection algorithm is, if your program holds on to object references which have long life time, say in an instance variable or static variable without being used, your program will have memory leaks.

Reference count have a known problem of cyclic refernces meaning

Object 1 refers to Object 2 and Object 2 refers to Object 1 

but no one else refers to object 1 or Object 2, reference count algorithm will fail in this scenario.

Since you are working on garbage collector itself, its worth reading about different implementation strategies.

3
  • will it work if the developer himself checks that both the objects are marked as null if they want it to be deleted?
    – linuxeasy
    May 14, 2012 at 4:50
  • Thanks for the linkage I'll definitely take the reading material. Most GC I thought could handle cyclical references though. May 14, 2012 at 4:52
  • 1
    @RobotRocker yes the modern gc's can handle cyclic reference count
    – mprabhat
    May 14, 2012 at 4:54
0

You can have memory leaks with a GC in another way: if you use a conservative garbage collector that naively scans the memory and for everything that looks like a pointer, doesn't free the memory it "points to", you may leave unreachable memory allocated.

2
  • I'm reading the link you provided but it seems that that is using a less than ideal garbage collector. Jun 15, 2012 at 17:45
  • Well, if you can always reconstruct the graph of exactly those objects in memory that are reachable, then you should use a precise garbage collector, not a conservative one (which is indeed "less than ideal"). However, conservative garbage collectors are used in practice, in implementations where such information is not available, see this link for some details: hpl.hp.com/personal/Hans_Boehm/gc/conservative.html
    – gfour
    Jun 15, 2012 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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