7

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?

  • 1
    Look at cocos2dx how they do it. cocos2d-x.org/wiki/… – Dawid Drozd Nov 7 '14 at 7:14
  • You could make your method similar to a "create" method where it is the caller's job to release the object. The callee "retains" implicitly on "alloc", and the caller "releases" when it's done. – Cole Johnson Nov 7 '14 at 18:36
4

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.

  • Note: in a doubly-linked list, removing an element is O(1), it's the finding of the element to be removed that's O(n). However, if you can somehow figure that out via other means (e.g. because of the way your algorithm is structured, you already have a reference to the element at that point), then removal is very efficient. That's why insertion-ordered maps have no asymptotic overhead compared to unordered maps: yes, you need a list to keep track of insertion order, but you never need to search in that list, because you can look the keys up in the map. – Jörg W Mittag Nov 2 '14 at 11:46
1

The usual way is to retain for the calling code, To make it consistent you should do it for all objects that you return.

//popFromQueue will remove from the queue and pass the buck to the calling code
Foo* pop(FooQueue* q){
    Node* foo = q.head;
    q->head = foo->next;
    foo->next=null;//make sure new head isn't released; could have also retain the new head instead
    Foo retValue = retain(foo->value);
    release(foo);//will release next and value
    return retValue; //passes our ownership to calling code
}
// peekQueue will return the head value and give ownership to calling code
Foo* peek(FooQueue q){
    return retain(q->head->value);//add a retain and pass to calling code
}

For example when you create an object: Foo* foo = createFoo(); it already has been retained once to let the calling code get ownership.

This has the downside that all returned values need to be released and you need to ensure they have been retianed before returning them.

  • I see, it violates the rules of reference counting, but it does solve the problem. – NSAddict Nov 2 '14 at 8:10
  • @NSAddict well unless you have actual RAII language support (where destruction happens after the copy to the callers variable) then that is a decent second choice – ratchet freak Nov 2 '14 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.