title: Memory considerations for BFS in Objective-C
body: <p>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.</p>
  
  <p>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.</p>
  
  <p><strong>Does the following (simplified) code ever allow the run loop to complete an iteration and drain the autorelease pool?</strong></p>
  
  <pre><code>- (void) search {
      while (![myQueue empty]) {
          State *state = [myQueue pop];
          for (State *s in [state allReachableStates]) {
              [myQueue push:s];
          }
      }
  }
  </code></pre>
  
  <p>Profiling shows lots of memory used for NSArrays. This makes sense as <code>allReachableStates</code> 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.</p>
  
  <p>Note all code is run on the main thread and I'm not using ARC.</p>
  
  <p><strong>Edit:</strong> So the fix was wrapping the <code>for</code> loop in an <code>@autoreleasepool</code>.</p>