Hacker News Reader

Comment by smasher164 | Hacker News Reader

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.

View on HN

Not my experience at all. I am maintaining a very high performance JIT compiler for a Haskell like programming language used in production at large enterprises around the world. So I am used to very carefully analyse performance. And reference counting is never the bottleneck. You might be right in theory but not in practice.

Not sure about the characteristics of your workload, but here's a talk where a group wrote device drivers in several high-level languages, and measured their performance: https://media.ccc.de/v/35c3-9670-safe_and_secure_drivers_in_...

They found that the Swift version spent 76% of the time doing reference counting, even slower than Go, which spent 0.5% in the garbage collector.

Yeah, GP has no idea what they are talking about. They replied something similar on another thread without ever providing evidence for their claims. They even claimed their RC implementation in Haskell is faster than hand-crafted C++.

Gave me a chuckle.

And your reply game me a chuckle :) The code is unfortunately not open source so I can’t provide the evidence. You believe what you want to believe of course. However I am happy to answer any questions on how it is implemented down to the lowest-level nitty gritty details.

All that tells me is that the Swift implementation is different from the one I implemented.

Well, it won’t be the bottleneck itself, but it has an overhead on basically every operation, which likely won’t show up during profiling.

Also, I fail to see the advantage of RC in case of a presumably mostly immutable language - a tracing GC is even faster there due to no changes to the object graph after allocation, making a generational approach scale very well and be almost completely done in parallel.

Nope. The compiler does a full program optimisation, reducing the reference counting to an absolute minimum. There is close to zero overhead passing data around. It does not work like C++ shared_pre. shared_ptr is slow.

> The compiler does a full program optimisation

That's the equivalent of an escape analysis I assume, which optimization exists for tracing GCs as well.

I wonder how Haskell's purity influences RC usage patterns. Are there tricks which aren't possible in an imperative language?

