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

261–270 of 460 posts

Re: For Better Computing, Liberate CPUs from Garbage Collection

#261

Post by apta »

cyphar wrote: post #255
tomp wrote: post #210

Earlier quoted context omitted.

This comment is just bad and misinformed all over. (1) Automatic Reference Counting doesn't work; its equivalent in interpreted languages is, well, reference counting , which can be optimized quite a lot (though has some issues with multithreading), but cannot collect cycles. (2) therefore, if you want reference counting, you have to either also have GC (for cycles), or program carefully to avoid creating cycles (whi…

> (1) Automatic Reference Counting doesn't work; its equivalent in interpreted languages is, well, reference counting, which can be optimized quite a lot (though has some issues with multithreading), but cannot collect cycles. This is what weakrefs (or better data structures) are for. The Linux kernel uses reference counting incredibly effectively for almost every structure. I think that pretty much discounts any arg…

I think the poster to whom you're responding means things like Cell and/or RefCell, which allow mutation behind the scenes while still being safe.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#262

Post by m0th87 »

cyphar wrote: post #255
tomp wrote: post #210

Earlier quoted context omitted.

This comment is just bad and misinformed all over. (1) Automatic Reference Counting doesn't work; its equivalent in interpreted languages is, well, reference counting , which can be optimized quite a lot (though has some issues with multithreading), but cannot collect cycles. (2) therefore, if you want reference counting, you have to either also have GC (for cycles), or program carefully to avoid creating cycles (whi…

> (1) Automatic Reference Counting doesn't work; its equivalent in interpreted languages is, well, reference counting, which can be optimized quite a lot (though has some issues with multithreading), but cannot collect cycles. This is what weakrefs (or better data structures) are for. The Linux kernel uses reference counting incredibly effectively for almost every structure. I think that pretty much discounts any arg…

The point with weakrefs, though, is that they still require developer intervention.

Also, you can use most memory management facilities in Rust (including reference counting) without `unsafe`.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#263

Post by pedrocr »

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…

> Like Rust but without the need for Rc and Arc boxes. Rust gets us 80% of the way there.

I think you're qualifying Rc/Arc as kludges to get around the type system. They may end up being used like that sometimes but when well used they are actually encoding extra semantics, just like &Type and &mut Type.

A simple example is a cache get() method:

pub fn get(&self, key: &K) -> Option>

https://docs.rs/multicache/0.5.0/multicache/struct.MultiCach...

This allows you to get and use a cache value across your program and depending on outside input the value can disappear first in the cache by eviction or in the consumer. So Arc is already expressing to the compiler the exact semantics. It just so happens that the actual lifetime is runtime defined from outside input so it must be managed dynamically.

I don't see a general way around that without copying but maybe a lot more can be inferred automatically so you get similar ergonomics to a GC language by introducing Rc/Arc/etc automatically at compile time. I don't think that's a good fit for a system programming language like Rust though where you don't pay extra costs without asking for them explicitly. But maybe there's space for a higher level language that does all that magic and doesn't use a GC. Someone trademark Rustscript.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#264

Post by DenisM »

Objective-C ARC (automatic reference counting) solved the problem neatly for my iOS apps.

Is there some overhead? Maybe, but it's neatly spread out through the entire application life time, so there is rarely[1] a UI-freezing stutter associated with GC. To reduce the overhead I turned off thread-safety and simply never access the same objects from more than one thread (object has to be "handed off" first if it comes to that).

One wart on the body of ARC is KVO, which I avoid like a plague for many other reasons anyway.

The other wart is strong reference loops. This can be solved by the app developer by designing architecture around the "ownership" concept (owners use strong references to their ownees, all other links are weak references). This is a good idea in itself as it increases clarity of the program. I do make an occasional slip, which is where I need to rely on Instruments, and I do wish I had better tools than that, something more automatic that would catch me in the act. Maybe a crawler that looks for loops in strong references during the development process but is quiet in release builds. Or at least give me a pattern to follow that makes it easy to catch my errors. For example, we could assign a sequential number to each allocated object, and only higher-ranked object could strongly refer to lower-ranked object. This won't work for everyone but I wouldn't mind fitting my app to this mold if that gave me immediate error when I slip.

[1] if you release a few million objects all at once it may stutter for a second. Could be handed off to a parallel thread maybe.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#265

Post by lispm »

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?

According to Prof. Herbert Stoyan, probably the oldest GC algorithm description is in 'J. McCarthy, M.L. Minsky: Artificial Intelligence. Quarterly Progress Report No. 53, Res. Lab, of electronics MIT, Cambridge, April 1959.' Prof. Stoyan then mentioned that the 'first garbage collector was implemented by Dan Edwards during June/July of 1959'.

So we have 60 years of GC research.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#266

Post by p_l »

_old_dude_ wrote: post #253
p_l wrote: post #130

Earlier quoted context omitted.

