5 ms·

Baby’s First Garbage Collector (2013)

125 points by pcr910303 7y ago

youdontknowtho 7y ago
This is awesome. I'm working my way through The Garbage Collection Handbook and it's always nice to see a GC link on HN. "What does “low on memory” even mean, especially on modern computers with near-infinite virtual memory?" is a question that I've been wondering about for a while.
- Alupis 7y ago
  near-infinite virtual memory, yes, but there's practical limits to what the hardware can support. After exhausting actual RAM, and swap - there's nowhere else to put things... so you'll crash anyway.
- tempguy9999 7y ago
  If you mean the jones/lins book, it's excellent[0]. Fully recommended to all. [0] https://www.amazon.co.uk/gp/product/0471941484 https://www.amazon.co.uk/gp/product/0471941484 I think there's a 2nd edition but I can't find it.
  - mangamadaiyan 7y ago
    > 2nd edition but I can't find it Perhaps you're referring to this one [1]? [1] https://www.amazon.co.uk/Garbage-Collection-Handbook-Management-Algorithms/dp/1420082795/ https://www.amazon.co.uk/Garbage-Collection-Handbook-Managem...
    - tempguy9999 7y ago
      Thanks, I think I was confusing that with the 2nd ed, which doesn't seem to exist (in fact there is a 1999 2nd printing of the 1996 book with a different cover but with the same ISBN, just to make things worse, https://www.cs.kent.ac.uk/people/staff/rej/gc.html https://www.cs.kent.ac.uk/people/staff/rej/gc.html, so if you want to buy the later one which incorporate the errata from the first printing, check his website first. Publishers do make a mess of things sometimes). Jones' website https://www.cs.kent.ac.uk/people/staff/rej/gc.html https://www.cs.kent.ac.uk/people/staff/rej/gc.html is excellent too.
- kazinator 7y ago
  Basically, the memory management on modern computers with virtual memory has to self-impose some constraints to create internal pressure to clean up memory. The implementation may have the option to set some absolute maximum heap size. Or other parameters that set growth hurdles. The memory management tries to keep things within a given hurdle, but when it's obvious that more memory is needed, it changes to another hurdle: e.g. it allocates a new heap area from the OS with a big allocation. There is a performance trade off there, because if lots of memory is available, but we tighten the belt anyway, the application may perform less well due to running garbage collection when it could have gotten away with allocating more external memory. On the other hand, the application is then less of a "pig" with regard to other things in the system.
- user5994461 7y ago
  Memory is a very finite resources actually. Pretty sure virtual memory and over allocation is a major issue with virtual machines and containerization nowadays. Software preempt huge amount of memory because it's assumed to be unlimited free virtual memory. Except the software is running within a container or an OS, within a virtual machine, on a physical machine, that's running another hundreds things like that more or less isolated from one another. While the application may be aware of what memory it's really using, the layers above may not be able to tell exactly what's used or sitting idle. It's a major challenge to estimate and distribute resources appropriately.
sdegutis 7y ago
From the same guy: https://craftinginterpreters.com https://craftinginterpreters.com great stuff
peterwwillis 7y ago
I'm no great programmer, so my stupid question of the day is: why do people depend on GC so much? Garbage collection is one of those weird things that everyone seems to accept must be necessary in higher level languages, and end up being quite a burden in operation. The more people depend on dynamic memory, the more likely GC problems are. Meanwhile, the simplest fix in the world - restart the process frequently - prevents memory leaks from accumulating, and requires no complicated tuning.
- stormbrew 7y ago
  > Meanwhile, the simplest fix in the world - restart the process frequently - prevents memory leaks from accumulating, and requires no complicated tuning. This is just a degenerate case of garbage collection, really.
  - tempguy9999 7y ago
    A novel and valid perspective. I have simply relied on leaking wildly before, knowing it's a small program that will end soon. It's an acceptable solution in some cases.
    - segfaultbuserr 7y ago
      Agree. The best way to manage memory in trivial, one-off C programs is not managing it at all. Don't try to free() everything. When I first started to write in C, I attempted to free() whenever I have a chance to, no matter how trivial the program is. Later a textbook convinced me that the effort is not worthwhile (unless for learning C) if all your program does is some simple calculation or processing.
    - LadyCailin 7y ago
      The JVM now has the epsilon GC, which does basically that, it just never GC’s. It’s unfortunate though that there’s no explicit way to tell java to free up a certain reference, if so, in combination with epsilon, you could write real time programs. Maybe you already can do something like that in the embedded java version though? Not sure.
mikorym 7y ago
Reach-ability in graphs is quite an interesting topic in applied sciences. For example, recently I had to figure out (nontrivial) investment proportions in funds and realised two things: 1. You can use a weighted DAG [1] and sum the products of paths from each leaf to the root to get to the investment proportions; the total of all such paths from leaves to the root should be 100% of the underlying investing entities. 2. Tax offices should use weighted DAGs to figure out cases where there is suspected fraud. Whenever you sum and don't get to 100%, then you know that people are doing fishy things with their investment vehicles and shell companies. [2] [1] https://en.wikipedia.org/wiki/Daw https://en.wikipedia.org/wiki/Daw [2] https://en.m.wikipedia.org/wiki/CumEx-Files https://en.m.wikipedia.org/wiki/CumEx-Files
- mikorym 7y ago
  Sloppy, really. [1] https://en.wikipedia.org/wiki/Directed_acyclic_graph https://en.wikipedia.org/wiki/Directed_acyclic_graph
rkangel 7y ago
Discussion from 2013: https://news.ycombinator.com/item?id=6871202 https://news.ycombinator.com/item?id=6871202

