Lisp was the first garbage collected language. But early garbage collectors were painful to use. They had significant overhead and would pause your program for several seconds or even minutes at the worst possible times. People tried to avoid garbage collection by re-using objects, using allocation pools, etc. Many people would run their Lisp programs with the garbage collection turned off. They would reboot their Lisp machines when they ran out of memory. Lisp Machine Inc. had a product called "Picon" which was carefully crafted to avoid any runtime allocation.
Generational garbage collectors began to be adopted in the early 80s. Generational collectors have much less overhead than the earlier "Stop the world" collectors. Memory has gotten much cheaper, so larger heaps are practical. Large heaps have two benefits: garbage collection becomes less frequent, and objects have time to "age" and perhaps become garbage before the next generational collection. Some garbage collection algoriths have no cost overhead for very short-lived objects.
It is no longer necessary to re-use objects or try to avoid allocating memory. Garbage collection pauses are usually short enough to be unnoticeable. You can typically set the heap size nice and large and forget about it. It is certainly possible to encounter a program that has a pathological memory usage pattern, but it is much less common than it used to be.
Because of the way linked lists work, the result of walking down a
list usually comes out in the reverse order. In the old days, you
would make the effort of trying to accumulate the result in the
forward direction by keeping track of the last cell in the answer
and mutating it to accumulate the next cell. This is a pain. These
days, it you can just accumulate the result in the reverse order and
then call reverse when you are done. In practice, this
is no slower than accumulating the result in the forward direction,
but certainly a lot simpler. It generates more garbage, but it is
short-lived garbage with little or no overhead.
5 comments:
I think you mean nreverse...
No, actually. nreverse is fine, but it isn't significantly better than reverse these days. You have to be careful with nreverse that you didn't capture an intermediate cons cell while you were accumulating, but reverse is unconditionally safe.
I'm sure you know that, but generational and "stop the world" are orthogonal concepts. I would have contrasted it with "always scan the entire heap", personally.
Anyway, I "kinda" agree, but with a few caveats (https://world-playground-deceit.net/blog/2024/11/how-i-learned-to-stop-worrying-and-love-gc.html).
Thinking about how one time I was talking with someone who was adamant that all forms of garbage collection were garbage (heh) and literally unstably slow, because they primarily used Swift which uses exclusively automatic reference counting. They refused to listen to any proof I had that pretty much any form of actual garbage collection is better than ARC, since the latter despite has very pathological performance characteristics for some of the most common usage patterns you can think of.
It's just really hard to cause excessive pauses for stop-the-world collectors and pretty difficult to cause concurrent collectors to generate pathological overhead.
@nytpu: Have your acquaintance read this paper: https://courses.cs.washington.edu/courses/cse590p/05au/p50-bacon.pdf
Post a Comment