Performance issue while building data tree with operations create and destroy.

[vishaldhingra]

libyang_scale.zip
Hi,

We are currently facing performance issues on FRR where libyang is used for configuration processing.
I have noticed API lyxp_eval() consumes lot of cycles in lyd_find_path() in a scaled environment.
I have attached the test code, to reproduce this issue.

Our Requirement is to create a scaled data tree with given set of configurations
which have operations create and destroy.

Steps are done to reproduce the issue :

1. Created a context.
2. Loaded a module frr-scale.yang
3. Building the data tree via lyd_new_path/lyd_find_path APIs.

At present we tries to configure 10K routes in one commit.
In order to configure 1 route.
We have 4 X-Paths, 3 with operation NB_OP_CREATE and one with operation NB_OP_DESTROY.

Steps to use test code (It will create a data tree with 10K entries)

1. bin folder : make clean; make all
   It will give you executable libyang_scale
   run it with ./libyang_scale
   The yang module is also placed under this bin folder only name : frr-scale.yang
2. src folder : yang.c contains the code to create context, load module and create entries in data tree.
   ROUTE_COUNT Macro controls the number of route entries to create, At present it sets to 10K.

In code these xpaths are mapped to Macros:
Opertaion Create : XPATH_PREFIX, XPATH_PATH, XPATH_NEXTHOP
Operation delete : XPATH_MPLS

Libyang version : Latest master at commit ID : 773653e

Observations :
RUN 1: When i execute this binary, it would take around 4 min.
time ./libyang_scale
log_time: Data Tree start = 05-27-2020 04:39:23.207444
log_time: Data Tree end = 05-27-2020 04:43:48.662590

real 4m25.469s
user 4m20.463s
sys 0m1.608s

RUN 2: When i execute this binary after commenting out the lyxp_eval() in lyd_find_path(), then it
takes around .618 seconds
time ./libyang_scale
log_time: Data Tree start = 05-27-2020 06:57:30.713136
log_time: Data Tree end = 05-27-2020 06:57:31.323144

real 0m0.618s
user 0m0.618s
sys 0m0.012s

Please help us, to resolve this issue.
If any other information is required then let us know.

[michalvasko]

Hi,
unfortunately, there is not much I can do to help you. XPath (lyd_find_path()) is very generic and powerful but the downside of that is that it is quite slow. I was a bit surprised that you had only problems with lyd_find_path() and not lyd_new_path(). As it turns out, lyd_new_path() uses optimized search for existing instances using hashes, which I do not even remember implementing (but it is 2 years old when I have checked). The reason for it is that it supports only a small subset of the whole XPath so it was not that difficult.

Now, it is not really possible to find data nodes faster with the current libyang and its API. However, I have finished implementing an optimization for XPath for the new libyang version 2 that is still in development a few days ago that actually recognizes paths in the form you are using them in this example and is able to use hashes then. I have briefly measured it and the complexity really was constant. But we will not be adding this optimization to the current libyang.

So, I am not sure what exactly your plans with libyang are but we plan to have the new version ready for some public testing at the end of June. If you were to move to this version as soon as it is reasonably stable, all you would need to do is wait and perhaps help us with some testing. But if that is not what you want to do then I guess there are 2 other possibilities.

One is to port the optimization to the current libyang. But note that many other refactoring changes were made prior to this optimization and I am not sure to what extent they are related and would also need to be cherry-picked.

Another option is to implement a simple data-finding function that would accept only these simple paths and use hashes to find the data instances. Utility functions for the hash search were added even to the current libyang fairly recently so you could use those (lyd_find_sibling_val mostly).

Regards,
Michal

[vishaldhingra]

Hi Michal,

Thanks for the reply. lyd_find_sibling_val() is helping.
We will wait for libyang version 2.