Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

For Better Computing, Liberate CPUs from Garbage Collection

spectrum.ieee.org

Post reply on HN
Print view View original

161–170 of 460 posts

Re: For Better Computing, Liberate CPUs from Garbage Collection

#161

Post by xxs »

gpderetta wrote: post #146
xxs wrote: post #98

Earlier quoted context omitted.

Garbage collection is godsend when it comes to concurrency algorithms. Determine liveness is hard on its own, ABA issues are totally eliminated by GC enabled setups. As for energy costs, I'd bet generation/copy collectors are cheaper than malloc/free. They are way cheaper than ref. counting which requires deeper pipelines + branch predictor extra load; ref. counting with concurrency requires atomics, cache coherency…

> Determine liveness is hard on its own, ABA issues are totally eliminated by GC enabled setups. FWIW, Herlihy has examples of ABA issues on algorithms implemented in Java.

I wonder what that be... It can happen with primitives only and the usual solution is: increment only and use prepare/publish with two distinct counters (for circular buffers alike).

Do you have any references?

Re: For Better Computing, Liberate CPUs from Garbage Collection

#162

Post by lokedhs »

mafribe wrote: post #143
lispm wrote: post #138

Earlier quoted context omitted.

See the chapter 6.3 'The Free-Storage List and the Garbage Collector' in the LISP I Programmer's manual from March 1960. http://bitsavers.org/pdf/mit/rle_lisp/LISP_I_Programmers_Man...

Thanks. That's amazing. I always though GC must have been in Lisp from Day 1, but the Minsky article used to be the oldest one I was aware of. Has anybody dug into the original LISP sources (do they still exist?) to see when working GC first arrived?

You can find the source code here: http://www.softwarepreservation.org/projects/LISP/lisp15_fam...

The same site has the sources for plenty of other versions.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#163

Post by simen »

mafribe wrote: post #143
lispm wrote: post #138

Earlier quoted context omitted.

See the chapter 6.3 'The Free-Storage List and the Garbage Collector' in the LISP I Programmer's manual from March 1960. http://bitsavers.org/pdf/mit/rle_lisp/LISP_I_Programmers_Man...

Thanks. That's amazing. I always though GC must have been in Lisp from Day 1, but the Minsky article used to be the oldest one I was aware of. Has anybody dug into the original LISP sources (do they still exist?) to see when working GC first arrived?

