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

Reference count, don't garbage collect

kevinlawler.com

Post reply on HN
Print view View original

341–350 of 415 posts

Re: Reference count, don't garbage collect

#341

Post by mamcx »

pjmlp wrote: post #272
musicale wrote: post #125

Earlier quoted context omitted.

Maybe Apple just hires mediocre developers (I certainly have lots of complaints about their software and UI issues, but I would probably suspect management/priorities/schedules rather than the technical staff) but they implemented GC and Automatic Reference Counting for ObjC and found that the latter resulted in better and more consistent responsiveness, which is probably what most users care about in apps. (Apps sti…

https://github.com/ixy-languages/ixy-languages The real reason why a tracing GC was a failure in Objective-C was due to the interoperability with the underlying C semantics, where anything goes. The implementation was never stable enough beyond toy examples. Naturally automating the Cocoa release/retain calls made more sense, given the constraints. In typical Apple fashion they pivoted into it, gave the algorithm a f…

> What Apple has is excellent marketing.

Whoa! Marketing? Interop with C is a MASSIVE use-case. And iOS is A LOT faster and more responsive than android. That is, right there, total proof that can't denied.

I do both, and the speed of apple way and the simplicity of bridge the C-abi is not a joke.

Re: Reference count, don't garbage collect

#342

Post by kaba0 »

_gabe_ wrote: post #329
kaba0 wrote: post #218

Earlier quoted context omitted.

Come on, object graphs are completely dynamic, noone can say where will “a variable go out of scope”, unless we literally have a hello world. Do you honestly claim that you know when deallocations happen in any codebase full of conditionals depending on outside effects (user input, network, etc)?

> Do you honestly claim that you know when deallocations happen in any codebase full of conditionals depending on outside effects (user input, network, etc)? Yes. C programs have been doing this for over 40 years now. A leak free C program has an equivalent free for every malloc, which means they know exactly when everything gets allocated and freed.

That just means that every allocation has a pair that frees it - that’s different from knowing how many allocations happen, when and when does the corresponding free happen.

For a simple example, take a text editor (sure, you would likely allocate a much bigger buffer in practice) that allocates for each line of text an object, and adds the buffer’s pointer to a list to be freed - this freeing happens when the user closes the open text file window. While you do know that every allocation will be freed and know their relative order, you don’t know anything more specific - will the user open multiple such files first, close them in some random order, etc.

Re: Reference count, don't garbage collect

#343

Post by bjourne »

staticassertion wrote: post #311
bjourne wrote: post #275

Time to tout my own horn. I made a project comparing different types of garbage collectors (I still prefer the original terminology; both ref-counting and tracing garbage collection collects garbage, so they are both garbage collectors) a few years ago: https://github.com/bjourne/c-examples Run ./waf configure build && ./build/tests/collectors/collectors and it will spit out benchmark results. On my machine (Phenom I…

This is cool, thank you. Note that my comments are those of a layman, I don't consider myself an expert on these topics, but this gave me some thoughts. Happy to learn more, would love links to blogs/ papers where I can read more. I would not be surprised to find that even a naive mark and sweep collector is faster than naive refcounting on some workloads. One obvious thing to consider is that the work is delayed, yo…

Let me preface by stating that I'm no expert. I created the repo a few years ago when I was self-studying gc. Then I realized the rabbit hole was much deeper than I thought and retreated. The book I read is The Garbage Collection Handbook. Quite expensive but definitely worth its price.

Throughput-wise, it's hard to beat naive tracing gc. The algorithms are just too simple and they don't "interfere" with "normal operations" like ref counting does. Assuming the same allocation pattern (i.e no cheating by stack allocating objects), a tracing gc would likely (again, throughput-wise) beat manual memory management too. The additional benefit tracing gives you is easy heap compaction. Thus future pointer-chasing and memory allocations will be more efficient. With ref counting, compaction is harder.

True, you could delay sweeping, but ime, marking time dominates so you don't gain much. Even with a huge heap of several gigabytes, sweeping is just a linear scan from lowest to highest address.

Quick fit is a memory allocator, see: http://www.flounder.com/memory_allocation.htm Most gcs do not keep the heap contiguous so you need it in a layer below the gc. Quick fit is the algorithm almost everyone uses and it is very good for allocating many small objects of fixed sizes (8, 16, 32, etc.). It could be swapped out with malloc/free pairs instead, at the price of some performance.

I have to disgree with naive tracing being advanced. My mark & sweep implementation is only about 50 lines and that includes comments: https://github.com/bjourne/c-examples/blob/master/libraries/... A copying collector isn't much more complicated. Neither is beyond the reach of most comp sci students. Yes, optimized multi-generational tracing collectors supporting concurrent and resumable tracing makes them very complicated. But the same is true of optimized ref counting schemes. :)

Pony looks very interesting. It looks like it is supposed to have less object churn than very dynamic languages like JavaScript which probably makes ref counting very suitable for it.

Re: Reference count, don't garbage collect

#344

Post by Someone »

hamstergene wrote: post #85
shwestrick wrote: post #12

This debate has gone round and round for decades. There are no hard lines; this is about performance tradeoffs, and always will be. Perhaps the biggest misconception about reference counting is that people believe it avoids GC pauses. That's not true. Essentially, whereas tracing GC has pauses while tracing live data, reference counting has pauses while tracing garbage. Reference counting is really just another kind…

For a unifying term I prefer Automatic Memory Management. One reason is that GC is already universally used to mean only tracing garbage collection, and trying to defend its wider meaning is a pointless uphill battle. Another is that is suits the job much better, because not every AMM technique works by producing garbage then collecting it, you know.

> not every AMM technique works by producing garbage then collecting it

And the confusing thing is that garbage collection (GC) doesn’t collect garbage, while reference counting (RC) does.

GC doesn’t look at every object to decide whether it’s garbage (how would it determine nothing points at it?); it collects the live objects, then discards all the non-live objects as garbage.

RC determines an object has become garbage when its reference count goes to zero, and then collects it.

That difference also is one way GC can be better than RC: if there are L live objects and G garbage objects, GC has to visit L objects, and RC G. Even if GC spends more time per object visited than RC, it still can come out faster if L ≪ G.

That also means that GC gets faster if you give it more memory so that it runs with a smaller L/G ratio (the large difference in speed in modern memory cache hierarchies makes that not quite true, but I think it still holds, ballpark)

Re: Reference count, don't garbage collect

#345

Post by ahartmetz »

origin_path wrote: post #330
ahartmetz wrote: post #235

Earlier quoted context omitted.

Even the best "real world" garbage collectors pause the program for order of magnitude a hundred milliseconds, no? I was recently reading some blog posts of the V8 JS engine team. There is nothing to understand or not understand there, it's hard data.

The best real world garbage collectors are like ZGC, Shenandoah or C4 which don't pause your program at all. They are fully concurrent. Even if you go for a GC that is designed to balance throughput and latency, like G1, you can still configure what pause times it should target and those can easily be ~10-20msec if you want, with the vast majority of pauses being far less than that (less than 3 msec). "I was recently…

Serious questions: if these garbage collectors are so good, why aren't they widely used? My guess is that they have downsides such as low throughput, high CPU usage, high memory usage, etc... You can't import a JVM GC into V8, to stay with my example, but you can reimplement the ideas if you have quasi-infinite money like Google.

Re: Reference count, don't garbage collect

#346

Post by viktorcode »

kgeist wrote: post #333
viktorcode wrote: post #249

Earlier quoted context omitted.

Deterministic means that running the same part of the program will take the same amount of time. Deallocating the same memory object graph is pretty much deterministic. GC can throw a spanner in that by deciding that now is the time to do its thing.

>Deterministic means that running the same part of the program will take the same amount of time The object graph can easily be different from run to run depending on user input, timing, etc. Say, in the first run, the graph has a large subgraph due to a runtime condition (a property is set to a certain value), and on the next run, the graph is more lightweight because the property was not updated. It will take diffe…

That is expected. With different input data (what you call runtime condition) you get different result. With the same input data the determinism holds for RC, but not for GC.

Re: Reference count, don't garbage collect

#347

Post by viktorcode »

brabel wrote: post #255
viktorcode wrote: post #236

Earlier quoted context omitted.

Putting both under the same term is meaningless. Reference counting and Garbage Collection have very clear difference: when the referenced objects are destroyed (not deallocated). In RC it happens when the count reaches zero. In GC it happens some time later. That difference is crucial for having or not having deterministic performance in your program.

Is the Pony language's GC a GC then? It runs at determinate times, namely when a behaviour (an actors' receive function, basically) finishes running... and because actors cannot share mutable state, and immutable values with more than one owner can be handled easily by a simple common parent actor, each actor's GC is completely independent of each other. Things are rarely as clear cut as we would want to believe.

