Code review comment for lp:~jameinel/bzr/1.17-chk-multilevel

This is a slightly better fix for bug #390563. The main changes are:

1) Rewrite iter_interesting_nodes using a class, rather than maintaining state between functions
2) Split up the processing of root nodes into:
  a) Read all uninteresting roots, and find uninteresting chks and items
  b) Filter out any interesting root keys that were found in (a)
  c) Read all remaining root pages and yield them
  d) Find interesting references that are not in (a) (and interesting items)
     Note the search key prefixes for these references and items, and queue
     them up to be returned later.
  e) Filter out uninteresting chk pages based on the search key prefixes in (d)

(d) and (e) are the main differences.
For (d) Robert found an edge case where we could return a non-interesting item (which would, in turn, be a text key, which would then be a failure for fetch) when one side had an immediate leaf node, and the other side had a deep tree. The only real change is to just defer returning interesting *items* until all uninteresting pages have been read.

(e) Before we used the 'intersection of interesting references', whereas now we filter simply based on prefix. Likely to be a small win if there are lots of uninteresting pages (lots of merge parents that are not being transmitted).

3) After processing root nodes
  a) Process the uninteresing queue until completion
  b) Process the interesting queue, filtering out all uninteresting items.
     (some minor things here, like doing batch '.difference()' checks rather than .difference on every record processed)

I looked at trying to use a heapq to unify things more with 'iter_changes' but the constraints are *very* different.

1) CHKMap.iter_changes() is symmetric. In that we need to return a record for (source, target, extra), for iter_interesting_nodes, we *only* need to return information for the 'target' side.
2) CHKMap.iter_changes() only ever effects 2 records, a single source and a single target. iter_interesting_nodes is looking at a many-to-many comparison.
3) CHKMap.iter_changes() only cares about the actual keys, and not about sending the raw byte records to be transmitted for fetch.
4) iter_interesting_nodes is much more concerned about batching because of its many-to-many nature, and the fact it is used for fetch. We really don't want to be doing a round trip per page.
5) The only gain for doing heapq is if we could figure out the algorithm for filtering out nodes that we thought we would want to read, but really don't. However,
  a) I do this at the root level, because it is fairly straightforward. So any further improvements only effect trees that are deeper than 2 (1 root, 1+ internal, 1 leaf), however this only happens for trees > 50k items.
  b) Reading extra chk pages isn't "incorrect", just "inefficient" (the stacking code ensures all referenced chk pages are present in the stacked-on branch, just like we ensure compression texts.)
  c) The best I could come up with would be to split the reads up by prefix. So you would page in the 'a' references, then the 'b' references, etc. However, that forces us to split the requests up even further, rather than larger batches of requests. (more round trips for dumb fetch, wouldn't effect round trips for smart fetch directly.)
  d) The code is simpler this way, especially with references that can be at different depths. (One side can go root => 'aa' => 'aaa-id':value, and the other goes root => 'a' => 'aaa-id':value)

This also includes a lot more direct testing of edge cases with trees of different sizes/shapes. I've benchmarked that this code performs ~ the same as the existing code. (note that under lsprof we spend ~45s filtering in iter_interesting_nodes, but more than 35s of that is get_record_stream().

The next big win, IMO, would be to restructure objects a bit. To be able to compute the difference between nodes without deserializing them, rather than deserializing and then putting stuff into a set to make it unique. However, I don't have any good numbers for what the difference would be.