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

311–320 of 415 posts

Re: Reference count, don't garbage collect

#311

Post by staticassertion »

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, you can perform the sweeping 'as needed'. Even the marking doesn't have to run on any deterministic schedule.

The thing is that, from my naive perspective, run of the mill tracing collector algorithms are just way more advanced than your typical refcount. Most refcounting is just that - either an integer, atomic integer, or both, that gets incremented and decremented based on a number of operations applied to the underlying type. The naive approach has no delays.

Tracing GCs on the other hand, although perhaps not naive ones (could you link me info on the quickfit algorithm? I can not find anything online), might contain epochs that bump allocate in the majority of cases. That'll be particularly nice for benchmarks where allocations are likely very short lived and may actually never need to get to the mark/sweep phase. Your algorithm isn't really documented and I just really don't feel like looking at C right now.

Although naive refcounting is very common it's not the only game in town. Depending on the language you can group refcounts together - for example, imagine you have:

(assuming all fields are automatically refcounted) struct Foo { bar: Bar, baz: Baz, }

In theory, a "copy" of this type would involve 3 increments, possibly atomic increments. Each increment would also require a heap pointer dereference, and there would be no locality of those integers behind the pointers. That would be the trivial implementation.

But depending on the language you could actually flatten all of those down to 1 RC. This is language dependent, and it requires understanding how these values can be moved, referenced, etc, at compile time. You could also store all reference counts in tables associated with structures, such that you have locality when you want to read/write to multiple counters. The pointer dereference is going to be brutal so having locality there will be a nice win. I'd be curious to run your benchmarks through valgrind to see how much the refcount is just spending time on memory fetches that get invalidated in the cache immediately.

Anyway, an example of a pretty slick refcounting GC is what Pony built: https://tutorial.ponylang.io/appendices/garbage-collection.h... https://www.ponylang.io/media/papers/OGC.pdf

Pony has different types for: 1. Local, Immutable 2. Local, Mutable 3. Shared, Immutable 4. Shared, Mutable

You can read the paper where they discuss how they track local variables vs shared variables, the implementation of counter tables, etc.

So I guess to summarize:

1. The results make sense, or as much sense as anything. I'd be interested in more details on the algorithms involved and your benchmark methodology.

2. "Naive" tracing GCs are actually pretty advanced, and advanced refcount implementations are pretty scarce.

Re: Reference count, don't garbage collect

#312

Post by staticassertion »

brabel wrote: post #248
deterministic wrote: post #132

Earlier quoted context omitted.

I am the maintainer of a very high-performance JIT compiler for a Haskell like rules programming language used by large enterprises around the world. It uses reference counting + a global optimisation step to reduce the reference count updates to an absolute minimum. The result is compiled code that runs faster than C++ code carefully hand optimised by C++ experts over a 10 year period. There are zero GC pauses. Unle…

You've gone from claiming reference-counting is faster than tracing GC to claiming it's even faster than hand optimized C++, which is quite honestly unbelievable - whatever the reference counting algorithm is doing can be emulated by the hand-optimised C++ code so that's just literally impossible. But anyway, it's a completely fruitless discussion here unless you provide data that we can look at and scrutinize. OP ha…

> whatever the reference counting algorithm is doing can be emulated by the hand-optimised C++ code so that's just literally impossible.

shared_ptr and unique_ptr have pretty significant overhead and are common practice, even for optimized codebases, so I wouldn't say it's impossible at all.

Re: Reference count, don't garbage collect

#313

Post by staticassertion »

dento wrote: post #306
aaaaaaaaaaab wrote: post #299

Earlier quoted context omitted.

On any OS which is not hard realtime, there could be arbitrary pauses with any syscall. This is just nitpicking.

Nitpicking: arbitrary pauses can occur even without syscalls, when the OS preempts the program. More nitpicking: on x86-64, SMI interrupts can cause arbitrary pauses even without any software control involved. Hard realtime on x86-64 is not possible.

More nitpicking: Your computer might turn off, cosmic rays might blow fuck up your RAM/CPU, Capital G God could reach down and pause the system, there's a universal quantum pause every 5.391247 × 10^-44 so that the universe can reboot, etc etc etc

Orrrrr, GC pause just means pauses caused by the GC as part of its implementation's work to manage memory.

Re: Reference count, don't garbage collect

#314

Post by pizlonator »

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 mutated lines you didn’t mean to mutate.

So, GC is usually faster. RC has other benefits (more predictable behavior and timing, uses less memory, plays nicer with OS APIs).

Re: Reference count, don't garbage collect

#315

Post by becquerel »