> Is the Pony language's GC a GC then? It runs at determinate times, namely when a behaviour (an actors' receive function, basically) finishes running...

It is. It might run when a behaviour finishes running, according to their docs.

Re: Reference count, don't garbage collect

#348

Post by glouwbug »

klodolph wrote: post #70
arcticbull wrote: post #62

Earlier quoted context omitted.

Nope, you can just mark the back-reference as weak. GC is only required if you as a programmer (or programming language) do not provide sufficient information to the compiler or runtime to understand the object graph.

It's not always obvious to know which reference to mark as weak, and there's not necessarily a clear indication of which reference is a back-reference. You can find various algorithms in journals or whatnot written with the assumption that there's GC. Algorithms designed with this assumption may not have clear ownership for objects, and those objects my have cyclic references. It's easy to say, "objects should have c…

But, I mean, the whole purpose of using a reference counted GC language is for the productivity gain. If I'm going to be using a reference counted language and manually specifying weak pointers then I'd just C++

Re: Reference count, don't garbage collect

#349

Post by pizlonator »

manuelabeledo wrote: post #317
pizlonator wrote: post #314

Atomic inc/dec is hella expensive relative to not doing it. It’s true that CPUs optimize it, but not enough to make it free. RC as a replacement for GC means doing a lot more of this expensive operation - which the GC will do basically zero of in steady state - so this means RC just costs more. Like 2x slowdown more. The atomic inc/dec also have some nasty effects on parallel code. The cpu ends up thinking you mutate…

