Reference count, don't garbage collect • Hacker News Board

Re: Reference count, don't garbage collect

#351

Post by mypalmike » Sat, Jul 30, 2022, 5:59 PM UTC

int_19h wrote: post #297

mypalmike wrote: post #270

Earlier quoted context omitted.

But what if my application is say, a diagramming GUI where the user can create many nested items. When they delete a million items by removing a top level item, how are you going to avoid a pause if using single threaded synchronous RC? Per object determinism doesn't mean systemic determinism on a dynamic graph.

You're not going to avoid it. But you will know that it'll happen at that exact moment. Whether that is actually important or not depends on the use case. Personally, I think that GC is plenty good enough for most GUI apps other than games, and allows for non-contorted modelling of said GUI (e.g. with backreferences where they make sense).

You say, "you will know that it'll happen at that exact moment". I'm curious what you mean by this.

Do you mean that the user will know? Well sure, that's the pain point to avoid in this case. Anyone who has tried to quit certain versions of various browsers after a long session with many tabs, etc. will know this pain when closing a window. Server side applications can have similar issues.

Or do you mean the code will "know"? That is, the code will need to predict, at runtime, that a code path will be expensive and choose a memory release strategy based on some criteria?

Or do you mean the designer of the code will know, and avoid RC before implementing?

Honest question, I'd like to understand your perspective. Thanks.

Re: Reference count, don't garbage collect

#352

Post by gus_massa » Sat, Jul 30, 2022, 6:12 PM UTC

eru wrote: post #160

nikolay wrote: post #129

When I wrote a Lisp interpreter in the '90s, that's how I did it and I'm ashamed to admit that I have no idea how modern GC is done - I've always assumed (naively!) that it was like Lisp's!

Modern Lisps likely have modern GCs. I mean there's no reason for them not to. Racket probably has a state-of-the-art garbage collector. (I don't actually know, but that's where I would start looking.) Clojure obviously has the same garbage collector as any other JVM language.

Racket has like 5 GC, perhaps more.

In one extreme you can build Racket using the Senora GC that is conservative and not moving, that is used only for bootstraping.

On the other extreme, both of the normal versions of Racket have custom moving incremental GC. The docs with some high level explanations are in https://docs.racket-lang.org/reference/garbagecollection.htm...

The implementation details of the main "CS" version are in https://github.com/racket/racket/blob/master/racket/src/Chez... It's a replacement of the default GC of Chez Scheme that has better support for some features that are used in Racket, but I never have looked so deeply in the details.

Re: Reference count, don't garbage collect

#353

Post by pornel » Sat, Jul 30, 2022, 6:19 PM UTC

kaba0 wrote: post #92

pornel wrote: post #79

Earlier quoted context omitted.

Saying that both have pauses is a false equivalence to me. It overlooks the difference in how likely this can occur (without large enough object graphs freed from the top it may never be an issue), when this occurs (any time vs on cleanup that may not be latency sensitive), and how much control the programmer has over RC costs (determinism allows to profile this and apply mitigations). RC with borrow checking can avo…

> and how much control the programmer has over RC costs (determinism allows to profile this and apply mitigations). I fail to see how would it be deterministic in a highly dynamic program. Like, imagine a game for example where the user can drag'n'drop different things to a "parent" object. Observability is imo an entirely different axis. > RC with borrow checking can avoid a lot of refcount increments. That's the sa…

Even in a highly dynamic program you can know all the places where releases happen. If you find a slow case, you can reproduce it, and mitigate (e.g. send object to a background thread to avoid lag on the ui thread). This is different from tracing GC that may fire on any allocation, on a timer, and workload depends on heuristics and other things in the program.

Escape analysis is hard, and GC is typically used to free programmers from assisting it with extra syntax or unsafety. This is why GC languages tend to use generational GC instead of having precise analysis.

Re: Reference count, don't garbage collect

#354

Post by klodolph » Sat, Jul 30, 2022, 6:40 PM UTC

glouwbug wrote: post #348

klodolph wrote: post #70

Earlier quoted context omitted.

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

It sounds like you're saying that the only productivity gain from ARC (automatic reference counting) is that you don't have to manually annotate what type of pointer you want. I don't agree with that.

Yes, if you forget to mark a ref-counted pointer as weak, then you may get a memory leak. Memory leaks can be disastrous, but they can be benign, and they're always better than use-after-free.

In C++ it is easy to create a raw pointer (with & or *). It's unsafe. Soon enough, you have some lambda inside another function, but the lambda is executed after the enclosing function returns, and you've captured a variable with &. Oops. You thought that the lambda would get executed during the enclosing function's execution, but you misread the API you were using.