ncmncm wrote: post #237
ElectricalUnion wrote: post #101

Earlier quoted context omitted.

> what we really hated was Java's verbose semantics I believe it's actually the opposite - Java has pretty simple, compact and well defined semantics. Too simple and compact for confort - a little syntatic sugar would have made the language a lot less verbose.

Java's fundamental problems are well beyond reach of any syntactic sugar.

Please explain these fundamental problems.

Re: Reference count, don't garbage collect

#316

Post by becquerel »

musicale wrote: post #122
mandevil wrote: post #112

Earlier quoted context omitted.

Not OP, but someone who has gotten paid to write Java for several years. I would say that isn't that Java's semantics are that verbose, it's that the way Java is traditionally written, with every line actually 3 lines on your screen of public function makeItalicTextBox(String actualTextIWantToBeItalic) { ItalicTextBox itb = italicTextBoxFactoryGenerator.GenerateFactory().buildItalicTextBox(actualTextIWantToBeItalic);…

The builder pattern with method chaining is unfortunate and should usually be replaced by named/optional parameters, in any sensible/modern programming language at least. IDEs are an enabler for horriblyLongIdentifierNames because they enter them for you automatically without requiring you to type them on a keyboard.

Can you explain why you feel this way? I personally hate named and optional parameters, as they inevitably seem to drastically inflate the complexity of the function. I would much rather deal with a builder class that encapsulates doing something over calling a method with fifteen parameters, half of which are optional.

And god forbid you have optional bool args!

If I need to call a monster like that repeatedly, I'm likely to make my own wrapper that's simpler anyway - so why not start out that way.

Re: Reference count, don't garbage collect

#317

Post by manuelabeledo »

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.

Re: Reference count, don't garbage collect

#318

Post by yakubin »

afiori wrote: post #310
yakubin wrote: post #304

Earlier quoted context omitted.

What happens in your language when a linked list is freed? Doesn't running its destructor (or its equivalent) take a linear amount of time relative to the length of the list?

My guess is that this could be done concurrently and/or in parallel. It still take time linear in length, but dead nodes are by definition stable so it does not really matter when you free them.

So just like with tracing GCs. You do have a pause, which you may avoid with parallelism, or smear out incrementally. If you do it in parallel, your reference counting needs to be atomic, which adds further overhead. You still need to perform all the reference counting operations for each element of the list, not just free them, because part of the list may be shared. E.g. in SML:

  fun replace_head_with_1 (_::xs) = 1::xs;
  val a = [2, 3, 4];
  val b = replace_head_with_1 a;
Now a and b share the tail.

And a linked list is only a simple demonstration of a chain of pointers. It occurs spontaneously outside of containers, when you just write e.g. classes which have objects of other classes as their fields. In Haskell that would be records, or just an algebraic data type. Or just closures.

Re: Reference count, don't garbage collect

#319

Post by [deleted] »

staticassertion wrote: post #312
brabel wrote: post #248

Earlier quoted context omitted.

You've gone from claiming reference-counting is faster than tracing GC to claiming it's even faster than hand optimized C++, which is quite honestly unbelievable - whatever the reference counting algorithm is doing can be emulated by the hand-optimised C++ code so that's just literally impossible. But anyway, it's a completely fruitless discussion here unless you provide data that we can look at and scrutinize. OP ha…

> whatever the reference counting algorithm is doing can be emulated by the hand-optimised C++ code so that's just literally impossible. shared_ptr and unique_ptr have pretty significant overhead and are common practice, even for optimized codebases, so I wouldn't say it's impossible at all.

[deleted]

Re: Reference count, don't garbage collect

#320

Post by kaba0 »

wizofaus wrote: post #300
kaba0 wrote: post #89

Earlier quoted context omitted.

Most GCs do exactly that -- they only "work" when absolutely necessary, and their heuristics says that they are getting behind the created garbage. If the program exits shortly after it will just leak the memory. The problem with that in the case of C++ is that you likely only want to leak things used in the end from the main thread, but not "recursively" - the distinction is hard to do.

It actually wouldn't surprise me that's the main reason GC often outperforms ARC in real- life software - simply because it's only necessary to actually bother doing GC once memory usage is high and there's a known need to allocate further memory. But couldn't ARC do the same thing in principle - i.e. only bother incrementing/decrementing reference counts when there's likely to be a need to reclaim memory? Even an in…

As mentioned elsewhere in the thread, the actual reclamation can be done asynchronously, but the most problematic part, namely decrementing a counter atomically is the most problematic part and it can’t just be done later willy-nilly.
Post reply on HN