[PATCH] Improve lib/param handling and remove another unused script
abartlet at samba.org
Wed Jan 29 13:16:44 MST 2014
On Wed, 2014-01-29 at 20:53 +0100, Michael Adam wrote:
> Hi Andrew,
> On 2014-01-30 at 07:57 +1300, Andrew Bartlett wrote:
> > On Wed, 2014-01-29 at 13:34 +0100, Michael Adam wrote:
> > >
> > > And I don't quite understand your arguments:
> > >
> > > - Currently this code is essentially O(1) for each call.
> > > Looping over all to search for aliases would make it O(n) for each call.
> > > (What am I missing?)
> > That looking for the parameter in the first place is O(n), so we get to
> > O(n^2).
> Well... The function lpcfg_set_cmdline does:
> - one loop over all parameters (map_parameter(..))
> - and afterwards the treatment of aliases
> (this is O(1) in the current setting and would be
> O(n) if we looped over all)
> But these loops are not nested but in sequence,
> so we have not O(n^2) but O(n) or O(2n) which is
> also O(n).
> What am, I missing?
Nothing, indeed it's O(2n), not O(n^2).
> But quite frankly, these O(n) considerations (although
> interesting) are not very relevant here, I think, because
> they describe the order of magnitude of operations
> depending on a varying input and are the more accurate
> the larger the input is. Our 300 parameters are
> relatively constant and also not a particularly
> large input number (in terms of complexity). The
> concrete figures are more relevant here. :-)
> > > - And isn't it that the lpcfg_set_cmdline is usually called for
> > > individual parameters from the command line or in selected
> > > places? Or is that also called in a loop over all parameters?
> > >
> > > - So the impact would not be too bad and essentially only affect
> > > startup - right?
> > >
> > > - One could also add an index or create backlinks by one initial
> > > traverse if it is too slow.
> > I think we should move to better data structures in the medium term.
> First step in my opinion could be to properly encapsulate
> the existing data structures (param_table, services array, ...)
> behind good APIs (that
> can then ideally last the change of data structures
> under the hood)...
> > > Scanning the code, I found two more places where similar things
> > > happen.
> > >
> > > - One in set_variable which suffers the same local vs
> > > global problem as lpcfg_set_cmdline.
> > > --> patch attached.
> > >
> > > - One in lpcfg_do_service_parameters() where
> > > copymapy entries for the parameter and its aliases
> > > are cleared: This is done by a full walk of the
> > > list.
> > > This is performance-wise possibly the worst case.
> > > because this is afaik called for each parameter
> > > read from the config each time the config is read.
> > >
> > > Patch for this is following, but I had a small confusion
> > > in my understanding of the copymap... :-)
> > Garming and I found many - too many - things in loadparm that are either
> > just a little too subtle for their own good, or just plain confusing.
> > Some from the code split, some from the kludges I did for the merge, and
> > much from 20 years of history.
> > The good news is that by working in the code and making it ready for
> > more auto-generation, we are already flushing out many strange things
> > that don't need to be true any more (like magic behaviour for -),
> > finding other special cases that don't need to be special any more, and
> > generally making things more consistent. We think we can remove much of
> > the complexity from the loadparm_s3_context case!
> That sounds good.
> Since you got me looking into loadparm again,
> I will also poke around and try to improve
> structure and remove inconsistencies. :)
Given that, I'll get you as much of our cleanup patches in as I can in
the next day or so, so you don't duplicate the work either of us has
already done. My param-after-reviewed branch has many interesting
patches from Garming and I, all of which are looking for review into
master. I'm posting them here has I group them into batches, but all
need to get into master eventually, either in smaller sets or simply
just working though them in the order they are in the that tree.
> > > My plan is to follow up with a patch that introduces
> > > a foreach_alias() function (or so) that takes a callback
> > > to do the action, so that we can have one central
> > > implementation of something that is done to or with
> > > each alias.
> > Sounds good. That is indeed an important O(n^2) case.
> > > There are more occurrences of "-" in the code, e.g. in
> > > lpcfg_next_parameter ..
> > Sure, and there is may have made sense, as lpcfg_next_parameter is like
> > dump, an enumeration case. Happily it is also unused, attached is the
> > patch to just remove it, along with the also-unused lp_is_default.
> > Please review/push.
> Looks good - pushing to autobuild.
Andrew Bartlett http://samba.org/~abartlet/
Authentication Developer, Samba Team http://samba.org
Samba Developer, Catalyst IT http://catalyst.net.nz/services/samba
More information about the samba-technical