Garbage Collection is Wrong(lb-stuff.com)
lb-stuff.com
Garbage Collection is Wrong
http://www.lb-stuff.com/gc.html
22 comments
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?
"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.
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.
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.
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).
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.
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.
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.
Of course, not having to implement the garbage collector yourself is a benefit.
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?
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.
shared_ptr works fine for my example. Shared immutable state is a case where reference counting works extremely well, since immutability implies no cycles.
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.
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.)
https://news.ycombinator.com/item?id=7315575
(Don't want to duplicate the comment once again.)
[deleted]
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.
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 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.
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).
> Global variables exist
And are generally considered bad practice.
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.
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.
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.
Meh, GC has its uses. It helps that the vast majority of resources are indeed memory, so it makes sense to special-case.
Although in some situations it isn't acceptable and it's interesting to look at what languages like Rust do about it. It ends up guaranteeing safety, but with not much more effort than GC.
Although in some situations it isn't acceptable and it's interesting to look at what languages like Rust do about it. It ends up guaranteeing safety, but with not much more effort than GC.
Idiomatic Rust code follows the RAII pattern and does not use garbage collection; we've been finding that it works very effectively.
Of course it helps that Rust has notation for object lifetimes. :)
Zero-suppressed Binary Decision Diagrams (ZDD) requires reference-count based garbage collection in order to be efficient. RAII isn't a viable replacement.
See for example http://ashutoshmehra.net/blog/2008/12/notes-on-zdds/ - "ZDD-bases, which though conceptually easy to understand, are non-trivial to implement efficiently because behind the scenes, lots of things have to be taken care of: o New nodes are born and old ones die — nodes have to be efficiently allocated, ref-counted and garbage-collected."
Or from http://www.ecs.umass.edu/ece/labs/vlsicad/ece667/reading/som... :
> One would like to release the memory used by those BDDs, but there are two problems. First, some subgraphs may be shared by more than one function and we must be sure that none of those functions is of interest any longer, before releasing the associated memory. Second, BDD nodes are pointed from the unique table and the computed table, as well as from other BDD nodes. There are therefore multiple threads and one cannot arbitrarily free a node without taking care of all the threads going through it [12].
> A solution to these two problems is garbage collection.
Similarly, http://vlsi.colorado.edu/~fabio/CUDD/node3.html ("The CUDD package relies on garbage collection to reclaim the memory used by diagrams that are no longer in use. The scheme employed for garbage collection is based on keeping a reference count for each node."),
See for example http://ashutoshmehra.net/blog/2008/12/notes-on-zdds/ - "ZDD-bases, which though conceptually easy to understand, are non-trivial to implement efficiently because behind the scenes, lots of things have to be taken care of: o New nodes are born and old ones die — nodes have to be efficiently allocated, ref-counted and garbage-collected."
Or from http://www.ecs.umass.edu/ece/labs/vlsicad/ece667/reading/som... :
> One would like to release the memory used by those BDDs, but there are two problems. First, some subgraphs may be shared by more than one function and we must be sure that none of those functions is of interest any longer, before releasing the associated memory. Second, BDD nodes are pointed from the unique table and the computed table, as well as from other BDD nodes. There are therefore multiple threads and one cannot arbitrarily free a node without taking care of all the threads going through it [12].
> A solution to these two problems is garbage collection.
Similarly, http://vlsi.colorado.edu/~fabio/CUDD/node3.html ("The CUDD package relies on garbage collection to reclaim the memory used by diagrams that are no longer in use. The scheme employed for garbage collection is based on keeping a reference count for each node."),
not even sure where to start...
1. plenty of garbage collectors do not pause all threads or wait for memory to be full.
2. you CAN ask for gc anytime you want in java and in C# (you need not wait for it to happen)
3. new and delete are still integral to C++ (check out any large codebase, like llvm)
1. plenty of garbage collectors do not pause all threads or wait for memory to be full.
2. you CAN ask for gc anytime you want in java and in C# (you need not wait for it to happen)
3. new and delete are still integral to C++ (check out any large codebase, like llvm)
1. Can you give an example of some of these systems?
2. Designing your code in such a way that requires it to invoke the GC seems counter-productive. If your algorithm is producing a bunch garbage that is statically known, why not just release that memory explicitly? Invoking the GC is way more expensive than necessary here.
3. New/delete will always be used in performance critical code but I think the point is that in general it's not a good practice.
2. Designing your code in such a way that requires it to invoke the GC seems counter-productive. If your algorithm is producing a bunch garbage that is statically known, why not just release that memory explicitly? Invoking the GC is way more expensive than necessary here.
3. New/delete will always be used in performance critical code but I think the point is that in general it's not a good practice.
1. http://www.azulsystems.com/presentations/qcon-london-2011
2. fair but irrelevant. the argument was that there is no way to make GC happen. It was wrong. I never objected to the (perhaps more interesting) argument that one should be able to manually delete objects
3. then the parent should have said "in toy codebases, whose function is to look pretty, new and delete have no place" instead of a sweeping generalization that all uses of new and delete are archaic and wrong. That one generalization was an insult to every llvm & WebKit developer out there.
Disclaimer: i have no dog in this race - i prefer to work in C and think anyone who cannot free their own memory should maintain a safe 5 meter distance from any compiler. (this is my opinion only, of course)
2. fair but irrelevant. the argument was that there is no way to make GC happen. It was wrong. I never objected to the (perhaps more interesting) argument that one should be able to manually delete objects
3. then the parent should have said "in toy codebases, whose function is to look pretty, new and delete have no place" instead of a sweeping generalization that all uses of new and delete are archaic and wrong. That one generalization was an insult to every llvm & WebKit developer out there.
Disclaimer: i have no dog in this race - i prefer to work in C and think anyone who cannot free their own memory should maintain a safe 5 meter distance from any compiler. (this is my opinion only, of course)
> 3. New/delete will always be used in performance critical code but I think the point is that in general it's not a good practice.
There's zero runtime overhead to using std::unique_ptr - the compiler will inline the calls to delete you'd otherwise be writing by hand.
There's zero runtime overhead to using std::unique_ptr - the compiler will inline the calls to delete you'd otherwise be writing by hand.
To speak to point 2, of course this is possible but the time it takes to do a GC is not determinable.
As for point 3, just because it's in use, doesn't mean it's correct. With the introduction of unique_ptr, most uses of new and delete can and should be factored out.
As for point 3, just because it's in use, doesn't mean it's correct. With the introduction of unique_ptr, most uses of new and delete can and should be factored out.
Can you give an example of any codebase not using any new or delete at all that compares in size?
"Right or Wrong" are irrelevant in the face of "Practical or Not".
The fact that all large pieces of serious code use new and delete would either imply that the author is smarter than all the people writing that code combined, or (more likely) he did not consider something w.r.t. the practicality of not using them.
Let me go further and explain my original post in a more succinct fashion:
One giant [[citation needed]] on every claim in this article, including, but not limited to, new and delete being useless.
"Right or Wrong" are irrelevant in the face of "Practical or Not".
The fact that all large pieces of serious code use new and delete would either imply that the author is smarter than all the people writing that code combined, or (more likely) he did not consider something w.r.t. the practicality of not using them.
Let me go further and explain my original post in a more succinct fashion:
One giant [[citation needed]] on every claim in this article, including, but not limited to, new and delete being useless.
No but it is the trajectory of the future and it's very practical. I'm not saying there aren't oddball cases that will require new and delete, but for the most part, it simply isn't necessary.
As for the citation, if you are immersed in the C++ community in general (going native, c++ now, subreddits, irc, accu meetings, etc), it's the general feeling.
As for the citation, if you are immersed in the C++ community in general (going native, c++ now, subreddits, irc, accu meetings, etc), it's the general feeling.
In modern C++, using new or delete in your code is wrong. It's not done. Nobody writes code like that anymore in C++.
It's been quite a while since I wrote any significant C++ code, but this statement seems wrong. Is this really "state of the art" for C++?
It's been quite a while since I wrote any significant C++ code, but this statement seems wrong. Is this really "state of the art" for C++?
Professional C++ coder here.
Seeing new and delete has very heavy code smell and can be avoided 99% of the time.
Seeing new and delete has very heavy code smell and can be avoided 99% of the time.
What have you done to your language that the native syntax for creating and deleting objects is a code smell?!
Included an alternative to new/delete's form of allocation that covers a good range of its use cases and is less prone to screwup.
Recognized that the average programmer can't reliably handle the tool?
They are the primitive functions for making and destroying objects on the heap which requires more care than construction and destruction on the stack.
In practice, no. People still write new and delete all the time in large C++ codebases (LLVM, Gecko, WebKit, etc. etc.)
unique_ptr is gaining traction, of course.
unique_ptr is gaining traction, of course.
You can get surprisingly far without using new or delete. std::vector, std::list and std::string are good replacements for many uses, you can of course create objects on the stack, and if your objects are stateless then they can maybe be const globals - and that can often save you a big pile of bother.
Though while new and delete are best avoided where possible, it's hardly the end of the world if you do use them. And my experience has always been that you're better off just using them, if the alternative is heavy use of smart pointers.
As member variables, smart pointers are tolerable, if copied to an ordinary pointer before heavy use; as locals or parameters, they're almost always best avoided. Over the years I've have had far more annoyance from painful single stepping, spitefully poor unoptimised performance and inconvenient watch window behaviour than I have ever had from just picking out all the memory leaks after the fact. (Which, if the code is written relatively tastefully, is usually pretty straightforward. And unless your colleagues are actively being dicks, I've always found there aren't too many to get rid of anyway.)
Though while new and delete are best avoided where possible, it's hardly the end of the world if you do use them. And my experience has always been that you're better off just using them, if the alternative is heavy use of smart pointers.
As member variables, smart pointers are tolerable, if copied to an ordinary pointer before heavy use; as locals or parameters, they're almost always best avoided. Over the years I've have had far more annoyance from painful single stepping, spitefully poor unoptimised performance and inconvenient watch window behaviour than I have ever had from just picking out all the memory leaks after the fact. (Which, if the code is written relatively tastefully, is usually pretty straightforward. And unless your colleagues are actively being dicks, I've always found there aren't too many to get rid of anyway.)
Why use new/delete when you have make_shared and make_unique?
Like 99.99999999% of the time you can use those. Like the only situation where I think they might be not enough is for some weird uses of placement new.
Like 99.99999999% of the time you can use those. Like the only situation where I think they might be not enough is for some weird uses of placement new.
I don't develop C++ professionally or anything, but it's my understanding that a lot of people agree that unique_ptr's and shared_ptr's are the way to go these days.
It depends a lot on the framework, but you can avoid almost 100% of new and delete on code you have control.
As someone who's not interested in following every acronym and resource allocation strategy there is... is this even remotely useful? Lately I've gotten back into Java for Android, and after a very long time with Python, it's the first exposure in over a decade I've had to this argument...
...which, for some of us, isn't an argument, as we have basically no choice in the matter. But I'm still interested to know whether this is actually useful input or whether it's more holier-than-thou posturing.
To me, this is missing the forest for the trees. It's easy to argue about language implementation semantics when, in practice, it means almost nothing to anyone as we're stuck with the idiosyncrasies of the platforms we work on, even when we choose the platform.
I guess it's good that someone is looking at these things, but I can't see the utility in it. Best case scenario, this becomes a paradigm shift in new languages (which doesn't help us or anyone else for years) or gets implemented in the next major revision of language X (which doesn't go mainstream for years).
...which, for some of us, isn't an argument, as we have basically no choice in the matter. But I'm still interested to know whether this is actually useful input or whether it's more holier-than-thou posturing.
To me, this is missing the forest for the trees. It's easy to argue about language implementation semantics when, in practice, it means almost nothing to anyone as we're stuck with the idiosyncrasies of the platforms we work on, even when we choose the platform.
I guess it's good that someone is looking at these things, but I can't see the utility in it. Best case scenario, this becomes a paradigm shift in new languages (which doesn't help us or anyone else for years) or gets implemented in the next major revision of language X (which doesn't go mainstream for years).
I disagree. I believe even if you're stuck with a certain situation, it's important to know whether the status quo is actually a good thing and you should work to keep it or if it's unavoidable for the moment but generally bad and you should do your best to move away from it if you can.
As someone who recently transitioned from C to C++ programming with RAII is an incredibly useful tool. In addition to making resource management easier when done properly it helps clarify your code, well worth the minor amount of time it takes to implement IMO.
This is totally on point. Ref-counting / RAII is the only sane way to do resource management. It's super lightweight and easy to understand.
The vast majority of resources are short-lived and don't create cycles. Our garbage collections "systems" should be designed for this case.
Cycles are a special case required for few data structures. They are not the norm and we shouldn't ship a huge heaping mess of a garbage collection system and make everything else slower to account for this rarely used special case.
Anyway people programming today shouldn't be thinking in terms of pointers and references. We should be thinking in terms of VALUES. Finite values have no cycles! The Haskell and C++ community have already embraced this, everyone else is still catching up.
Yet another reason why Java is a horrible language holding people back and the JVM is basically a hamster wheel keeping itself busy.
The vast majority of resources are short-lived and don't create cycles. Our garbage collections "systems" should be designed for this case.
Cycles are a special case required for few data structures. They are not the norm and we shouldn't ship a huge heaping mess of a garbage collection system and make everything else slower to account for this rarely used special case.
Anyway people programming today shouldn't be thinking in terms of pointers and references. We should be thinking in terms of VALUES. Finite values have no cycles! The Haskell and C++ community have already embraced this, everyone else is still catching up.
Yet another reason why Java is a horrible language holding people back and the JVM is basically a hamster wheel keeping itself busy.
> The vast majority of resources are short-lived and don't create cycles. Our garbage collections "systems" should be designed for this case.
Many modern GC systems are tuned for exactly this. It often is called generational garbage collection and the youngest generation is tuned to quickly collect these short-lived and non cyclic objects.
I used to work in this field so I've got at least a decent grasp of what modern GC's do and don't do well:)
Many modern GC systems are tuned for exactly this. It often is called generational garbage collection and the youngest generation is tuned to quickly collect these short-lived and non cyclic objects.
I used to work in this field so I've got at least a decent grasp of what modern GC's do and don't do well:)
My point is that, what GCs do at runtime (discover garbage) can be done statically in all of these cases. The sole reasons GCs do that work at runtime is because of cycles.
Cycles aren't common at all and the answer shouldn't be "let's create a huge complex GC that handles all cases, then down the road we'll optimize for the common case" the answer should be "let's do the sane reasonable thing that handles the common case and push the problem of cycle-management to the programmer"
Cycles aren't common at all and the answer shouldn't be "let's create a huge complex GC that handles all cases, then down the road we'll optimize for the common case" the answer should be "let's do the sane reasonable thing that handles the common case and push the problem of cycle-management to the programmer"
Someone mentioned returning a closure from a function. That's something that is done all the time in higher-level languages and hard to do without a GC.
Also, in general GC's are much faster than reference counting (especially when the reference count updates needs to be thread-safe), so the only reason one would use them is to have deterministic object destructions. These aren't common at all and should not be the deciding factor when choosing a memory management scheme.
Also, in general GC's are much faster than reference counting (especially when the reference count updates needs to be thread-safe), so the only reason one would use them is to have deterministic object destructions. These aren't common at all and should not be the deciding factor when choosing a memory management scheme.
RAII is great, and should be used where appropriate. I'm not sure what it has to do with reference counting, though. Reference counting is just a particularly slow and unreliable form of garbage collection; I don't see why you would ever prefer it to a proper garbage collector.
Tracing and Refcounting are each others duals,
www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf
www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf
Because it is deterministic? (i'm just guessing that what you call "proper" garbage collector is non-deterministic).
Furthermore, the only "advantage" I see in garbage collectors is that they can deal with cycles.
I say "advantage" because i'm of the strong opinion that having a cycle in your code is a software design error.
Furthermore, the only "advantage" I see in garbage collectors is that they can deal with cycles.
I say "advantage" because i'm of the strong opinion that having a cycle in your code is a software design error.
Say you are implementing a self-tracking objects model for data management. How do you fix the reversal of control required to manage that? Specifically you need to go from the representative object to the controller to store the fact that you changed.
Could you elaborate?
Entity Framework, when you modify an object it stores in a central location what the change was to be written out to a location latter.
It is performance wise infeasible to avoid that circular reference because it is very easy to pull back a lot of data from entity framework and change none of it.
It is performance wise infeasible to avoid that circular reference because it is very easy to pull back a lot of data from entity framework and change none of it.
Classic RAII in C++ is a limited form of ref-counting (only one ref).
I have to disagree with your second statement, ref-counting is extremely fast. If you consider it a GC then it's the fastest GC. It's also deterministic and does not pause.
I have to disagree with your second statement, ref-counting is extremely fast. If you consider it a GC then it's the fastest GC. It's also deterministic and does not pause.
> If you consider it a GC then it's the fastest GC. It's also deterministic and does not pause.
No, it's not, not unless you use a lot of cleverness. "We find that an existing modern implementation of reference counting has an average 30% overhead compared to tracing…" (They did perform a lot of optimizations to get it up to speed with tracing garbage collection... however, these are far beyond what shared_ptr does.)
http://users.cecs.anu.edu.au/~steveb/downloads/pdf/rc-ismm-2...
No, it's not, not unless you use a lot of cleverness. "We find that an existing modern implementation of reference counting has an average 30% overhead compared to tracing…" (They did perform a lot of optimizations to get it up to speed with tracing garbage collection... however, these are far beyond what shared_ptr does.)
http://users.cecs.anu.edu.au/~steveb/downloads/pdf/rc-ismm-2...
I'm a bit skeptical of the results of that paper without the seeing the source code and in what contexts they are performing the comparison. One can always find situations where one scheme is faster than the other but I'm not totally sure if micro benchmarks are representative of the real world. In long-lived servers, ref-counting can be preferable because it avoids random pauses. Maybe it's a latency vs throughput performance dichotomy. But yeah, thanks for posting that.
Reference counting doubles the number of memory access - you have to update the reference and the counter every time. That is a big performance hit. Reference counting may randomly halt your code, too, because you never know when you hit zero and the resource gets freed.
And you don't know how many resources will be freed when you drop the last pointer to that giant tree structure.
Of course, you could queue up and lazily delete the resources, but then you're back to nondeterministic behavior.
Of course, you could queue up and lazily delete the resources, but then you're back to nondeterministic behavior.
Two extra memory accesses plus whatever overhead for you have for locking if you are multi-threaded? That's pretty much the opposite of fast.
With refcounting you have:
With refcounting you have:
- Slow memory allocations (need to manage a fragmented heap)
- Slow accesses and pointer handovers (updates to the refcounter)
- Slow free (need to manage the free list)
- No asynchronous pauses (since there is no garbage collector)
- Fast allocations (usually just an "add" instruction since the heap is not fragmented)
- Zero cost accesses and pointer handovers
- Zero cost free (just stop using the pointer)
- Some asynchronous pauses and CPU usage while running the GC
I think in multi-threaded code ref-counting usually uses atomic_fetch_add instructions. This results in a memory barrier and is much more expensive that you might think.
When was this written? It seems to be at least half a decade out of date. Certainly nothing it espouses is actually new...
Indeed. The "garbage collection" described seems to have been state-of-the-art in the late '80's. And, of course, it's compared to features that weren't officially added to C++ until 2011.
Yes, garbage collection is inappropriate for things with finalizers---for resources other than memory. Other than that, I can't see anything useful here.
Yes, garbage collection is inappropriate for things with finalizers---for resources other than memory. Other than that, I can't see anything useful here.
Returning closures from functions without massive copying and/or massive headache seems to pretty well demand a GC.
I skim read the article, but I think the author is absolutely right, only for those Resource specific instances he pointed out that need to to have an explicit lifetime.
For everything else, there is garbage collection.
For everything else, there is garbage collection.
Isn't it simply a form of garbage collection? Instead of garbage collecting all the unused objects at random moments, an object is garbage collected as soon as it goes out of scope.
The way I understand it, no garbage collection means you take care of cleaning after yourself, whereas garbage collectors do it for you. It sounds like what he calls resource acquisition.
The way I understand it, no garbage collection means you take care of cleaning after yourself, whereas garbage collectors do it for you. It sounds like what he calls resource acquisition.
No. I think cleaning up, manually or automatically, after objects go out of scope is not the same as garbage collecting. "Garbage" here implies objects that linger beyond their usage scope, from construction to destruction, and now have become garbage taking up memory that can only be reclaimed by an extraneous routine, ie the GC.
C++ has wider options managing resource acquisition. Scope is just one case.
https://en.wikipedia.org/wiki/Smart_pointer#C.2B.2B_smart_po...
https://en.wikipedia.org/wiki/Smart_pointer#C.2B.2B_smart_po...
Garbage collection is not a synonym for automatic memory management.
I surely prefer RAII to any garbage collection. It doesn't mean it's completely wrong though and has no uses at all. It's just of limited usefulness that's why languages which overuse it claiming it's always needed (like Java) are too limiting. If anything, GC should be optional, not mandatory.
Well... if C and (early) C++ showed us anything, it's that programmers aren't very good at managing memory. (It's not just leaking memory. Accessing deleted memory is much worse.)
So, what are you going to do? Just say "Most programmers are lousy, deal with it"? Introduce garbage collection, which solves 90% of the problem (memory) with no programmer intervention, but does nothing whatsoever to help the other 10% of cases (files, sockets, mutexes, etc.)? Rely on RAII, which in turn relies on programmer education and discipline? Or do you have another alternative?
Optional GC could be interesting - maybe some kind of a switch that you set at compile time that says "this program uses GC" or "this program uses destructors". But then you're essentially talking about two similar, but different languages (like, say, Java and C++).
So, what are you going to do? Just say "Most programmers are lousy, deal with it"? Introduce garbage collection, which solves 90% of the problem (memory) with no programmer intervention, but does nothing whatsoever to help the other 10% of cases (files, sockets, mutexes, etc.)? Rely on RAII, which in turn relies on programmer education and discipline? Or do you have another alternative?
Optional GC could be interesting - maybe some kind of a switch that you set at compile time that says "this program uses GC" or "this program uses destructors". But then you're essentially talking about two similar, but different languages (like, say, Java and C++).
You are right, in case of C++ the language doesn't ensure safety because of RAII since one can always go back to manual new / delete and etc. But in newer languages this can be avoided.
Rust actually does that, and GC there is optional by the way.
Rust actually does that, and GC there is optional by the way.
Worth a mention: In Objective-C with ARC, the compiler treats every pointer to an Obj-C object as a std::shared_ptr or std::unique_ptr (static analysis is used to optimize out unnecessary reference counting), unless it's marked otherwise with keywords such as __weak, __unsafe_unretained, etc.
GC is not 'wrong'. It's just an overused method of memory management. There are plenty of valid uses for GC where ref counting wouldn't make sense. Lua immediately comes to mind.
I think the author's core issue is that in most cases GC aren't optional.
An optional opt-out would invite a wider range of developers.
An optional opt-out would invite a wider range of developers.
> Don't believe me? Then don't skim-read.
My hero.
My hero.
Yup, some people think they can teach others as soon as their first C++ program compiles without errors.
What's the catch?
You can run out of space on the stack, which has a smaller size than the heap, where new'd objects are placed. This can easily happen with large objects that own other large objects and it is difficult to debug without knowledge of the implementation of all of the child objects.
That's too strong of a critique. You can have just a handle on the stack, with the data on the heap. When the destructor of the handle is executed, it deallocates the data on the heap. This is what almost all resource holding library or user-defined types do in C++.
Sure, but at that point, it's not RAII all the way down. RAII is a great wrapper around new and delete, but I saw people talking about how they rarely use new and delete anymore.
Edit: Actually, reading about auto_ptr<> and friends I see what you're getting at. The codebase I worked on some years ago didn't use those so I'm not totally familiar with that idiom for wrapping heap allocation.
Edit: Actually, reading about auto_ptr<> and friends I see what you're getting at. The codebase I worked on some years ago didn't use those so I'm not totally familiar with that idiom for wrapping heap allocation.
1-