Lisp Machines didn't use tags for tracking liveness/evacuation of objects, though. They used them for safety, which automatically gave them precise , as opposed to conservative , GC which always knew whether it was dealing with a pointer. They also had special, CPU-handled type of forwarding pointers, which when accessed "normally" would transparently redirect you to forwarded location.

The forwarding pointer you are describing is equivalent to a ZGC colored pointer with the evacuation bit set that a GC barrier (a load barrier) will rewrite to the evacuation address. and yes ZGC doesn't use colored pointer to track if a value is an integer or a pointer because Java unlike Lisp is typed so the VM derives those information from the bytecode.

Lisp is also typed - the tagging made for easier native code compilation vs. bytecoded approaches.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#267

Post by simias »

norswap wrote: post #250
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…

Ridiculous. The problem is not that you don't know when/where the lifetime will end — that can usually be characterized by a terse "English" description. The problem is that this lifetime is dynamic in nature. The end of the lifetime of an object may coincide with some user input, for instance. At this point, either you go back to manual management, with the potential for errors (and for what it's worth, I think manu…

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 resources here while you're at it?

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. Just remove your object from whatever data structure was holding it and let the language automagically run the destructor for you. I find RAII a lot easier to model and think about than "you drop this reference and one day maybe your object is destroyed, but don't really rely on that".

>No one has ever devised a scheme that lets you specify very dynamic lifetimes AND statically checks that no leak can occur.

GC doesn't solve that either. If you're not careful and let a reference to old data dangle somewhere in your code you can effectively "leak" data just fine. When there's no clear ownership and nobody knows who's supposed to clean what it's very easy to end up with data dangling everywhere through complex ownership graphs. GC may mitigate some use-after-free problems (generally by masking the problem) but that is something that can be solved without GC either.

I'm not saying that applications with (justifiably) extremely complicated ownership semantics that also require very high performance don't potentially benefit from using a GC and that it could outperform manual memory management by, for instance, batching the object deletions. What I'm saying is that it's that such applications are few and far in-between, basically 100% of all the code I've ever wrote in my ~15years as a professional software developer didn't have such requirements.

GCs should be an opt-in niche tool used to solve specific problems, not a kludge to let developers write sloppy code and get away with it.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#268

Post by cyphar »

apta wrote: post #261
cyphar wrote: post #255

Earlier quoted context omitted.

> (1) Automatic Reference Counting doesn't work; its equivalent in interpreted languages is, well, reference counting, which can be optimized quite a lot (though has some issues with multithreading), but cannot collect cycles. This is what weakrefs (or better data structures) are for. The Linux kernel uses reference counting incredibly effectively for almost every structure. I think that pretty much discounts any arg…

I think the poster to whom you're responding means things like Cell and/or RefCell, which allow mutation behind the scenes while still being safe.

Right, but I think their main complaint is that RefCell is implemented using "unsafe" -- hence my point about "unsafe".

Re: For Better Computing, Liberate CPUs from Garbage Collection

#269

Post by jandrewrogers »

reitzensteinm wrote: post #244
jandrewrogers wrote: post #234

Earlier quoted context omitted.

In high-performance systems, software architectures have actually been moving toward non-shared mutability. Shared immutability tends to waste a performance-limiting resource (memory bandwidth).

I'm a bit confused by your phrasing. Non-shared mutability makes perfect sense (and is not the thing I believe needs to go), but at some point you have to share the results of a computation. If not shared immutability, how is this done in the systems you're describing? I assume message passing, queues or similar?

Sorry, I wasn't clear. There are two common software architecture schools for scaling practical concurrency.

The first is the copy-on-mutate style commonly used in functional programming paradigms. This is what I assumed was meant by "shared immutability".

As you surmised, in the second model individual threads own all mutable state, and operations on that state are requested via message passing (usually SPSC queues within individual servers, which are scalable and extremely efficient). This makes all the code effectively single-threaded. The key technical element for these designs is that there often needs to be a mechanism to sporadically transfer ownership of state between threads to balance load, also arbitrated over the SPSC queues. This has a number of straightforward solutions.

The second model has come into favor mostly because it is very memory-friendly, due to excellent natural cache locality and requiring minimal copying of state.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#270

Post by wglb »

MrEldritch wrote: post #242
jerf wrote: post #236

Earlier quoted context omitted.

"I can live with that because if you do it right it does not impact end user latency." The vast majority of GC use does not impact end user latency. Thinking otherwise is either the availability heuristic at work, or you work in AAA videogames or another ultra-high-real-time-performance industry and don't realize you're not in the center of programming work, you're on an extreme. (A perfectly valid and sizeable extre…

"Downvote as disagreement" is such a pervasive pattern that I Find myself doing it automatically even when I know that's not what downvote is "supposed" to be for. I suspect it's because I'm more likely to view posts that I disagree with as being poorly thought-out. This even extends to platforms where downvoting is not a thing - witness 4chan's struggles with "sage is not a downvote" ("sage" being a function which a…

PG long ago said that it is ok to use downvotes (in part) to signal disagreement.
Post reply on HN