We spent a lot of time adding and removing keys from tails.
Because we walk parent_map randomly, we don't know early on whether we will see
a parent node again or not. And it turns out that we rarely do, but we often
have to enqueue lots of nodes in case they show up later.

My getting rid of add/remove and instead iterating over the dict a second time,
we are down to 547ms and 44ms for OOo and bzr.dev.