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?

Improve this question
3
  • 1
    Look at cocos2dx how they do it. cocos2d-x.org/wiki/… Commented Nov 7, 2014 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. Commented Nov 7, 2014 at 18:36
  • 1
    @Cole that is exactly what an auto release pool is there for to avoid. Commented Mar 2, 2020 at 8:46

4 Answers 4

Reset to default
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.

Improve this answer
2
  • 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. Commented Nov 2, 2014 at 11:46
  • There’s usually just two operations: Retain an item and add it to the list (may happen multiple times), and release all items in the list and destroy the list. Commented Mar 3, 2020 at 9:12
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.

Improve this answer
2
  • I see, it violates the rules of reference counting, but it does solve the problem. Commented Nov 2, 2014 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 Commented Nov 2, 2014 at 11:32
0

You reduce the impact of autorelease from two sides: From the implementation side, and from the use side.

From the use side, it is very efficient to create auto-release pools and close them down very quickly. You just shouldn’t have a loop that creates 1 million autoreleased objects before releasing them. Don’t do it. The biggest reason is that you may have a million objects wasting memory that could have been released.

On the implementation side there are plenty of tricks possible. One not mentioned is to use a different implementation for objects that may be autoreleased multiple time by using a hash table based on the object pointer, and not doing retain+add to pool if an instance is already in the autorelease pool.

Improve this answer
0

The way that Objective C does is this pretty interesting, when you call autorelease(), that function examines the code at the calling site to see if the caller is calling retain().

If the caller is calling retain(), autorelease() doesn't have to change the reference count or add the object to the autorelease pool at all, it just needs to set a per-thread flag that retain() can check and make itself a no-op as well.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.