I\'m experimenting a bit in C and I\'m trying to implement my own Reference Coun

Question

I'm experimenting a bit in C and I'm trying to implement my own Reference Counting System. I've mainly worked with Objective-C in the past but AFAIK autoreleasing objects is something that is unique to Objective-C.

The problem with reference counting is that, when returning objects from methods, there is no correct way to release the object and return it at the same time. If the reference count is 1 releasing it will deallocate the object before it can be returned.

void *testMethod() {
   return release(object); // Object is already deallocated :'(
}
Therefore, by autoreleasing an object, it is not deallocated instantly. Instead, when the autorelease pool is drained, all the objects that were autorelease in the scope of the autorelease pool get released.

void *testMethod() {
   return autorelease(object);
}

@autorelease {
    object = retain(testMethod());
}
As you can see above, the object gets released when the @autorelease {} block ends, which is after the object has been retained again. This solves the problem.

This solution however can become quite a bottleneck. You have to store every object that gets autoreleased in an array with no predeterminable size, requiring you to realloc a lot of times. Loops that require an autorelease pool have become much slower because of this.

Is there a better solution to this problem?
Or rather, are there any other solutions to this problem at all?

Explanation / Answer

Arrays aren't the only option for implementing autorelease pools. Anything suitable for a set implementation should be suitable for an autorelease pool, including (single- or double-linked) lists, trees, and hash tables. When picking which data structure to use, consider the timing of the various operations and match that to usage.

For an autorelease pool, insertion is a commonly used operation, as is removing recently added items (which is the scenario in question: retaining autoreleased objects). Draining the pool will at a minimum be O(n) for iteration, which should be supportable by any data type (though possibly at an O(n) space cost overall for an extra pointer per record to the next item in the sequence).

Linked lists support insertion & head removal in O(1) time, though removing arbitrary items from a pool also happens relatively frequently, and is O(n) for linked list.
Trees can support insertion & removal in O(log n) time, but iteration is O(n log n) without "next item" pointers.
Operations on hash tables vary from O(1) to O(n), depending on the hash function and the specific data stored in it.
For arrays, best case for insertion is O(1); you only hit the O(n + f(m)) worst-case when the array would overflow, where n is the old array size, m the new array size and f(m) the complexity of allocation. You can reduce the overall timing for insertion by using a dynamic array (doubling the array size on overflow) for an O(1) amortized cost (assuming f(m) ? m). However, there's a time-space tradeoff: a portion of the array is allocated but unused. Removing recent items is O(1), though removal is O(n) in general.
You can potentially get further performance gains (at a space cost) by defining a top-level class that all other classes descend from (your own analog to NSObject), and include a pointer to the object's record in the autorelease pool. Using this pointer, searching takes O(1) time, which can reduce removal complexity if searching is the dominant operation during removal (such as for linked lists).

If you declare the object's record pointer as the same type as the autorelease pool's record type, you'll create a tight coupling between objects and memory management, which is undesirable. Instead, you can apply the bridge pattern (aka the Handle-Body idiom in C++ circles): have a abstract memory management strategy class that ties together a family of abstract memory management types (including a type for memory management records and for memory pools), with the object's record pointer of the abstract record type. The strategy would include a stack of AR pools. You could then define concrete autorelease pool and record types for whichever strategies you want. You'd have a static pointer to a memory management strategy, which the basic memory management functions (retain(), release(), autorelease() and pool() (to push a new AR pool)) would reference.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.