nest / nestml

A domain specific language for neuron and synapse models in spiking neural network simulation
GNU General Public License v2.0
46 stars 45 forks source link

``get_parent()`` is excruciatingly slow #1024

Closed clinssen closed 4 months ago

clinssen commented 5 months ago

There is a context condition check on the NESTML built-in resolution() function, which needs to find the block that each resolution() function call is enclosed in: the update block, equations, parameters, etc. (In the equations block and in functions, it is not allowed.) To check this coco, there is a visitor which finds each resolution() function call, and then tries to find the parent block of the call by calling ast_neuron.get_parent(ast_resolution_func_call). It turns out that get_parent() is implemented by hand for each AST node, and does a depth-first search on the entire ast_neuron to find ast_resolution_func_call. This works, in principle. However, we now have a model that has several resolution() function calls, which is resulting in tens of millions of calls to get_parent() on various AST nodes. This is making code generation excruciatingly slow.

The simplest and fastest approach could be to simply add a "parent" attribute to each AST node to create a "doubly linked tree". However, this means that this attribute needs to be passed around in each constructor and the tree should be kept consistent. Could we implement this instead by a new "parent aware" visitor pattern? But would we then assign the parent information to each AST node instance, or to a centralised data structure inside the visitor? And would the get_parent() methods go away on all the AST node classes?

If we use the "parent aware" visitor pattern, all visitors would derive from this ParentAwareVisitor. Would it be the case that for each of their methods (visit_statement(), visitequation(), etc.), they would need to invoke the corresponding visit...() method in the ParentAwareVisitor? This means that we would have to explicitly make this call for all derived visitors, e.g.

class MyVisitor(ParentAwareVisitor):
    def visit_statement(self, node):
        super().visit_statement(node)   # <-- has to be done explictly to get ParentAwareVisitor to update the stack?!
        # ... things here specific to MyVisitor; can now call node.get_parent() here ...

See paragraph 8.2.3 ("Parent Aware Visitor") in the MontiCore reference manual.