The Artima Developer Community
Sponsored Link

Weblogs Forum
Myths of Memory Management

81 replies on 6 pages. Most recent reply: Sep 12, 2005 6:10 PM by Max Lybbert

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 81 replies on 6 pages [ « | 1 2 3 4 5 6 | » ]
Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: Myths of Memory Management Posted: Sep 5, 2005 7:46 AM
Reply to this message Reply
Advertisement
> > The problem with lack of GC is that certain kinds of programming
> > styles and abstractions become either impossible or impractical.

> You can give a specific example?

The problem with specific examples, in this specific context, is that it is difficult to see the forest from the trees. I'm pretty sure that whatever specific example I gave you (and I do have some) there are ways to get something similar without GC. The problem is that the complexity you need to implement those things without GC is distributed and you can't easily abstract it away. In other words, in each particular case the complexity (without GC) can be argued to be acceptable, but on the whole, the distributed complexity significantly hampers the ability to use certain programming styles or abstractions. [In general, anything that involves manipulating non-trivial data structures (even trees), makes non-trivial use of higher-order programming (combinator libraries), or involves playing with evaluation order, suffers greatly without GC.]

The snippet of code we were discussing demonstrates one issue that arises when you don't have GC. The problem is that you can not easily design modules that are invariant with respect to memory management. In other words, the interface of every module must make some commitments regarding memory management. For instance, you might have a module either sharing a resource or taking the ownership of the resource. Unfortunately, there can be situations in which different clients would prefer different behaviors. It may be inappropriate or costly to transfer the ownership or it may be inappropriate or costly to share the ownership.

Under explicit memory management, all interfaces become riddled with complexity related to memory management. Explicit memory management essentially imposes a cost in the form of distributed fat (complexity in every interface). Without GC, your code will always be more complicated than with GC (which is appropriate in all but a few memory management situations).

> This is common code in Java-like languages, where people ignore the
> concern of ownership. A module should either be explicitly sharing a
> resource, or owning a resource.

Whether a resource given to a server module should be shared or the ownership trasnferred may depend on the properties of the client module rather than the server module. Without GC, all interfaces become riddled with memory management protocols rather than just the few interfaces where it makes sense.

> A module which creates an object, should also destroy it. Not doing so,
> makes it impossible to manage resources and accurately predict how your
> software will use resources, which is why I say GC'd code sucks at
> resource management.

Why do you think that GC prevents a module from releasing the resources it creates?

Michael Feathers

Posts: 448
Nickname: mfeathers
Registered: Jul, 2003

Re: Myths of Memory Management Posted: Sep 5, 2005 7:52 AM
Reply to this message Reply
> No problem, I guess it is apparent that I am a big fan of
> the bondage and discipline approach to programming
> language design.

But, here's the rub. People usually want static typing because it is "safer." Less surprises at runtime. Opting for an exception rather than undefined behavior (as in C++) is still a surprise, and the typical programmer will abort because there is no good place to handle that exception except at every delete or the top level.

Dropping GC and using exceptions for improper deletion puts statically typed languages right into the same sphere of reliability as dynamically typed languages. It's not a bad place to be, but it's inconsistent with the static typing agenda. It trades runtime safety for performance. C++ does that all over the place without flinching, but it is hard to sell that idea outside of that community.

Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: Myths of Memory Management Posted: Sep 5, 2005 8:17 AM
Reply to this message Reply
> Explicit management in the explicit management scheme I
> outlined is not more expensive than a GC, it should be at
> most precisely the same. When the programmer explicitly
> calls delete, the system doesn't have to actually
> deallocate the block right away it could simply pass it to
> a GC.

Even when an object would have en empty destructor, you would need to somehow mark the object deleted. This means touching some area of memory. The cost of even a single access (read or write) may be extremely high if the target of the access has been paged to disk by the OS. When a delete causes a cascade (recursive deletion of a complex data structure), the effect on performance can be devastating.

Even if this isn't the case (paging isn't involved), the explicit call of delete (marking the object deleted) has a cost. Furthermore, some forms of GC only traverse live objects. By requiring the GC to walk the dead, you are committing yourself to forms of GC whose performance characteristics clearly aren't always optimal.

Brian Slesinsky

Posts: 43
Nickname: skybrian
Registered: Sep, 2003

Re: Myths of Memory Management Posted: Sep 5, 2005 1:10 PM
Reply to this message Reply
>> If a design calls for object O to be deleted on condition C, but some
>> other module M continues to reference O, then O will continue to be kept
>> alive. This is a design error, and damn hard to detect.

