Garbage Collection - Why?

Pages: 1234
Why is this a thing? Is manually deleting your memory really that hard to do? This is an honest question, not meant to flame. From my experience, deleting memory isn't very hard. I can't imagine needing to rely on GC of some sort.
Even if it's not hard it's still an issue. With GC you don't have to worry about it at all.
Check it out:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>

struct Whine {
    Whine() {std::clog << this << " constructed!\n";}
    ~Whine() {std::clog << this << " destroyed!\n";}
};

int main()
{
    Whine *pw = new Whine();

    throw "Oops";

    delete pw;
}


Of course, you needn't do this anymore in C++11.
You'd use smart pointers because it's the RAIIght thing to doTM.
The RAIIght way would be Whine pw;
I don't see what your example is meant to show. Why on earth would anyone ever do anything like that?
I think that it is meant to show that using raw pointers is a bad thing even if you are fastidious about your memory management.
Didn't you want an example of a hypothetical situation where a GC would help?
In C++, even with smart pointers and RAII, you still have to be concerned about memory management and ownership.

Take for example the dreaded/classic circular reference problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct A;

struct B
{
    std::shared_ptr<A> a;
};

struct A
{
    std::shared_ptr<B> b;
};

void leakMemory()
{
    std::shared_ptr<A> foo( new A );
    std::shared_ptr<B> bar( new B );

    foo.b = bar;
    bar.a = foo;
}  // memory leak!  despite use of smart pointers, neither foo nor bar get deleted
//  due to lingering references.  They both are owning each other so they never go
//  out of scope! 


GC languages do not have to worry about this, as the GC will still detect and remove objects no longer in use.


GC really does make memory management much simpler for the developer. Though, yes, it is not necessary.


EDIT: fixed a small problem with the example.
Last edited on
Ah I hadn't thought of the circular reference problem here. I guess that would be a situation where having some form of GC would be handy.
Circular reference problem is just one of the many problems you may face when writing concurrent lockless structures with manual memory management. A huge problem is that to get acceptable level of performance, you have to avoid mutations and promote sharing at the same time. And sharing is exactly the kind of a thing that manual memory management makes hard and error-prone (or slow in case of shared_ptr). Probably this is the reason C++ still doesn't have a single concurrent data structure in its standard library and all the third party ones I've seen were subtly broken (e.g. leaking memory sometimes or having ABA problems, etc.).

People write scientific papers about it: http://sysweb.cs.toronto.edu/publication_files/165/ipdps06.pdf


Though, yes, it is not necessary.


It is not necessary, but lack of it makes some things so hard that they can be safely regarded as "near-impossible". E.g. functional programming. That's why every functional language has a GC.
Last edited on
manually deleting and allocating memory via new/delete can cause memory fragmentations, thats why memory pools were invented, to wrap the heap and speed up allocation of memory that an application needs (knowing what you want beforehand). every time you call new/delete you make a call to the kernel. But then now with C+0 there is garbage collection now, am i right?
Last edited on
do you need to delete memory or you get a memory leak?
Probably this is the reason C++ still doesn't have a single concurrent data structure in its standard library and all the third party ones I've seen were subtly broken (e.g. leaking memory sometimes or having ABA problems, etc.).


That's because all concurrent data structures designed for general use are fundamentally broken. For any nontrivial use you always end up needing an external lock, making the internal synchronization completely pointless.

This is why the only concurrent data structure I ever really use is a queue. Even then, checking the size of the queue is not directly possible; the size check needs to be combined with the pop operation by either making it blocking or somehow returning an error code along with the object.

Garbage collection does help in certain systems where cyclical references are unavoidable, although these situations are not that common in practice (how often do you really want your objects to pop out of existence because the last reference disappeared?). I rarely use shared_ptr as it is, and this is not because of the circular reference problem.

