Hacker News Reader

Comment by danbruc | Hacker News Reader

Yes, in some scenarios you can associate the lifetime of a resource with the lifetime of a storage location, but this simply does not work in all cases, probably only in a small fraction of all cases. And then? How do you handle resources that have no single obvious owner? How do you determine if the resource is still in use when you are done with it in one place? You implement some kind of reference counting? You keep the resource alive until you reach a point where you definitely know it is no longer in use? You turn your code upside down and force it into a single owner structure destroying the semantics of your code on the way?

View on HN

"Yes, in some scenarios you can associate the life time of a resource with the life time of a storage location"

In what cases is this not possible? I model the resource as an object and that object has a memory location.

(Yes, in a non-deterministic GC, you can't do this for expensive resources, but that's a problem of GCs, not an in-principle problem).

EDIT: I am guessing the parent actually meant "associate the life time of a resource with the life time of a single, non-/never-shared storage location". The statement as written is one I have seen proponents of non-deterministic GCs make.

For example, two lists both contain a reference to the same object. Neither one is a sole owner, and you can't safely destroy the object until both lists are destroyed.

Then the lists should only have a weak_ptr to the object.

Something is handling both list [1], that something could own the object, or maybe something external to that. Giving ownership of the object to both list is a design error [2].

[1] e.g. if the two list are an implementation detail of a data structure, the data-structure itself could own the objects in the lists.

[2] Do non-deterministic garbage collectors that handle cycles allow you to have a resource with multiple owners? Yes. Should you do it? No, god, please don't.

It's only a design error when you don't have a GC.

Imagine you have an arbitrary long lived connected cyclic graph that can be incrementally updated from multiple short lived worker threads. With a GC, this is a no brainer: just put the objects in the graph. No workarounds, no extra tracking.

Without a GC, on removing a node, you have to walk to essentially do a mark/sweep of the graph to find dead nodes that were connected through the node you removed.

Have a vector of shared_ptr that own the objects in the graph and build a graph with weak_ptr ?

