Comment 3 for bug 388269

So to be clear, I think the slowdown is in

SmartServerRepositoryGetParentMap and the fact that it is doing:
        search_result, error = self.recreate_search_from_recipe(
            repository, body_lines)

Which is causing us to walk 100,000 revisions to find out what the next 1000 revisions are.

Also note, that by the time we get to even 20k revisions searched, we are pretty much stepping one-by-one. Now, these 100k revs *are* used on the server to make sure that we don't return parents that we already know about. However, I'm pretty sure that while this is probably good when N searched is small, it is pretty terrible when N searched is big.