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

171–180 of 460 posts

Re: For Better Computing, Liberate CPUs from Garbage Collection

#171

Post by eru »

tempguy9999 wrote: post #111
arcticbull wrote: post #83

Earlier quoted context omitted.

> 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…

> If we do, the compiler can just make instances disappear statically when we're done with them -- not dynamically! Not possible generally. It would be easy to create a situation where some kind of refcount is a necessary final fallback. > The truth is with most of the Rust I write, I don't have to worry about allocation and deallocation of objects, and it happens. If Rust is the answer, why are you pushing for new l…

>> If we do, the compiler can just make instances disappear statically when we're done with them -- not dynamically!

> Not possible generally. It would be easy to create a situation where some kind of refcount is a necessary final fallback.

Either refcount or a GC. But those situations might be rare in practice with a good system.

If you think about it, generational garbage collection implements lots of those heuristics. (But it's closer to a JIT optimizer, not a static optimizer.)

Re: For Better Computing, Liberate CPUs from Garbage Collection

#172

Post by p_l »

tjoff wrote: post #156
p_l wrote: post #123

Earlier quoted context omitted.

Not having GC in no way improves understanding of architecture or gives better performance. Hordes of C/C++ programmers that don't understand memory management but swear by malloc()/free() are a good example of that. And it's not like C/C++ are only language without GC, they are just popular now . Typical programmer is taught nothing about memory management, till maybe they learn bits and pieces (often by hearsay and…

Not necessarily no. Just as having type information doesn't lead to a better program. But it helps. And is something you need to reason about regardless. Being explicit about it isn't a huge overhead but has lots of benefits.

Being explicit usually means that you have to drop whole classes of optimizations, or manually perform the analysis yourself (probably resulting in errors).

Re: For Better Computing, Liberate CPUs from Garbage Collection

#173

Post by eru »

bollu wrote: post #101
arcticbull wrote: post #83

Earlier quoted context omitted.

> 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. Whi…

GHC infers these kinds of things all the time. It can't do so in general, but neither can you do that in a static language.

GHC even has a strictness analyzer.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#174

Post by gpderetta »

xxs wrote: post #161
gpderetta wrote: post #146

Earlier quoted context omitted.

> 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?

Herlihy, The Art of Multiprocessor Programming. I would quote chapter and verse, but somehow the book has disappared from my desk.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#175

Post by eru »

pron wrote: post #104
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 c…

> 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.

Depends on how you set your thresholds. Paying more attention to side-effects / purity / const has been pretty useful, too. And so have mainstream languages adopting first class functions. And making it easy to compose data structures. (Compare eg how Python allows you to return essentially two values via a tuple, and how cumbersome the same tasks is in Java; so people are tempted to use side-effects instead.)

Re: For Better Computing, Liberate CPUs from Garbage Collection

#176

Post by geocar »

tempguy9999 wrote: post #135
geocar wrote: post #113

Earlier quoted context omitted.

> 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…

You say > but it was a false dichotomy: We can have memory safety without garbage collection. but then say > Automatic reference counting (ARC henceforth). Naive ARC is AFAIK very expensive as it causes a lot of updates at each pointer 'take' even if it's a read only (chasing pointers), trashing caches. Poss. even worse if multithreading is used as a memory barrier may have to be issued. Also it does not collect cycl…

> Naive ARC is AFAIK very expensive as it causes a lot of updates at each pointer...

Yes, and I think that's why people shy away from it. Language design can help a lot though: Array languages use reference counting almost exclusively because nesting objects is uncommon. That means no pointers to chase the vast majority of the time.

> if ARC is what you think it is, how is it not an implementation of GC?

Garbage Collection involves crawling live objects from roots to determine what's still alive.

If you're not doing that, you might still be doing automatic memory management, but you're not doing GC.

There's tricks (gardens, barriers, treadmills, colouring, etc) to do less work or less work at a time, but it remains predicated on the assumption is that you have more garbage than you have live objects so you're doing less work by only crawling the live objects. If this is true, then GC should be a win, but it's not true an awful lot of the time, which is why manual memory management always beats GC for performance (latency and throughput).

[†]: notwithstanding your earlier point about pointer chasing...

> I'll check out linear lisp if I can find the time.

I can recommend everything Baker has written on this subject: it's all gold.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#177

Post by eru »

rbehrends wrote: post #155
dochtman wrote: post #114

Earlier quoted context omitted.

Good throughput with GC seems to come with significant extra memory use: "We compare explicit memory management to both copying and non-copying garbage collectors across a range of benchmarks using the oracular memory manager, and present real (non-simulated) runs that lend further validity to our results. These results quantify the time-space tradeoff of garbage collection: with five times as much memory, an Appel-s…

This is not only a dated paper (a decade and a half old), but it relies on assumptions that do not necessarily hold in practice. If you test actual allocation performance on actual current day hardware, you may end up with completely different results, e.g.: https://github.com/rbehrends/btree-alloc

That's a very fresh repo. I wonder how GHC would fare. I guess I should contribute.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#178

Post by fnord123 »

tempguy9999 wrote: post #135
geocar wrote: post #113

Earlier quoted context omitted.

> 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…

You say > but it was a false dichotomy: We can have memory safety without garbage collection. but then say > Automatic reference counting (ARC henceforth). Naive ARC is AFAIK very expensive as it causes a lot of updates at each pointer 'take' even if it's a read only (chasing pointers), trashing caches. Poss. even worse if multithreading is used as a memory barrier may have to be issued. Also it does not collect cycl…

>it causes a lot of updates at each pointer 'take' even if it's a read only

This isn't required in the read-only case. If you're only borrowing the value, for example, taking a const& in C++ and not holding onto it, then you can cast to the underlying type and use the reference. In Rust you can also just borrow:

https://play.integer32.com/?version=stable&mode=debug&editio...

>trashing caches

ARC is usually atomic reference counting. Indeed that will trash caches because it must invalidate the cache line where the reference count lives in other cores whenever it's updated. RC without atomicity won't invalidate cache lines on other cpus.

FWIW, GCC has an extension to shared_ptr that doesn't use atomic reference counting:

https://gcc.gnu.org/onlinedocs/libstdc++/manual/memory.html#...

> Also I've read it causes memory fragmentation

Any heap allocations not bound to an arena and not part of a compacting garbage collector is likely to cause memory fragmentation. Stack allocations for example are implicitly compacted.

>Also and even more, if ARC is what you think it is, how is it not an implementation of GC?

This is a "can submarines swim" type of question and is completely uninteresting (imo).

>Finally, if [perl5] outperforms [python], please provide a reference.

It doesn't. Not by a long shot. Reference: https://bitbucket.org/ewanhiggs/csv-game/

Re: For Better Computing, Liberate CPUs from Garbage Collection

#179

Post by Patient0 »

eru wrote: post #169
Patient0 wrote: post #149

Earlier quoted context omitted.

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.

I was simply stating that RAII does not solve the memory fragmentation issues. Many GC's do solve the memory fragmentation issue.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#180

Post by titzer »

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…

IMO manual memory management is the epitome of sunk cost fallacy. Sixty years of good programmer effort thrown at a bad idea that has produced an endless stream of security bugs and performance problems that have only hidden the cost of memory management behind non-obvious barriers and done severe violence to systems languages with an absurd obsession with custom allocators and baked ownership into otherwise straightforward APIs and made all programming harder.

> we have a giant for loop that iterates over all of memory over and over and over

I don't think you understand how garbage collectors work.

Post reply on HN