4 ms·

>That makes freeing memory O(n) in the number of chunks freed A GC can't outdo that. For everything the GC frees, it has to do some work to answer the questio

by xamuel 12y ago

>That makes freeing memory O(n) in the number of chunks freed A GC can't outdo that. For everything the GC frees, it has to do some work to answer the question, "Should I free this or not?" Even if that question can magically be answered with a single CPU instruction, that's still O(n) answers in the number of chunks freed.

Doradus 12y ago
I think you're referring to a mark and sweep collector. Java's garbage collector uses better algorithms. The collector never even looks at objects that are not referenced from the root set, and an allocation operation is nothing but a pointer bump. Even Cheney's algorithm from the early 1970s works this way, and collectors have only improved since then.
- TheLoneWolfling 12y ago
  Except that the OS zeros memory when it's released...
  - Doradus 12y ago
    The JVM doesn't release the memory to the OS when garbage is collected; only when the heap shrinks. Any zeroing the OS might do is proportional to the size change in the heap, not to the number of objects freed.
    - TheLoneWolfling 12y ago
      Good point. However, that brings up a related issue - namely that the JVM requires all (or close enough to all) object memory to be initialized. And given that the amount of memory required to be initialized is at minimum linear w.r.t. the number of objects required to be initialized... Work done is still O(n) minimum w.r.t. the number of objects allocated regardless.
      - Doradus 12y ago
        Well, it's hard to deny that the work done by the program is O(n) (or even Ω(n)) in the number of objects created by the program. That's almost tautological. The thing that is interesting about the asymptotic complexity of garbage collection, though, is that it gives you a peek into the future of GC overhead as heaps get larger. Consider a program with some bounded steady-state memory consumption, and a GC that takes O(1) time to free unlimited amounts of memory. In such a system, you can reduce your GC overhead arbitrarily simply by enlarging the heap. A larger heap gives a larger time interval between collections, yet doesn't make the collections any slower. Don't like 6% overhead? Fine. Make the heap 10x larger and you have 0.6% overhead. This time-space trade-off is always available to the end user of such a system. It's certainly not available with more primitive systems like malloc+free. [These are my personal opinions, not those of my employer.]
        xamuel 12y ago
        >and a GC that takes O(1) time to free unlimited amounts of memory If the unlimited amounts of memory are all in one contiguous block and ALL of them are ready to be free'd (and determining that all of them are ready, takes O(1) time somehow) then what you say is plausible. In any other case it's fantasy. Suppose I have n variables and I point each of them at a distinct new object (not pointed to from anywhere else). Then I re-set a random subset of them to null. Based on which ones I randomly set to null, there's 2^n possibilities for what the GC must do. If your claimed GC O(1) is long enough for the processor to take k conditional jumps, there are at most 2^k possible results of running it. For n>k, there are necessarily subsets in the above scenario which your GC fails to handle. >This time-space trade-off is always available to the end user of such a system People routinely run servers on virtual machines with very limited RAM.
        Doradus 12y ago
        Your argument proves that the time taken can be no less than O(n) in the number of object references in live objects. The (potentially billions of) unreachable objects are never touched. I agree that limited RAM environments are important. Asymptotic complexity only matters when you're effectively operating at the asymptote.

by xamuel 12y ago

Doradus 12y ago

I think you're referring to a mark and sweep collector. Java's garbage collector uses better algorithms. The collector never even looks at objects that are not referenced from the root set, and an allocation operation is nothing but a pointer bump. Even Cheney's algorithm from the early 1970s works this way, and collectors have only improved since then.

TheLoneWolfling 12y ago
Except that the OS zeros memory when it's released...
- Doradus 12y ago
  The JVM doesn't release the memory to the OS when garbage is collected; only when the heap shrinks. Any zeroing the OS might do is proportional to the size change in the heap, not to the number of objects freed.
  - TheLoneWolfling 12y ago
    Good point. However, that brings up a related issue - namely that the JVM requires all (or close enough to all) object memory to be initialized. And given that the amount of memory required to be initialized is at minimum linear w.r.t. the number of objects required to be initialized... Work done is still O(n) minimum w.r.t. the number of objects allocated regardless.
    - Doradus 12y ago
      Well, it's hard to deny that the work done by the program is O(n) (or even Ω(n)) in the number of objects created by the program. That's almost tautological. The thing that is interesting about the asymptotic complexity of garbage collection, though, is that it gives you a peek into the future of GC overhead as heaps get larger. Consider a program with some bounded steady-state memory consumption, and a GC that takes O(1) time to free unlimited amounts of memory. In such a system, you can reduce your GC overhead arbitrarily simply by enlarging the heap. A larger heap gives a larger time interval between collections, yet doesn't make the collections any slower. Don't like 6% overhead? Fine. Make the heap 10x larger and you have 0.6% overhead. This time-space trade-off is always available to the end user of such a system. It's certainly not available with more primitive systems like malloc+free. [These are my personal opinions, not those of my employer.]
      - xamuel 12y ago
        >and a GC that takes O(1) time to free unlimited amounts of memory If the unlimited amounts of memory are all in one contiguous block and ALL of them are ready to be free'd (and determining that all of them are ready, takes O(1) time somehow) then what you say is plausible. In any other case it's fantasy. Suppose I have n variables and I point each of them at a distinct new object (not pointed to from anywhere else). Then I re-set a random subset of them to null. Based on which ones I randomly set to null, there's 2^n possibilities for what the GC must do. If your claimed GC O(1) is long enough for the processor to take k conditional jumps, there are at most 2^k possible results of running it. For n>k, there are necessarily subsets in the above scenario which your GC fails to handle. >This time-space trade-off is always available to the end user of such a system People routinely run servers on virtual machines with very limited RAM.
        Doradus 12y ago
        Your argument proves that the time taken can be no less than O(n) in the number of object references in live objects. The (potentially billions of) unreachable objects are never touched. I agree that limited RAM environments are important. Asymptotic complexity only matters when you're effectively operating at the asymptote.