In the most important case it was sets. There was a collision detection routine that took up too much time because checking membership for vectors is not constant time. The sets/vectors were very small though, low double digits, but once you do stuff 30 times per second for a couple a hundred objects it can get slow. (only on the iPhone though, in the simulator everything was good)

For the general world representation I used a static grid, as the object size was very homogenous, so a quad tree would have been overkill.