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
_______________________________________________
Mercurial-devel mailing list
Mercurial-devel@mercurial-scm.org
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
