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

101–110 of 460 posts

Re: For Better Computing, Liberate CPUs from Garbage Collection

#101

Post by bollu »

arcticbull wrote: post #83
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. The economics make sense. Of course, with traditional languages, that's the trade-off we're being asked to make. That's my point! We need to develop languages that accurately encapsulate lifetimes statically so that we can express that to the compiler. If we do, the compiler can just make instances disappe…

This only works if your language is strict. With a lazy language like Haskell, you can't statically infer (at least naively with respect to scoping rules) when something lives and dies.

Performing this statically is hard, and GHC tries to do it (Demand analysis).

But without a GC, these sorts of languages would be a no-go, as would logic-based languages like Prolog which need to GC their internal data structures.

While we now have the expertise for eliminating the GC from single threaded strict programs (multi threading in Rust is still quite complex, and you do see Rc> more often than not in these settings, which is essentially refcounting/GC), this _does not scale_ to all models of languages.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#102

Post by ddebernardy »

jondubois wrote: post #85

>> consumes a lot of computational power—up to 10 percent or more of the total time a CPU spends on an application. I stopped reading there. 10% is nothing. For such a useful feature as automatic garbage collection, for the vast majority of applications, I'd gladly give away 50% of the CPU. In terms of ensuring code correctness and robustness, if I had to choose static typing or automatic garbage collection, I'd pick…

There are times when it counts...

https://www.youtube.com/watch?v=JEpsKnWZrJ8

Re: For Better Computing, Liberate CPUs from Garbage Collection

#103

Post by mafribe »

arcticbull wrote: post #97
reitzensteinm wrote: post #92

Earlier quoted context omitted.

In my opinion, shared memory mutability is the actual bad idea that's going to eventually die. It's not just error prone, it doesn't scale; try mutating the same cache line from two threads on an Intel desktop chip and see how that goes. Let alone across mesh buses, chiplets, dual sockets or (God forbid) the network. Garbage collection on immutable data is vastly easier; it's intrinsically non blocking, concurrent an…

Am I wrong in thinking that a system comprised of entirely immutable memory doesn't even need a garbage collector? If you built such a system in Rust would not all memory just be deallocated once no longer utilized? The rust principal is (many readers XOR one writer) leads to fully static memory management. This is my point. We need to go back and re-think our language design principals keeping memory management in m…

   Am I wrong ...
Yes.

Unless your memory is infinite. Rust also automatically deallocates memory that is no longer used, so it's some kind of GC, but one where the point of deallocation is either statically determined (based on nesting of life-times) or dynamically (using reference-counting). The problem with static dealloc is that the compiler cannot always work out when memory becomes free and must make conservative approximations (see Rice's theorem [1]), the problem with ref-counting is circular data structures (and also the cost in space and time and synchronisation across threads of maintaining an index).

[1] https://en.wikipedia.org/wiki/Rice%27s_theorem

Re: For Better Computing, Liberate CPUs from Garbage Collection

#104

Post by pron »

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…

I think that garbage collection has proven to be the best idea in programming languages in the past decades, and probably the only one that has made an impact at all. It's getting so good these days that few are willing to consider "moving on." In terms of throughput, it beats manual memory management (in fact, in principle, the cost of GC can be made arbitrarily low; a famous Andrew Appel paper shows how it can be cheaper than a stack), and in terms of latency we now have GCs with worst-case pauses of ~1ms on terabytes of heap, with an acceptable impact on throughput.

> Think about it, instead of finding a way of expressing when we're done with instances, we have a giant for loop that iterates over all of memory over and over and over to guess when we're done with things. What a mess!

It would be a mess if that's how modern GCs worked, but they don't. The problem with "expressing when we're done with instances" is that it's just wasteful, especially when concurrency is involved. This is one area of computing where the computer can offload a human task, and do so quite efficiently.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#105

Post by tempguy9999 »

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…

You say a lot of things without justification: "IMO garbage collection is the epitome of sunk cost fallacy. Thirty years of good research thrown at a bad idea." "Garbage collection is just plain bad." And more.

> The reality is we as developers choose not to give languages enough context to accurately infer the lifetime of objects.

