High complexity in the '_add_missing_reverse_references' method.

[xydan83]

Hi everybody!:)
When trying to import with a large number of nodes (from 1 thousand to 10 thousand), I noticed that the import takes a very long time. I started profiling and it turned out there is a method that has a minimum complexity of O(n ^ 3).
Was added in this commit

Import of 1 thousand nodes: 0:00:52
Import of 10 thousand nodes: 3:46:00
Profiling indicated that more time was spent on _add_missing_reverse_references() method in the xmlimporter.py.

Is it possible to search for and add missing reverse references in a different way?

[swamper123]

hey ho,

well we have different problems here. One is, that Python isn't performing well with XML (which is one part of not so good performance).
The other one is the problem, I mentioned in the comment to the commit itself.

Since a new node has different reference types to different existing nodes and the possibility of a faulty node exists (caused by wrong programming or faulty xml file) you have to check that...and touch every single one to be sure. I couldn't figure out a more performing way.

What exists (but is more hidden in backround and atm I am not a friend of it) is to pickle the whole aspace, when it got everything you need, and dump or load it.. But you would still need to run this process atleast once, so that everything would be still alright with the references.

[swamper123]

In case of better ideas, comments are welcomed and PRs even more. :^)

[xydan83]

As far as I understand, the dump can only be done on the server, which means that you need to already have a loaded structure on the server.
Can the client collect the address space inside himself to make a dump?
This is necessary, for example, to make a dump from another OPC server (not only opcua-asyncio).

[swamper123]

As far as I understand, the dump can only be done on the server, which means that you need to already have a loaded structure on the server.

Correct.

Can the client collect the address space inside himself to make a dump?

We haven't got a feature for that.
If I understood you idea right, this wouldn't be a good idea either, since you had to browse all Nodes from a server and then pickle the structure somehow. It doesn't sound impossible, but I see different problems with this plan.

[xydan83]

We haven't got a feature for that. If I understood you idea right, this wouldn't be a good idea either, since you had to browse all Nodes from a server and then pickle the structure somehow. It doesn't sound impossible, but I see different problems with this plan.

Yes, in fact, you would have to make some kind of "internal server", but without interfaces to the outside, which would only store the address space. But for this you have to do browsing and read each node in order to add it to the server. Essentially the same "import". Perhaps it really doesn't make sense. 🤔

[xydan83]

The idea came to try to parallelize the search for each node by processes. There is a general loop that iterates over all the nodes and from it is already looking for children and their links, in which it looks for a parent, and if it does not find it, it adds a reference reverse. I think we can try to separate this process for processing each such node into a separate python process. Let's say we find out the number of cores in the processor and create an equal number of processes. It seems that there is no dependence between the nodes themselves. In theory, the import speed will increase by the number of cores. Maybe the decision is dubious, but so far I can not think of anything better.
I do not consider threads, since CPython blocks them (GIL).

[xydan83]

Another option is to single out one process and add missing reverse references in the background, but I don't quite understand if it is possible to do this?

[swamper123]

I noticed one thing - is it really necessary to add reverse references to the standard nodes of the OPC UA types?

As far as I know:
If a new Node has a reference from the standard nodes, which is not unidirectional, the standard Node has to get a reverse reference as well.

[xydan83]

The presence check is performed by attempting to retrieve a reference to the searched-for node from the dictionary - n_ref = n_refs.get(new_node_id)

Sorry if I may confused you. ^^ I just followed your thoughts now and was confused about some things (and stuck in my old thinking of looping a list). This seems to be a good boost!

Perhaps at best it was possible to reduce the complexity to O (n ^ 2)
If you do not mind, how will the time be I will prepare the PR :)

[xydan83]

I noticed one thing - is it really necessary to add reverse references to the standard nodes of the OPC UA types?

As far as I know: If a new Node has a reference from the standard nodes, which is not unidirectional, the standard Node has to get a reverse reference as well.

Is this from the spec?

I just tried to compare data on another server, for example UAСPPServer, and there were no reverce references to demo data in the standard OPC Nodes ...

https://www.unified-automation.com/downloads/opc-ua-servers.html

It just turns out that, for example, we have added 1000 nodes and they all have at least one reference to the standard node "type of node", which means that this standard node will have 1000 reverce references. It is very cumbersome and incomprehensible why standard nodes need it?

I'll try to find it in the spec ... If you remember where this statement is located, can you send a link?

[swamper123]

Is this from the spec?

It's how I interpreted things at that time. I remember that we had problems with importing Nodes and adding the references on them (and no complains so far).
It is a while ago, since I tackled this topic tbh. and not great in touch with it at the moment. It is possible that some references shall not be added to the SourceNode (like unidirectional references).

If this is the case, it might be a challenge to sort out the good and the bad ones. 😅

[xydan83]

Is this from the spec?

It's how I interpreted things at that time. I remember that we had problems with importing Nodes and adding the references on them (and no complains so far). It is a while ago, since I tackled this topic tbh. and not great in touch with it at the moment. It is possible that some references shall not be added to the SourceNode (like unidirectional references).

If this is the case, it might be a challenge to sort out the good and the bad ones. sweat_smile

I will try to search for these moments in the spec. It may be possible to somehow alter this search engine to further increase performance. Without this method, I did not observe any problems, it seems that all references were added, but it is quite possible that I simply have not yet encountered such a case.

[oroulet]

Is import speed an issue? I would prioritize code readability. That XML code is horrible

[xydan83]

Is import speed an issue? I would prioritize code readability. That XML code is horrible

Rather, the problem is with one of the import methods.