From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, MAILING_LIST_MULTI autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 6667 invoked from network); 26 Sep 2023 00:58:24 -0000 Received: from alyss.skarnet.org (95.142.172.232) by inbox.vuxu.org with ESMTPUTF8; 26 Sep 2023 00:58:24 -0000 Received: (qmail 55736 invoked by uid 89); 26 Sep 2023 00:58:49 -0000 Mailing-List: contact supervision-help@list.skarnet.org; run by ezmlm Sender: Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Received: (qmail 55729 invoked from network); 26 Sep 2023 00:58:48 -0000 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=westernsemico.com; s=default; h=Message-ID:Date:To:From:Subject:References: In-Reply-To:Content-Transfer-Encoding:MIME-Version:Content-Type:Sender: Reply-To:Cc:Content-ID:Content-Description:Resent-Date:Resent-From: Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id:List-Help: List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=j4+0A6HBrm58C64CtcIUlES9V4N4egICJvNi0u5Fe80=; b=QODth1ps/wE53FadWFl4G6qiLk nasarSoiocpmOPYQKEHPgBBCJ2KzI0B9Fwlan4uwxMhWUPeiTs94961F0TCgA2vmgv3svv6K2tLso i/LbmtCbk5bD/6A9pWrn25/u+LgXsNBr9x+pZ7Qel4r8nDdHHjNAWMrSqdMj7ZvD/rC9dMBwymqdQ UCEb9BcbYFySliYpfVjMIUomTFxLbW4zyNE7MNRoDZOKKQHhvWwTnKp8DmGWHujqB52pUNEAxTH10 lQ5QFQ6U/0elD+4KcdnpGYzM/9C4lHqVbQI6vabjKl7PiDuubIeniv2bhmugroSe14tL2e0RYTbj7 kr9j5LOg==; Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable In-Reply-To: <20230926004418.24990-2-adam@westernsemico.com> References: <20230926004418.24990-1-adam@westernsemico.com> <20230926004418.24990-2-adam@westernsemico.com> Subject: Re: [PATCH 2/3] s6-rc-update.c: rewrite O(n^2) loop as O(n) complexity From: Adam Joseph To: supervision@list.skarnet.org Date: Mon, 25 Sep 2023 17:57:44 -0700 Message-ID: <169568986462.6030.10556581815632056289@localhost> X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - server220.web-hosting.com X-AntiAbuse: Original Domain - list.skarnet.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - westernsemico.com X-Get-Message-Sender-Via: server220.web-hosting.com: authenticated_id: westwhdn/from_h X-Authenticated-Sender: server220.web-hosting.com: adam@westernsemico.com X-Source: X-Source-Args: X-Source-Dir: X-From-Rewrite: unmodified, already matched 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: >=20 > 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 >=20 > This takes advantage of the fact that invimage is an injective > (partial) function. As discussed on IRC, this commit touches the dependency computation routine= s, 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