Oh my: fast, incremental redraws are doable in any gui

[Edward K. Ream]

I could try to explain how these idea came about, but they came so thick and fast that it wouldn't be accurate.  Recent work did contribute:

- Passing full and incremental redraw dicts from the Py to JS side.

I started thinking anew about the representation of positions.

- Trying to optimize app.redraw. 

At present, app.redraw ignores redraw requests if g.callers() contains c.outerUpdate!  It's ridiculous, but it got me thinking about boundaries.  As did the constant presence of the PY/JS divide.

The big ideas

1. Ever since day one, Leo's core has been trying to tell the gui redraw code what to do.  Actually, the gui can do just fine on its own, thank you very much.

2. In fact, there isn't all that much work involved, since the gui redraw code only has to analyze visible nodes!

3. Python's diff lib can tell which nodes have changed, provided we represent the "before" and "after" snapshots of the tree that don't muck up the diffs.  The simpler the snapshots, the better.  Forget about node indices, position stack, etc.

So a snapshot might be a simple linear list of all visible positions: like this:

level:gnx

level:gnx

...

We don't care about clones, or about much else.

4. In the first draft of this post, I said that detecting simple patterns on the line-oriented diffs will tell the redraw code what Leo did.  But, as I write this I see (huge aha) that the gui redraw code doesn't care what Leo did!  It only cares about minimizing the number of tree widgets that have to be inserted, deleted or moved.  But that's precisely what diff tells us!

Diff will tell the redraw code exactly what to do.

A big speedup

The present Qt and Flexx gui code (almost) always does a full redraw, which means deallocating all existing nodes and then immediately reallocating and redrawing the same nodes.  This is crazy.  It takes a lot of time (comparatively) to mess with actual gui widgets.  It should be much cheaper to do an analysis that lets the redraw code insert, delete or move just a few nodes.

Summary

Diff will tell the redraw code exactly what to do.

Flexx code is all about the PY/JS divide.  Incremental redraw creates an almost perfect divide between Leo's core and the gui redraw code.  All calls to c.redraw might disappear!  Leo's core would simply inform the gui when a command has finished.

Diffs tells the gui the minimum changes needed to change the before screen to the after!

It's a new world.

Edward

[Edward K. Ream]

On Sunday, November 25, 2018 at 6:03:51 PM UTC-6, Edward K. Ream wrote:

4. In the first draft of this post, I said that detecting simple patterns on the line-oriented diffs will tell the redraw code what Leo did.  But, as I write this I see (huge aha) that the gui redraw code doesn't care what Leo did!  It only cares about minimizing the number of tree widgets that have to be inserted, deleted or moved.  But that's precisely what diff tells us!

Hmm.  Now I'm not quite so sure.  It may be indeed be necessary to analyze the diffs.  For example, if Leo move's a node up, and that node is expanded, all the node's children will "move" with the parent node.

Presumably, having the gui move the parent node will automatically cause the child nodes to move with it.  So some further analysis will be required, as I first thought.

The problem is kinda like a peephole optimizer.  The only thing to know about such things is that:

1. They are easy to write and test and

2. They are very fast and effective ;-)

This is just incredibly exciting stuff.

Edward

[vitalije]

This was the approach I took to made several demos while we were discussing the new data model for Leo. This idea worked perfectly but not with the current Leo data model. The main challenge is to have the list you have described above (list of pairs (level, gnx)), always in sync with the Leo's vnode graph without recreating the list every time. Recreating the list takes almost the same time as redrawing the whole tree from scratch. The only way to really exploit this idea of small redraws is to force Leo to keep this list always in sync. In other words, this list becomes part of Leo data model. Including it in the Leo's data model makes a lot of information contained in vnode graph redundant. That would make a lot of processing that VNode class now does, unnecessary. After cleaning those redundant parts and avoiding unnecessary processing, one would most probably end up with the model very similar to the model I have suggested before.

Vitalije

[vitalije]

And yes, I fully agree with the title of this thread "Oh my: fast, incremental redraws are doable in any gui", provided that the list of pairs (level,gnx) is integral part of Leo's data model.

