@topic:

Meego and Qt/C

Another benefit to the GC scheme I previously mentioned is that the GC would be free to collect on a separate de-prioritized thread.

Currently (according to the aforementioned post), the GC must analyse a runtime object hierarchy which means that it must freeze the thread whilst running. This would degrade performance terribly. By analyzing de-allocation when it happens, the GC wouldn't need to interfere with a running system at all and could be run completely separate and with a minimum priority!

Not only is it trivial to detect inaccessible objects (O(1)), but it is also less disruptive to freeing them for future allocation. Everyone wins.

Taken a step further: compile time optimization could isolate objects that are short-lived. This would apply to objects that used only momentarily in a method or loop block, and spare these from GC altogether (eg. parameters, counters, etc).

I'm probably missing something obvious, or if not, am scratching my head as to why GC isn't handled this way.

This site points out a problem that I had not considered with the reference counting scheme. If you have a pair of objects referencing each other, but inaccessible to the root tree they will never be de-allocated, and thus the memory is as good as leaked:
http://www.morefor.org/documentation/gc.html

This is a very serious problem. But is there a simple solution to this? Sure.

I refer to these pockets of circular referencing objects as bubbles.

This 'bubble' of references inaccessible to the root tree can be determined quite readily if we know all points of connection to the root tree, and upon de-allocation, we traverse the bubble to decrease the root-count of the 'child' objects. The trick is to know all of the objects during the search so that decrementing the reference count excludes objects in the bubble pointing to one another! Once this count reaches zero, we know with certainty that the object is inaccessible regardless if it's part of a bubble!

After that, it's simple counting and traversal, and requires no pause of a running system as this can be done asynchronously with the program on a de-prioritized thread, just so long as you maintain a stack of to-be-dealt-with de-allocations and a single Garbage Collector is in operation. There is no need to suspend the application for clean-up.

This works.

This is slightly different than simple reference counting, and requires a slightly more complex allocation/de-allocation procedure and additional object storage. However, the cost is still quite minimal, and with the right structure, and would save copious amounts of runtime performing the GC by eliminating the need for a periodic traversal of the root tree (mark-sweep).

Memory fragmentation is another problem. The only thing I can think of at the moment is to maintain a 'doubly linked list' of objects and their referrers, so that object re-location can have all referrer object references updated. Since we have a structure of the object tree, this should be easy. Also, the use of a temporary virtual address at the old object offset can stand in for the object until all referrer's references have been mended (can this be accomplished without a test?). This eliminates the need to pause operations during a relocation!

I just learned that CPython uses references for its GC implementation but uses Cycle protection to ensure that these 'bubbles' can be detected.
SOURCE: http://docs.python.org/release/2.5.2/ext/refcounts.html

Goat! I love computer science!

"the GC sweep can be O(1) rather than O(N) especially for persistent data structures"

O(1) for each dealloction

root->1st->2nd->3rd->....nth removing the link between root and 1st is still an O(n) operation

take into account all the atomic increments and decrements (I think Arm may not be that great for this) going on with normal code usage the win over a generation GC is not necessarily as obvious as things would first appear

In the first scheme it would be O(1) in that it would be a reference decrease, and if say a linked list were used (check on each de-allocation) and a single insertion into the front of a cleanup list. There would be no need to traverse the nodes to search for the elements that required final de-allocation. But this scheme is still vulnerable to circular dependent references.

The second scheme (the latest post -- detecting bubbles) has different timings and is certainly not O(1) as you point out.

I am programming in C for 10 years, and before that in various ASM languages for another 8 years or so. And I never understood the concept of GC. I mean, why invent something so awkward and resource consuming, instead of.. I don't know, free your unused memory? Is it THAT hard?

Not hard or rocket science, but can get... tricky The issue is of course keeping track of ownership, circular references and such.

I think it's a productivity thing. It takes time to audit code or develop a style to minimize leakage. Apparently, many programmers are not good at such things.

It may be worth noting that the upcoming link seems seems to suggest that the Dalvik VM garbage collector may be fully able to a) run on a separate thread/core, and b) run concurrently with the application:

http://stackoverflow.com/questions/4...bage-collector

The Dalvik project is quite interesting, and I'm looking forward to seeing where it goes.

I would rather see that Dalvik became a generalized LLVM implementation (if it isn't already) and bytecode compiled to LLVM bitcode to open the floodgates for freedom for the developer to choose language without compromising architecture independence.

Currently Android's Renderscript (a C99 language) compiles to LLVM bitcode, and then is natively compiled on first-run/install and the resultant executable cached for future runs. This method is fast (native), portable (LLVM), and gives freedom to the developer to choose language. I would like to see this extend beyond renderscript to the general development platform.