From nobody Thu Aug 25 07:27:44 2022 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4MCvgj2GJzz4b66P; Thu, 25 Aug 2022 07:27:45 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4MCvgj1jr8z3W1R; Thu, 25 Aug 2022 07:27:45 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1661412465; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=2ZBvv0ooqsxTNeC2OB0sjWGbSf6HVg2fZE5uBh7werE=; b=m6FRprIDms8HXoCMaFjqGWWyARtcJ9cf2otd00L1TvlTif0xIJRJbOgOtRNt4SiaIQB12g kDmK1VCdKfRccFadSUafUmgmlalaP9IzamV9xP+E8d94Xj6qa9kT1uVY8omTw/fWloHe/Q W0LJLcJL5Pnzq/3w17YG0PnOPI9rrK04gYQmj8AJjurA45XrP1P/c4y5jkvkGYIUrK26Yg Z79W+fdZAHyWr2Ggy2Pt3K8PHgADhuAqnbn9MyuksnEGUnyKaFEualYS7NABlZeRyPxTVd dcOfGv2Jn5y7wJX6u5IduTCxWjsaCVNrbb+v54t91WvVmJg0J82xfd0FZrz/mQ== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4MCvgj0WVNzfyJ; Thu, 25 Aug 2022 07:27:45 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 27P7Ril3084743; Thu, 25 Aug 2022 07:27:44 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 27P7Ri6M084742; Thu, 25 Aug 2022 07:27:44 GMT (envelope-from git) Date: Thu, 25 Aug 2022 07:27:44 GMT Message-Id: <202208250727.27P7Ri6M084742@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Doug Moore Subject: git: b6ce129d24ff - main - rb_tree: optimize rb_insert List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: dougm X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: b6ce129d24ffe393c43378b1c922d1e56ea2be67 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1661412465; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=2ZBvv0ooqsxTNeC2OB0sjWGbSf6HVg2fZE5uBh7werE=; b=PeWISt0vKERTceD7ZuE2vZcqXeJa6pXBF2Ld16qGQe3Z2LSyxLNikgywgerhMSjZrLKe1j S8Jzk8zb3l1knWVpNN5SAQoGXs5x/kpc/DXciE3i0LA4cpyvtWiMyglm3EwTyTVZmX5izJ 31/vX4BWVa/s5nnUKmN/5K8CqyZn3FdNfzRGVNdp5CEHZi5M7K7oHozMOB6AYZsoLh3g1M Y0Tvn4FEcbnth8gPorFswdxQuI4QYUeivVdI1yLhwhdA7YqcflTwgu7vyDca6HbkWkEh6J /aihNoH8hcjjkdjIBWhQaJEes+G1GbwCmOJ49KZNGHZKQA8m/L/gPy8yN1K0pg== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1661412465; a=rsa-sha256; cv=none; b=vBp3un63jwgXjGtlM9MaoYfAV5lbKYCbiIUKxS2pJWY3dZAJwwPFmhAbCKOO05BCFWAk5l +Micyo8iq5tlW4ZS6xzhT9XS8h+TkpU9rB8vo9/SRuGuKSvDS7Yps4MqSgXbb+XEcUemCz MGz7+5BVCWkhTNSOtecu6NgBy3ydTk02UICbliGBfSwYFaNnO/JGv3fgVz/wVhoNDPXtx2 RUmBh+HIvhQV+J/xRgkjLPycN3JyeBAB9xQ0lI+2I79n21gOTSmn/EBQlZCNIGoLgrTrH3 oIy/StKWZkZKFa1Q6256Rh4zW9hbWIk63QSiCiGf0X7K331AMziZbmnXiFtKSg== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=b6ce129d24ffe393c43378b1c922d1e56ea2be67 commit b6ce129d24ffe393c43378b1c922d1e56ea2be67 Author: Doug Moore AuthorDate: 2022-08-25 07:26:04 +0000 Commit: Doug Moore CommitDate: 2022-08-25 07:26:04 +0000 rb_tree: optimize rb_insert In searching for where to insert a new node, RB_INSERT discards the address of the pointer that will have to be modified, so that it must find it again from the values of 'parent' and 'comp'. Stop discarding that address, and so avoid having to recompute it. Reviewed by: alc MFC after: 3 weeks Differential Revision: https://reviews.freebsd.org/D36317 --- sys/sys/tree.h | 21 ++++++++------------- 1 file changed, 8 insertions(+), 13 deletions(-) diff --git a/sys/sys/tree.h b/sys/sys/tree.h index 1d4271c2144a..35c6b28be868 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -728,26 +728,21 @@ attr struct type * \ name##_RB_INSERT(struct name *head, struct type *elm) \ { \ struct type *tmp; \ + struct type **tmpp = &RB_ROOT(head); \ struct type *parent = NULL; \ - __typeof(cmp(NULL, NULL)) comp = 0; \ - tmp = RB_ROOT(head); \ - while (tmp) { \ + \ + while ((tmp = *tmpp) != NULL) { \ parent = tmp; \ - comp = (cmp)(elm, parent); \ + __typeof(cmp(NULL, NULL)) comp = (cmp)(elm, parent); \ if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ + tmpp = &RB_LEFT(parent, field); \ else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ + tmpp = &RB_RIGHT(parent, field); \ else \ - return (tmp); \ + return (parent); \ } \ RB_SET(elm, parent, field); \ - if (parent == NULL) \ - RB_ROOT(head) = elm; \ - else if (comp < 0) \ - RB_LEFT(parent, field) = elm; \ - else \ - RB_RIGHT(parent, field) = elm; \ + *tmpp = elm; \ name##_RB_INSERT_COLOR(head, elm); \ RB_UPDATE_AUGMENT(elm, field); \ return (NULL); \