Vitalije

[Edward K. Ream]

​On Mon, Nov 26, 2018 at 1:58 AM vitalije <vita...@gmail.com> wrote:

This was the approach I took to made several demos while we were discussing the new data model for Leo.

Yes. I was aware of that.  You could call this yet another factor that primed my mental pump.

This idea worked perfectly but not with the current Leo data model.

Well, I think it just works ;-)

The main challenge is to have the list you have described above (list of pairs (level, gnx)), always in sync with the Leo's vnode graph without recreating the list every time. Recreating the list takes almost the same time as redrawing the whole tree from scratch.

That's hard to believe. For this purpose, we only care about visible nodes.  Leo doesn't have an "all_visible_positions" generator, but surely it's got to be easy and fast. See below.

My core intuition is that traversing Leo's tree is fast.  Messing with with actual widgets is slow.  I mentioned this several weeks ago.  app.create_all_data reports: 0.006 sec. 2763 entries.

For the flexx code there seems to be no alternative to passing a full representation of the tree to the JS side.  This is what app.make_redraw_dict & helpers does. I added some timing stats:

app.make_redraw_dict: 5 direct children 0.006 sec.

app.make_redraw_dict iterates over only visible positions.  Its helper, app.make_dict_for_position, contains:

children = [
    self.make_dict_for_position(child)
        for child in p.children()
            if level == 0 or child.isVisible(c)
]

Happily, this can be improved, because it is already known that p is visible!

if p.level() == 0 or p.v.isExpanded():
    children = [
        self.make_dict_for_position(child)
            for child in p.children()
    ]
else:
    children = []

Now the stats are:

app.make_redraw_dict: 5 direct children 0.0004 sec.

The only way to really exploit this idea of small redraws is to force Leo to keep this list always in sync. In other words, this list becomes part of Leo data model.

Not really, as I have just shown.

Edward

[Edward K. Ream]

On Monday, November 26, 2018 at 5:21:10 AM UTC-6, Edward K. Ream wrote:

Happily, this can be improved, because it is already known that p is visible!

if p.level() == 0 or p.v.isExpanded():
    children = [
        self.make_dict_for_position(child)
            for child in p.children()
    ]
else:
    children = []

And the test on p.level() is not necessary:

if p.v.isExpanded():

    children = [
        self.make_dict_for_position(child)
            for child in p.children()
    ]
else:
    children = []

However, this doesn't change the speed significantly.

In any case, the time to compute this vital dict is 0.0004 sec. on my machine.

Edward

[vitalije]

I don't know what is redraw_dict and where did it come from? In this thread you described a list of pairs (level, gnx).

So a snapshot might be a simple linear list of all visible positions: like this:

level:gnx

level:gnx

...

I know that computing this list on a large outline like leoPyRef.leo takes much more time than 4ms.

If you skip invisible members of the outline when re-creating this list, you end up with the algorithm Leo currently uses. I don's see the "A-HA" here. That algorithm have the same issues when dealing with big fully expanded outlines. OTOH, having this list ready enables much more efficient redraws (what I understood was this thread's 'A-HA' all about).

Vitalije

[Edward K. Ream]

On Mon, Nov 26, 2018 at 6:02 AM vitalije <vita...@gmail.com> wrote:

I don't know what is redraw_dict and where did it come from?

The redraw_dict is the dict that the PY side of leoflexx.py passes to the JS side.  This dict describes the entire screen to the JS side, so that the JS side can completely redraw the screen.

Yesterday morning I worked on what turned out to be a very minor optimization: passing only the newly-visible children to the JS side when the user expands an outline node using a mouse click.

It was a good "failed" experiment. It took a lot of difficult code to do even this minor optimization.  Worse, expanding a node using Alt-RtArrow would not use the new optimization.  This "failure" was the spur to do something much more interesting.

In this thread you described a list of pairs (level, gnx).

This list is the input to diff.  Clearly, it can be computed in less time than it takes to compute the redraw dict, that is, in less time that app.make_redraw_dict takes.

I know that computing this list on a large outline like leoPyRef.leo takes much more time than 4ms.

