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 6166 invoked from network); 26 Sep 2023 00:45:12 -0000 Received: from alyss.skarnet.org (95.142.172.232) by inbox.vuxu.org with ESMTPUTF8; 26 Sep 2023 00:45:12 -0000 Received: (qmail 54671 invoked by uid 89); 26 Sep 2023 00:45:37 -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 54664 invoked from network); 26 Sep 2023 00:45:37 -0000 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=westernsemico.com; s=default; h=Content-Transfer-Encoding:MIME-Version: References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender:Reply-To: Content-Type: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=BHBaDY3DZ2PbI8diT7WQAzkGV5mwuM49f2R8OdxHzhI=; b=W3yMf4+YJyxPNFlvder/Mb/k0n VQGihe3i6bxnSdOcnyZPE+hcrG3NCIXe1E8Lf1g9MScc52oexzl0W/yXQQrruoez3gIqhKf0yCwke YOAHH6jP5zJTuZTIsYq8YOGtFKFWMOUAXnpZmUUYGXqkK4V3/YfkDm0hxrx+2fWjCJW7mpPLbQzt+ R9/G1LaJ6rafRO3I7Te4bawm1mgzLH+ab4n5QjaaHOxuEXwOzmcJrn/pvRtw3qZ8GBCA8n5oXZAMz kEjaT6HRMEVfjs1GeSth1DgozETwHSC9EYD5O1ojzGqZORJx6XU7SXvUmBaBkQ73GlPqn3IJL3DOn JCJCvhLg==; From: Adam Joseph To: supervision@list.skarnet.org Cc: Adam Joseph Subject: [PATCH 2/3] s6-rc-update.c: rewrite O(n^2) loop as O(n) complexity Date: Mon, 25 Sep 2023 17:44:17 -0700 Message-ID: <20230926004418.24990-2-adam@westernsemico.com> X-Mailer: git-send-email 2.41.0 In-Reply-To: <20230926004418.24990-1-adam@westernsemico.com> References: <20230926004418.24990-1-adam@westernsemico.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit 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 Prior to this commit, s6-rc-update had a loop with the following comment: This part runs in O(oldn*newn). There are no syscalls in the loop, so it should still be negligible unless you have 10k services. The loop does the following: for each old service which was already up for each new service if the old service converts to the new service, set some new service flags based on old service flags 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. Signed-off-by: Adam Joseph --- src/s6-rc/s6-rc-update.c | 15 ++++++--------- 1 file changed, 6 insertions(+), 9 deletions(-) diff --git a/src/s6-rc/s6-rc-update.c b/src/s6-rc/s6-rc-update.c index c1074de..e0726a2 100644 --- a/src/s6-rc/s6-rc-update.c +++ b/src/s6-rc/s6-rc-update.c @@ -257,20 +257,17 @@ static void compute_transitions (char const *convfile, unsigned char *oldstate, /* Convert the old state to the new state: if an old service is up, the new service will be either up or wanted up. - This part runs in O(oldn*newn). There are no syscalls in the loop, - so it should still be negligible unless you have 10k services. */ - i = oldn ; + i = newn; while (i--) - if (oldstate[i] & OLDSTATE_WAS_UP) { - unsigned int j = newn ; - while (j--) - if (bitarray_peek(conversion_table + i * newm, j)) - newstate[j] |= - (oldstate[i] & OLDSTATE_WANT_DOWN_OR_RESTART) + if (newstate[i] & NEWSTATE_IS_CONVERSION_TARGET) { + if (oldstate[invimage[i]] & OLDSTATE_WAS_UP) { + newstate[i] |= + (oldstate[invimage[i]] & OLDSTATE_WANT_DOWN_OR_RESTART) ? NEWSTATE_INCLUDE_IN_UP_TRANSITION : (NEWSTATE_WAS_UP | NEWSTATE_WANT_UP_AFTER_CLOSURE) ; + } } -- 2.41.0