[PATCH 2 of 5] adjustlinkrev: use C implementation to test ancestor if possible

[Pierre-Yves David]

On 11/07/2016 02:01 AM, Jun Wu wrote:
> Excerpts from Pierre-Yves David's message of 2016-11-07 01:08:18 +0100:
> […]
>> What about an intermediate version that use C code to fill a Python heap
>> object? A good way to get a good grasp on the boost I think having a
>> small Cython proof of concept would help.
>
> That might be helpful. However, I don't have immediate plans for it. Because
> we will use C code to do fast "isancestor" test for the "changelog.i" walk,
> and if we pre-build the linkrev database, there is no need to do
> "changelog.d" walk. So "lazyancestors" won't be actually used in
> "adjustlinkrev", which is my main focus right now.

Can you setup a plan page for this linkrev database  project ?

>>> I'd note that I think the C code may have room to improve. And if we are
>>> going to add some "state" to speed up testing ancestors, I think it should
>>> be done globally, i.e. on the C index object. So the state is private to the
>>> C code and the Python code just calls index.isancestor, without knowing
>>> about the details. As the changelog is shared globally and it may be a waste
>>> of memory to have separated states for each fctx.
>>
>> I'm a bit afraid of the space complexity of such cache. However, one of
>> you colleague at the sprint some idea around this.
>
> The memory usage of the global cache would be something like O(log(N) * N)
> or O(N), depending on how useful we want it to be.

I'm not sure how you forsee this cache, can you elaborate ? A naive 
persistent cache approach would give a O(N²) space.

> This is better than the "_ancestrycontext" approach - suppose every ctx has
> an "_ancestrycontext", it's N^2 memory usage, where N is len(repo).

Except we don't do that right now. Especially, if we use many changectx 
with a _ancestrycontext, it is likely to be the same object used for all 
if I remember correctly.

Cheers,

-- 
Pierre-Yves David