That's the very worst case.  Remember, we care only about visible nodes.  We can always ignore the children of unexpanded nodes.

Btw, we must be careful to use p.isVisible(), not p.v.isVisible(), because cloned positions can be expanded individually.  In most cases, p.isVisible() is almost as fast as p.v.isVisible(), because most nodes aren't clones.

If you skip invisible members of the outline when re-creating this list, you end up with the algorithm Leo currently uses. I don's see the "A-HA" here.

The Aha is that the redraw code doesn't have to redraw all the visible nodes.

Instead, the analysis phase (diff followed by a post-pass), will determine which widgets must be moved, inserted or deleted.  This might not be a big deal for the Qt code, but it surely will be a very big deal for leoflexx.py, for several reasons:

1. The analysis phase will minimize the traffic across the PY/QT divide.  That's why we'll do the analysis on the PY side.

2. Instead of passing the full redraw dict, the PY side will pass a redraw instruction list to the JS side.  By definition, this instruction list specifies the minimum number of gui operations needed to update the screen. I said that the analysis phase was kinda like a peephole optimizer because the analysis phase will optimize the instruction list.

3. The flx.TreeWidget struggles with full redraws.  We want to make it's job as easy as possible.

That algorithm have the same issues when dealing with big fully expanded outlines.

As I said, that's the (rare) worst case.

OTOH, having this list ready enables much more efficient redraws (what I understood was this thread's 'A-HA' all about).

Exactly.

Thank you for your excellent questions.  They have helped me explain my ideas more fully.

Edward

[Edward K. Ream]

​

On Mon, Nov 26, 2018 at 5:34 AM Edward K. Ream <edre...@gmail.com> wrote:

> the test on p.level() is not necessary​...[but]​ ​this doesn't change the speed significantly.

​...​

> In any case, the time to compute this vital dict is 0.0004 sec. on my machine.

​Strange.  Increasing the resolution of the timing stats yields:

app.make_redraw_dict: 5 direct children 0.00011 sec

It looks like %f always rounds up.

I'm going on about this because this is a crucial figure of merit, which depends on the number of visible nodes.  We might realistically expect 100 times more nodes to be visible.  Happily, the code is O(N), so we can expect the time to be 0.01 seconds when 500 nodes are visible.

Edward

[Edward K. Ream]

On Monday, November 26, 2018 at 6:30:20 AM UTC-6, Edward K. Ream wrote:

The Aha is that the redraw code doesn't have to redraw all the visible nodes.

 

[snip]

...the PY side will pass a redraw instruction list to the JS side.  By definition, this instruction list specifies the minimum number of gui operations needed to update the screen.

Important:  it's not clear that the flx.TreeWidget or flx.TreeItem classes can actually take advantage of such a list.  Indeed, it seems like only the following methods are relevant.

- TreeItem.set_parent

It might be possible just to reset the parents of the to-be-drawn tree items, but this would have to be done in outline order, for all visible widgets. I'll explore this avenue first, but there are no guarantees.

- Widget_render_dom()

This is a general-purpose fallback for all kinds of troubles.  It would likely be a lot of work, and the performance implications are completely unclear.

Summary

It's important not to lose sight of the big picture. Imo, the redraw instruction list is worth any amount of effort:

- The redraw list enforces a bigger divide between Leo's core and the gui code.  It might eliminate all calls to c.redraw in Leo's core.

- The redraw list is the gateway to general-purpose optimizations in leoflexx.py.

Edward

[Edward K. Ream]

On Monday, November 26, 2018 at 6:59:37 AM UTC-6, Edward K. Ream wrote:

Important:  it's not clear that the flx.TreeWidget or flx.TreeItem classes can actually take advantage of [the redraw instruction list].

This may be true now, but perhaps Almar will be open to adding new methods to the TreeWidget or TreeItem classes.  Assuming that's possible :-) And assuming a real performance gain would result.

Edward

[Terry Brown]

On Mon, 26 Nov 2018 05:13:38 -0800 (PST)

"Edward K. Ream" <edre...@gmail.com> wrote:

> This may be true now, but perhaps Almar will be open to adding new
> methods to the TreeWidget or TreeItem classes.  Assuming that's
> possible :-) And assuming a real performance gain would result.