> [The error may also be that the condition C is wrong.]

Well, this can be true of any assertion, but that doesn't stop us from making assertions that we *think* are true. Making an assertion and finding out we're wrong is a good way to gain better understanding of the code. The only thing I would object to is being forced by the language to make an assertion about memory when it's better to leave it unspecified.

It may be that some assertions about memory usage are expensive, which is why they should be optional and preferably part of unit tests rather than production code.

In Java it's difficult to make certain interesting assertions, such as "this object is only used in one thread", or "this object will be freeable after this method exits". Figuring out how to add these to a language while still having efficient, automatic garbage collection would be pretty valuable.

Anjan Bacchu

Posts: 18
Nickname: anjanb
Registered: Mar, 2002

Re: Myths of Memory Management Posted: Sep 6, 2005 1:29 PM
Reply to this message Reply
hi there,

pls. see Brian Goetz's article on IBM developerworks about GC in javaa -- http://www-128.ibm.com/developerworks/java/library/j-jtp01274.html

relevant excerpts below
========================
Explicit nulling is simply the practice of setting reference objects to null when you are finished with them. The idea behind nulling is that it assists the garbage collector by making objects unreachable earlier. Or at least that's the theory.

There is one case where the use of explicit nulling is not only helpful, but virtually required, and that is where a reference to an object is scoped more broadly than it is used or considered valid by the program's specification. This includes cases such as using a static or instance field to store a reference to a temporary buffer, rather than a local variable (see Resources for a link to "Eye on performance: Referencing objects" for an example), or using an array to store references that may remain reachable by the runtime but not by the implied semantics of the program. Consider the class in Listing 3, which is an implementation of a simple bounded stack backed by an array. When pop() is called, without the explicit nulling in the example, the class could cause a memory leak (more properly called "unintentional object retention," or sometimes called "object loitering") because the reference stored in stack[top+1] is no longer reachable by the program, but still considered reachable by the garbage collector.

Listing 3. Avoiding object loitering in a stack implementation


public class SimpleBoundedStack {
private static final int MAXLEN = 100;
private Object stack[] = new Object[MAXLEN];
private int top = -1;

public void push(Object p) { stack [++top] = p;}

public Object pop() {
Object p = stack [top];
stack [top--] = null; // explicit null
return p;
}
}


In the September 1997 "Java Developer Connection Tech Tips" column (see Resources), Sun warned of this risk and explained how explicit nulling was needed in cases like the pop() example above. Unfortunately, programmers often take this advice too far, using explicit nulling in the hope of helping the garbage collector. But in most cases, it doesn't help the garbage collector at all, and in some cases, it can actually hurt your program's performance.

Consider the code in Listing 4, which combines several really bad ideas. The listing is a linked list implementation that uses a finalizer to walk the list and null out all the forward links. We've already discussed why finalizers are bad. This case is even worse because now the class is doing extra work, ostensibly to help the garbage collector, but that will not actually help -- and might even hurt. Walking the list takes CPU cycles and will have the effect of visiting all those dead objects and pulling them into the cache -- work that the garbage collector might be able to avoid entirely, because copying collectors do not visit dead objects at all. Nulling the references doesn't help a tracing garbage collector anyway; if the head of the list is unreachable, the rest of the list won't be traced anyway.

Listing 4. Combining finalizers and explicit nulling for a total performance disaster -- don't do this!


public class LinkedList {

private static class ListElement {
private ListElement nextElement;
private Object value;
}

private ListElement head;

...

public void finalize() {
try {
ListElement p = head;
while (p != null) {
p.value = null;
ListElement q = p.nextElement;
p.nextElement = null;
p = q;
}
head = null;
}
finally {
super.finalize();
}
}
}


Explicit nulling should be saved for cases where your program is subverting normal scoping rules for performance reasons, such as the stack example in Listing 3 (a more correct -- but poorly performing -- implementation would be to reallocate and copy the stack array each time it is changed).
========================

Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: Myths of Memory Management Posted: Sep 6, 2005 1:48 PM
Reply to this message Reply
Yep. This is what I was referring to with my comment about imperative containers.

John D. Mitchell

Posts: 244
Nickname: johnm
Registered: Apr, 2003

Memory management vs. Resource management Posted: Sep 6, 2005 1:51 PM
Reply to this message Reply
(A) To learn a lot about garbage collection, a good place to start is Jones & Lins' book, Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Your aguments about GC seem to misunderstand the tradeoffs involved in manual and automated memory management. For example, there's no need to set references to null in e.g., Java.

