News for hackers. Stuff that matters.
Re:Garbage Collection is Wrong by danbruc on Thursday February 27, 2014 @04:11PM (#7315096)
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?
Re:Garbage Collection is Wrong by mpweiher on Thursday February 27, 2014 @04:21PM (#7315165)
"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.

Re:Garbage Collection is Wrong by mikeash on Thursday February 27, 2014 @04:23PM (#7315183)
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.
Re:Garbage Collection is Wrong by letzjuc on Thursday February 27, 2014 @04:32PM (#7315251)
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.

Re:Garbage Collection is Wrong by ori_b on Thursday February 27, 2014 @04:35PM (#7315270)
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.

Re:Garbage Collection is Wrong by letzjuc on Thursday February 27, 2014 @04:44PM (#7315330)
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).

Re:Garbage Collection is Wrong by danbruc on Thursday February 27, 2014 @05:03PM (#7315490)
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.

Re:Garbage Collection is Wrong by mikeash on Thursday February 27, 2014 @04:49PM (#7315381)
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.

Re:Garbage Collection is Wrong by letzjuc on Thursday February 27, 2014 @05:06PM (#7315513)
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.
Re:Garbage Collection is Wrong by mikeash on Thursday February 27, 2014 @09:11PM (#7316830)
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.
Re:Garbage Collection is Wrong by dllthomas on Thursday February 27, 2014 @05:02PM (#7315480)
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.

Re:Garbage Collection is Wrong by danbruc on Thursday February 27, 2014 @04:42PM (#7315318)
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?
Re:Garbage Collection is Wrong by letzjuc on Thursday February 27, 2014 @04:57PM (#7315444)
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.

Re:Garbage Collection is Wrong by danbruc on Thursday February 27, 2014 @05:15PM (#7315600)
Re:Garbage Collection is Wrong by mikeash on Thursday February 27, 2014 @04:39PM (#7315297)
Sharing immutable data between multiple places with no single master owner is a perfectly reasonable thing to do in a program.
Re:Garbage Collection is Wrong by letzjuc on Thursday February 27, 2014 @04:47PM (#7315366)
I fail to see why you need cycles' support for that.
Re:Garbage Collection is Wrong by mikeash on Thursday February 27, 2014 @04:52PM (#7315395)
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.
Re:Garbage Collection is Wrong by letzjuc on Thursday February 27, 2014 @05:09PM (#7315540)
>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?

Re:Garbage Collection is Wrong by mikeash on Thursday February 27, 2014 @09:13PM (#7316843)
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.

Re:Garbage Collection is Wrong by dllthomas on Thursday February 27, 2014 @08:26PM (#7316647)
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.
Re:Garbage Collection is Wrong by rian on Thursday February 27, 2014 @04:25PM (#7315205)
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.

Re:Garbage Collection is Wrong by danbruc on Thursday February 27, 2014 @04:35PM (#7315264)
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.
Re:Garbage Collection is Wrong by rian on Thursday February 27, 2014 @04:45PM (#7315345)
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.
Re:Garbage Collection is Wrong by danbruc on Thursday February 27, 2014 @04:51PM (#7315392)
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.

Re:Garbage Collection is Wrong by letzjuc on Thursday February 27, 2014 @05:21PM (#7315646)
> 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.

Re:Garbage Collection is Wrong by danbruc on Thursday February 27, 2014 @05:35PM (#7315738)
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.
Re:Garbage Collection is Wrong by letzjuc on Thursday February 27, 2014 @08:55PM (#7316753)
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).
Re:Garbage Collection is Wrong by rian on Thursday February 27, 2014 @05:10PM (#7315555)
Ah, I don't think ref counting is generally considered GC. It's more like RAII and used in C++ elsewhere via shared_ptr.
Re:Garbage Collection is Wrong by danbruc on Thursday February 27, 2014 @05:31PM (#7315714)
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.
Re:Garbage Collection is Wrong by gnaritas on Thursday February 27, 2014 @04:37PM (#7315286)
> Global variables exist

And are generally considered bad practice.

Re:Garbage Collection is Wrong by sanderjd on Thursday February 27, 2014 @05:04PM (#7315500)
> 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.

Re:Garbage Collection is Wrong by danbruc on Thursday February 27, 2014 @05:13PM (#7315575)
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.
Re:Garbage Collection is Wrong by sanderjd on Thursday February 27, 2014 @05:23PM (#7315659)
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.
Re:Garbage Collection is Wrong by danbruc on Thursday February 27, 2014 @05:45PM (#7315793)
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).
Re:Garbage Collection is Wrong by sanderjd on Friday February 28, 2014 @10:14AM (#7319098)
> 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.