Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Real-Time Garbage Collection Is Real

michaelrbernste.in

Post reply on HN
Print view View original

11–20 of 62 posts

Re: Real-Time Garbage Collection Is Real

#11

Post by adrianm »

lumpypua wrote: post #6
Dewie wrote: post #5

Earlier quoted context omitted.

> The only downside to ARC Doesn't reference counting typically have a worse throughput than garbage collection? That's what I've read anyway.

GC has better throughput at the expense of significantly increased memory usage, and variable latency for any individual task. On servers, that's fine. On my phone, I'll take lower memory usage and predictable latency any day. Yay refcounting.

All GC algorithms are not created equal.

What algorithm are you referring to when you say "better throughput at the expense of significantly increased memory usage"?

Also, why is unpredictable latency acceptable for you on servers but not phones? Wouldn't a latency spike on remote requests from an application degrade user experience just as much as if that latency were localized to the phone?

Re: Real-Time Garbage Collection Is Real

#12

Post by ltta »

youngthugger wrote: post #2

I think more languages should adopt Swift and Objective-C's automatic reference counting. The only downside to ARC is retain cycle's which rarely happen in my experiance. A deterministic object life cycle just feels right.

As far as I know ARC (like manual memory managenent) can lead to release cascades that can also cause application delays in games eg. Something you have to watch for. Malloc() and free() and equivalents do quite a bit of work under the hood (check today's linked tcmalloc article for example) that takes time.

Re: Real-Time Garbage Collection Is Real

#13

Post by ltta »

youngthugger wrote: post #2

I think more languages should adopt Swift and Objective-C's automatic reference counting. The only downside to ARC is retain cycle's which rarely happen in my experiance. A deterministic object life cycle just feels right.

And also check out this paper comparing reference counting and GC, and the accompanying discussion on LtU.

http://lambda-the-ultimate.org/node/2552

(Although I think the paper has problems and bias)

Re: Real-Time Garbage Collection Is Real

#14

Post by tolmasky »

lumpypua wrote: post #6
Dewie wrote: post #5

Earlier quoted context omitted.

> The only downside to ARC Doesn't reference counting typically have a worse throughput than garbage collection? That's what I've read anyway.

GC has better throughput at the expense of significantly increased memory usage, and variable latency for any individual task. On servers, that's fine. On my phone, I'll take lower memory usage and predictable latency any day. Yay refcounting.

There are certainly classes of mobile apps that need the guarantees of lower/deterministic memory usage. In my experience, that is not the common app being written however. These concerns seem largely like fantasies not backed up by any concrete evidence for your every-day twitter client/mail app/weather/whatever. Generic list-based apps simply do not need to be acting as if you need to squeeze every ounce out of the processor/ram anymore. They would instead benefit much more from not having to worry about whether self in the closure you're creating should be weak or not. Especially when you consider that many (most?) of the apps on the App Store that are actually pushing things to the limit -- games -- are running in a (old) GC environment (C# in Unity).

Re: Real-Time Garbage Collection Is Real

#16

Post by userbinator »

our running programs may exceed the amount of space we want them to take

The majority of real-time systems are the small embedded ones where both speed and size are usually highly constrained, so this doesn't look as useful as it may seem. It's well known that GC overhead decreases with increasing available memory, so the result shouldn't be so surprising. A relevant phrase I've heard is "garbage collection is free only if memory is worth nothing."

Limiting the amount of work the GC can do also means that some quite subtle bugs can arise from exceeding the "allocation rate" that it can handle, which is something that might not be as easy to determine in GC-using code.

but not the amount of space that we estimate they could possibly take

I think it's a bad sign when the word "estimate" is used in talking about a real-time system... this is an area of guarantees and proofs, not educated guesses.

Re: Real-Time Garbage Collection Is Real

#17

Post by lumpypua »

adrianm wrote: post #11
lumpypua wrote: post #6

Earlier quoted context omitted.

GC has better throughput at the expense of significantly increased memory usage, and variable latency for any individual task. On servers, that's fine. On my phone, I'll take lower memory usage and predictable latency any day. Yay refcounting.

All GC algorithms are not created equal. What algorithm are you referring to when you say "better throughput at the expense of significantly increased memory usage"? Also, why is unpredictable latency acceptable for you on servers but not phones? Wouldn't a latency spike on remote requests from an application degrade user experience just as much as if that latency were localized to the phone?

> What algorithm are you referring to when you say "better throughput at the expense of significantly increased memory usage"?

Here's a discussion of the particular paper behind that statement: [1]

I'd also like to recommend the paper "A Unified Theory of Garbage Collection" [2] that breaks down the divide between GC and refcounting. There is a lot of gray area between tracing GC and refcounting. You can make different tradeoff decisions in different parts of your collection algorithm. But fundamentally it breaks down to time-space tradeoffs—you want to save time and get throughput, you're gonna eat some extra space.

> Also, why is unpredictable latency acceptable for you on servers but not phones? Wouldn't a latency spike on remote requests from an application degrade user experience just as much as if that latency were localized to the phone?

We as developers make UI efforts to mitigate network unreliability (fallacy #1 of distributed computing: the network is reliable) so it's ok if a server is being temporarily shitty. It's a lot harder to keep responsive, smooth UI behavior in the face of dropped frames and long GC pauses.

[1] http://stackoverflow.com/questions/2982325/quantifying-the-p...

[2] http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf

Re: Real-Time Garbage Collection Is Real

#18

Post by psykotic »

ltta wrote: post #12
youngthugger wrote: post #2

I think more languages should adopt Swift and Objective-C's automatic reference counting. The only downside to ARC is retain cycle's which rarely happen in my experiance. A deterministic object life cycle just feels right.

As far as I know ARC (like manual memory managenent) can lead to release cascades that can also cause application delays in games eg. Something you have to watch for. Malloc() and free() and equivalents do quite a bit of work under the hood (check today's linked tcmalloc article for example) that takes time.

Release cascades can be a big problem even with plain old RAII in C++. I once diagnosed a performance issue in a C++ network server where the server listening thread would sometimes temporarily hang when clients disconnected. The culprit turned out to be the destructor of a large std::map that directly and indirectly accounted for tens of millions of heap-allocated objects that had to be individually destructed and freed. It's very rare for destructors to have intentional global side effects, so this kind of work could almost always have been done asynchronously, at least in principle.

An unfortunately common symptom of large C++ applications is that they take forever to shut down because they insist on calling destructors on everything in the known universe. In reality, most applications only have a tiny handful of resources that you truly have to release yourself at shut down, and memory certainly is not one of them.

Re: Real-Time Garbage Collection Is Real

#19

Post by rayiner »

youngthugger wrote: post #2

I think more languages should adopt Swift and Objective-C's automatic reference counting. The only downside to ARC is retain cycle's which rarely happen in my experiance. A deterministic object life cycle just feels right.

Automatic reference counting has its own issues: 1) allocating short-lived objects is not cheap, because they call down into an underlying malloc/free; 2) as a consequence of (1), throughput is lower; 3) getting acceptable overhead for manipulating references in the heap/stack requires compiler optimizations to elide those reference counts, which adds a layer of complexity to your mental model of the program; 4) implementing the reference-count operating in a multi-core system requires pretty heavy-weight atomic primitives, and race conditions can result in incorrect reference counts.[1]