I'm pretty sure that is the first implementation of Lisp. Earlier "versions" of Lisp were hand-compiled, because it was considered too difficult to produce a compiler. Then Steve Russell realized that McCarthy's "eval" function could be implemented in assembly language (which apparently hadn't occurred to McCarthy, he considered it merely theoretical) and produced the first Lisp interpreter. Note that the manual is from March 1960 and McCarthy's first paper on Lisp was published in April 1960, so nobody outside his circle at MIT would have known about Lisp at the time.

The manual also states that it's for "a version of Lisp being prepared for the IBM 709", implying the manual was written while the interpreter was still being developed, and all references I've found state that the IBM 709 version was the first practical implementation.

More on the very early history of Lisp here: http://jmc.stanford.edu/articles/lisp/lisp.pdf

Re: For Better Computing, Liberate CPUs from Garbage Collection

#164

Post by simen »

They're comparing to an in-order CPU. Given that most CPUs are out-of-order (at least of the non-embedded variety, and GC is less used in such applications anyway), it would be better and more intellectually honest to actually compare to a typical CPU that performs GC. They kind of address this in the paper but only in a short aside: "Note that previous research [1] showed that out-of-order CPUs, while moderately faster, are not the best trade-off point for GC (a result we confirmed in preliminary simulations)." So they don't quantify what any of this means.

I think it's an interesting idea, but it doesn't bode well when they seemingly choose the wrong target for comparison and hand-wave away the difference as insignificant.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#165

Post by fao_ »

geocar wrote: post #113
davedx wrote: post #82

Earlier quoted context omitted.

> It wastes time, it wastes space, it wastes energy. But all of these are much cheaper than developer labour and reputation damage caused by leaky/crashy software. The economics make sense. Anecdotally, I spent the first ~6 years of my career working with C++, and when I started using languages that did have GC, it made my job simpler and easier. I'm more productive and less stressed due to garbage collection. It's o…

> But all of these are much cheaper than developer labour and reputation damage caused by leaky/crashy software. And that's why so much effort has gone into making it fast and low latency, but it was a false dichotomy: We can have memory safety without garbage collection. - Automatic reference counting: Most people know about Objective-C's efforts in this space, but it's admittedly less automatic than programmers wou…

I think you mean "Automatic Garbage Collection", rather than just "Garbage Collection". The latter is exactly what you do in C when you use `free()`, the former is an automated system that does `free()` on your behalf at runtime. Indeed, the fact that you consider Rust's borrow checker to be part of the non-gc methods of handling memory, make it clear that you do indeed recognise this distinction, even thought it is merely implicit.

For the record, Automatic Reference Counting can't collect self-referential objects. And is also considered a method of automatic garbage collection. I haven't heard of any research on ARC being done statically, if you have that it would indeed be interesting.

Linear Lisp indeed looks extremely promising, I don't remember finding any code examples when I looked it up, it seems to be something that's languished in the theoretical department. HBaker has a series of really interesting papers, by the way, it's worth just going through his website :) There are a lot of nuggets of gold there.

It might also be worth for you to read up on the Mercury compiler -- if you haven't already -- which boasts compile-time memory allocation: https://mercurylang.org/documentation/papers.html#mazur-thes...

Re: For Better Computing, Liberate CPUs from Garbage Collection

#166

Post by eru »

davedx wrote: post #82
arcticbull wrote: post #80

IMO garbage collection is the epitome of sunk cost fallacy. Thirty years of good research thrown at a bad idea. The reality is we as developers choose not to give languages enough context to accurately infer the lifetime of objects. Instead of doing so we develop borderline self-aware programs to guess when we're done with objects. It wastes time, it wastes space, it wastes energy. If we'd spent that time developing…

> It wastes time, it wastes space, it wastes energy. But all of these are much cheaper than developer labour and reputation damage caused by leaky/crashy software. The economics make sense. Anecdotally, I spent the first ~6 years of my career working with C++, and when I started using languages that did have GC, it made my job simpler and easier. I'm more productive and less stressed due to garbage collection. It's o…

To steelman the idea a bit: giving more context for the GC is not the same as manual memory management.

Better static analysis of programs can precompute a lot of GC decisions.

Allocation on the stack is one example of that kind of optimisation. But you can imagine more sophisticated optimizations.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#167

Post by eru »

geocar wrote: post #113
davedx wrote: post #82

Earlier quoted context omitted.

> It wastes time, it wastes space, it wastes energy. But all of these are much cheaper than developer labour and reputation damage caused by leaky/crashy software. The economics make sense. Anecdotally, I spent the first ~6 years of my career working with C++, and when I started using languages that did have GC, it made my job simpler and easier. I'm more productive and less stressed due to garbage collection. It's o…

> But all of these are much cheaper than developer labour and reputation damage caused by leaky/crashy software. And that's why so much effort has gone into making it fast and low latency, but it was a false dichotomy: We can have memory safety without garbage collection. - Automatic reference counting: Most people know about Objective-C's efforts in this space, but it's admittedly less automatic than programmers wou…

Compare the "Unified Theory of Garbage Collection" (https://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf). Reference counting is a variant of garbage collection. But yes, you can take ideas from their to make your garbage collection better.

Linear/uniqueness typing is interesting. Clean is another language that uses something like it, and you can implement these ideas in Haskell as well.

Though in practice you want affine typing, not linear typing. (Basically, you want to be able to drop arguments without explicitly having to consume them.) The important bit about linear typing / affine typing is that you use your arguments at most once, not that you have to use them at least once.

That's how you can model mutation in a pure FP way, too. Not just GC.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#168

Post by eru »

Patient0 wrote: post #136
davedx wrote: post #82

Earlier quoted context omitted.

> It wastes time, it wastes space, it wastes energy. But all of these are much cheaper than developer labour and reputation damage caused by leaky/crashy software. The economics make sense. Anecdotally, I spent the first ~6 years of my career working with C++, and when I started using languages that did have GC, it made my job simpler and easier. I'm more productive and less stressed due to garbage collection. It's o…

In the ~15 years I spent building software in C++ I don't recall a single time that I wished for garbage collection. By using RAII techniques, it was always possible (nay, easy!) to write code that cleaned up after itself automatically. I always found it easier to reason about and debug programs because I knew when something was supposed to be freed, and in which thread. The only time that use of simple reference cou…

C++ code is full of use after free problems. You can avoid those with garbage collection.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#169

Post by eru »

Patient0 wrote: post #149
apta wrote: post #140

Earlier quoted context omitted.

While RAII is a very good technique, it is not the solution to all issues here. I read that some concurrent datastructure implementations would not be possible without a GC. Furthermore, when a project reaches a certain level of complexity, it ends up implementing GC anyway (see Unreal engine).

I agree that RAII does not solve everything - in particular, issues with memory fragmentation. However, I prefer the direction being taken by Rust and suggested by the top level poster: rather than having to run a separate thread which tries to infer which resources are no longer needed, with potentially large runtime costs, instead augment the language semantics with a clear ownership model, and thereby give the com…

RAII has nothing to do with memory fragmentation.

Solving memory fragmentation requires moving objects around. Usually you get that via a moving (or compacting) garbage collector. But there's no reason RAII style resource allocation couldn't move things around.

And there are plenty of garbage collection strategies that don't move objects around.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#170

Post by daemin »

One talking point I'd like to ask is:

For small short lived scripts and applications, do we even need to free any memory these days? For example you write a script which takes several seconds to execute, moves files, computes stuff with strings, etc. Should we really invest time and effort in the script interpreter to free the memory, where instead we can just exit normally and let the OS handle the clean up.

I would imagine this kind of paradigm could be much faster to run because of less runtime work being performed. The allocator used could also be a simple linear allocator which just returns the next free address and increments the pointer. If using multiple threads there could be one per thread.

What do people think of this?

Post reply on HN