Thread: Meego vs Android apps (C or Java?)
View Single Post
Capt'n Corrupt's Avatar
Capt'n Corrupt is offline Capt'n Corrupt
2011-06-16 , 17:28
Posts: 3,524 | Thanked: 2,958 times | Joined on Oct 2007 @ Delta Quadrant
#206
Originally Posted by tpd View Post
"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.