(B) Your arguments also seem to be conflating memory management and the more general issue of resource management. GC as a tool specifically for memory management isn't the same as trying to piggyback generalize resource management on top of the memory management system. Java, for example, added stuff like finalizers because they too got a bit suckered into trying to piggyback general resource management on top of the memory management system -- and it was an abject failure.

(C) Resource management is, IMNSHO, absolutely critical in software and general purpose programming languages are generally wretched at it. I totally concur that this is a big deal that e.g., needs to be addressed in new/updated languages. I don't see how your shifting of where things are dealt with in Heron is anything new / significantly better. Perhaps you can clarify?

Michael Feathers

Posts: 448
Nickname: mfeathers
Registered: Jul, 2003

Re: Memory management vs. Resource management Posted: Sep 6, 2005 2:09 PM
Reply to this message Reply
> (A) To learn a lot about garbage collection, a good place
> to start is Jones & Lins' book, Garbage Collection:
> Algorithms for Automatic Dynamic Memory Management
.

It's a very good book. I second the recommendation.

Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: Memory management vs. Resource management Posted: Sep 6, 2005 2:15 PM
Reply to this message Reply
> (A) To learn a lot about garbage collection, a good place
> to start is Jones & Lins' book, Garbage Collection:
> Algorithms for Automatic Dynamic Memory Management
.

Seconded. There are also some fairly comprehensive and freely available surveys. Here is one: http://citeseer.ist.psu.edu/wilson92uniprocessor.html .

> For example, there's no need to set
> references to null in e.g., Java.

In certain situations you must explicitly set references to null unless you want to create a space leak.

> (B) Your arguments also seem to be conflating memory
> management
and the more general issue of resource
> management
. GC as a tool specifically for memory
> management isn't the same as trying to piggyback
> generalize resource management on top of the memory
> management system.

Exactly. That is a good point. It is a well known fact that GC+finalizers is not a good way to free arbitrary resources.

> (C) Resource management is, IMNSHO, absolutely critical in
> software and general purpose programming languages are
> generally wretched at it.

Yes. I have a recollection that type systems based on linear logic may have been used to make resource management type safe (see the first chapter in the book Advanced Topics in Types and Programming Languages). It might also be possible to generalize region based memory management (and region inference) to other kinds of resources (chapter 3 in the same book).

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Memory management vs. Resource management Posted: Sep 6, 2005 2:16 PM
Reply to this message Reply
> (A) To learn a lot about garbage collection, a good place
> to start is Jones & Lins' book, Garbage Collection:
> Algorithms for Automatic Dynamic Memory Management
.
> Your aguments about GC seem to misunderstand the
> e tradeoffs involved in manual and automated memory
> management. For example, there's no need to set
> references to null in e.g., Java.

See Anjan Bacchu's post:

There is one case where the use of explicit nulling is not only helpful, but virtually required, and that is where a reference to an object is scoped more broadly than it is used or considered valid by the program's specification.

Nulling is not neccessary is the strict sense of the term, but failure to do so is probably a violation of the design requirements.

> (B) Your arguments also seem to be conflating memory
> management
and the more general issue of resource
> management
.

But memory is a resource.

> GC as a tool specifically for memory
> management isn't the same as trying to piggyback
> generalize resource management on top of the memory
> management system. Java, for example, added stuff like
> finalizers because they too got a bit suckered into trying
> to piggyback general resource management on top of the
> memory management system -- and it was an abject failure.

Agreed.

> (C) Resource management is, IMNSHO, absolutely critical in
> software and general purpose programming languages are
> generally wretched at it. I totally concur that this is a
> big deal that e.g., needs to be addressed in new/updated
> languages. I don't see how your shifting of where things
> are dealt with in Heron is anything new / significantly
> better. Perhaps you can clarify?

Heron doesn't do this any differently than C++. You can use an object to represent a resource, and free the resource once the object is destroyed. I don't see any particular problems with this approach, but that is probably because I am unaware of any better way to do it. I am open to suggestions, as to how this can be improved, though I would be curious what the problems are with the RAII approach used commonly in C++.

John D. Mitchell

Posts: 244
Nickname: johnm
Registered: Apr, 2003

