history.Cache needs improvement

[aboodman]

It's super slow and naive right now, reloading the entire history every time it is used. Here are many ideas I have had, from simplest to cleverest:

1. Make it actually a cache, stored globally over the lifetime of the process

• Downside: doesn't help for CLI use cases, where the process is short-lived

2. Make it a persistent cache - can use an index-style approach where on every commit, we update a persistent set of all known reachable commits

• Downside: the index and truth can get out of date

3. Implement Contains() incrementally -- Refs contain a height field, so it is possible to implement Contains() without walking the entire tree. In most cases we're going to be checking commits that have a height that is higher than the latest known-good commit, so if we added this, it Contains() would instantly become a no-op
4. We need to improve the implementation of history in noms anyway, because it is very slow. One of the proposed solutions would make the need for history.Cache go away completely since it would store an index of all reachable commits on every commit.

• Downside - same as (2) - the index can conceivably be out of date with truth.

5. Noms actually already internally stores all chunks that are reachable from the current committed database state. The only reason this doesn't work for us is that it tracks all written chunks, not all reachable chunks. So relying on this would be a bit brittle.

[aboodman]

Fixed by d3330cf