Possibly because it's hard and until compilers + maths developed enough, it wasn't possible. Maybe. I dunno, but there's probably a reason Rust didn't appear in the 1970s. They're probably harder to use than conventional langs, judging by what I read about Rust's borrow checker (dunno, Rust's on my todo list so no actual experience).

> we have a giant for loop that iterates over all of memory over and over and over to guess when we're done with things

This is from memory so I may be wrong, but a conservative GC will iterate over the whole memory but if you're using one of those you've probably got other problems because yes, conservative GCs do 'guess'. (Edit: and when it guesses wrongly it can fail to free, causing leaks. And some optimisations that temporarily make pointer values 'disappear' can cause premature frees of the object pointed to. I believe an example of the latter is using branch-free XOR on pointers to swap them. 'proper').

Most modern systems will use something more sophisticated and known-correct such as tracing and will trace just the live stuff. Mark-compact for sure only touches live data which makes it efficient for functional langs (for some definition of 'efficient', I have questions).

I'd recommend reading a book ('The Garbage Collection Handbook: The Art of Automatic Memory Management' 2nd edition, Richard Jones et al) before abusing GC. I actually agree with some of what you're saying but you need to say why.

> It wastes time, it wastes space, it wastes energy.

I quite possibly agree! (see a recent previous post where I call lack of optimisation in scala 'immoral') But if you just give your opinion without some solid backup I can't endorse you. Please read the GC book, it really is very good indeed. The author's a nice guy too, met him years ago.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#106

Post by lemagedurage »

jondubois wrote: post #85

>> consumes a lot of computational power—up to 10 percent or more of the total time a CPU spends on an application. I stopped reading there. 10% is nothing. For such a useful feature as automatic garbage collection, for the vast majority of applications, I'd gladly give away 50% of the CPU. In terms of ensuring code correctness and robustness, if I had to choose static typing or automatic garbage collection, I'd pick…

I can agree with that but also you missed the point of the article by not reading along there.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#107

Post by p_l »

incompatible wrote: post #59
mailslot wrote: post #13

Seems like we could just as easily stop using garbage collection. ... or even go back to reference counting / smart pointers and just live with the “limitation” that we can’t have circular references.

Why would a reaction to a faster / low resource GC method be to stop using GC?

Because people aren't taught about GC or memory management at all, so cheap soundbites about "GC being bad" from old survives as "wisdom"

Re: For Better Computing, Liberate CPUs from Garbage Collection

#108

Post by szemet »

dan-robertson wrote: post #99
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…

Knowing when you’ll be finished with an object solves the issue of knowing which objects to free but not the issue of heap fragmentation. The main reason that eg C programs don’t suffer so much from heap fragmentation is that writing a C program which uses ephemeral objects in the way a GC’d language might is so incredibly painful that one mostly avoids the convenient programming techniques which lead to fragmentatio…

E.g. Redis is a well known example, that have to battle with the fragmentation problem:

https://github.com/antirez/redis/pull/3720

Re: For Better Computing, Liberate CPUs from Garbage Collection

#109

Post by xxs »

mailslot wrote: post #13

Seems like we could just as easily stop using garbage collection. ... or even go back to reference counting / smart pointers and just live with the “limitation” that we can’t have circular references.

Ref counting is worse than GC. Ref counting: deeper pipelines, branch predictor extra load.

And when you need multithreaded/concurrency it goes to atomic operations, cache coherency traffic, memory and compiler barriers.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#110

Post by moring »

gizmo686 wrote: post #10
etaioinshrdlu wrote: post #5

It does seem like just doing it in hardware may be a linear gain but isn't a fundamentally better algorithm. There's a proof that you do need to pause your program eventually, if you want to be sure you get all the garbage.

Hardware is fundamentally parallel, CPUs are fundamentally serial; it is possible for a hardware solution to have a super-linear speedup in time. As a simple example, what is the time complexity of zeroing out n bytes of memory. With a CPU, this is O(n). However, with proper hardware support, this can be done in O(1) time. For a simple garbage collecting example (no idea how their chip does it), consider a simple mar…

You would need an infinite amount of hardware, though, as the O() notations only apply for n towards infinity.
Post reply on HN