IMO the big productivity gain is being able to write code where I don't have to think too hard about whether the code is memory-safe. Modern C++ code makes this easier, but languages with ARC (like Objective-C or Swift) make this even easier. Code is mostly safe by default, and you can visually inspect code to look for unsafe behavior, more easily than you can with C++.

There are also hybrid ref-counted + tracing GC options. CPython uses this approach.

Re: Reference count, don't garbage collect

#355

Post by Jweb_Guru » Sat, Jul 30, 2022, 7:02 PM UTC

kcl wrote: post #309

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 l…

Of course I have considered similar allowances for Rc (this has nothing to do with stack allocation by the way, I'm hoping this is not a misunderstanding on your part). I referenced RC Immix throughout the post. It is extremely clear that the author of the article did not consider such allowances because they do not see that there is a problem. Even if the author had done so, there is a big difference between saying "whatever, I could do that same thing for Rc!" and actually doing it--a hugely nontrivial one that has not been fully bridged until quite recently. These kinds of techniques are still not used in production languages with reference counting garbage collection, including Swift.

Re: Reference count, don't garbage collect

#356

Post by thirdmunky » Sat, Jul 30, 2022, 8:49 PM UTC

chrisseaton wrote: post #243

thirdmunky wrote: post #138

Earlier quoted context omitted.

Java idioms are one contributing factor. There's some inherent wordiness too - for example, Hello World in Java is wordier than in most other programming languages.

That's syntax not semantics though.

agreed, I think everyone under the child comment of yours is talking about the verbosity coming from non-semantic stuff.

Re: Reference count, don't garbage collect

#357

Post by scruple » Sat, Jul 30, 2022, 9:10 PM UTC

pjmlp wrote: post #282

viktorcode wrote: post #245

Earlier quoted context omitted.

> it's the myth that garbage collection always automatically means your program is going to be spending 80% of its time doing it and freezing for a second every five seconds the instant you use a language with garbage collection. Not 80%, but still annoying enough to dump it: https://discord.com/blog/why-discord-is-switching-from-go-to...

Magpie developers would use any excuse to move on. It is less boring than building up the skills to fix the plane in mid-flight. https://github.com/usbarmory/usbarmory/wiki

> Magpie developers

That was a new one for me. I sort of understood the reference but the Jeff Atwood post [0] where it's introduced is as relevant today as it was when this was published in 2008.

[0]: https://blog.codinghorror.com/the-magpie-developer/

Re: Reference count, don't garbage collect

#358

Post by tpolzer » Sat, Jul 30, 2022, 9:11 PM UTC

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.

unique_ptr is nearly overhead free compared to a bare pointer (except for argument passing... because of ABI concerns).

shared_ptr is expensive and easy to build leaks with, so a lot of code bases avoid it where possible. Though it's only expensive when you copy it, moving it is ~free.

Re: Reference count, don't garbage collect

#359

Post by staticassertion » Sat, Jul 30, 2022, 9:44 PM UTC

tpolzer wrote: post #358

staticassertion wrote: post #312

Earlier quoted context omitted.

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

unique_ptr is nearly overhead free compared to a bare pointer (except for argument passing... because of ABI concerns). shared_ptr is expensive and easy to build leaks with, so a lot of code bases avoid it where possible. Though it's only expensive when you copy it, moving it is ~free.

This is just a more detailed version of my point lol you just listed the reasons they are not free.

Re: Reference count, don't garbage collect

#360

Post by int_19h » Sat, Jul 30, 2022, 10:06 PM UTC

mypalmike wrote: post #351

int_19h wrote: post #297

Earlier quoted context omitted.

You're not going to avoid it. But you will know that it'll happen at that exact moment. Whether that is actually important or not depends on the use case. Personally, I think that GC is plenty good enough for most GUI apps other than games, and allows for non-contorted modelling of said GUI (e.g. with backreferences where they make sense).

You say, "you will know that it'll happen at that exact moment". I'm curious what you mean by this. Do you mean that the user will know? Well sure, that's the pain point to avoid in this case. Anyone who has tried to quit certain versions of various browsers after a long session with many tabs, etc. will know this pain when closing a window. Server side applications can have similar issues. Or do you mean the code wi…

This was specifically a response to:

> you know when deallocations happen in any codebase full of conditionals depending on outside effects

What I'm saying is that the author of the code, and anyone else who can read and understand it, will know that, if the user does X, Y, and Z, it'll trigger a deeply nested release of an object graph that'll cause a period of non-responsiveness visible to the user.

Whether the author will consider this acceptable or not is a different question.