[PATCH 2 of 8] transaction: track newly introduced revisions

[Jun Wu]

Excerpts from Pierre-Yves David's message of 2017-05-03 14:49:53 +0200:
> > Since changelog is append-only, and strip won't happen during a transaction.
> > Why not just record len(changelog) during transaction start, and test
> > len(changelog) at the end of transaction?
> 
> Mostly for simplicity, having the pure raw information on the 
> transaction is simple and cheap. And it gives us access to all kind of 
> native operation directly (len, membership, iteration) without the needs 
> to perform the same (simple) operation all over the place. It also allow 
> user code to operation without having a changelog object, another small win.
> 
> User-code in this series are fairly simple, but we'll have smarter and 
> smarter usage of these data as more code uses it.

The above are still abstract to me. Could you give some examples about the
future usage of the new information (in a short way) ?
 
> I'm not worried about the memory usage since many other place assumes we 
> can keep all repository revs in memory.

Yes. But I don't think "this is already O(N)" is a good reason to add
another "O(N)" thing given the fact we know there is an easy "O(1)"
alternative.

> > That's O(1), instead of O(N log N)
> 
> (note: I'm not sure what type of complexity you refer to, nor what is 
> the operation you are considering to get theses number)

Both time and memory. If I pulled N revisions, this series is building a set
with N elements by calling set.add N times. The set is only used to detect
new revisions added to changelog, which could be represented as an O(1)
"xrange" by recording changlog length at the start and end of transaction
(which has an O(1) time complexity).