125 points by pcr910303 7y ago

This is awesome. I'm working my way through The Garbage Collection Handbook and it's always nice to see a GC link on HN. "What does “low on memory” even mean, especially on modern computers with near-infinite virtual memory?" is a question that I've been wondering about for a while.

Alupis 7y ago
near-infinite virtual memory, yes, but there's practical limits to what the hardware can support. After exhausting actual RAM, and swap - there's nowhere else to put things... so you'll crash anyway.
tempguy9999 7y ago
If you mean the jones/lins book, it's excellent[0]. Fully recommended to all. [0] https://www.amazon.co.uk/gp/product/0471941484 https://www.amazon.co.uk/gp/product/0471941484 I think there's a 2nd edition but I can't find it.
- mangamadaiyan 7y ago
  > 2nd edition but I can't find it Perhaps you're referring to this one [1]? [1] https://www.amazon.co.uk/Garbage-Collection-Handbook-Management-Algorithms/dp/1420082795/ https://www.amazon.co.uk/Garbage-Collection-Handbook-Managem...
  - tempguy9999 7y ago
    Thanks, I think I was confusing that with the 2nd ed, which doesn't seem to exist (in fact there is a 1999 2nd printing of the 1996 book with a different cover but with the same ISBN, just to make things worse, https://www.cs.kent.ac.uk/people/staff/rej/gc.html https://www.cs.kent.ac.uk/people/staff/rej/gc.html, so if you want to buy the later one which incorporate the errata from the first printing, check his website first. Publishers do make a mess of things sometimes). Jones' website https://www.cs.kent.ac.uk/people/staff/rej/gc.html https://www.cs.kent.ac.uk/people/staff/rej/gc.html is excellent too.
kazinator 7y ago
Basically, the memory management on modern computers with virtual memory has to self-impose some constraints to create internal pressure to clean up memory. The implementation may have the option to set some absolute maximum heap size. Or other parameters that set growth hurdles. The memory management tries to keep things within a given hurdle, but when it's obvious that more memory is needed, it changes to another hurdle: e.g. it allocates a new heap area from the OS with a big allocation. There is a performance trade off there, because if lots of memory is available, but we tighten the belt anyway, the application may perform less well due to running garbage collection when it could have gotten away with allocating more external memory. On the other hand, the application is then less of a "pig" with regard to other things in the system.
user5994461 7y ago
Memory is a very finite resources actually. Pretty sure virtual memory and over allocation is a major issue with virtual machines and containerization nowadays. Software preempt huge amount of memory because it's assumed to be unlimited free virtual memory. Except the software is running within a container or an OS, within a virtual machine, on a physical machine, that's running another hundreds things like that more or less isolated from one another. While the application may be aware of what memory it's really using, the layers above may not be able to tell exactly what's used or sitting idle. It's a major challenge to estimate and distribute resources appropriately.

sdegutis 7y ago

From the same guy: https://craftinginterpreters.com https://craftinginterpreters.com great stuff

peterwwillis 7y ago

I'm no great programmer, so my stupid question of the day is: why do people depend on GC so much? Garbage collection is one of those weird things that everyone seems to accept must be necessary in higher level languages, and end up being quite a burden in operation. The more people depend on dynamic memory, the more likely GC problems are. Meanwhile, the simplest fix in the world - restart the process frequently - prevents memory leaks from accumulating, and requires no complicated tuning.

stormbrew 7y ago
> Meanwhile, the simplest fix in the world - restart the process frequently - prevents memory leaks from accumulating, and requires no complicated tuning. This is just a degenerate case of garbage collection, really.
- tempguy9999 7y ago
  A novel and valid perspective. I have simply relied on leaking wildly before, knowing it's a small program that will end soon. It's an acceptable solution in some cases.
  - segfaultbuserr 7y ago
    Agree. The best way to manage memory in trivial, one-off C programs is not managing it at all. Don't try to free() everything. When I first started to write in C, I attempted to free() whenever I have a chance to, no matter how trivial the program is. Later a textbook convinced me that the effort is not worthwhile (unless for learning C) if all your program does is some simple calculation or processing.
  - LadyCailin 7y ago
    The JVM now has the epsilon GC, which does basically that, it just never GC’s. It’s unfortunate though that there’s no explicit way to tell java to free up a certain reference, if so, in combination with epsilon, you could write real time programs. Maybe you already can do something like that in the embedded java version though? Not sure.

mikorym 7y ago

Reach-ability in graphs is quite an interesting topic in applied sciences. For example, recently I had to figure out (nontrivial) investment proportions in funds and realised two things: 1. You can use a weighted DAG [1] and sum the products of paths from each leaf to the root to get to the investment proportions; the total of all such paths from leaves to the root should be 100% of the underlying investing entities. 2. Tax offices should use weighted DAGs to figure out cases where there is suspected fraud. Whenever you sum and don't get to 100%, then you know that people are doing fishy things with their investment vehicles and shell companies. [2] [1] https://en.wikipedia.org/wiki/Daw https://en.wikipedia.org/wiki/Daw [2] https://en.m.wikipedia.org/wiki/CumEx-Files https://en.m.wikipedia.org/wiki/CumEx-Files

mikorym 7y ago
Sloppy, really. [1] https://en.wikipedia.org/wiki/Directed_acyclic_graph https://en.wikipedia.org/wiki/Directed_acyclic_graph

rkangel 7y ago

Discussion from 2013: https://news.ycombinator.com/item?id=6871202 https://news.ycombinator.com/item?id=6871202