Haskell specifically is a poor choice of language here, because it creates cycles like the pest. (This is because it uses lazy evaluation, and programming patterns (design patterns?) using lazy evaluation tend to use cyclical references. Strict FP languages might support your point better, but then Ocaml again doesn't work because it mutates like the pest.)

Furthermore it also allocates like the pest: busy Haskell programs regularly allocate on the order of 1GB/sec. However, this works out fine because the majority of those allocations are short-lived, hence become dead quickly, hence a GC that is designed to only touch live data (like Haskell's GC!) will handle that well.

It is a Haskell inspired language but not Haskell. The syntax is similar but it is eagerly evaluated and has no IO and no data cycles. It is used 100% for evaluating complex optimisation and business rules within a client application. The language was carefully crafted to maximise rules writer productivity and execution performance.

Ah, I was just responding to my parent, committing the sin to not remember what they are replying to.

Interesting; with purity and eager evaluation, and presumably no mutually recursive bindings either, you should indeed get absence of cycles. I do wonder: does absence of mutually recursive bindings come back to bite you at some point? Or does the need for that just not arise in your domain?

Is there stuff that you feel is awkward to express in your language that would be fine in Haskell proper?

One reason you'd choose ref counting is because it's deterministic behavior, whereas you lose that granularity with gc, even if you did a gc cleanup.

I see great reasons for both systems being useful, but both systems also bring their own warts.

Yes, ref counting affects cache and branch prediction, but gc is a whole complete subsystem running in parallel with your main code, constantly cleaning up after you. It will always depend upon the application which will determine what's best for that application.

Some languages lean heavily one way than the other too. Scripting with ref counting would be a nightmare, as would running a garbage collector on an 8bit micro. Since the article's talking C & C++, then of course a pro ref counting stance makes sense.

>One reason you'd choose ref counting is because it's deterministic behavior

Not sure if it's entirely deterministic. A variable going out of a scope can trigger deallocation of a large object graph and it's not always clear by just looking at a code what will happen (especially if objects have destructors with side effects, your object graph is highly mutable, and your code is on a hot path). A common trick is to delay deallocation to a later time, but then again you can't be sure when your destructors will be run. Another issue is cycles, if your RC system has cycle detection, your program will behave differently depending on whether a cycle formed at runtime or not.

> trigger deallocation of a large object graph and it's not always clear by just looking at a code what will happen

If you can't understand what's happening when an object gets freed, it may be a sign that your code is too tightly coupled and/or becoming spaghetti. I've found that the more graph-like my data structures become, the more inadvertent complexity I'm adding. That's the whole reason we talk about data normalization, is to avoid these types of couplings.

Come on, object graphs are completely dynamic, noone can say where will “a variable go out of scope”, unless we literally have a hello world.

Do you honestly claim that you know when deallocations happen in any codebase full of conditionals depending on outside effects (user input, network, etc)?

I mean... people program large developments in Rust with pretty minimal use of Arc. It's clearly possible to structure many programs this way (though they do not necessarily look like programs in other languages). It's important not to make extreme and definitive statements about what's realistic that are contradicted by a bunch of existing programs... in any case this has little bearing on the reference counting vs tracing GC performance thing. It also might be instructive to look at how Rust frameworks deal with your UI example: mostly, by keeping a vector of UI widgets and reusing the allocation over and over. Therefore, you shouldn't see a significant pause there (you could probably argue the pause comes when resizing the vector technically, but it is generally efficient enough that you're not going to notice it unless the vector is very very large).

Statically adding code at the end of scope-leaves is different than knowing when the deallocation will happen.

The borrow checker doesn’t know when will the scope end, it only knows that however it happens upholds the invariants it cares about. You might call two entirely different code path inside a method and rust will only execute the dealloc logic at the end at a non-deterministic time. But maybe we just use different terminology here.

Fun fact: Rust actually had a proposal at one point to execute drops entirely statically, with no runtime flags on the stack. It was decided against because people thought it would be too confusing as it would be hard to tell when the destructor would run, but for purely memory related destructors it would probably be acceptable.

I do see what you're trying to get at, I think, but it's also worth noting that the use of stuff like arenas and vectors to absorb the cost of the repeated reallocations goes a long way here towards making deallocation times predictable in practice (if not in theory). It is certainly the case that you can mostly reduce the deallocation overhead to ~ zero for any particular part of your Rust program without that much effort, unless you are writing an interpreter for a different language that expects GC semantics (at least, that's been my experience).

> Do you honestly claim that you know when deallocations happen in any codebase full of conditionals depending on outside effects (user input, network, etc)?

Yes. C programs have been doing this for over 40 years now. A leak free C program has an equivalent free for every malloc, which means they know exactly when everything gets allocated and freed.

That just means that every allocation has a pair that frees it - that’s different from knowing how many allocations happen, when and when does the corresponding free happen.

For a simple example, take a text editor (sure, you would likely allocate a much bigger buffer in practice) that allocates for each line of text an object, and adds the buffer’s pointer to a list to be freed - this freeing happens when the user closes the open text file window. While you do know that every allocation will be freed and know their relative order, you don’t know anything more specific - will the user open multiple such files first, close them in some random order, etc.

It's not different though. You asked:

> Do you honestly claim that you know when deallocations happen in any codebase full of conditionals depending on outside effects (user input, network, etc)?

And the answer to that is yes. You even admitted that here:

> While you do know that every allocation will be freed and know their relative order

This is a lot more specific than "the GC will free this memory at some indeterminate point that it deems acceptable".

Additionally, in your specific example:

> this freeing happens when the user closes the open text file window

So you can plan for that. You can pop up a saving screen if you run tests and realize that the deallocations take a bit of time. With GC, it's luck of the draw. I'm speaking from experience.

I wrote a tool that used Roslyn to do some transpiling of a custom format in our company. It was very important that it ran fast, since this algorithm was going to be run in a time sensitive situation. And it had to free it's memory as soon as it was done using it, since it was hot swapping the DLLs and I needed to make sure I wasn't getting name collisions from DLLs that were waiting for the GC to run to fully unload the old DLLs. I tried so many different ways to tell C# GC to collect the object tree that I knew was no longer necessary, but it was seemingly impossible.

Microsoft even has a page dedicated to debugging why an assembly won't unload and it reads:

> The difficult case is when the root is a static variable or a GC handle.[0]

Now you may say that this while problem only arises because of my weird specific use case, which is true but I couldn't change my requirements since those were hard requirements from my company. This could all easily be solved if a GC allowed you to define the concept of ownership. I had references hanging around that didn't matter because the object holding the references didn't own that memory.

All that to say, yes you can know exactly when you're memory will be deallocated in a language like C. In a language like C#, your left to the whims of the GC which can be a deal breaker in lots of cases.

What really gets me too, is languages like C# end up creating DI frameworks with the "novel" concept of lifetime requirements to make sure object lifetimes are properly scoped. What the heck? It's got a GC. Why did they go through all that trouble if the GC just cleans it up for you? If I have to think about object lifetimes, I may as well switch to a language that makes that explicit rather than a language that obfuscated it as much as possible.

[0]: https://docs.microsoft.com/en-us/dotnet/standard/assembly/un...

Well, you can always go a layer below and use a bytebuffer (or its C# equivalent). You can drop it at the end of the task in an instant.

But I don’t think that giving up the comfort/performance of a good GC is a good tradeoff in all the other cases. The same way Rust et alia can opt into some form of GC with (A)RC, GC languages can have escape hatches as well.

In most cases, yes, you should be able tell when deallocations are going to happen once you know the inputs.

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.

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.

Deterministic means that running the same part of the program will take the same amount of time. Deallocating the same memory object graph is pretty much deterministic.

GC can throw a spanner in that by deciding that now is the time to do its thing.

>Deterministic means that running the same part of the program will take the same amount of time

The object graph can easily be different from run to run depending on user input, timing, etc. Say, in the first run, the graph has a large subgraph due to a runtime condition (a property is set to a certain value), and on the next run, the graph is more lightweight because the property was not updated. It will take different amounts of time to collect such graphs (especially if they have destructors). I don't see how GC is any different here, it also depends on input, timing, etc. It's true though that a programmer has less control of GC because the rules when it is triggered are not always 100% clear (implementation details of a particular runtime) but imho they are as deterministic as RC; RC is just a form of GC which has very simple rules which are eaiser to understand.

That is expected. With different input data (what you call runtime condition) you get different result. With the same input data the determinism holds for RC, but not for GC.

> Scripting with ref counting would be a nightmare, [...]

Why? Old version of Python used ref counting only, and Python still largely relies on reference counting (but has a GC to detect cycles).

Reply on news.ycombinator.com