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

441–450 of 460 posts

Re: For Better Computing, Liberate CPUs from Garbage Collection

#441

Post by pjmlp »

seanmcdirmid wrote: post #188
barrkel wrote: post #184

Earlier quoted context omitted.

> Garbage collection is about visiting live objects to figure out what's alive and ignoring the dead stuff That's a description of tracing GC, not a definition of GC. GC is whatever technology that enables what you've called automatic memory management: a kind of illusion that there is infinite memory, from the programmer's perspective. That might involve some mix of reference counting (Python is probably the biggest…

GC has always meant tracing GC while reference counting (ever since McCarthy invented it) was considered another form of automatic memory management (like using arenas, doing escape analysis, etc...). Only recently in hacker news have they become all merged into the same word, for some reason.

That reason are academic worthy books describing garbage collection algorithms, I can provide a couple of them.

Lets start with the Garbage Collection Handbook, chapter 5.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#442

Post by pjmlp »

blub wrote: post #239
simiones wrote: post #215

Earlier quoted context omitted.

The nicest point about GC is that, for the vast majority of data, you no longer need to have a concept of ownership at all. Ownership is not a fundamental architectural property - it is "only" a powerful technique for tracking data with a specific lifetime (of course, even in GC languages you still need proper ownership semantics for some pieces of data).

Ownership itself might not be, but lifetimes are and the two concepts are tightly related. That's why Java and C# both had to introduce a way of (semi-)automatically closing resources, waiting for the GC was a catastrophe.

Common Lisp, CLU, Mesa/Cedar, Modula-3 and many other system languages with GC always supported those kind of mechanisms.

Java and C# did nothing new there, only catching up with was already the state of the art before they were born.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#443

Post by geocar »

barrkel wrote: post #418
geocar wrote: post #196

Earlier quoted context omitted.

> GC is whatever technology that enables what you've called automatic memory management: a kind of illusion that there is infinite memory, from the programmer's perspective. That's definitely not what McCarthy meant by it. I understand that's probably a common view nontheless, but I can use sbrk() and the fact my computer has gobs of ram/swap, and I'm not going to call that garbage collection. I don't think this defi…

Actually, I think process termination is pretty useful as garbage collection. It's normally much more reliable for releasing resources, for one thing. And there's little sense in cleaning up RAM when you're just going to quit.

The kernel still deallocated those pages as an explicit [manual] result of a free-like call -- that just so happens to be named exit().

To seriously tell people that every C program running on unix has automatic "garbage collection" built-in seems like it would create very confusing conversations.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#444

Post by geocar »

pjmlp wrote: post #440
stouset wrote: post #351

Earlier quoted context omitted.

> Naïve ARC is very expensive… So is/was garbage collection, and we’ve spent thirty years trying to squeeze every possible bit of performance out of it. Maybe it’s time to look at other approaches.

Even more so from reference counting, given that it was the very first kind of garbage collection algorithms.

I don't think that's true.

Garbage collection (to my knowledge) was invented by McCarthy back in the late 1950s[1] in the following three paragraphs of his paper "Recursive Functions of Symbolic Expressions and Their Computation by Machine":

Nothing happens until the program runs out of free storage. When a free register is wanted, and there is none left on the free-storage list, a reclamation cycle starts.

First, the program finds all registers accessible from the base registers and makes their signs negative. This is accomplished by starting from each of the base registers and changing the sign of every register that can be reached from it by a car − cdr chain. If the program encounters a register in this process which already has a negative sign, it assumes that this register has already been reached.

After all of the accessible registers have had their signs changed, the program goes through the area of memory reserved for the storage of list structures and puts all the registers whose signs were not changed in the previous step back on the free-storage list, and makes the signs of the accessible registers positive again.

That's mark/sweep!

He adds as a footnote "We already called this process ``garbage collection'', but I guess I chickened out of using it in the paper--or else the Research Laboratory of Electronics grammar ladies wouldn't let me." but doesn't explain where the term came from. I suppose it's possible he didn't invent it, but I've never seen anything on that and I think most of the existing strategies used for memory allocation at the time were very explicit -- FORTRAN didn't even have ALLOCATE yet!

Do you have a reference for that?

[1]: http://www-formal.stanford.edu/jmc/recursive/node4.html

Re: For Better Computing, Liberate CPUs from Garbage Collection

#445

Post by klodolph »

steveklabnik wrote: post #434
klodolph wrote: post #432

Earlier quoted context omitted.

Hi! I think you may have repeated what I said in my comment, that the letter "a" stands for different things. Although they do the same thing: they are both atomic (in the sense of concurrency) and automatic (in the sense that you do not have to explicitly retain or release objects).

That’s the thing: they’re not automatic in Rust. You have to explicitly retain. (Release is automatic though.) Furthermore, in Swift it’s pervasive, and in Rust, it only happens for types that explicitly opt-in.

It sounds automatic to me. Maybe we disagree about what "automatic" is.

It also sounds like you are hunting for ways in which Swift and Rust are different. This is completely unnecessary! It turns out that I already know that they are different languages, and that the features do not map exactly 1:1 to each other. I hope next time you give me a little credit.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#446

Post by mailslot »

mantap wrote: post #58
mailslot wrote: post #45

Earlier quoted context omitted.

It has optional cycle detection, yep. But... you could also just spend a couple of minutes to not have cyclic references.

Closures are objects that can participate in cycles. And the lifetime of closures is very hard to track statically.

They are and they should be used responsibly. I’d argue sparingly also.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#447

Post by apta »

geocar wrote: post #436
apta wrote: post #376

Earlier quoted context omitted.

> still need to pay attention with GCd languages no to leak references that cannot be GCd. Java has this sort of problems. Unless you're doing weird things with class loaders, this is a non-issue. > Erlang on the other hand has a VM that makes GC much faster than in other languages What makes Erlang's VM make GC faster than other languages?

That's a very loaded question. I don't think it's easy to point to one thing Erlang is doing and say that is why it's faster, partly because I think the way Erlang programmers are encouraged to write their programs also has an effect; The language itself may have a greater effect on its GC performance than the GC implementation itself. As an example: In Erlang, we have function calls like F(X) but we also have messag…

Thanks for the links. That being said, new developments in GCs on the JVM (like Shenandoah and ZGC) are yielding very impressive results. Things like < 1ms pause times for heaps in the TB range. No other free GC for any other language approaches this as far as I'm aware, including golang's which people claim is fast, but completely gets destroyed for even heaps in the GB range (I did some benchmarks).

Re: For Better Computing, Liberate CPUs from Garbage Collection

#448

Post by skrimp »

c-smile wrote: post #320
simias wrote: post #267

Earlier quoted context omitted.

I don't see your point. Of course sometimes the lifetime of an object is not tied to code scope but actually to something dynamic. Let's say for instance when you close a tab in your browser you expect the resources to be freed (ignoring caching to simplify the argument). Clearly somewhere in your code you have to explicitly handle tab closing and break the references to allow the GC to do its job. Why not free the r…

> GCs should be an opt-in niche tool used to solve specific problems. That is true. Sciter ( https://sciter.com ) contains implementation of DOM(tree), CSS and script. DOM is a regular tree structure - each element of the tree has strictly one parent and no cycles on the tree in principle. It does not need GC at all and is not using it for DOM tree management. CSS is a collection of collections of name/value pairs. N…

This is very hard to achieve because GC + RAII do not play nice together. It's hard to reason about whether an RAII resource has been cleaned up since managed objects have non-deterministic destruction. This non-determinism is unsuitable for common RAII patterns like scoped mutex locks. Now, the question being begged is "Can this be avoided by not using destructors with managed objects?" Yes, but not reasonably. Any unmanaged objects that are owned in the entire managed object graph now also have non-deterministic destruction. Thus, the only way to reasonably follow this constraint is to have the compiler disallow/warn when an object with a non-trivial destructor (explicit or implicit) is used with GC. If that wasn't enough of a pain, any runtime-polymorphic types may also need to be destructed and these can't be known at compile time if dynamic linking is used. In essence, these concepts are incompatible to a point where any language supporting both will likely make extensive trade-offs.

I find this really sad because many developers may never be exposed to how elegant RAII can be if they are never exposed to non-memory-managed languages. Sure it can be approximated using `with` constructs, but those don't allow resource allocations to cross scope boundaries.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#449

Post by UncleMeat »

Shikadi wrote: post #401
rayiner wrote: post #326

Earlier quoted context omitted.

> When you say "manual memory management" if you're thinking C-style malloc-free then you have a point, it's very easy to forget a free() somewhere. But any language with destructors can handle these situations without much more overhead than GC-based approaches. What happens when that object is shared and still referenced from somewhere else? Now you have a use after free error waiting to happen.

That's what smart pointers/ref counting is for

That's literally GC.
Post reply on HN