<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Thu, Sep 24, 2015 at 2:27 AM, Dominic Cleal <span dir="ltr"><<a href="mailto:dcleal@redhat.com" target="_blank">dcleal@redhat.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">On 22/09/15 20:18, Laine Stump wrote:<br>
> <br>
> 1) has anyone thought about/looked into optimizing/changing the data<br>
> structure used to store nodes in augeas to scale better with larger<br>
> datasets (execution time seems to increase at > linear)?<br>
<br>
</div></div>Yes, I've seen something similar before - it was reported to us in the<br>
context of a Puppet provider working on a huge file with many Nagios<br>
service definitions.  When lots of nodes with the same name, but<br>
different index (e.g. service[1], service[2]) exist then Augeas is<br>
extremely slow to traverse paths with a high index value.<br></blockquote><div><br></div><div>That's not a huge surprise, as the data structure for a tree is incredibly simple: children are kept in a singly-linked list, so dealing with nodes that have lots of children is bound to be slow. <br> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

I spent a while profiling it and found a couple of very inefficient<br>
memory operations - here's my branch:<br>
<a href="https://github.com/hercules-team/augeas/compare/master...domcleal:ns-filter-perf3" rel="noreferrer" target="_blank">https://github.com/hercules-team/augeas/compare/master...domcleal:ns-filter-perf3</a><br></blockquote><div><br></div><div>Interesting .. that looks like it would get rid of some of the inefficiencies in dealing with nodes with a large number of children. Is the main issue to address expressions of the form 'service[%d]', i.e. addressing nodes by their position ? I wonder if it wouldn't be worth to just special-case that in ns_filter - we know that at most one node can match such a predicate and we could save ourselves a lot of effort by treating that specially. Other things, like "service/foo[. = 'bar']" will be much harder to get speed up since we still need to go over a large number of service nodes ...<br><br></div><div>David<br><br></div></div></div></div>