Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Fully automated memory management increases productivity and integrity greatly, but usual implementation (GC) has a critical problem. It's non-deterministic, and not controllable. This causes many problems such as burst CPU load which is critical for realtime applications. Some kind of optimizations (incremental/concurrent GC) can reduce those problems but still non-deterministic and can't eliminate the problem completely.

I have been thought GC never can solve this problem, but recently, I learned and realized that GC operation doesn't need to be fully hidden. GC also can be deterministic and CPU burst-free by exposing some properly designed behavior controls.

I think (RC + manually invoked cycle detection) can do this. But this doesn't look efficient. Is there any better approach for deterministic and controllable fully automatic memory management implementation? Or can I get some link to example implementations?

Edit

I added these lines to make my question more clear.

  • deterministic and controllable in this context means user can track and run code at object creation and destroying explicitly. And also controls amount and time of memory management operation load.

  • fully automatic means it allocates and clears memory as like GC without extra concern.

share|improve this question
add comment

6 Answers

Let me re-phrase that.

"Is there any way I can get a memory management system which is absolutely perfect and has every desirable property?".

No such systems exist.

share|improve this answer
add comment

The C++ RAII model gives you deterministic and automatic memory management (from the perspective of the library consumer). It's not exactly what you're looking for but it's a start. Although it is an opt-in design where you must explicitly choose to use it with smart pointers. Theoretically a library user could know nothing of memory management, and get the same automatic clean up as in Java.

Maybe a language with "forced" RAII could approach what you are looking for.

The determinism of RAII is nice because it allows you to apply the same technique for resources even more precious than memory. Such as connections and handles.

void foobar()
{
    //connections are even more precious than memory. A leak is bad news.
    Connection conn("foobar");
    conn.Open();
}//conn is automatically closed as it leaves scope. Memory is free too.
share|improve this answer
1  
One thing I've never seen solved by RAII automatically are cyclic references. There are weak references, but with a GC we do not need to care about those (for cycle resolution; there are other good reasons). Any thoughts? –  delnan Feb 21 '13 at 18:16
    
RAII cannot solve cycles, it is only acyclic. However, you can add in other memory techniques- for example, on a graph class that can hold cyclic graphs, each node can be owned by the parent rather than the linking nodes. –  DeadMG Feb 21 '13 at 19:53
    
+1 for RAII/smart-pointers. However, note that you should have at least a vague idea how they operate or you may run into problems when binding pointed-to-objects to references. –  bitmask Feb 21 '13 at 20:33
add comment

There was a description by Butler Lampson in Hints for Computer System Design (Operating Systems Review 15, 5, Oct. 1983, p 33-48) of a system that combined both an incremental collector based on automatic reference counting and a trace-and-sweep collector that could clean up unreachable circular references. The idea is that an application could rely on the incremental collection to do most of the work, then do the "stop the world" garbage collection "used during coffee breaks to reclaim accumulated circular structures."

This was, according to that paper, implemented in the Interlisp-D and Cedar programming environments. It cites the following two articles that I haven't yet read but which—Lampson claims—describe the collector in more detail:

  • Burton, R.R. et al. Interlisp-D overview. In Papers on Interlisp-D, Technical report SSL-80-4, Xerox Palo Alto Research Center, 1981.
  • Deutsch, L.P. and Bobrow, D.G. An efficient incremental automatic garbage collector. Comm. ACM 19, 9, Sep. 1976, pp 522-526.
share|improve this answer
add comment

IBM's Metronome garbage collector for the JVM is deterministic. Basically, it runs continuously in parallel with the application. You specify how much CPU time it can use, with lower CPU time values requiring a larger heap. It isn't suitable for applications that do a lot of heap thrashing, but for typical applications it supposedly works well.

Azul System's C4 garbage collector for their Zing JVM appears to be similar, but I haven't seen any technical details about how it works, so I don't know if it's fully deterministic or not.

share|improve this answer
add comment

All memory management systems have their trade-offs. As DeadMG's answer points, you can't have everything.

Here's a quick guide to some of the trade-offs you can make, and some of the things you CAN have.

Note this isn't necessarily comprehensive, but it's a starting point on thinking about memory allocation/deallocation strategies.

1) Full bore manual - the nadir of determinism.

Upside: You decide when each piece of memory goes away. You'll never get paused by a garbage collector!

Downside: You've GOT to do all the accounting for used memory your own self. And you're likely to screw it up at some point, especially if you try to handle the cases where you need more memory and want to recover it from another part of your program on the fly.

Implemented in: C is the poster child for this one.

2) Deallocate on last reference drop

Upside: You can generally see where deallocation is going to happen, and plan for it appropriately. Since references are automatically cleaned up appropriately, you won't accidentally lose memory. If you've got compiler support, you simply can't screw up and lose memory.

Downside: If you forget or don't realize that you're dropping the last reference to a massive data structure, you can take a big hit at an inappropriate moment.

Implemented in: Perl 5, if I'm not mistaken. Also, if you use it correctly, you can emulate this in C++, though since there's no compiler forcing of it, it's not as safe.

3) Full-on GC

Updside: You don't have to deal with it. Ask for objects, they show up and get cleaned up when you're done with them. Eliminates all the hassle of accounting for memory - if there's free memory, you're good to go! By doing the deallocation in bigger chunks, this also reduces the total cost of the deallocations. If you do a lot of create/delete, that can actually be a good savings.

Downside: The garbage collector may end up locking the heap for extended periods of time. How long is a function of the implementation, but it's going to be larger than any single deallocation. More complex GC algorithms lock for less time, but at the cost of increased complexity. In general you can't do useful work based on object destruction, because the objects may well get destroyed at a time MUCH later than when it's last been used (No RAII for you).

Implemented in: Java's the GC platform I'm most familiar with. Older versions of Java had less capable GCs and bogged down a lot. Modern Java doesn't do this much unless you're doing something pathological.

share|improve this answer
    
The deallocate on last reference drop is familiar to some in Objective C with retain-release. The Perl approach is transparent and less familiar because one doesn't actually have to do any explicit management of the memory. –  MichaelT Feb 21 '13 at 19:52
    
@MichaelT - Thanks for the Objective C ref, I've never used it. I personally would like to see a Java compiler & JVM hacked to do this transparently (like Perl does). I think it might be a nice environment to program in. –  Michael Kohne Feb 21 '13 at 20:05
    
The essence of the objective C rules can be found in interfacelab.com/objective-c-memory-management-for-lazy-people - The simplest form is if you are passed some data that you want to keep, you retain it. If you don't care about some data that you retinaed, you release it. When the reference count on an object reaches 0, it is dealloc'ed. –  MichaelT Feb 21 '13 at 20:47
add comment

It is possible to write in C / C++ your own memory manager, that meets the needs for your project. I have seen this done to solve the memory management bottleneck in a server application that had huge numbers of threads with each thread making and destroying large numbers of small objects. This app's performance was limited by a critical section in the memory manager, and was solved by threads grabbing much larger blocks of memory and managing their own objects.

It is also possible to create an application in C/C++ that largely avoids using the heap for memory allocation. The application creates large fixed size arrays of objects at start up, so then only uses indexs to the array of that object type. I believe that this was a strategy in some big name computer games back in the 1990's. It completely elminiates the problem of memory fragmentation, and with threads having their own cache of index numbers they can use, it reduces contention memory allocation.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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