4

I was reading about the fact that LLVM v3 uses a static analysis of the code to implement a sort of automatic garbage collection that is prepared and done during compilation.

If the compiler statically inserts retains and releases then no runtime component for garbage collection is needed anymore or what?

Is this true? Will it work as a replacement of normal garbage collection either on iOS and OS X development? It is not clear what will happen..

Should we rely this kind of "static garbage collection"?

Barry Wark
  • 107,306
  • 24
  • 181
  • 206
Jack
  • 131,802
  • 30
  • 241
  • 343
  • While this was closed because of when it was asked, my answer [here](http://stackoverflow.com/questions/6260256/what-kind-of-leaks-does-objective-cs-automatic-reference-counting-in-xcode-4-2/6388601#6388601) talks a little about the differences between ARC in LLVM 3.0 and garbage collection. See also Chris Lattner's message [here](http://lists.apple.com/archives/objc-language/2011/Jun/msg00013.html) about the subject. – Brad Larson Jun 20 '11 at 22:02

3 Answers3

4

This is an interesting question: can a static analyzer implement a complete garbage collection system?

The answer, it appears, would be no. The only way to implement garbage collection is knowing that an allocated piece of memory (e.g. an object instance) is no longer useable. In a runtime GC, this knowledge is gained by (effectively) scanning the stack and heap. Doing this at compile time would require analyzing all possible code paths through the system to determine where in its execution a particular allocation would no longer be reachable. This is equivalent to the halting problem. However, LLVM claims to support at least a limited form of automatic reference counting (inserting retain/releases) for you. See http://developer.apple.com/technologies/ios5/. I suspect that what LLVM is doing is not a full GC, it's using the static analyzer to find when all references to an object go out of scope, and inserting appropriate retain/releases for you. The reference counting happens at run time, just as before. I highly doubt that it will do automatic free-ing of malloc'd blocks for you.

If it works as advertised on the public site above, I'd say use it.

Barry Wark
  • 107,306
  • 24
  • 181
  • 206
  • It is certainly possible, at least partially; See http://en.wikipedia.org/wiki/Region-based_memory_management – SK-logic Jun 09 '11 at 13:34
1

If the compiler statically inserts retains and releases then no runtime component for garbage collection is needed anymore or what?

ARC stands for "Automatic Reference Counting" and, therefore, resorts to reference counting (RC) in general. RC is one of the oldest forms of garbage collection dating back to 1960 and is rarely used in practice because it is very slow, incurs unbounded pauses and is inaccurate because it leaks cycles.

RC is slow because reference counts are incremented and decremented every time you handle a reference to an object (e.g. read a reference from the heap or write one into the heap) and thread safe reference counting must adjust counts using atomic increment and decrement operations. Naive reference counting (e.g. shared_ptr in C++) is ~10x slower than tracing garbage collection. ARC uses static analysis to remove some of these counter increments and decrements which will improve performance but I am not aware of any benchmarks and I seriously doubt the result is competitively performant when compared to, for example, the JVM or CLR (both of which ditched reference counting long ago because they found tracing garbage collection to be a lot faster and more accurate).

J D
  • 48,105
  • 13
  • 171
  • 274
0

What you heard is right. See "Automatic Reference Counting" at http://developer.apple.com/technologies/ios5/. If you are a registered developer, you can read much more about ARC in the "What's New" documents recently released (under NDA).

Graham Perks
  • 23,007
  • 8
  • 61
  • 83