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

[Yuya Nishihara]

On Fri, 12 May 2017 08:38:05 -0700, Jun Wu wrote:
> Excerpts from Yuya Nishihara's message of 2017-05-12 23:42:42 +0900:
> > Jun, do you have any other thoughts on this?
> 
> Nope. Feel free to queue it.

Okay, queued these. Many thanks.

> > >>> 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.
> > 
> > (not: here memory in O(N))
> > 
> > > If I pulled N revisions, this series is building a set
> > > with N elements by calling set.add N times.
> > 
> > If you pull N revisions, You are adding at least N new revlog entries + 
> > over implied computation on these N new revisions (eg: cache update) .
> > The time spend doing 'set.add' will be negligible in regard with the above.
> > 
> > > 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).
> > 
> > You seems to be missing the goal of 'tr.changes'. Its goal it to 
> > contains an accurate record of the changes made by a transaction. The 
> > current user is simple, because we start simple.
> 
> Do you mean we could have non-contiguous tr.changes['revs'] ? I don't care
> much about the O(N) memory use (as the set should be smaller than the other
> data we currently have), but I think keeping (startrev, endrev) will be
> simpler if the range is contiguous.

I hope this will be addressed as a follow up if that's reasonable.