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

381–390 of 415 posts

Re: Reference count, don't garbage collect

#381

Post by mbrodersen »

tsimionescu wrote: post #211
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…

free() calls that have to run for a data-dependent amount of time are more or less equivalent to GC pauses (assuming a concurrent GC that doesn't need to stop the world, like Java's). The most typical example is free()-ing a a linked list, which takes O(n) free() calls to free with a simple RC mechanism.

The compiler uses arrays for lists instead of linked lists. It is a performance improvement compared with how functional compilers usually do it. And the language is designed in such a way that rule writers manipulate whole lists at a time instead of one element at a time. A bit like array languages. It changes how the code is written compared with traditional functional code.

Re: Reference count, don't garbage collect

#382

Post by mbrodersen »

cakoose wrote: post #140
refulgentis wrote: post #134

Earlier quoted context omitted.

I'm not sure whats being asserted here, could you explain more? This sounds like you're describing a non-stopping GC, and its well understood reference counting is garbage collection. I'm not sure how the rest applies, you're correct, it is possible to write software with just malloc and free.

Re: "it's well understood reference counting is garbage collection". I think this might just be a terminology thing. There appear to be two ways the terms are categorized: 1. "reference counting" and "garbage collection" are two types of automatic memory management/reclamation. 2. "reference counting" and "tracing garbage collection" are two types of garbage collection. I think mbrodersen is using #1. (Back in the 90…

Yep. The compiler generates code that works the same way that an experienced C programmer would hand optimise alloc/free calls and manually keep track of shared data by increasing/reducing a reference counter. There is no separate mark/sweep or whatever step.

Re: Reference count, don't garbage collect

#383

Post by mbrodersen »

UncleEntity wrote: post #284
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…

> 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. Which is a very good reason to develop an optimized GC algorithm, the domain experts can crank out code without having to optimize every single memory (de)allocation which sounds like a waste of their time. It’s funny, people don’t usually doubt that a modern compiler can do a bette…

Yep you are absolutely right. The business rules domain experts using the language are way more productive using a pure functional language that takes care of all the nitty gritty performance and memory issues for them. The code they write is 100% focused on solving customer problems.

Re: Reference count, don't garbage collect

#384

Post by mbrodersen »

elcritch wrote: post #210
viraptor wrote: post #141

Earlier quoted context omitted.

How do you collect cycles without a pause?

By requiring non-cyclic data structures or provide "weak" references. It's actually pretty easy to write most code without cycles. I program a lot in Nim and generally compile lots of programs with ARC and no cycle collector without issue.

Yep. The language doesnt allow data cycles. Nobody ever complained about that or even noticed it.

Re: Reference count, don't garbage collect

#385

Post by eru »

klodolph wrote: post #339
eru wrote: post #163

Earlier quoted context omitted.

And if you have really clear ownership, you don't need reference counting either..

That's definitely not true. "Clear ownership" may still be shared ownership.

Hmm, ok. But how is that different from situations where tracing GC is useful? (And even languages with a tracing GC often offer weak pointers. Eg Haskell and Java do. Python does as well, but Python has both reference counting and tracing garbage collection.)

Apart from performance (latency vs throughput) considerations, the only difference between RC and GC for your algorithms and datastructure design is whether you allow circles in your datastructures.

Re: Reference count, don't garbage collect

#386

Post by eru »

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

As a slight tangent, weak pointers are useful in languages with a tracing GC, too. Haskell offers weak pointers.

For example they make certain kinds of caches easier.

Re: Reference count, don't garbage collect

#387

Post by eru »

gus_massa wrote: post #352
eru wrote: post #160

Earlier quoted context omitted.

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" ve…

Thanks for doing the legwork! I didn't find anything definite in twenty seconds of Googling, so I left my comment vague.

Re: Reference count, don't garbage collect

#388

Post by eru »

int_19h wrote: post #232
eru wrote: post #150

Earlier quoted context omitted.

Yes. In Python reference counting precedes tracing garbage collection. So they didn't 'go through the hassle of implementing reference counting' after they already had tracing garbage collection. Instead they went through the hassle of implementing tracing garbage collection after they already had reference counting. (And as you say for backwards compatibility reasons, they can't get rid of reference counting.)

It should be noted that the Python language spec explicitly says that refcounting, and the resulting deterministic cleanup, is an implementation detail of CPython, and not part of the Python language proper. Precisely so that other implementations like Jython or IronPython could just use GC without refcounting. https://docs.python.org/3/reference/datamodel.html#objects-v... So, idiomatic Python does not rely on this,…

Yes, I know that I was referring to a detail of CPython when I said 'Python' in general. Alas, in practice Python really is CPython, more or less.

The biggest problem is that reference counting is baked into how CPython's C-modules work.

Re: Reference count, don't garbage collect

#389

Post by eru »

kaba0 wrote: post #208
eru wrote: post #146

Earlier quoted context omitted.

I wouldn't call reference counting a hack. The paper mention elsewhere in the comments, https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-... "A Unifying Theory of Garbage Collection" put this in context. For example, a generational garbage collection essentially employs a hybrid approach between tracing and reference counting. Similarly, depending on your system's trade-offs, reference counting might be be…

I meant hack as in languages meant for primarily for manual memory can still have RC (rust, C++), but that will only be a conservative GC algorithm due to no cycle detection. My use of hack here was only to denote that library-only RC , while possible, may not be the best approach and is used as an escape hatch in rare cases.

Oh, ok. That makes sense. Though I would count the Boehm Garbage Collector as a hack then, too?

Apropos hacks, have a look at this memory management 'thing' that doesn't move, but manages to compact: https://github.com/plasma-umass/Mesh

Re: Reference count, don't garbage collect

#390

Post by wizofaus »

mbrodersen wrote: post #384
elcritch wrote: post #210

Earlier quoted context omitted.

By requiring non-cyclic data structures or provide "weak" references. It's actually pretty easy to write most code without cycles. I program a lot in Nim and generally compile lots of programs with ARC and no cycle collector without issue.

Yep. The language doesnt allow data cycles. Nobody ever complained about that or even noticed it.

That seems a little hard to believe. I can't think of many complex pieces of software I've worked on that didn't have such cycles (e.g. any sort of tree structure where parents need to know about children and children need to know about parents - how does Nim handle that?)
Post reply on HN