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

301–310 of 415 posts

Re: Reference count, don't garbage collect

#301

Post by aaaaaaaaaaab »

dataflow wrote: post #283
pclmulqdq wrote: post #147

Earlier quoted context omitted.

The global optimization step is often what people commonly refer to as "garbage collection." Putting it inside a framework to RC as few times as possible is pretty cool. However, I doubt the efficacy of your C++ experts: most of the people I know who write C++ are actually really bad at optimizing code. They mostly use it for legacy reasons. If you get a team of experienced (and expensive) systems programmers, you wi…

What I understood from their comment (which may not be correct) is the following. Say you have something like this: extern void foo(T *p); // some arbitrary function void bar1(bool cond) { .. auto p = std::make_unique (); if (cond) { return foo(p.release()); } ... } This requires the compiler to call your_deleter::operator() regardless of whether cond is true or false, even though it's unnecessary (and can thus be sl…

std::unique_ptr::release() resets the ptr to nullptr, which will be the first thing the deleter will check for and bail out.

This is a non-issue.

Re: Reference count, don't garbage collect

#302

Post by dataflow »

aaaaaaaaaaab wrote: post #301
dataflow wrote: post #283

Earlier quoted context omitted.

What I understood from their comment (which may not be correct) is the following. Say you have something like this: extern void foo(T *p); // some arbitrary function void bar1(bool cond) { .. auto p = std::make_unique (); if (cond) { return foo(p.release()); } ... } This requires the compiler to call your_deleter::operator() regardless of whether cond is true or false, even though it's unnecessary (and can thus be sl…

std::unique_ptr::release() resets the ptr to nullptr, which will be the first thing the deleter will check for and bail out. This is a non-issue.

> which will be the first thing the deleter will check for and bail out.

The point is that check itself is an extra instruction (or two, rather) that would otherwise be skipped entirely.

I'm not saying this commonly makes a difference. I'm just saying this might be something that does make a difference for them in their particular use case.

Also note that I was trying to describe the general phenomenon with a simple example, but this obviously isn't limited to std::unique_ptr.

Re: Reference count, don't garbage collect

#303

Post by benibela »

An advantage of RC is that you can also use it to verify ownership.

When the counter is 1, you can do anything with the object without affecting any other references.

Like the object could be mutable for a counter=1, and copy-on-write otherwise. Then you can make a (lazy) deep copy by just increasing the counter.

Re: Reference count, don't garbage collect

#304

Post by yakubin »

deterministic wrote: post #132
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…

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…

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?

Re: Reference count, don't garbage collect

#305

Post by fnord123 »

brabel wrote: post #293
fnord123 wrote: post #268

Earlier quoted context omitted.

> 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. There is nuance here. They claimed that their project is faster than a specific hand optimized project. Not faster than a theoretical peak performance c++ program. I've run into similar situ…

> And %timeit in the ipython shell is way easier than the black magic involved in profiling and benchmarking java Unfair criciticm... first, Java has had a REPL for several years and you can time stuff like in Python as easily... second, profiling tools in Java are some of the best available, and are not blackmagic... quite simple to use, just attach them to the running process and hit "profile". With that said: yes,…

> Unfair criciticm... first, Java has had a REPL for several years and you can time stuff like in Python as easily... second, profiling tools in Java are some of the best available, and are not blackmagic... quite simple to use, just attach them to the running process and hit "profile".

You're right that the java tooling is powerful. But getting numbers out of the JVM is not the black magic. The dark arts are setting up an experiment, managing the JIT warm-up, and interpreting the results. In my experience it's just hell trying to turn those numbers into a convincing argument that we have confidence in our performance. Concrete example: convincing openjdk11 to use AES instructions Vs conscrypt using AES out of the box with no warm-up...

The whole song and dance means that we just don't take it as a priority because it's a tiring sink of effort. On the other hand %timeit is so easy and remains consistent that you can use it with unit tests and offer algorithm fixes in PRs.

Re: Reference count, don't garbage collect

#306

Post by dento »

aaaaaaaaaaab wrote: post #299
naasking wrote: post #288

Earlier quoted context omitted.

> There are zero GC pauses. Unless you claim that a C++ alloc/feee call is “garbage collection”. Alloc/free can introduce arbitrary pauses last I checked, so yes, there are pauses. Any time doing book keeping for resources rather than running your code counts as GC time.

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.

Re: Reference count, don't garbage collect

#307

Post by andreareina »

altfredd wrote: post #233
kccqzy wrote: post #217

Earlier quoted context omitted.

If you are assuming GC does not need to stop the world, you can also assume that the freeing of memory (including the O(n) calls to free()) will not be done in a critical path; all memory could be handed off to a separate dedicated thread that actually calls free(). Or in a RPC or HTTP server all memory can be freed after the request has been served. It's very easy to make a reference counting scheme not stop the wor…

> all memory could be handed off to a separate dedicated thread that actually calls free() That only works when you have infinite memory (or infinite CPU resources). > It's very easy to make a reference counting scheme not stop the world. It's a bit more difficult to make a GC implementation so. Only if by "not stopping the world" you mean your previous suggestion (leaking unbounded amount of memory to free() everyth…

I don't think the gp is describing the null garbage collector, rather one that can work incrementally and concurrently with the program doing its thing. Whereas a concurrent tracing gc has the problem of data changing while it runs and so special care has to be taken not to corrupt memory.

Re: Reference count, don't garbage collect

#308

Post by Bolkan »

Waterluvian wrote: post #131
imtringued wrote: post #130

Not only does the author ignore the huge progress in conventional garbage collected languages like Java, he also dismisses GC as inherently flawed despite the fact that the common strategy of only having one heap per application has nothing to do with garbage collection. In Pony each actor has its own isolated heap which means the garbage collector will only interrupt a tiny portion of the program for a much shorter…

I’m out of my league so this may be dumb, but does any language or VM or whatnot have a combined system where each thread has its own heap, and you can talk by passing messages, but they also have a common heap for larger data that’s too expensive to pass around, but at the cost that you have to be much more careful with lifetimes or have to manage it manually or something?

Dart

Re: Reference count, don't garbage collect

#309

Post by kcl »

Jweb_Guru wrote: post #98

I'm sorry, but this is a very poorly reasoned article that does not engage with any of the serious work that's been underway to get reference counting competitive with tracing GC. This is evident from the very first point: > 1. Updating reference counts is quite expensive. > No, it isn't. It's an atomic increment, perhaps with overflow checks for small integer widths. This is about as minimal as you can get short of…

GC researchers insist on conflating GC with all of automatic memory management. The public doesn't do this and neither does the article.

> Secondly, you know what's cheaper... Not doing anything at all.

These techniques are on the level of resetting a stack pointer or calling `sbrk()`. Incorporating them doesn't produce more-advanced GC schemes, it just means you neglected to consider similar allowances for RC.

The line of contention is at traversing the object graph and pausing threads.

Re: Reference count, don't garbage collect

#310

Post by afiori »

yakubin wrote: post #304
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…

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.

Post reply on HN