Manual vs. Assisted/Automated Memory Management Posted: Sep 6, 2005 2:16 PM
Reply to this message Reply
IMHO, this anti-GC rabidness is a variation of the Lake Wobegone Effect... Developers thinking that they can explicitly management complex memory (and resource) usage better manually than can be done with help. This is similar to the fallacy that people have that they are safer driving than e.g., flying because (of course!) not only are they an excellent driver but that they are in control of the car. In general, everybody thinks that they (and their pet language, library, IDE, whatever) are the exception to the rule.

John D. Mitchell

Posts: 244
Nickname: johnm
Registered: Apr, 2003

Re: Memory management vs. Resource management Posted: Sep 6, 2005 2:34 PM
Reply to this message Reply
> See Anjan Bacchu's post:
>
> There is one case where the use of explicit nulling is
> not only helpful, but virtually required, and that is
> where a reference to an object is scoped more broadly than
> it is used or considered valid by the program's
> specification.


Yes, that's a design bug, not a problem with GC-based (or manual) memory management.

> Nulling is not neccessary is the strict sense of the term,
> but failure to do so is probably a violation of the design
> requirements.

So you seem to be arguing for this additional complication (nulling references) instead of actually fixing the design? That makes no sense.

> > (B) Your arguments also seem to be conflating memory
> > management
and the more general issue of resource
> > management
.
>
> But memory is a resource.

It's a special resource because of how it's treated throughout the chain (hardware, OS, libraries, languages, etc). Seriously, this is a major issue in terms of perennial attempts to piggyback and all of the complexity and failures that have resulted.

[...]
> > (C) Resource management is, IMNSHO, absolutely critical in
> > software and general purpose programming languages are
> > generally wretched at it. I totally concur that this is a
> > big deal that e.g., needs to be addressed in new/updated
> > languages. I don't see how your shifting of where things
> > are dealt with in Heron is anything new / significantly
> > better. Perhaps you can clarify?
>
> Heron doesn't do this any differently than C++. You can
> use an object to represent a resource, and free the
> resource once the object is destroyed. I don't see any
> particular problems with this approach, but that is
> probably because I am unaware of any better way to do it.
> I am open to suggestions, as to how this can be improved,
> though I would be curious what the problems are with the
> RAII approach used commonly in C++.

Are you also piggybacking general resource on top of the memory management system or just relying on the usual C++ approach?

I thought one of the goals with Here was performance? Completely manual memory management is more error prone and slower, in general, than good GC.

I thought one of the points of spending the time to actually create a new general purpose programming language was to actually make the world a better place. If you're sticking with the same old (dysfunctional) memory and resource management model, how are things going to improve?

In terms of the problems with that approach isn't the voluminous literature enough? Managing all of the issues around identity, ownership, access, scope, and extent are all ridiculously complicated. To be clear, I'm not just picking on Heron or C/C++ but the vast majority of general purpose programming languages including Java, Lisp, etc.

John D. Mitchell

Posts: 244
Nickname: johnm
Registered: Apr, 2003

Nulling for fun and profit Posted: Sep 6, 2005 2:40 PM
Reply to this message Reply
> > For example, there's no need to set
> > references to null in e.g., Java.
>
> In certain situations you must explicitly set
> references to null unless you want to create a space
> leak.

Yes, and those exceptions are specific bugs in languages/libraries/runtimes/etc. and how they are used both in terms of implementation and design.

Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: Nulling for fun and profit Posted: Sep 6, 2005 2:55 PM
Reply to this message Reply
> > In certain situations you must explicitly set
> > references to null unless you want to create a space
> > leak.
>
> Yes, and those exceptions are specific bugs in
> languages/libraries/runtimes/etc. and how they are used
> both in terms of implementation and design.

That's an interesting assertion. Care to elaborate? Where is the bug when you implement a stack using an array as the internal representation (and you (don't forget to) nullify the reference to a popped element)?

John D. Mitchell

Posts: 244
Nickname: johnm
Registered: Apr, 2003

Re: Nulling for fun and profit Posted: Sep 6, 2005 3:10 PM
Reply to this message Reply
In that particular case, the loitering is a by-product of the implementation of the stack. Nulling is only one of the solutions in that case.

We can argue that that case is an example of the confusing grey area between memory management and resource management. I.e., that implementation of the stack using a manually managed, bounded, captive array is a general resource management issue but it's interacting with the specific, automated memory management.

Flat View: This topic has 81 replies on 6 pages [ « | 1  2  3  4  5  6 | » ]
Topic: How Much Profit is Enough? Previous Topic   Next Topic Topic: QA and TDD


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2017 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us