speed up update system

[Durman]

The idea is to protect us from extra calculations.

For example we have spiral node that generate huge data (700 000 points particularly). There is no need to generate this data each time when update system is calling.
It is very simple to avoid recalculations. All that we have to do is to memorize properties of the spiral node and next time when update system will call to update the node, we will compare current properties and memorized properties, if nothing is changed do nothing.

Next step is do something with this data for example move points somewhere. But if this needs only once there is also no need recalculate this each time.
In this case we should check not only properties of the move node but also was data coming from inputs sockets changed. For this goals I created new property of output sockets that returns True if parent node was recalculated.

I made speed test for old and new update system with next layout:

Spiral node generates 700 thousand points. New update system shows increasing speed to 15-75 times. It looks strange that with the same conditions new update systems shows different increasing speed. And I think it should work even faster.
Old update system:

New update system:

Related theme: #121

[Durman]

I have understood that stethoscope node and loggind was guilty in decreasing speed. This still seems too slower.

[portnov]

See also #1934, #1990.

[Durman]

If output or input data is big it is take a lot of memory for memorizing more than one result. And it is difficult to predict how a node will be used. So I think in most cases there is no sense to memorize more than one (last) result.

input	output	complexity	memory	times
big	big	hard	a lot of	1
big	big	easy	a lot of	1
big	small	hard	a lot of	1
big	small	easy	a lot of	1
small	small	hard	low	100
small	small	easy	low	10

By times I meant how much times to memorize result of a node.

One more reason against memorizing more than one result is that we should do calculate something like a hash number of input data.
I make several functions that can compare two lists of points.

@get_time
def hash1(l1, l2):
    for p1, p2 in zip(l1, l2):
        if p1 != p2:
            return False
    return True

@get_time
def hash2(l1, l2):
    l1, l2 = hash(tuple(l1)), hash(tuple(l2))
    if l1 == l2:
        return True
    else:
        return False

>>> test_all()
Function hash1 time = 0.04088926315307617
Function hash2 time = 0.2922191619873047

whole code

import random
import time

def get_time(f):
    def iner(l1, l2):
        t1 = time.time()
        res = f(l1, l2)
        print('Function {} time = {}'.format(f.__name__, time.time() - t1))
        return res
    return iner

def mem_points(f):
    kip_points = []
    def iner(n):
        nonlocal kip_points
        need_num = n - len(kip_points)
        if need_num > 0:
            kip_points.extend(f(need_num))
        return kip_points
    return iner

@mem_points
def get_points(n=10):
    r = random.random
    return [(r(), r(), r()) for _ in range(n)]

@get_time
def hash1(l1, l2):
    for p1, p2 in zip(l1, l2):
        if p1 != p2:
            return False
    return True

@get_time
def hash2(l1, l2):
    l1, l2 = hash(tuple(l1)), hash(tuple(l2))
    if l1 == l2:
        return True
    else:
        return False    

def test_hash1(n=1000000):
    l = get_points(n)
    return hash1(l, l)

def test_hash2(n=1000000):
    l = get_points(n)
    return hash2(l, l)

def test_all(n=1000000):
    test_hash1(n)
    test_hash2(n)

Also there is no need in catching output data this information already is keeping in Sverchok. Each output sockets have their own unique number which associated with output data. And if we memorize only last result there is no need in memorizing input result.

We can't help noticing that, then more nodes there is in node tree then more memory Sverchok use and more calculating is done for making copy of data.

So I think we can have great benefits with small overhead if we just protect node tree from recalculation what was allready calculated. This will not be even implementation of memorizing because memorizing allready done in Sverchok.

[Durman]

Mind map of general update function.
From left side callable function are, from right side from where callable function was called.

It is interesting is there way to do such graphs automatically.

[Durman]

For making update system more carefully, before updating a node it should be checked was parental nodes changed.

For this goal it looks like is better to keep status of sockets. But only output sockets will keep real status. Input sockets will return either status of parental socket ore if such does not exist return False.

Changing of the statuses will be happened during updating node groups.

class SvSocketCommon:
    """ Base class for all Sockets """

    output_has_changed = BoolProperty(default=True)

    @property
    def has_changed(self):
        if self.is_output:
            # "I'm output"
            return self.output_has_changed
        if self.is_linked:
            # "I'm inpunt and linked" - so its data is equal to root socket
            return self.other.output_has_changed
        if self.prop_name:
            # "I'm input, not linked and I have property" - this also means that socket could not be changed.
            return False
        else:
            # "I'm input, not linked and I have not property" - so it can't be changed
            return False

    def update_status(self, has_changed=False):
        self.output_has_changed = has_changed

>>> socket = bpy.data.node_groups['NodeTree'].nodes['A Number'].outputs[0]
>>> socket.has_changed
True

>>> socket.update_status()
>>> socket.has_changed
False

>>> socket.update_status(True)
>>> socket.has_changed
True

[Durman]

I made short video how I think update system should work.

[Durman]

Can be useful:
Blender Python API example: detection of changes in mesh object (edit mode)
https://blender.stackexchange.com/questions/19524/python-basics-interactive-script
https://blog.michelanders.nl/2017/04/how-to-add-progress-indicator-to-the-info-header-in-blender.html
https://blender.stackexchange.com/questions/1050/blender-ui-multithreading-progressbar/1052#1052

[Durman]

Now, with more experience, I'm seeing lacks of my previous attempt:

• The links attribute was widely used what makes all very inefficient. Instead of this looks like Sverchok should have its own data structure of node tree which will keep links and finding next connected node for constant time.
• Direction of evaluation of node tree should be from right to left. Firstly such nodes like viewer draw or set property should be found. Then from them recursively other connected nodes should be updated.
• Most likely there is no need in keeping status of properties of nodes for checking whether they was changed or not. Blender already has update event which hooked to changes of any property.

https://wiki.blender.org/wiki/Source/Nodes/NodeInterfaceFramework