Re: [PATCH 2/3] s6-rc-update.c: rewrite O(n^2) loop as O(n) complexity

[Adam Joseph <adam@westernsemico.com>]

Quoting Adam Joseph (2023-09-25 17:44:17)
> The loop is O(n^2) due to the nested iteration.  We can rewrite this
> with a single iteration by making use of the invimage[] array, which
> maps from new services to old services:
> 
>    for each new service
>      if *ANY* old service converts to the new service,
>        set some new service flags based on that old service's flags
> 
> This takes advantage of the fact that invimage is an injective
> (partial) function.

As discussed on IRC, this commit touches the dependency computation routines,
which are quite delicate and (at this point) battle-tested; tampering with them
probably isn't worth the mostly-theoretical performance benefit.

I wrote this commit mainly because it seemed like there was an easy way to do
this in O(n) time, and the fact that it hadn't been done that way must mean that
I had overlooked something important.  If anybody sees an obvious mistake in
this commit, please do let me know -- it's a sign that I misunderstood
something.  Otherwise there's no need to apply this patch.

  - a