Memory considerations for BFS in Objective-C

Question

I've written a puzzle solver in Objective-C. It uses a breadth first search to explore the states reachable from the initial puzzle state. The search is terminated when the first winning state is encountered. The only optimization is a look-up table that helps prevent re-exploring from a state already seen.

The algorithm seems to work correctly. However profiling shows it's using a lot of memory and I'd like to understand why. I think my gap in understanding is related to the Objective-C run loop and the autorelease pool.

Does the following (simplified) code ever allow the run loop to complete an iteration and drain the autorelease pool?

- (void) search {
    while (![myQueue empty]) {
        State *state = [myQueue pop];
        for (State *s in [state allReachableStates]) {
            [myQueue push:s];
        }
    }
}

Profiling shows lots of memory used for NSArrays. This makes sense as allReachableStates does create a fair number of arrays. Since they're all autoreleased it seems possible that the above code is preventing the autorelease pool from draining.

Note all code is run on the main thread and I'm not using ARC.

Edit: So the fix was wrapping the for loop in an @autoreleasepool.

Answer 1

You're right that the autorelease pool associated with this turn of the runloop won't be drained within this method. It won't be drained until some time after this method returns.

You can wrap the while block in an @autoreleasepool yourself (one for each state)

Answer 2

It's better not to use a lot of autorelease in a for loop. You can check this Understanding Objective-C autorelease memory management