What are some examples of algorithms and/or data structures are difficult or impossible to implement correctly without garbage collection?

I've heard it mentioned in very general terms that such things exist开发者_JS百科, but the details are rarely discussed. What are your favourites? What makes it difficult?

The standard implementation of many lock-free structures like a concurrent hash table often are nearly impossible to write without a garbage collector. These structures work by storing long linked lists of elements, then changing the heads of the lists whenever a new value is added or removed. That way, one thread can make a change to the structure so that new threads see the change (they traverse a new linked list) while older threads continue reading older linked lists. It's crucial that the memory be reclaimed by a garbage collector, since otherwise the thread that changed the linked list would have to somehow clean up the list it just replaced, but that list is in use by other threads, this either leads to data races or requires the use of locks, both of which are bad.

A similar argument can be made for multithreaded lock free binary search trees, which use a related trick.

Anything is possible without GC, because computer hardware works without GC and it computes all algorithms. :-) But sometimes it is easier to implement a local GC and use it instead of writing a huge complicated code to do the same without GC. In real-world scenarions, algorithms using GC are often much simpler than their non-GC counterparts.

Anything which generates a lot of temporal data/variables is a big problem (i.e. difficult, not technically impossible) without some sort of garbage collection. For example imagine a web server with php or asp.net support where the engine of php/c# scripts has no garbage collection. Each web request from a browser creates a lot of temporal data on web server and if you had just a small memory leak in a script on server, the whole web server ends in a horrible death...

I mean if many people put scripts or plugins to server, there can be memory leaks. These scenarios require some sort of garbage collection.

Also LINQ in C# creates a lot of temporal objects. It would be paint to use it without garbage collection.

I conjecture that you mean concurrent data structures. If so, a lot of lockfree algorithms require Garbage Collection (or deferred/safe memory reclamation). And the most simplest example is classical lock-free stack: [search Wikipedia by "ABA problem" - the site prohibits me from posting the link] (ABA and safe memory reclamation are closely related problems, if you solve the latter than you solve the former too) Is it impossible to implement them without GC? No, it's not impossible. However, it's definitely more difficult. One solutions is to implement limited form of GC. For example, strongly thread-safe reference counting: http://www.1024cores.net/home/lock-free-algorithms/object-life-time-management/differential-reference-counting Another solution is to design an algorithm around the requirement, so that it just does not require a GC. For example, some lockfree producer-consumer queues (most notable the M&S queue) do require a GC. And here is a simple an efficient queue algorithm that is especially designed around GC requirement: http://www.1024cores.net/home/lock-free-algorithms/queues/non-intrusive-mpsc-node-based-queue

var v = FunctionThatAllocatesMemory2(FunctionThatAllocatesMemory1());

Without GC there is no way to deallocate the memory returned by FunctionThatAllocatesMemory1().