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

[Pierre-Yves David]

On 05/13/2017 12:13 PM, Yuya Nishihara wrote:
> 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:
 >
> […]
 >
>>>>>> 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.

My plan is to revisit this once we have more data in the dictionary (eg: 
phase movement), this will having a more concrete grasp on consistency 
there.

Cheers,

-- 
Pierre-Yves David