Removing an object is just as easy as removing an element from the vector. (If you test the weak_ptrs on use, that's actually the only thing you would need to do).

shared_ptr means reference counting, reference counting means you lose determinism because you no longer know if releasing a reference will trigger releasing a resource. Delay and offload releasing the resource to a separate thread, you lose your guarantees when a resource is actually freed, too, just like using a garbage collector.

And I know it for the .NET GC, they tried a reference counting GC as alternative to a collecting GC and it performed worse and comes with the cycle trouble.

Isn't that equivalent to using a shared_ptr directly, just unnecessarily complicated?

Reference counting works fine as long as you don't have cycles, of course.

The solution above works even if your graph has cycles. Of course if you know that it doesn't you can just build the graph with unique_ptrs.

It works with cycles, as long as you can know exactly when you want to remove something from the graph (as opposed to having it be removed when no longer referenced). Reference counting works fine that way too, though. It's a bit more work, but you just dive into the structure and manually remove references which breaks any cycles it may be involved in.

Isn't it better to walk the graph than all your objects, other things being equal?

Of course, not having to implement the garbage collector yourself is a benefit.

I am mostly developing business applications. The user decided to view a couple of orders, orders reference products and some of the orders reference the same product. Who owns the product? Definitely non of the orders and neither the form showing the order. Well, I could attach them to the main form, but now they stay in scope until you close the application. This is not what we wanted. I could implement referencing counting - use shared_ptr - but well, the designers of garbage collectors tried it and found reference counting garbage collectors perform worse than collecting garbage collectors. Am I missing a obvious solution?

It's simple. The key is that something has to have _ownership_ of the products. [1]

User decides to view a couple of orders. Orders reference products. Those products are managed by something (e.g. an unordered_map of shared_ptr). The order can check, is my product there? If so, i'll copy the shared_ptr to it. Otherwise, I create a shared_ptr for a product and store a copy in the manager. When the order's destructor is triggered, you check the count of the shared_ptr. If it is 2 (i.e. the order and the manager), the order removes the shared_ptr.

[1] Single ownership is the key concept, not reference counting which is just an implementation detail.

https://news.ycombinator.com/item?id=7315392

https://news.ycombinator.com/item?id=7315575

(Don't want to duplicate the comment once again.)

Sharing immutable data between multiple places with no single master owner is a perfectly reasonable thing to do in a program.

I fail to see why you need cycles' support for that.

You asked for a situation where the lifetime of a resource can't be directly tied to the lifetime of a single storage location. Cycles are a different matter.

>You asked for a situation where the lifetime of a resource can't be directly tied to the lifetime of a single storage location.

I don't think I asked for that but correct me if I did (maybe I'm just not understanding your point).

Anyways, could you elaborate why shared_ptr, unique_ptr, and weak_ptr don't work in that case?

Oops, wasn't you, but the OP I was responding to initially.

shared_ptr works fine for my example. Shared immutable state is a case where reference counting works extremely well, since immutability implies no cycles.

In my experience, "small fraction of all cases" is inaccurate - in my C it's probably 1/3 to 2/3 of cases, depending on how much I structure my program to allow for it. For instance, synchronous processing of messages makes it relevant in many more cases, but has obvious costs (which isn't to say they aren't sometimes worth bearing). It is still true that there is a significant fraction of coding where it does not apply, and which must be treated specially.

Examples of a situation where you don't want a resource associated with a variable/storage location?

Global variables exist and can be used to hold resources. If you have a resource that's not associated with any single function context you can move it into the global variable.

See mikeash's comment for a very simple situation. I mostly develop business applications with customers, products, orders, contracts, addresses and hundreds of other things connected and entangled in sometimes insane ways as dictated by the business. And at any point the user may just open another form viewing the orders of a different customer linked to the same products as in five other forms. Managing such complex object graphs by hand would be a nightmare. And this is just the model of the business, we did not even start to think about database connections, client connections, UI components and what not.

Yes I think you would use a ref counted resource in that case. For your tangled mess of database connections I can't imagine ref counting not being adequate in those scenarios as well.

And now we are back at garbage collection - the two main options are reference counting GCs and collecting GCs. I know it for the .NET GC, they tried a reference counting GC and it performed worse than a collecting GC and not to forget the trouble with cycles when implementing a reference counting GC.

And reference counting also renders the point of determinism moot - now you never know if releasing a reference while trigger freeing a resource. You could of course delay offload it to a separate thread, but this makes you lose any guarantee about the time when the resource is actually freed, too.

> And reference counting also renders the point of determinism moot - now you never know if releasing a reference while trigger freeing a resource.

You know that releasing the last reference will. That is why the important concept is single ownership of resources and not reference counting by itself.

But you don't know which reference is the last until you actually get there - that is why you used reference counting in the first place, because you were unable to statically determine which reference will be the last one. So every time you abandon a reference it might be the last one and you might have to spend extra cycles to free the resource. This is no more deterministic than a garbage collector.

In a non-deterministic garbage collector memory _might not_ be released when the last reference goes out of scope (and this is often the case).

Ah, I don't think ref counting is generally considered GC. It's more like RAII and used in C++ elsewhere via shared_ptr.

It is a mechanism to figure out if a resource is no longer in use and can be released - that sounds like the very definition of garbage collection.

> Global variables exist

And are generally considered bad practice.

> You implement some kind of reference counting?

Yep! Or, ideally, you use one of the good reference counting libraries that your language almost certainly ships with if it is one which encourages RAII.

Reference counting is just one form of garbage collection, the other main alternative is a collecting garbage collector. And comparisons showed - I know that they tried both for .NET - that a collecting GC outperforms a reference counting GC. Yes, you will have to take a performance hit when you perform garbage collection in cases where it would not be necessary but the convince of not having to care far outweighs this because program correctness is important and development time expensive, computing power is cheap and does not matter. At least in my field, mainly business applications.

Well, reference counting is definitely a way to collect garbage, but when people say X language used a reference counting GC versus a collecting GC, they typically mean that X language was using that GC for all objects. I'm guessing that the .NET experiment you're thinking of used the terminology in that way, and if so, I don't think it's particularly surprising that reference counting was slower. But using a reference counting library only in cases where you find that you need multiple references to a single object is a very different animal. Most programs don't actually need much shared data, even without any design contortions.

Of course, you are right, I did not want to imply that we should call C++ a garbage collecting language just because it has shared_ptr. And you are right that you can achieve more optimal code if you can use you knowledge to decide when reference counting is necessary and when not. But there is just an enormous spectrum of cases where the convenience of a garbage collector - which gives you less (but not zero) opportunities for memory leaks and speeds up development - far outweighs the performance hit. And the performance hit is really not large, modern garbage collectors are highly tuned pieces of software. Obviously you probably don't want a GC run when you are in the middle of some timing critical driver code, but I never wanted to imply a black/white world where garbage collectors are the silver bullet. But the article is definitely wrong - garbage collection is not wrong (in all scenarios).

> But there is just an enormous spectrum of cases where the convenience of a garbage collector - which gives you less (but not zero) opportunities for memory leaks and speeds up development

I think the article is actually more of an argument against that line of reasoning than an argument about performance. Its main proposition is that properly used RAII gives you less opportunities for resource leaks of all sorts, and is very easy to do. I agree with you that it isn't wrong in all scenarios (I mostly program in Ruby and Javascript for goodness sake!), but I think a lot of people are unaware of some of the advances in patterns, libraries, and compilers that make it much easier to write software that doesn't need a GC.

Reply on news.ycombinator.com