Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Garbage Collection is Wrong

lb-stuff.com

Post reply on HN
Print view View original

71–80 of 111 posts

Re: Garbage Collection is Wrong

#71

Post by agwa »

rian wrote: post #45
dmitrygr wrote: post #14

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. 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…

> 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.

Re: Garbage Collection is Wrong

#72

Post by dllthomas »

ori_b wrote: post #35
letzjuc wrote: post #32

Earlier quoted context omitted.

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 tha…

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 co…

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

#73

Post by danbruc »

letzjuc wrote: post #51
ori_b wrote: post #35

Earlier quoted context omitted.

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 co…

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.

Re: Garbage Collection is Wrong

#74

Post by sanderjd »

danbruc wrote: post #7

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 ke…

> 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

#75

Post by dalke »

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."),

Re: Garbage Collection is Wrong

#76

Post by letzjuc »

mikeash wrote: post #62
letzjuc wrote: post #51

Earlier quoted context omitted.

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).

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.

Re: Garbage Collection is Wrong

#78

Post by rian »

pcwalton wrote: post #31
rian wrote: post #26

Earlier quoted context omitted.

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.

> 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.)…

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.

Re: Garbage Collection is Wrong

#79

Post by letzjuc »

mikeash wrote: post #66
letzjuc wrote: post #61

Earlier quoted context omitted.

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?

Re: Garbage Collection is Wrong

#80

Post by rian »

danbruc wrote: post #65
rian wrote: post #55

Earlier quoted context omitted.

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…

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