Memory fragmentation is not the huge issue GC fans want you to think it is. While the worst case is infinitely inefficient, real fragmentation is limited to wasting a fairly small percentage of the memory in use. Garbage collected languages are known for having very large memory overhead per allocation, so this only becomes a threat when using lots of large allocations (which aren't likely to fragment significantly by themselves). This leaves the speed penalty caused by fragmentation, until you realize that garbage collection is also slow, and again, fragmentation is not that common.

It all boils down to one simple reason why so many languages have garbage collection: it looks slightly easier. They get to claim that their language is SO much easier to use because you don't have to manage the memory, but GC does not extend to resources other than memory. A correctly written class in C++ knows how to clean up all of its resources even if the client fails to call cleanup methods. Good luck implementing this behavior in garbage collected languages.

That's because all concurrent data structures designed for general use are fundamentally broken.


Nope. Things like concurrent lockless sets, hashmaps or queues are extremely useful.

For any nontrivial use you always end up needing an external lock, making the internal synchronization completely pointless


Not true. You seem not to know what concurrent structures are. Putting a lock on a standard vector is *not* making a concurrent structure. The point of having those structures is to avoid synchronization at all. There are no locks there. That's why they are called concurrent. Putting a global lock on a structure is no concurrency at all - it would serialize accesses and incur lots of context-switching, which is very inefficient.

Guys in MongoDB (C++) represented a similar mindset as you here - put a lock here and there and we are "concurrent". That's why MongoDB loses signifficantly in all benchmarks to Apache Cassandra (Java), which is probably the fastest production-level NoSQL available now.


real fragmentation is limited to wasting a fairly small percentage of the memory in use


... and that small percentage can vary from 2% to 1000% according to many studies. The problem with fragmentation is that it is somehow unpredictable. Usually it is below 20%, but 3x-10x overhead sometimes happen. And then you have a big problem. Much bigger than forgotten delete.

Another problem with fragmentation is it almost always prohibits returning memory back to the OS. You really have to free the whole memory page until it can go back to OS. GCs do not have this limitation, because they move objects around. Just make a simple experiment - allocate a million of small objects o the heap, then delete 95% of them randomly. Most of that memory won't be released to the OS.


It all boils down to one simple reason why so many languages have garbage collection: it looks slightly easier.


"slightly" as in the sentence - writing a game in C++ is "slightly" easier than in pure assembly - then I agree.
Last edited on
closed account (o1vk4iN6)
Putting a global lock on a structure is no concurrency at all - it would serialize accesses and incur lots of context-switching, which is very inefficient.


If you are talking about a server run by a company that can afford $$$$ but getting the size of a queue using O(n) is no where near as efficient as O(1) even if you cause a block somewhere in another thread (read: on an average system there wouldn't be that many threads) than if the queue was exceedingly large.

"slightly" as in the sentence - writing a game in C++ is "slightly" easier than in pure assembly - then I agree.


True, might even say that it's equally as difficult.
Why O(n)? I can easily write a lockless linked-list based queue with method for getting exact size O(1). Size needs to be tracked separately then.


True, might even say that it's equally as difficult.


And that's why almost everyone writes games in C++ and almost noone in assembly. :D


(read: on an average system there wouldn't be that many threads)


You don't know the numbers you are talking about. Gaining a contended lock on a beefy multiprocessor machine, can cost up to several microseconds. You may be easily wasting hundred of thousand CPU cycles per single lock (note, that if more threads are forced to wait, their wasted CPU cycles add up). In that time you could scan a linked list thousands elements long, without disturbing any other threads. So even a lockless O(n) solution can often outperform O(1) solutons as long as n is reasonable small - i.e. hundreds, not millions. And most queues are usually not longer than a few tens of elements - really. If you have longer queues, fix the architecture first...
Last edited on
closed account (o1vk4iN6)
I can easily write a lockless linked-list based queue with method for getting exact size O(1).


Go ahead.

noone in assembly


Not true.
I can easily write a lockless linked-list based queue with method for getting exact size O(1).


Go ahead.

I think he was referring to keeping track of size during operations.
rapidcoder wrote:
The point of having those structures is to avoid synchronization at all.

No, the point of lockfree and waitfree algorithms is to *have* synchronization between multiple threads, with certain provable guarantees about making progress. Whether they are faster or slower than lock-based algorithms depends on usage and platform (that article you linked correctly says "In some cases, lock-free
approaches can bring performance beneļ¬t")

rapidcoder wrote:
People write scientific papers about it:

People certainly do (e.g. there were some interesting ones about the time when lockfree n-ary trees were invented), but this is just a conference paper made by a CS student for his master's thesis, a fairly good one for something from 8 years ago, which makes a few good points (although it's wrong about DCAS, misses a few then-known algorithms, and uses sub-par setup for the tests). It isn't really relevant to the discussion on this thread either way, but if someone is curious to see it in the published form it was http://dx.doi.org/10.1016/j.jpdc.2007.04.010

rapidcoder wrote:
all the third party ones I've seen were subtly broken (e.g. leaking memory sometimes or having ABA problems, etc.).

What did you look at, forum posts? Either way, GC is not magic, it does the same things, only as an application writer, you have less control over it. It's easy to switch to another lockfree queue implementation in C++, but how many JVMs have multiple lockfree GCs to choose from?
GC is not always reliable for certain memory leeks, for exemple, in C#, you can cause a memory leak if you don't unsubscribe events when needed.
Pages: 1234