Please create an account to participate in the Slashdot moderation system

 


Forgot your password?
Close
typodupeerror
×
Programming Software IT Technology

A Glance At Garbage Collection In OO Languages 216

Posted by timothy from the go-on-strike dept.
JigSaw writes "Garbage collection (GC) is a technology that frees programmers from the hassle of explicitly managing memory allocation for every object they create. Traditionally, the benefit of this automation has come at the cost of significant overhead. However, more efficient algorithms and techniques, coupled with the increased computational power of computers have made the overhead negligible for all but the most extreme situations. Zachary Pinter wrote an excellent article about all this."
This discussion has been archived. No new comments can be posted.

A Glance At Garbage Collection In OO Languages More

A Glance At Garbage Collection In OO Languages

Comments Filter:

  • An Obvious Fault (Score:3, Interesting)

    by vandel405 ( 609163 ) on Tuesday April 27, 2004 @11:02PM (#8992838) Homepage Journal
    An obvious fault that seems to go with out notice about garbage collectors, particularly stop-and-copy collectors is that when ever they do the full blow stop and copy, they have to touch all of those memory pages, and fault all of your virtual memory back into ram.

    • Re:An Obvious Fault (Score:4, Insightful)

      by p2sam ( 139950 ) on Tuesday April 27, 2004 @11:56PM (#8993176)
      An obvious fault that seems to go with out notice about sorting algorithms, particularly bubble sort is that it takes O(n^2) time to complete.
      • What?!? Bubble sort is O(n^2), but sorting algorithms can be O(n log n), like quicksort.
        • I'm not sure if I'm being trolled, but as a technicality, quicksort is actually O(n^2). It just so happens that if you pick a good pivot point, it will be average case of n * log(n). Heapsort and merge sort, are actually O(n * log(n)). Quicksort is also handy because if I remember correctly, it is easy to write a stable quicksort, and that's harder to do with merge and heap sorts.

          Kirby

        • Re:An Obvious Fault (Score:3, Insightful)

          by hding ( 309275 )
          Obviously the poster's point was that there are better garbage collection algorithms that do not generally suffer from the original poster's problems, as there are sorts that generally perform better than bubble sort. It was intended to be a tad sarcastic, I'd think.
        • > but sorting algorithms can be O(n log n), like quicksort.

          You forgot to say "comparision" based. Sorting can be done in O(n), ala Radix Sort, which can be adapted to sort floating-point numbers in O(n).
          i.e.
          Radix Sort Revisited [codercorner.com] by Pierre Terdiman

          --
          "I'd rather be idealistic, so people are inspired at what might be,
          Then be realisic and not have any hope of what could be."
    • That's one of the reasons that generational collectors were created. The "young" generation is where most of the activity takes place and it tends to be in your working set anyway.
    • I think you mean "mark and sweep" collectors. "Stop and copy" collectors just trace the working set from whatever your heap root is. Add in the copy step, and you only touch twice the size of you working set. If your collector is well-written and the OS provides the hooks, it will ask for the new space to be allocated in core, and the old space to be discarded, wherever it is.

  • Sigh. It's not a "feature" of other languages... (Score:3, Insightful)

    by devphil ( 51341 ) on Tuesday April 27, 2004 @11:14PM (#8992923) Homepage


    ...it's required by them.

    Stack-based languges like the C family (including Java) don't need GC to operate correctly, but can use it if it's available. (Java just has it all turned on by default.)

    By "correctly," I'm specifically leaving out memory leaks. Your program may leak, but it will still run correctly, give the right answers to computations, not suddenly lose track of variables, etc. (Right up until you run out of swap.)

    Those "other languages" the author dumps a list of don't use GC just to free the poor programmer from the burden of thinking, or whatever. Nearly every one of those languages either has support for functional programming, or is centered around it. And in functional programming, you're creating functions on the fly.

    Which means returning functions as data. Possibly involving local variables in the creating function. Which means that locally-declared variables have to keep existing after the creating function returns, even if the coder can't get to them anymore. And the only way to do that is to have the runtime system manage its own heap, which means a garbage collector.

    So for all those languages, it's not an "ease of use" thing. It's a "there's no way for a programmer to do even do it manually at all" thing. GC is the only option.

    • How about some facts:
      • All the languages mentioned in the article are just as "stack-based" as C and Java (with the possible exceptions of prolog and haskell, depending on your definition.)
      • If you turn off the GC, all the GC'd languages will leak memory but continue to work "correctly".
      • Java has no means of managing memory sans GC.
    • > By "correctly," I'm specifically leaving out memory leaks.

      What a thing to leave out. Memory leaks are one of the hardest-to-track-down
      and most annoying kinds of bugs that we perpetually see in application after
      application. Okay, crashes are more annoying and pervasive, sure. And
      buffer overruns (which are not a problem in most languages that have GC,
      albeit GC is not the reason they're not a problem). But memory leaks are
      high on the list.

      > And in functional programming, you're creating functions

      • I knew some kid was going to start bitching and moaning about the memory leak comment. I'm not saying they're not important. I'm saying that one has nothing to do with the other.

        I'm trying to imagine a programming language that doesn't let you create functions on the fly but is powerful enough for writing real applications.

        C, C++, Java. None of these support closures or lambdas. C++'s Boost makes a good try, but none of them allow me to construct new functions using nothing more than standard la

        • > > I'm trying to imagine a programming language that doesn't let you
          > > create functions on the fly but is powerful enough for writing real
          > > applications.
          >
          > C, C++, Java.

          [Scratches Java off list of languages to learn.]

          I know C and C++ have been traditionally used for writing applications, but I
          have long been of the opinion that they're not really powerful enough for the
          job. It takes several times as many programmer-hours as it ought to to do
          anything, from prototyping to new fea
      • [memory leaks]
        • What a thing to leave out. Memory leaks are one of the hardest-to-track-down
          and most annoying kinds of bugs that we perpetually see in application after
          application.

        Well, there are plenty of applications that never need to (or should for optimal performance) release any memory, only shuffle it around, and have well defined points for releasing other resources (such as closing files and sockets) that can't be left to be done in the background. Such applications have no fear of memory leaks

        • > Any compiled language by definition can't create functions on the fly

          This is flat-out false. There are various compiled languages (compiled as
          in compiled to native machine code, yes) that not only allow creating functions
          on the fly but actively encourage it. Common Lisp is just one example. Yes,
          garbage collection gets compiled in. (This is no weirder than compiling a
          memory-management library into a C program, and actually being standardized
          is an advantage.)

          Besides that, the whole compiled-versus-
    • The implementation of higher order functions as closures does not require garbage collection, if you are willing to leak memory. The same exact issue comes up whenever someone returns an allocated object from a function in Java or C. The creation of a closure is an allocation of an object (which may copy values from the current stack frame into it), but the stack frame still goes away when you leave it, as do the local variables.

      You seem to have a mistaken impression of the way functional languages are imp
    • Stack-based languges like the C family (including Java) don't need GC to operate correctly

      Correct memory management in the presence of heap-allocated mutable objects require garbage collection, even in C.

      There simply is no way around it: you can allocate an arbitrary graph of objects, and what can be freed depends on what is reachable from the roots.

      And if garbage collection isn't built into the language, then the language has to be unsafe, like C is.

      So, if you want a safe language with heap allocation

  • Under the Rug (Score:5, Informative)

    by Markus Registrada ( 642224 ) on Tuesday April 27, 2004 @11:46PM (#8993110)
    As with most such presentations, this article sweeps under the rug most of the reasons why languages dependent on garbage collection have always failed to find much deployment in industrial settings.

    A previous poster noted that most GC algorithms are distinctly unfriendly to virtual memory systems. They usually have similar problems with cache locality, which can result in an enormous slowdown, regardless of the time actually spent in the GC itself. A practical problem is that GC regimes are notoriously non-portable, so that each new language implementation needs to have the (increasingly complex) GC re-done again.

    A more fundamental problem is that memory is only one of many resources a typical industrial program must manage. GC takes over memory management, but leaves the other scarce resources -- file descriptors, sockets, mutexes, database connections -- to be managed manually, as in C. (Java has this problem, for instance.) "Finalization" simply cannot provide the necessary guarantees.

    Given a resource management regime that can handle all these other important resources, as is commonly practiced in C++, memory becomes just another resource. Management is encapsulated the same way for all. A language that lacks the tools necessary to implement such a regime needs GC, so the presence of GC may actually (as in the case of Java) indicate a fundamental weakness in the language.

    (Anybody who thinks languages like Haskell or ML are fundamentally more powerful than C++ must be unaware of the Boost Lambda library, and of FC++, a set of header files that implements Haskell language semantics for C++ programs. They get along fine without GC, as well.)

    • Re:Under the Rug (Score:3, Interesting)

      by sfjoe ( 470510 )
      ...languages dependent on garbage collection have always failed to find much deployment in industrial settings.

      Huh? The world's busiest e-commerce websites are largely written in Java. Just what is your definition of "industrial settings"? If you mean that Java isn't used much in a foundry, then I guess you're right.
    • A language that lacks the tools necessary to implement such a regime needs GC, so the presence of GC may actually (as in the case of Java) indicate a fundamental weakness in the language.

      Please explain to me exactly how you can implement a resource management system (or regime as you call it) in C++ for, lets say, managing socket connections, that has no equivlent in Java. You are aware of this method [sun.com], right?

      Then, please, further explain to me how a task performed by a software platform, in this case th

      • Re:Under the Rug (Score:2, Interesting)

        by DavidTurner ( 614097 )

        Please explain to me exactly how you can implement a resource management system (or regime as you call it) in C++ for, lets say, managing socket connections, that has no equivlent in Java. You are aware of this method, right?

        Okie dokie (pardon the bad formatting):

        class TCPSocket
        {
        int handle_;
        public:
        TCPSocket()
        {
        handle_ = socket (AF_INET, SOCK_STREAM, 0);
        }

        ~TCPSocket()
        {
        close(handle_);
        }
        };

        I think you'll find that there's no equivalent to the above in Java.

        This [att.com] may prove to be good

        • And here's the Java equivalent:

          public class MySocket
          {
          private Socket socket;

          public MySocket()
          {
          socket = newSocket("myhost.com", 8080);
          }

          public void closeSocket()
          {
          socket.close();
          }
          };

          Ah, but you say....you have to manually call closeSocket() to close the socket! True, but that's no different that your implementation. The only difference is that instead of calling 'mySocket.closeSocket()', I have to call 'free tcpSocket'. Either way, the programmer is responsible for managing the resource

    • Re:Under the Rug (Score:5, Informative)

      by WayneConrad ( 312222 ) * <wconradNO@SPAMyagni.com> on Wednesday April 28, 2004 @12:56AM (#8993530) Homepage

      GC takes over memory management, but leaves the other scarce resources -- file descriptors, sockets, mutexes, database connections -- to be managed manually, as in C.

      Ruby has an interesting approach using closures to handle manual resource allocation. One calls the function that allocates a resource, passing it a closure. The function allocates the resource, calls the closure, and then deallocates the resource (even if an exception occurs). Here's how you might write to a file the manual way (I apologize for the lousy formatting; I don't know how to trick /. into indenting):

      file = File.new("foo")
      file.puts "My mistress's eyes are nothing like the sun"
      file.close

      That's the usual way, easy to get wrong: What if an exception occurs? What if I forget to call close? Here's the better way, calling File.open and passing it a closure:

      File.open("foo") do |file|
      file.puts "My mistress's eyes are nothing like the sun"
      end

      File.open might use this common idiom:

      def File.open(filename)
      file = File.open(filename)
      begin
      yield(file)
      ensure
      file.close
      end
      end

      The "yield" calls the closure that was passed in, passing it the file object. The "begin...ensure" is like Java's "try...finally" construct, used here to make sure that the file gets closed whether the closure terminates normally or raises an exception.

      This idiom doesn't solve all manual resource allocation/cleanup problems, but it's a pretty way to solve some of them.

      I don't think Ruby invented this idiom, but I don't know where it came from. Perhaps Lisp: Everything seems to have come from Lisp.

      • Re:Under the Rug (Score:5, Informative)

        by BCoates ( 512464 ) on Wednesday April 28, 2004 @03:14AM (#8994032)
        That sounds like the way a C++ destructor is used with the "Resource Acquisition is Initialization" model. You'd open a file by creating an object on the stack, and the destructor would close the file-handle once control returns (or the object is deleted, if on the heap)
        // some_file_object is a hypothetical file i/o object with manual open(), close(), write(), etc. functions

        class File : public some_file_object {
        public:
        File( const std::string & fname ) : m_handle( open(fname) ) {}
        ~File() { close(m_handle); }
        private:
        const handle m_handle;
        };
        It's sort of inside-out relative to the ruby version becuase it doesn't use the closure, but the useage is near-identical:
        {
        File file( "foo" );
        file.write( "There are more things in heaven and earth, Horatio, than are dreamt of in your philosophy." );
        } // close happens here, or at the throw/return/break/continue site, if any
        new/delete just being another open/close pair to be avoided or contained away in a small object when practical, so it reduces the benefit gained from GC use.

      • Re:Under the Rug (Score:3, Insightful)

        by arkanes ( 521690 )
        Thats pretty cool, but I suspect that the code gets really tangled if you've got a need to lock more than one resource - you'd need chains of closures. It's functionally (hehe!) equivilent to the C++ RAII model, but I think the C++ one is more concise and clear.

        On the other hand,it can probably deal with transaction-style locks easier than RAII can - although I've seen a system to handle that that uses RAII objects combined with functors (instead of closures). It works almost identically to the Ruby model.

      • Re:Under the Rug (Score:3, Informative)

        by hding ( 309275 )
        In Lisp a pretty common way to handle this sort of thing is with a with-some-resource macro (with-open-file is a commonly used built-in). This sort of macro will typically take information for dealing with the resource (e.g. in the file example the pathname of the file, options for opening it, etc.) and the body of code to be executed with the resource; it will then expand to code that acquires the resource and then uses it and releases it (the latter two typically wrapped in unwind-protect to assure the r
      • > trick /. into indenting
        File.open("file.txt", "w") {|f|
        f << "Hello world!\n"
        }
        Use the ecode tag and put spaces in there.

        I agree that this is an excellent Ruby idiom... very handy.

      • Re:Under the Rug (Score:3, Informative)

        by Gaijin42 ( 317411 )
        the using keyword in c# handles exactly this situation.

        This code :

        using(DisposableObj x = new DisposableObj())
        {
        x.DoSomething();
        }

        is equivilent to

        DisposableObj x = new DisposableObj();
        try
        {
        x.DoSomething();
        }
        finally
        {
        x.Dispose();
        }

        So as long as the object's author put any "close/release" code into the dispose method, it will get handled automatically when you are done with it.
        (Even if an exception occurs!)

        Most c# objects that have dispose() also have a close()

        For example, databases. You can close() th
      • Using this technique for memory management comes from "regions," which are a kind of statically checked manual memory management system. Regions are good for some kinds of programs (and are easy to check), but often the lifetime of an object is not determined statically. If this is your only resource management strategy, it will be too restrictive to write many programs.

        Any language with higher order functions (which you are calling "closures"--an implementation strategy for higher order functions) can imp

    • Re:Under the Rug (Score:5, Insightful)

      by Pseudonym ( 62607 ) on Wednesday April 28, 2004 @12:58AM (#8993544)
      A previous poster noted that most GC algorithms are distinctly unfriendly to virtual memory systems.

      It depends on the language. Haskell, for example, has very different memory access patterns than Java. Being lazy, a value is produced only when it's time to be first consumed, at which point it often becomes garbage immediately. It follows that most of the garbage that a decent generational GC will be collecting will probably be in cache.

      Anybody who thinks languages like Haskell or ML are fundamentally more powerful than C++ must be unaware of the Boost Lambda library [...]

      I'm one of those rarest of beasts, a programmer who regularly uses (and likes) both Haskell and C++. (Disclaimer: I'm not familiar with FC++, though from what I've read it doesn't really support lazy evaluation, which is one of Haskell's most important distinguishing features.)

      From a reductionist point of view, of course, neither is more powerful than the other. However, even with Boost.Lambda and the likw, I still find Haskell almost always allows for far more rapid development than C++ does, all other things being equal. Naturally, all other things are rarely equal, and speed of development is not always the greatest concern, and I won't be drawn into ranking one of my two favourite languages over the other.

    • You bring up a good point. Whenever people talk about the glories of garbage collection, I always wonder why they think memory is the only resource. And if I'm supposed to manually deal with those other resources, why am I not supposed to likewise manually deal with memory?
      • well, the average (hell, even small) program makes thousands and thousands of memory allocations. Every string, every bit of math etc.

        However, database or file allocations are much less frequent.(and in a well written program, very localized and isolated)

        Just because you can't solve every problem, doesn't mean you can't solve the big one.

        • The frequency of the memory allocation is irrelevant, because it's the same code that doing it. The frequency of the allocation does not increase the complexity of the code. For example, a linked list with thousands of nodes is no more complex than a linked list with only two nodes.
          • Not quite what I meant.

            More like : I implement 10 linked lists/hashes/whatever, 50 arrays, and 10000 strings per program.

            (regardless of the length of string/number of elements etc)

            Therefore I have to get memory allocation right several thousand times.

            On the other hand, I only open up a handfull of database connections, and usually only 2 files. Therefore it is much easier to isolate those and make sure they are working right. VS checking for Thousands of pure memory leaks.
            • Except we were talking about OO Languages, and not OO Programming. So I was assuming C++. In C++ you don't have to manually allocate memory for strings. And you don't have to allocate memory for arrays either. In fact, with the STL you don't even have to allocate anything for the linked lists either. Of course you could, if you wanted to, but you don't have to.

              Because this is C++, I am using "new" and "delete". On the surface these seem to be about memory allocation, but they are really abstractions for ge
              • Well, I am primarily a web developer, which changes things for me somewhat (The lifetime of a program is only the lifetime of a page-view, so even if things stick around until the end, its not that long) Additionally, I am not instantiating brushes or anything like that.

                However, even in the winforms world, in c# (and Java) you dont handle getting rid of brushes etc.

                You can "early" dispose them using the dispose() methods we talked about before, but the GC is also smart. It takes into account relative co
    • In fact, C# can make handling of those other resources less reliable and more complex as compared with C++ for example. I miss smart pointers!

    • Re:Under the Rug (Score:3, Informative)

      by DavidTurner ( 614097 )

      Well put!

      Another important consideration is that where the programmer has the expectation that his garbage will be cleaned up for him, he will tend to assume that all of his resources will be cleaned up. This is clearly not the case. The seminal example for me was the use of database query result sets in C# - if you don't explicitly close them, they tend hang around, and the next time you try to perform a query on the same connection, you'll as likely as not get an exception. Surprise!

      Also, as some oth

      • D (see digitalmars.com/d, or the recent Slashdot article) is the holy grail here as far as I'm concerned - it has GC but also retains automatic objects you can use for RAII. On top of that, the GC is much more amenable to bypassing, unlike Java or C#s.

    • Re:Under the Rug (Score:4, Insightful)

      by Spy Hunter ( 317220 ) on Wednesday April 28, 2004 @07:11AM (#8994697) Journal
      So we should ignore GC because it doesn't solve all the world's resource problems at once? Your post doesn't provide a convincing argument against the use of GC. Non-portability is a non-issue; only language writers have to worry about that, and it's already their job. The cache-thrashing issue is the only real problem you mention. Generational GC significantly reduces this problem, to the point where the small runtime performance hit (if there is one at all; malloc and free take time too you know) is balanced out by increased programmer productivity (giving more time to optimize if you so desire, or add features if that's what you value more).

      Side note: Boost Lambda and FC++ are impressive but ugly hacks with horrible syntax, lots of "gotchas" that make code not work (often related to operator precedence and order of evaluation), and compiler errors from hell. Probably not the best examples of the power of C++. (OTOH, maybe that makes them the perfect examples of the "power" of C++ ;-)

      • It's not a problem with GC so much but that the implementation of GC in the language precludes the constructs that let you efficently manage other resources. I'm only aware of one language that has both GC and automatic objects. Java is probably the most poplar GCed language/environment, and it certainly brought GC into the mainstream, so it's particular resource management flaws are often seen to be part of GC. (Functional languages that use closures to manage resources are a different issue, and I have no
    • If you think that Boost Lamba and FC++ have anywhere near the power of haskall, then you haven't used it yet. One of the major problems of constructing things via templates in C++ is that you have to define everything statically at compile time. As soon as you start generating any kind of complex system or want to construct functions based upon user input or compuatation you do at run-time, then you reach a wall with these libraries.

      Now don't get me wrong, I like boost::lambda and use it a lot, but compari
      • I presume you meant Haskell.

        But I think you're confusing two concepts here. Compile-time vs. runtime semantics is a whole other axis for comparing languages. We use C++ in circumstances where a "method not implemented" (in Smalltalk parlance) message thrown in the customer's face at random intervals is considered evidence of incompetence. We like compile-time verification and only wish we had more of it.

        Of course it can be fun to have a compiler in your runtime system, and generate code for it on the

    • A previous poster noted that most GC algorithms are distinctly unfriendly to virtual memory systems.

      Actually generational collectors are fairly friendly w/r/t virtual memory.

      GC takes over memory management, but leaves the other scarce resources -- file descriptors, sockets, mutexes, database connections -- to be managed manually.

      Bogus argument. That's like saying steel-belted tires are more puncture resistant but they don't solve the problem of oil leakage so they're worthless.

      Management is encapsu
    • Anybody who thinks languages like Haskell or ML are fundamentally more powerful than C++ must be unaware of the Boost Lambda library, and of FC++, a set of header files that implements Haskell language semantics for C++ programs. They get along fine without GC, as well.

      If you like your memory management to be by reference counting, then they "get along fine without GC." But reference counting is an inefficient way to do memory management.

      Also, I actually believe that copying garbage collection can be go
      • Reference counting can be an inefficient way to do memory management if, in fact, it is the only way one does memory management. In practice, in C++ programs, only very few of the objects are reference-counted, so that argument is irrelevant, in context.

        ... most languages let you manually manage non-memory resources

        The goal is to enable encapsulation of resource management. In C++ one normally encapsulates management of all resources the same way. In most GC languages, as in C, you are left with no c

    • Re:Under the Rug (Score:4, Insightful)

      by hak1du ( 761835 ) on Wednesday April 28, 2004 @05:16PM (#9001096) Journal
      this article sweeps under the rug most of the reasons why languages dependent on garbage collection have always failed to find much deployment in industrial settings.

      For the same reason people in industry have kept programming in Cobol and Fortran, and for the same reason they keep producing software with all sorts of problems, bugs, and limitations.

      A previous poster noted that most GC algorithms are distinctly unfriendly to virtual memory systems. They usually have similar problems with cache locality, which can result in an enormous slowdown, regardless of the time actually spent in the GC itself

      Not true at all. Generational collectors generally achieve far better locality than malloc-style allocators.

      A more fundamental problem is that memory is only one of many resources a typical industrial program must manage. GC takes over memory management, but leaves the other scarce resources -- file descriptors, sockets, mutexes, database connections -- to be managed manually, as in C.

      Fundamentally, the point behind GC is not to make your life easier, it is to make it possible for the language to be safe. Without GC, a language with heap allocated mutable data structures just cannot be safe. GC generally cannot reliably manage any other resources besides memory and it is not meant to.

      Given a resource management regime that can handle all these other important resources, as is commonly practiced in C++, memory becomes just another resource.

      But memory isn't just any resource, memory is a resource that can contain machine pointers to other memory (as well as references to other resources).

      The problem of resource management for memory is that of arbitrary directed graph reachability. And that is exactly the problem that a garbage collector solves, as efficiently as possible.

      A language that lacks the tools necessary to implement such a regime needs GC, so the presence of GC may actually (as in the case of Java) indicate a fundamental weakness in the language.

      C++ solves a common but limited subset of the resource management problem and then just declares victory. And even that false victory is not very satisfying because in order to achieve it, C++ has sacrified runtime safety. (In fact, with that choice, it has also sacrificed efficiency, but you aren't going to believe that no matter what I say.)

  • Dilbert GC (Score:5, Funny)

    by StarWynd ( 751816 ) on Wednesday April 28, 2004 @01:02AM (#8993561)
    This is my kind of garbage collection [k12.va.us]!

  • a way to give the GC a hint? (Score:4, Interesting)

    by Doppler00 ( 534739 ) on Wednesday April 28, 2004 @01:20AM (#8993634) Homepage Journal
    It might be useful if some languages had an optional method of hinting that an object should be garbage collected soon. This would help in languages like Java where you get a huge amount of data stored and then all at once the disk thrashes as it GC everything. For some algorithms, it would be nice to tell Java ahead of time that you're done with the object and you're not going to reference it anymore. The nice thing is though, it wouldn't be a requirement, so you wouldn't have to worry about deleting an object still in use by mistake. I wonder how efficient this would be.
    • Simply doing something like:
      foo = null;
      is sufficient. If you really want to, you can call the garbage collector manually:
      System.gc();
      • > you can call the garbage collector manually

        Unfortunately, this doesn't force it to run. From the JDK 1.4.2 Javadocs for System.gc():
        Calling the gc method suggests that the Java Virtual Machine expend effort toward recycling unused objects in order to make the memory they currently occupy available for quick reuse.
        Note the "suggests". No guarantees...

    • I've always wondered if the opposite would help. i.e. being able to say "never GC this allocation"

      Many of my programs consist of objects that exist for the life of the program and every time the generation GC hits I picture it scanning over all of these permanent objects, forcing page hits, swapping, and possibly thrashing.

      • Well, a typical generational collector will promote the object to a longer lived generation after touching it a few times without collecting it (perhaps even just once), and many will allow you to simply allocate it into a longer lived (or even permanent) generation to begin with.

  • GC has always been efficient (Score:3, Insightful)

    by hak1du ( 761835 ) on Wednesday April 28, 2004 @02:21AM (#8993859) Journal
    however, [manual storage management] can be more efficient in many ways if properly handled. This discrepancy in efficiency has slowed the widespread adoption of the automated approach.

    There hasn't been a "discrepancy in efficiency". Good garbage collectors have been comparable to, or better than, manual storage allocators for decades.

    The perception of a "discrepancy in efficiency" has several causes:
    • Garbage collection allows programmers to get sloppy about storage managmentt: if a non-GC program gets sloppy about storage management, it crashes, if a non-GC program gets sloppy about storage management, it just runs slowly. Unfortunately, as a result, many core libraries in garbage collected languages are pretty sloppily written and slow--the fault is with the libraries, not with garbage collection.
    • Garbage collection allows language implementors to make different design decisions. Many garbage collected languages will do memory allocation every time you use a floating point number. Imagine how slow C would be if you called "malloc" for every floating point number.
    • Garbage collection often bundles memory management overhead into single chunks of time, while manual storage allocators don't. Furthermore, garbage collector implementations really rub your nose in it, printing messages like "[starting garbage collection... done]". But doing a lot of storage management at once is usually more efficient overall--in aggregate, manual storage managers spend more time, they just diffuse it out. However, both kinds of behaviors exist with both storage managers, and you can pick and choose.
    The article is right that garbage collection is a good choice today. It is wrong in that it has pretty much always been a good choice. Garbage collection could have been widely adopted in the 1970's or 1980's, and we would have saved ourselves a lot of headaches and troubles without any loss in efficiency.
    • Either I've had too much beer this evening, or your post is completely nonsensical. Given that I've had no beer this evening, I greatly suspect that latter. Unfortunately, since the moderators are on crack, I fear that your post will be moderated up.
    • What about real-time constraints? GC are generally non-deterministic (they start and finish according to their own rules), which might destroy your maximal response time in a RTOS. This is this very issue that has been the thorn in the side of GC adoption for the C and C++ standards.

      How about one of the earlier comments to the effect that mark-and-sweep type algorithms page-faults all the memory used by an application? That has got to be inefficient, and since virtual memory is not under the control of the
      • Micro-managed memory vs. GC Efficiency

        GC wins. And here is why...

        Most implementations of "micro-managed" memory use the allocate/free model. Programmers are very careful to allocate what they need, and free it when done.

        But... Allocation is usually very cheap. You have a big hunk of memory, and a "high water" mark. If the new allocation fits, just take it and advance the mark. Free is not so cheap. Blocks need to be coallesced (sp?).

        GC approach is to give the memory (same low cost as allocate), and simp
        • There's a way to avoid many mallocs/frees all at the same time, which is to use a memory pool and have some object look after it. Allocations usually come from an already allocated pool of memory, deallocations are simply the setting of a flag.

          The object handling the pool keeps some free space in the pool so that a burst of new small allocations won't cause a 'real' malloc.

          This technique is used by KDE. It's all done behind the scenes, so as a developer, you don't need to worry about it too much.

          Rik
          • There's a way to avoid many mallocs/frees all at the same time, which is to use a memory pool and have some object look after it. Allocations usually come from an already allocated pool of memory, deallocations are simply the setting of a flag.

            Yes, and the same technique works in garbage collected systems and has been used for pretty much as long as garbage collectors have been around. Good garbage collectors actually give you extensive APIs to manage areas and pools in a way that the GC knows about and c

      • Re:GC has always been efficient (Score:5, Insightful)

        by hak1du ( 761835 ) on Wednesday April 28, 2004 @11:18AM (#8996551) Journal
        What about real-time constraints?

        What about them? Real-time garbage collectors give you guaranteed real-time responses.

        I suspect that you have actually never used a real-time storage allocator of any form. The memory allocators that ship with major C/C++ compilers certainly make no real-time guarantees. The way people usually get real-time performance out of them is by pre-allocating large chunks of memory. Well, you can do in garbage collected languages as well.

        GC are generally non-deterministic (they start and finish according to their own rules),

        No, they don't. Just like with malloc implementations, their behavior may differ from implementation to implementation, but it is generally pretty well understood. It can usually also be controlled well.

        Simple garbage collectors only will start a garbage collection when you ask for a block of memory and it can't satisfy the request; they don't just start up for no reason at all. Parallel garbage collector may run a thread in parallel to the main program but never stopping it. Incremental collectors do a little bit of work each time you allocate. Real-time collectors guarantee well-defined maximum responses for allocation.

        If the garbage collector in your language (Java?) doesn't do what you want, it's not a problem with garbage collection in general, it's a problem with the specific implementation your vendor has chosen to give you. Just like there are mediocre or bad malloc implementations, there are mediocre or bad garbage collectors.

        How about one of the earlier comments to the effect that mark-and-sweep type algorithms page-faults all the memory used by an application? That has got to be inefficient, and since virtual memory is not under the control of the application by definition there is nothing that can be done, except if the GC is directly under the control of the OS, which doesn't often makes sense (it's not very flexible then).

        Well, that comment is wrong. First of all, you don't have to use a mark-and-sweep collector. Most high-performance collectors are, in fact, generational and are very VM friendly (moreso than malloc/free in many cases). Second, operating systems have interfaces to their VM subsystems, so the GC can, in fact, control what is happening with paging--prefetching pages, etc. And they do. Even 20 years ago, Berkeley UNIX had system calls specifically designed to let Franz Lisp let the kernel know what it was doing. Third, a malloc implementation cannot move pointers around to make accesses more local or sequential--good garbage collectors do, so GC is actually superior in that regard.

        The article itself says that there is no way to make a GC perform as well or better as a finely tuned hand-micro-managed in every case.

        You can "micro-manage" and "fine tune" in the presence of a GC as much as you can in its absence. But in the presence of GC, you have the freedom to be sloppy and your code will still run--so many people don't bother. In C/C++, you don't have a choice.

        In languages that don't have GCs you can add one yourself (Bohm's GC works fine for C/C++, and is in fact used for GCJ, the GNU implementation of the Java language), with the benefit that you can turn it off if you don't want it for some reason, something you can't do in Java for example.

        No, that is backwards. In languages without GC, you cannot add a GC and get all the benefits from the GC. Boehm's GC, for example, may retain arbitrary amounts of garbage, and its lack of integration with the language and compiler means that it can't be anywhere near as efficient as an integrated GC. Boehm's GC is a great hack, and it work really well, but it is not something you can ultimately rely on. Furthermore, if you add Boehm's GC to a language without GC, you are still left with an unsafe programming language.

        Secondly, languages with garbage collection often give you full control over the GC: you can enable it or disable i
      • A friend of mine did his thesis on a Garbage Collector that is parallell, concurrent, real-time and (mostly) tagless. We have it running in a real compiler. (Here's a later paper [psu.edu] he wrote.) So real-time GC is absolutely possible.

        How about one of the earlier comments to the effect that mark-and-sweep type algorithms page-faults all the memory used by an application?

        Not all garbage collectors are mark-and-sweep. Also, copying GCs have much better fragmentation than malloc, so if you're concerned about kee

  • Feels like (Score:3, Interesting)

    by nate nice ( 672391 ) on Wednesday April 28, 2004 @02:35AM (#8993903) Journal
    I feel like I just read a small section in the memory management section of an operating systems or programming languages text book. I'm not sure what to discuss here, no knew ideas were expressed or presented here. Perhaps the author could have postulated new ideas for memory management or suggested how current ideas could be improved. Interesting read if you're a programmer who never really got into the mechanics of a programming language and what certain runtime systems do to make your program work. Then again, I would probably call you a strict-scripter and when scripting you're generally more concerned with expressions rather than mechanics.

    Although, the point the author made about CPU's being cheaper and faster and how this is allowing the programmer to care less and less about mechanics so the can make use of this extra power to make programming a more expressive rather than mechanical practice is interesting.

    Personally, I see no problem with one day having high level application programmers who know nothing of hex, memory management or physical hardware but rather algorithms, computability and productions, etc. Of course, there will always be a place for the "computer programmer", but also a place for the "analytical abstractionist engineer".

  • The GC pitfall (Score:5, Insightful)

    by jtheory ( 626492 ) on Wednesday April 28, 2004 @03:01AM (#8993987) Homepage Journal
    Good article, though very limited in scope (basically just a list of GC methods, wrapping up with the methods used by recent Java and .NET interpreters). I was a little disappointed that they didn't get into the implications of using languages with GC.

    One pitfall that I've noticed basically comes along with the benefit of avoiding "micro-managed" explicit memory management -- there are a lot of Java coders who don't think at *all* about memory management, because they think it's all handled for them. Mix that in with an over-excitement about OO, and you get some impressively slow and non-scaleable code.

    You DO need to understand, at least on a basic level, what's going onto the heap, and what the garbage collector has to do to keep up with your "garbage". Carefully nulling out objects that are going to be out of scope in a millisecond is just wasting space, but you should definitely keep an eye on what objects you're allocating within that loop that runs a million times. They're all going on the heap; are they all going to be on there at the same time? When are they going to be eligible for collection? Are they just Strings, or larger objects (which possible create other objects when they are created)?

    If you have to optimize a section of code, consider sticking to primitives and Strings (obviously you're balancing this against the cost of possibly less-maintainable code!), and don't forget that when you instantiate com.foo.Bar, all of its superclasses are also instantiated, including any member objects they hold. And don't make a variable static for no reason -- it won't get collected with the object instance....

    Two useful things to think about -- heap size (the objects you're actively using at a given moment, so they can't be collected), and churn rate (how fast you're creating and trashing objects). Object creation/destruction isn't as costly as it was with the early versions of Java (no, you probably don't need that Thread pool!). But any application that needs to scale requires some thought on memory usage and churn before you start coding.
    • there are a lot of Java coders who don't think at *all* about memory management, because they think it's all handled for them. Mix that in with an over-excitement about OO, and you get some impressively slow and non-scaleable code.

      While you are entirely right, this is no differnt from previous generations of programming languages. You always do better if you have a bit of understanding of the wiring behind the board.

      I'm sure that there were objections to high-level languages by assembler coders who objec
      • While you are entirely right, this is no differnt from previous generations of programming languages

        Fair enough, though if you don't understand memory management in C you will know it, because you'll have massive memory leaks or serious, noticeable bugs.

        I think I mistakenly gave the impression that I don't like GC. I love it, and I think it's definitely worth the few drawbacks -- I just wanted to point out that it's not a silver bullet. And I do get frustrated with inexperienced programmers who speak s

  • Reference counting (Score:3, Informative)

    by Antity-H ( 535635 ) on Wednesday April 28, 2004 @06:27AM (#8994575) Homepage
    It was mentionned earlier that reference counting was pretty good, but had a few drawbacks when it came to cycles and multi-threading.

    I took a bit of time to go and read Wikipedia's page [wikipedia.org]

    In the description they give, they mention that reference counting GC can represent managed objects by directed graphs.
    I know there exists algorithm to find cycles in such graphs. So I suppose these could be applied to this problem. Other proposal are to use a tracing GC to detect them. To which it was replied that this would be able to reclaim the memory but not to properly finalize the objects. I don't see why that would be true. I mean, if you have found a member of the cycle to be collected, can't you just finalize that one and let the whole cycle unravel itself ? If there are cycles inside that cycle, just do it again on these etc ...

    As I said, another common objection was the cost of updating the counters in multithreaded environnments. Multiple solutions have been proposed, some more portable than others (using processor/platform specific atomic increments, or deferring the update until it is really necessary and using the standard mutex protection)

    All this said, I try to understand a couple of things.
    -I am no genius, thus these ideas must not be new, what is the problem which can't be solved with these?
    -Reference counting seems to integrate better in the runtime of the program. All the other techniques proposed seem to imply some monolithic operation on the memory summing up all the overheads at on time and doing the cleaning once in a while, with the possibility of becoming a bottleneck in heavily loaded systems. Reference counting OTOH seems to allow the cleanup to continually add a little bit of overhead to the system but nothing which will bring the whole thing to a grinding halt before allowing it to go on. What have I missed?

  • Relevant references (Score:3, Informative)

    by hding ( 309275 ) on Wednesday April 28, 2004 @10:03AM (#8995742)

    A couple of relevant references for garbage collection are the following website (which unfortunately hasn't been updated for a while - still, it's useful):

    The Memory Management Reference [memorymanagement.org]

    and of course Jones and Lins book, Garbage Collection: Algorithms for Automatic Dynamic Memory Management

  • Java doesn't have *a* garbage collector (Score:4, Informative)

    by blamanj ( 253811 ) on Wednesday April 28, 2004 @01:04PM (#8997793)
    It has different collectors, which you can select according to the needs of your application. Currently there are two, the default collector (generational) and an incremental collector which is slower but less likely to pause.

    Also, the default collector is a 3-generation one, not 2, at least as of Java 1.4.1. More details here [sun.com].

Slashdot Top Deals

For God's sake, stop researching for a while and begin to think!

Close