You can just subclass them?

Cheers -Terry

[Edward K. Ream]

On Mon, Nov 26, 2018 at 7:45 AM Terry Brown <terry...@gmail.com> wrote:

> This may be true now, but perhaps Almar will be open to adding new
> methods to the TreeWidget or TreeItem classes.  Assuming that's
> possible :-) And assuming a real performance gain would result.

You can just subclass them?

Hmm.  leoflexx.py already subclasses them, but I see your point.

I was thinking that flexx code in Anaconda3/Lib/site-packages/flexx/ui/widgets/_tree.py would have to change, but now I'm not at all sure.

Edward

[Edward K. Ream]

On Monday, November 26, 2018 at 6:41:09 AM UTC-6, Edward K. Ream wrote:

I'm going on about [the speed of of app.make_redraw_dict] because this is a crucial figure of merit, which depends on the number of visible nodes.

For timing,  app.redraw now contains:

ap = self.p_to_ap(p)
if 1:
    # For development of make_redraw_instruction_list
    #
    # 1. Measure time for a full redraw.
    for p2 in c.all_positions(copy=False):
        p2.expand()
    t1 = time.clock()
    d = self.make_redraw_dict(p)
    redraw_instruction_list = self.make_redraw_instruction_list(d)
        # Does nothing, at present
    t2 = time.clock()
    #
    # 2. Do a normal redraw, so the flexx tree doesn't choke.
    for p2 in c.all_positions(copy=False):
        p2.contract()
    c.expandAllAncestors(p)
        # Does not do a redraw.
else:
    w.tree.redraw_or_repopulate(d)
w.tree.select_ap(ap)
d = self.make_redraw_dict(p)
w.tree.redraw_with_dict(d)

The result is (for unitTest.leo):

app.make_redraw_dict: 5 direct children 0.057 sec.
app.make_redraw_dict: 5 direct children 0.000 sec.

This is plenty fast enough for even large .leo files.

app.make_redraw_instruction_list should be roughly as fast as app.make_redraw_dict.  It's next.

Edward

[Edward K. Ream]

On Monday, November 26, 2018 at 9:02:17 AM UTC-6, Edward K. Ream wrote:

app.make_redraw_instruction_list should be roughly as fast as app.make_redraw_dict.  It's next.

"make_redraw_instruction_list" is the wrong name. The intermediate step is to flatten the outline to make it diffable. The new name is "flatten_outline". Here it is, stripped of tracing code:

def flatten_outline (self):
    '''Return a flat list of strings "level:gnx"
    for all *visible* positions.'''
    c, aList = self.c, []
    for p in c.rootPosition().self_and_siblings():
        self.extend_flattened_outline(aList, p)
    return aList
       
def extend_flattened_outline(self, aList, p):
    aList.append('%s:%s' % (p.level(), p.gnx))
    if p.isExpanded():
        for child in p.children():
            self.extend_redraw_list(aList, child)

app.flatten_outline is almost four times faster than app.make_redraw_dict.  For unitTest.leo with all nodes expanded the times are:

app.make_redraw_dict: 5 direct children 0.058 sec.
app.flatten_outline: 2813 entries 0.016 sec.

So this is good :-)  On to diffing!

Edward

[Edward K. Ream]

On Monday, November 26, 2018 at 9:38:05 AM UTC-6, Edward K. Ream wrote:

app.make_redraw_dict: 5 direct children 0.058 sec.
app.flatten_outline: 2813 entries 0.016 sec.

On to diffing!

It's been quite a day.

app.make_redraw_list now uses diff to create a list of opcodes, and passes that list to app.peep_hole.  The peep_hole code is just as I thought it would be.  It successfully combines 'insert' and 'delete' opcodes on nodes with the same gnx to a single 'move' opcode.

In particular, the redraw list that will be passed to the JS side contains only this 'move' opcode after Ctrl-D, Ctrl-U, Ctrl-R and Ctrl-L.

The data involved are small, so there are no performance worries whatever.

Edward