One of the more interesting avenues of research, especially in mobile devices where you don't want to pay the power cost of having a 2x larger heap your live size, are various hybrids of garbage collection and reference counting. A neat, easy to understand one is: http://users.cecs.anu.edu.au/~steveb/downloads/pdf/rcix-oops....

Also interesting is what you can do when you have more information about what pointers can point to (as in Rust). It's not so much that reference counting in Rust is cheap, but that the language offers a lot of tools to let you avoid reference counted pointers in the first place, in favor of references with static lifetime guarantees.

[1] What Swift or Obj-C do when you overwrite a pointer-valued field is to do a objc_release() for the old pointer, and a objc_retain() for the new pointer. If two threads write to a field at the same time, you can corrupt the reference count (even if the objc_release()/objc_retain() operations are themselves atomic!) As far as I know, Apple's obj-c runtime does not attempt to handle this situation. See: http://clang.llvm.org/docs/AutomaticReferenceCounting.html#o....

Re: Real-Time Garbage Collection Is Real

#20

Post by ajross »

> It turns out that RTGC is very real, and research on it is very active.

I remember being promised the same stuff at JavaOne in 1997. It's a solved problem, we're just waiting on an implementation.

We're still waiting.

That doesn't mean any of this stuff isn't interesting (though I gotta be honest it's getting less so for me every year), or that such a thing is impossible. But that title is dancing around a rather different definition for "real" than most of us use.

Post reply on HN