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

101–110 of 415 posts

Re: Reference count, don't garbage collect

#101

Post by ElectricalUnion »

nemothekid wrote: post #90

It's my theory that Java, unintentionally, did a lot of damage to P&L research. I write a lot of Rust, and while the borrow checker is great, I've come to really admire the work that was put in the Go GC even if it's not as fast Java. There is a whole generation of programmers that have come to equate GC with Java's 10 second pauses or generics/typed variables with Java's implementation of them. Even the return to ty…

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

Re: Reference count, don't garbage collect

#102

Post by chrisseaton »

saagarjha wrote: post #100
pklausler wrote: post #88

Earlier quoted context omitted.

It's not marketed as a GC, but exit(2) is fast and effective when used as one.

Now you've pushed the job of cleaning up page tables to the OS.

But that’s extremely easy - you go through a linear list once and free them all. You don’t even need to bring the contents from main memory to do it.

(Exception is shared pages, not used for heap memory often.)

Re: Reference count, don't garbage collect

#103

Post by pclmulqdq »

OskarS wrote: post #50
kaba0 wrote: post #47

Earlier quoted context omitted.

> Deallocating can take arbitrarily long, but deallocation does not stop-the-world And modern GCs only have to stop the current thread to check for which thread-local objects are alive. The alice ones are moved to another generation, making the space reusable for free . And atomic writes need synchronization which is crazy expensive, I honestly don’t get why you think it isn’t. Also, just try writing rust/c++ code th…

> The alice ones are moved to another generation, making the space reusable for free. It's pretty hilarious to me that you first say "they have to move it to another generation" and then you say "it's free!" It's like saying "I paid for my dinner, and now I get to eat it for free!" Also: what do you think `free()` does? All modern memory allocators do this trick, keeping thread-local caches. This is not an advantage…

From experience, your benchmark is not correctly estimating how long a non-atomic increment takes. Run 10000 of them back to back inside each benchmark iteration (atomic and non-atomic), and then runcontested.

You will see that the counter increment is about 2-5 cycles, a few hundred ps, and the atomic is on the order of 10 ns uncontended.

If you then introduce contention and a multi-socket setup, the atomic will slow down significantly. Only one thread can touch it at a time, so they have to take turns.

Re: Reference count, don't garbage collect

#104

Post by forrestthewoods »

nemothekid wrote: post #90

It's my theory that Java, unintentionally, did a lot of damage to P&L research. I write a lot of Rust, and while the borrow checker is great, I've come to really admire the work that was put in the Go GC even if it's not as fast Java. There is a whole generation of programmers that have come to equate GC with Java's 10 second pauses or generics/typed variables with Java's implementation of them. Even the return to ty…

> There is a whole generation of programmers that have come to equate GC with Java's 10 second pauses

Anyone who has ever shipped a C# Unity game know the pain that is the garbage collector. It’s effectively impossible to avoid frame hitches with the GC.

I’ve spent a LOT of time going way out of my way to avoid any and all garbage collects. Which somewhat defeats the purpose of using a GC-based language.

I definitely would say “GC used to be bad but now it’s good”. That tale has been spun for 30+ years at this point!

Re: Reference count, don't garbage collect

#105

Post by game-of-throws »

pklausler wrote: post #88
kaba0 wrote: post #44

Earlier quoted context omitted.

One great example would be a C++ program that runs fast, and then just spends 10s of seconds doing “nothing” while it deallocates shared pointers’ huge object graphs at the end. They really are two sides of the same coin, with tracing GCs being actually correct (you need cycle detection for a correct RC implementation), and having much better throughput. It’s not an accident that runtimes with thousands dev hours are…

It's not marketed as a GC, but exit(2) is fast and effective when used as one.

I wouldn't call it a GC. It's more like an arena allocator, with the arenas managed by the OS :)

Re: Reference count, don't garbage collect

#106

Post by pclmulqdq »

hinkley wrote: post #52
kaba0 wrote: post #44

Earlier quoted context omitted.

One great example would be a C++ program that runs fast, and then just spends 10s of seconds doing “nothing” while it deallocates shared pointers’ huge object graphs at the end. They really are two sides of the same coin, with tracing GCs being actually correct (you need cycle detection for a correct RC implementation), and having much better throughput. It’s not an accident that runtimes with thousands dev hours are…

I don't know what the current state of the art is, but at one point the answer to GC in a realtime environment was to amortize free() across malloc(). Each allocation would clear up to 10 elements from queue of free-able memory locations. That gives a reasonably tight upper bound on worst case alloc time, and most workflows converge on a garbage-free heap. Big malloc after small free might still blow your deadlines,…

This is normal today inside malloc implementations.

Re: Reference count, don't garbage collect

#107

Post by fingerlocks »

yyyk wrote: post #73

Reference counting is garbage collection, just a different strategy - and all these strategies tend to blur to the same methods eventually, eventually offering a latency-optimized GC or a throughput-optimized GC. Swift is inferior here because it uses reference counting GC without much work towards mitigating its drawbacks like cycles (judging by some recent posts, some of its fans apparently aren't even aware RC has…

What do you mean? Potential reference cycles are a compile time error in Swift. That’s the whole point of the @escaping annotation

Re: Reference count, don't garbage collect

#108

Post by smasher164 »

For how strongly worded this article is, you'd think the author would provide some substance in their reasoning. Reference counting, even atomic, is quite expensive. Not only because it can invalidate the cache line, but depending on the architecture (looking at you x86), the memory model will deter reordering of instructions. On top of this, reference counting has a cascading effect, where one destructor causes another destructor to run, and so on. This chain of destructor calls is more or less comparable to a GC pause.

Re: Reference count, don't garbage collect

#109

Post by saagarjha »

OskarS wrote: post #43
adgjlsfhk1 wrote: post #32

Earlier quoted context omitted.

The blog post is largely incoherent for several reasons. 1. It recommends 8 byte counters. This implies making every object in your programming language 8 bytes bigger which is pretty much a non-starter. Almost everyone that actually uses reference counting uses more like 2-4 bits. 2. Reference counting can have arbitrarily long pauses as well. If you decrease the reference count of an object to zero, you have to dec…

> Almost everyone that actually uses reference counting uses more like 2-4 bits. Here is an incomplete list of languages which use 8 bytes for their reference count on 64-bit computers: 1. Rust, in Rc and Arc 2. C++, in std::shared_ptr 3. Objective-C, in NSObject's retainCount 4. Swift, because of Objective-C 5. Python, where reference count is Py_ssize_t These were literally the first languages i thought of, they al…

Objective-C stores the retain count in the tops bits of an object pointer. The hardware it runs on has been specially tuned to make atomic reference counting faster.

Re: Reference count, don't garbage collect

#110

Post by hayley-patton »

carry_bit wrote: post #4

You can optimize reference counting: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23... With allocating as dead, you're basically turning it into a tracing collector for the young generation.

https://users.cecs.anu.edu.au/~steveb/pubs/papers/lxr-pldi-2... is the most recent publication in this lineage of high-performance RC systems.
Post reply on HN