> So, GC is usually faster. GC is way faster if there is little collection. In memory or cache intensive applications, garbage collection as a whole can be significantly slower.

GC is faster even if you collect a lot. GCs create better cache locality especially for recently allocated objects, and their cache behavior is not generally worse than malloc (but there are many GCs and many mallocs and some try harder than others to make caches happy).

The total time spent in GC across a program’s execution time is usually around 30% or so. Maybe more in some cases (some crazy Java workloads can go higher) or less in others (JavaScript since the mutator is slow), but 30% is a good rule of thumb. That includes the barriers, and total cost of all allocations, including the cost of running the GC itself.

Reference counting applied as a solution to memory safety, as a replacement for GC, is going to cost you 2x overhead just for the ref counting operations and then some more on top of that for the actual malloc/free. When you throw in the fact that GCs always beats malloc/free in object churn workloads, it’s likely that the total overhead of counting refs, calling free(), and using a malloc() that isn’t a GC malloc is higher than 2x, I.e. more than 50% of time spent in memory management operations (inc, dec, malloc, free).

It’s a trade off, though. The GC achieves that 30% because it uses more memory. All of the work of understanding the object graph is amortized into a graph search that happens infrequently, leading to many algorithmic benefits (like no atomic inc/dec, faster allocation fast path, freeing is freeish, etc), but also causing free memory to be reused with a delay, leading to 2x or more memory overhead.

That also implies that if you ask the GC to run with lower memory overhead, it’ll use more than 30% of your execution time. It’s true that if you want the memory usage properties of RC, and you try to tune your GC to get you there, you gonna have a slow GC. But that’s not how most GC users run their GCs.

Re: Reference count, don't garbage collect

#350

Post by mypalmike »

kaba0 wrote: post #285
mypalmike wrote: post #260

Earlier quoted context omitted.

Yes. And you could use Lombok to do the same before that. (Though I'm one of the weirdos who likes Java in it's explicitness, which is related directly to its verbosity. I like reading code where I can see what the local variable types are.)

(I believe it depends on the exact scenario. In cases where the return type is not obvious I also much prefer explicit types (eg. ConcrType a = someObj.someMethod() ), but I don’t find A a = new A() any more readable than the var version)

Agreed. I'm not sure that the shortcut existing in the language is worth the fact that other devs on my team will use it in the former case.
Post reply on HN