For Better Computing, Liberate CPUs from Garbage Collection • Hacker News Board

Re: For Better Computing, Liberate CPUs from Garbage Collection

#351

Post by stouset » Thu, May 09, 2019, 5:26 PM UTC

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…

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

Re: For Better Computing, Liberate CPUs from Garbage Collection

#352

Post by beersigns » Thu, May 09, 2019, 5:27 PM UTC

jokoon wrote: post #349

It reminds me of the days I was reading Knuth's quote "97% of the time premature optimisation blabla" every time someone was trying to make something faster. CPUs are not getting faster, yet it seems using tools that makes things run faster are somehow taboo. Wirth's law: Wirth's law is an adage on computer performance which states that software is getting slower more rapidly than hardware becomes faster. Why is java…

Think most companies resist using lower level languages due to their ultimate purpose being to build products that provide value and sell them. They are generally far less concerned with the technical details and conciseness of the implementations. "Good enough" is a very squishy term but for most companies, for better or for worse, that bar is pretty low. There are plenty of industries that focus on lower level langs and use them pretty well but it's not the norm for big corporations who value rapid turn around over all other factors.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#353

Post by pcwalton » Thu, May 09, 2019, 5:28 PM UTC

rayiner wrote: post #329

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…

Cyclic data structures, memory safety, memory management without tracing. Pick 2.

Well, you can use weak pointers appropriately in a safe setting. It's not fun though. Alternately, you can use a layer of indirection, such as throwing all your graph nodes in a big vector and having them use indices to refer to one another.

So I would perhaps revise that statement to "easy cyclic data structures, memory safety, memory management without tracing, pick two".

Re: For Better Computing, Liberate CPUs from Garbage Collection

#354

Post by kazinator » Thu, May 09, 2019, 5:33 PM UTC

simias wrote: post #267

norswap wrote: post #250

Earlier quoted context omitted.

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

> Why not free the resources here while you're at it?

Because you do not have an exclusive reference to all of them; we could be freeing something that is still in use somewhere.

So why not reference-count? Because reference counting is slow, and must be meticulously maintained (here, languages help with constructs like smart pointers), and doesn't handle cycles in the object structure.

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

The RAII model doesn't do away with this "maybe" in any shape or form. We drop this reference, and the smart pointer decrements the refcount; maybe it has hit zero so the object is destroyed, maybe not. Maybe the zero refcount triggers a whole cascade of thousands of other objects hitting their zero refcount, which takes many cycles to execute, or maybe it doesn't.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#355

Post by kazinator » Thu, May 09, 2019, 5:35 PM UTC

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…

Rather, GC should be default, and you opt-out of GC for specific optimization problems.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#356

Post by jeffdavis » Thu, May 09, 2019, 5:37 PM UTC

lossolo wrote: post #274

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…

> Rust is a start, Rust is not a start, it's a next iteration over old ideas (look at Ada, Cyclone etc). All of those languages were niche and will stay niche for a reason. > Garbage collection is just plain bad. I for one am glad we're finally ready to consider moving on. We are not moving anywhere. You still need lifetime annotations in Rust and design your application in specific way to satisfy the borrow checker.…

Productivity has many facets and is hard to measure. A lot of people feel very productive in rust because it catches a lot of problems early on. GC allows you to be sloppy in reasoning about the lifetime of an object, which is often an important design point that affects the overall system.

Also, you typically have to think about lifetimes when writing libraries, not so much when writing applications that use the libraries.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#357

Post by tomp » Thu, May 09, 2019, 5:39 PM UTC

pedrocr wrote: post #335

tomp wrote: post #328

Earlier quoted context omitted.

By "conflating" I mean that Rust's memory management technology provides just one kind of multi-threading safety (i.e. "multiple readers/single-writer" model), but to implement other kinds of multi-threading-safe algorithms/data structures, you need to transcend beyond ownership+borrowing. I think "epoch-based memory reclamation" (which Linux kernel also uses IIRC) is still a (primitive / limited / contained) form of…

> By "conflating" I mean that Rust's memory management technology provides just one kind of multi-threading safety (i.e. "multiple readers/single-writer" model), but to implement other kinds of multi-threading-safe algorithms/data structures, you need to transcend beyond ownership+borrowing. That's not "conflating" anything. You're just saying that "to do other things you need other stuff". Sure, to implement multi-t…

I agree, the model of lock-free data structures is pretty much perfect for reference counting (no cycles, shallow reference tree... just needs to be thread-safe). I wonder then why epoch-based approaches are used, which (sound like they) are more difficult / tricky to implement... I honestly have no idea. The only thing that comes to mind is that they seem to require another atomic primitive (atomic increment, otherwise lock-free data structures only require compare-and-swap), which might not be available on all platforms...

Re: For Better Computing, Liberate CPUs from Garbage Collection

#358

Post by arcticbull » Thu, May 09, 2019, 5:40 PM UTC

kbenson wrote: post #321

simias wrote: post #303

Earlier quoted context omitted.

My point is that you need a "destructor" even with a GC. Continuing with my example you need to pop your tab from the data structure containing your tabs and you have to make sure that all references are dropped so that the GC will do its work. When I write Rust code I basically never have to explicitly free anything outside of FFI code dealing with C pointer or the like. The most straightforward way to allocate anyt…

> it's also important to recognize when something can't be pushed under the rug. If you haven't heard of it, you might be interested in the Waterbed Theory of Complexity[1]. The idea behind it is that it's not that you can't push down complexity in an area, but often that complexity just pops up in a different area. For example, you can do away with the vast majority of allocating and freeing memory, but the complexi…

I like the waterbed theory, thanks, I hadn't heard of it before.

You're absolutely right, in the GC context you:

(1) Have to manually reference count / manage external resources like sockets and files because you can't count on the destructor to ever run.

(2) Lose determinism and then have to spend huge amounts of effort tweaking GC parameters to fix your issue, but to your point, it becomes a Jenga tower where you touch one part and the whole thing falls down again.

(3) Can easily still leak huge portions of your object graph by, for instance, throwing them into long-lived dictionaries.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#359

Post by farisjarrah » Thu, May 09, 2019, 5:41 PM UTC

JudgeWapner wrote: post #350

lossolo wrote: post #287

Earlier quoted context omitted.

> 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? You are missing the point. The main point behind GC is removing the complexity of writing the software. Writing your own destructors, thinking about when to free your memory or writing lifetime annotations, needing to design your app in…

> mental overhead that is removed by GC and it is replaced by GC when your program behaves unexpectedly because, whoopsie , that's the one time the GC decided to run. Good luck debugging or even reproducing that.

Just run your program normally and use eBPF/bpftrace with something like a flamegraph to track your system and its GC. This isn't an easy problem by any stretch of the imagination, however, it is a solved problem.

Re: For Better Computing, Liberate CPUs from Garbage Collection

#360

Post by mcguire » Thu, May 09, 2019, 5:43 PM UTC

chrisseaton wrote: post #219

seanmcdirmid wrote: post #188

Earlier quoted context omitted.

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.

> Only recently in hacker news have they become all merged This is demonstrably not true. The Garbage Collection book by Jones is the key text in this area, and it covers reference counting under that term. It was published in 1996, before Hacker News existed. There is also Bacon's Unified Theory of Garbage Collection, 2004, which said the two are on a spectrum that meets in the middle. > all high-performance collect…

The updated Garbage Collection Handbook does as well.