iDevGames Forums
removeAllObjects - Printable Version

+- iDevGames Forums (http://www.idevgames.com/forums)
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Programming Languages & Scripting (/forum-8.html)
+--- Thread: removeAllObjects (/thread-448.html)

Pages: 1 2


removeAllObjects - Madrayken - Jan 11, 2010 10:13 AM

I was going through a bunch of code I wrote over a year ago and my understanding of memory management was hazier than it is now when I came across this:

Code:
- (void) update
{
    NSMutableArray *kill_list = [[NSMutableArray alloc] init];

    for (CEffectGenerator *effect_generator in effectGeneratorArray )
    {
        if([effect_generator update] == NO) // This effect is dead
        {
            [kill_list addObject: effect_generator];
        }
    }
        
    [effectGeneratorArray removeObjectsInArray: kill_list];
    
    for (CEffectGenerator *effect_generator in kill_list)
    {
        [effect_generator release];
    }
    
    [kill_list removeAllObjects];    
    [kill_list release];
}

When I looked at it I thought: "Hmm... that segment there looks redundant:
Code:
    for (CEffectGenerator *effect_generator in kill_list)
    {
        [effect_generator release];
    }

I commented it out and checked to see if the CEffectGenerator objects were actually being released as one would expect.

To my horror, I noticed that dealloc was never called on my CEffectGenerator objects, despite all references to them (the original effectGeneratorArray and kill_list) now being empty.

I was under the impression that 'removeAllObjects' caused a retain count reduction and then a subsequent release if that object was not referenced anywhere else.

What have I misunderstood? As ever, all help gratefully and humbly received.


removeAllObjects - longjumper - Jan 11, 2010 10:36 AM

Code:
for (CEffectGenerator *effect_generator in kill_list)
    {
        [effect_generator release];
    }

is bad. Very bad. Retain counts are an implementation of ownership - it is helpful to stop thinking about the retain count itself and start thinking about ownership and object responsibility instead.

Let's think about the objects you have here:
1. The object that implements this update method. Let's call it "View".
2. All of the CEffectGenerators
3. The kill_list
4. The effectGeneratorArray

How are these objects related?
View owns effectGeneratorArray and kill_list.
effectGeneratorArrays owns many CEffectGenerators
kill_list may own some of the CEffectGenerators that effectGeneratorArrays also owns.

View doesn't own any CEffectGenerators. It is not View's responsibility to release any CEffectGenerators and therefore if it does (like this little snippet of code), bad things happen. The only owners of the CEffectGenerators are kill_list and effectGeneratorArray. They are the only objects that can send release to their contents because they have ownership. The rule, then, is never release an object you don't own.

Now, without that for loop that incorrectly releases the items in the kill_list, this code is correct. (The removeAllObjects is unneeded, a deallocated array will send release to all of its objects. But it isn't hurting anything.) Any CEffectGenerators that are ready to get squashed are owned by effectGeneratorArray, then by kill_list. When you removeObjectsInArray, they are only owned by kill_list. When invoke removeAllObjects (or release kill_list, prompting deallocation), they are released again and owned by nobody - therefore, deallocated.

My guess is that when you allocate a CEffectGenerator and add it to the effectGeneratorArray, you don't relinquish ownership from the object that actually created it. That code probably looks something like this:
Code:
CEffectGenerator *generator = [[CEffectGenerator alloc] init];
[effectGeneratorArray addObject:generator];

This leaves whatever object that this code was called in an owner of generator, but without a pointer to it. That's a leak. When you create your generators, you need to make sure that only effectGeneratorArray owns them.
Code:
CEffectGenerator *generator = [[CEffectGenerator alloc] init];
[effectGeneratorArray addObject:generator];
[generator release];



removeAllObjects - Madrayken - Jan 11, 2010 01:18 PM

Just for informational purposes, the owner of my effectGeneratorArray is CEffectGeneratorManager. It is this that has responsibility for creating and deleting objects from my effectGeneratorArray, and as such I'd always considered *that* to be the owner of the effectGenerators. From what you are saying, this is wrong-headed.

I come from a C and assembler background, so I've been trying to use alloc and release like malloc and free wherever possible. Kill lists have been my standard way to remove elements from an array that is being iterated over for some years.

If NSMutable array in the form of my effectGeneratorArray is seen as the primary owner, what do you suggest as an alternative? Everything else I can think of either relies on removing things from an iterated list ('ewww!') or creating another kill list (also, apparently 'ewwww!').

I must also say, thanks for writing me such a thorough reply previously. I appreciate your patience and apologise if I'm being a bit dense.


removeAllObjects - SethWillits - Jan 11, 2010 02:14 PM

Code:
- (void) update
{
    NSMutableArray *kill_list = [NSMutableArray array];

    for (CEffectGenerator *effect_generator in effectGeneratorArray )
    {
        if([effect_generator update] == NO) // This effect is dead
        {
            [kill_list addObject: effect_generator];
        }
    }
        
    [effectGeneratorArray removeObjectsInArray: kill_list];
}



Code:
- (void) update
{
    for (int i = [effectGeneratorArray count] - 1; i >= 0; i--) {
    {
        if([effect_generator update] == NO) // This effect is dead
        {
            [effectGeneratorArray removeObjectAtIndex:i];
        }
    }
}



removeAllObjects - DoG - Jan 11, 2010 02:39 PM

It's much easier to create a live list instead of a kill list, and that also works with immutable source arrays.


removeAllObjects - Skorche - Jan 11, 2010 02:53 PM

DoG Wrote:It's much easier to create a live list instead of a kill list, and that also works with immutable source arrays.

That's usually what I do too. Not only is it simpler, but it's algorithmically cheaper to make a live list as it's O(n). A kill list built by iterating the list forwards means you will be removing low index items first and shifting the rest, so the worst case there is O(n^2) if all items expire at the same time. That is bad news if you are processing a particle system with a lot of big particle bursts. On the other hand if you have a lot of items and removing them is uncommon, then you waste a lot of time copying the same list over and over.

Whenever I implement that sort of thing most languages I remember why I like Ruby so much. Sad

Code:
list = list.select{|item| item.update()}

Or I've done this a few times:
Code:
list, dead_items = list.partition{|item| item.active?()}
dead_items.each{|item| # do some extra processing}



removeAllObjects - Madrayken - Jan 11, 2010 03:49 PM

FreakSoftware Wrote:
Code:
- (void) update
{
    NSMutableArray *kill_list = [NSMutableArray array];

    for (CEffectGenerator *effect_generator in effectGeneratorArray )
    {
        if([effect_generator update] == NO) // This effect is dead
        {
            [kill_list addObject: effect_generator];
        }
    }
        
    [effectGeneratorArray removeObjectsInArray: kill_list];
}



Code:
- (void) update
{
    for (int i = [effectGeneratorArray count] - 1; i >= 0; i--) {
    {
        if([effect_generator update] == NO) // This effect is dead
        {
            [effectGeneratorArray removeObjectAtIndex:i];
        }
    }
}


(Thanks - I wasn't asking for a code snippet, but it's appreciated anyhow).

D'oh! Of course that works, because removeObjectAtIndex alters all elements *after* the index specified. For heaven's sake. See. This is why I got out of coding and into direction...


removeAllObjects - Madrayken - Jan 11, 2010 03:59 PM

Skorche Wrote:That's usually what I do too. Not only is it simpler, but it's algorithmically cheaper to make a live list as it's O(n). A kill list built by iterating the list forwards means you will be removing low index items first and shifting the rest, so the worst case there is O(n^2) if all items expire at the same time. That is bad news if you are processing a particle system with a lot of big particle bursts. On the other hand if you have a lot of items and removing them is uncommon, then you waste a lot of time copying the same list over and over.

Whenever I implement that sort of thing most languages I remember why I like Ruby so much. Sad

Code:
list = list.select{|item| item.update()}

Or I've done this a few times:
Code:
list, dead_items = list.partition{|item| item.active?()}
dead_items.each{|item| # do some extra processing}



Python's my particular dram, nowadays. A far cry from Obj-C and all this nonsense. Wink


removeAllObjects - OneSadCookie - Jan 11, 2010 04:36 PM

So code your game in Python Wink


removeAllObjects - Madrayken - Jan 11, 2010 04:54 PM

OneSadCookie Wrote:So code your game in Python Wink

You evil man. You've seen how sucky my coding is. You think I'm going to able to get pyObjC to work with any ease? LOL


removeAllObjects - OneSadCookie - Jan 11, 2010 05:03 PM

Who said anything about PyObjC? You could use PyGame or Pyglet if you preferred.

On Leopard at least, a PyObjC app was as simple as choosing the right Xcode template.


removeAllObjects - longjumper - Jan 11, 2010 05:29 PM

Madrayken Wrote:Just for informational purposes, the owner of my effectGeneratorArray is CEffectGeneratorManager. It is this that has responsibility for creating and deleting objects from my effectGeneratorArray, and as such I'd always considered *that* to be the owner of the effectGenerators. From what you are saying, this is wrong-headed.

Anytime you add an object to an array the array becomes an owner of that object. Usually when you use an array, you create an object and transfer ownership of that object to the array. (AKA, release the creating object's reference to the created object thus giving the array sole ownership.) If you plan to store an object in an array and not have a pointer to it anywhere else, this is what you should be doing.

(A little rule: If an object (A) does not have a pointer to another object (B), A should not be an owner of B. The cases where this rule is ignored are so rare that you can consider it a rule.)

Quote:
I come from a C and assembler background, so I've been trying to use alloc and release like malloc and free wherever possible. Kill lists have been my standard way to remove elements from an array that is being iterated over for some years.
Kill lists are fine. As everyone else said, there is a more optimal implementation but unless its a performance problem, stick with what you are most comfortable with. However, this advice does not apply to memory management. Memory management with Cocoa/Cocoa Touch should never be treated like standard C memory management. It is a fundamentally different concept. You would be better served adopting reference counting instead of trying to fit reference counting into a mold you are more comfortable with.


removeAllObjects - SethWillits - Jan 11, 2010 05:31 PM

Madrayken Wrote:(Thanks - I wasn't asking for a code snippet, but it's appreciated anyhow).

Code is usually easiest understood Smile


removeAllObjects - Madrayken - Jan 11, 2010 06:09 PM

FreakSoftware Wrote:Code is usually easiest understood Smile

Indeed, and code is definitely preferred in my case, but wouldn't have dreamed of asking for it!

It's like saying 'do my coding for me, please' rather than... um... 'do my thinking for me please'. Crap. That's worse, isn't it?

(sigh)

As regards memory management, I think my confusion primarily came from the fact that I didn't understand that [NSMutableArray addObject: <object>] added to the retain count!

It's not stated anywhere in the objective C reference, and nor is the reverse. As a result, I've had only a wooly understanding of what does, and does not constitute ownership.

Longjumper's posts in particular have helped enormously, and I've already refactored nearly all my code based on this new information, rigorously checking retainCounts to ensure I understand things.

Thanks again, folks.


removeAllObjects - SethWillits - Jan 11, 2010 06:22 PM

Madrayken Wrote:As regards memory management, I think my confusion primarily came from the fact that I didn't understand that [NSMutableArray addObject: <object>] added to the retain count!

It's not stated anywhere in the objective C reference, and nor is the reverse.

It is in the documentation. A lot of the major information about using classes is up in the Overview section at the top of the docs.

In NSArray:

Quote:Arrays maintain strong references to their contents—in a managed memory environment, each object receives a retain message before its id is added to the array and a release message when it is removed from the array or when the array is deallocated. If you want a collection with different object ownership semantics, consider using CFArray Reference, NSPointerArray, or NSHashTable instead.


Also in NSMutableArray:

Quote:Like NSArray, instances of NSMutableArray maintain strong references to their contents. If you do not use garbage collection, when you add an object to an array, the object receives a retain message. When an object is removed from a mutable array, it receives a release message. If there are no further references to the object, this means that the object is deallocated.