Fast way to iterate all positions of a given vnode

[vitalije]

Here is a very fast way to iterate all positions for a given vnode:

from leo.core.leoNodes import Position
# or if inside Leo script and you have p instance
# Position = type(p)
def iter_all_positions(v, stack=None):
    """Generates all positions p in this outline where p.v is v"""

    if stack is None:stack = []

    def allinds(par, ch):

        for i, x in enumerate(par.children):

            if x is ch: yield i

    def stack2pos(stack):

        v, i = stack[-1]

        return Position(v, i, stack[:-1])

    for par in set(v.parents):

        for i in allinds(par, v):

            stack.insert(0, (v, i))

            if par is c.hiddenRootNode:

                yield stack2pos(stack)

            else:

                yield from iter_all_positions(par, stack)

            stack.pop(0)

The positions generated are not necessarily in the outline order.

HTH Vitalije

[Edward K. Ream]

On Monday, October 14, 2019 at 4:22:46 AM UTC-5, vitalije wrote:

Here is a very fast way to iterate all positions for a given vnode:

Thanks for this.  It should be useful in fixing #1392. 

I would like to make this code easily available to both scripts and Leo's core.  Making this a "c" method seems the best way, though it might slow down the script a teeny bit.

Of course, if speed is super important, people can use the script as is.  What say you, Vitalije?

Edward

[vitalije]

 What say you, Vitalije?

I am glad you liked it. Please add it to wherever you think is best. ATM I have too many other tasks that I can't add it myself. I've read in another thread some discussion about this problem and I remembered this function I wrote while trying to speed up Leo tree.

Vitalije

[Edward K. Ream]

On Mon, Oct 14, 2019 at 12:41 PM vitalije <vita...@gmail.com> wrote:

 What say you, Vitalije?

I am glad you liked it. Please add it to wherever you think is best.

Thanks!  Rev f45486a now contains c.all_positions_for_v.  The name follows the conventions for other generators.  The code is only slightly changed.

Edward

[Edward K. Ream]

On Monday, October 14, 2019 at 4:22:46 AM UTC-5, vitalije wrote:

Here is a very fast way to iterate all positions for a given vnode:

This is one place where speed is truly useful!!

Here is the present code for p.setAllAncestorAtFileNodesDirty:

def setAllAncestorAtFileNodesDirty(self, setDescendentsDirty=False):
    """Rewritten in Leo 6.1"""
    p = self
    c = p.v.context
    dirtyVnodeList = []
    for p2 in c.all_positions_for_v(p.v):
        for parent in p2.self_and_parents():
            if parent.isAnyAtFileNode() and not parent.v.isDirty():
                dirtyVnodeList.append(parent.v)
    for v in dirtyVnodeList:
        v.setDirty()
    return dirtyVnodeList

Notice: the setDescendentsDirty kwarg is not used.  I believe this is sound, because of the generality of c.all_positions_for_v.  The result is a spectacular collapse in the code.  In particular, the horrible p/v.findAllPotentiallyDirtyNodes methods are no longer needed.

The new code is in the "dirty" branch.  I want to test further before merging into devel.

Thanks again, Vitalije, for a superb optimization.

Edward

[Edward K. Ream]

On Monday, October 14, 2019 at 9:11:36 PM UTC-5, Edward K. Ream wrote:

> This is one place where speed is truly useful!!

...

> The result is a spectacular collapse in the code.

The code is also much faster than before, because the code only looks up the tree for those nodes in c.all_positions_for_v(p.v). There are typically only a few such positions, so in practice less than a dozen or so positions are actually examined.

In essence, the old code was perhaps O(N), where N is the size of the outline.  The new code is typically O(1).  This could well make a noticeable difference in performance.

Edward

[vitalije]

Without any measurement I think that this can be further simplified and speed up. The all_positions_for_v builds and yields positions, which means it builds entire stacks of (v, index) pairs for each visited v node. And for marking dirty parents it doesn't need to build positions at all. The following is not tested but I believe it should work.

def collect_dirty_parents(v):

    def it(ch):
        yield ch
        for par in ch.parents:
            yield from it(par)
    dirty_nodes = [x for x in it(v) if x.isAnyAtFileNode() and not x.isDirty()]

    for x in dirty_nodes:
        x.setDirty()

    return dirty_nodes

Vitalije 

[Edward K. Ream]

On Tue, Oct 15, 2019 at 4:32 AM vitalije <vita...@gmail.com> wrote:

Without any measurement I think that this can be further simplified and speed up. The all_positions_for_v builds and yields positions, which means it builds entire stacks of (v, index) pairs for each visited v node. And for marking dirty parents it doesn't need to build positions at all. The following is not tested but I believe it should work.

Thanks for this.  I'll look into it.

Edward

[Edward K. Ream]

On Tuesday, October 15, 2019 at 4:32:32 AM UTC-5, vitalije wrote:

Without any measurement I think that this can be further simplified and speed up.

Rev fe19829 in the "dirty" branch contains the new code.  It's certainly simpler, and it will stress the GC less.

Edward