From nobody Thu Sep 15 16:59:23 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 4MT3Mb263cz4cp6n; Thu, 15 Sep 2022 16:59:23 +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 4MT3Mb1bVdz3TX3; Thu, 15 Sep 2022 16:59:23 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1663261163; 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=hk49UYFtkVCUuktr+oXvZ0jpCgUEdVJXNMK/yPky7x0=; b=E+24BuKC82vsLSdjRxZX7g1CkIsfkqTN0V9c5alWs1eFJ6Y7fj7PavzuxrUdVELKP8K09/ Ac/BBHa06d42eaiIE7QvefXIJ8VyOXNUZEtaxFpz0qnb384Z4aZ1+b0oSCXQeJ4QnW/stQ kupDp7OCblZ9H8cAFbhyONK4haYRZ4TS/m44laLUC7plAGfKO7RTLtKew2bqRLn4SdJDQ2 JIpPtsinA7/pALVqpUx6fgp6Uhfs7+ccDqGE0nGvtBTIraMyOKlrUrwcjUBb9AbYFVO2Wj NxUFXFaUXSA1rPJpNoofmNY7IHoFsyPX+PrTbkUyP5b3+kfCs7ILOBbj9visNg== 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 4MT3Mb0dxDz14b3; Thu, 15 Sep 2022 16:59:23 +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 28FGxNA5073303; Thu, 15 Sep 2022 16:59:23 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 28FGxNI0073302; Thu, 15 Sep 2022 16:59:23 GMT (envelope-from git) Date: Thu, 15 Sep 2022 16:59:23 GMT Message-Id: <202209151659.28FGxNI0073302@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Doug Moore Subject: git: f42139db6396 - stable/13 - 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/stable/13 X-Git-Reftype: branch X-Git-Commit: f42139db63963da134b9075382cac239a52fd940 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1663261163; 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=hk49UYFtkVCUuktr+oXvZ0jpCgUEdVJXNMK/yPky7x0=; b=gZ6qcXdf/v0DnSi0Dik4nU+Xx/Sx+fWoHX4O6dgO9KcQPOQikg0BzhCVwE+A9PO0MrvNNo qRJ06ol0lLIpAPHGULUfKKXYnP53eY4oH9iA5lXy02YH7bl6F9Urea9unIJeFIFvUtdBOO yZoObdlkdqDn/isD89IKWJfmKcksE2fbG5ArXb64CAbk86CDrjK/xbcKMVY29kxw3EfPxy YDiXdJ56TqElctH5wi+KNB8jpCWvfhGsMh+faDaPcCwHMdtXSXBHOeQ4a0SbQY0Ae1kZQy zcI1a5Pmf6HtgLod+SfUYQvcfx4HG2YjO5Z3GfU32ntXdHQgsFEQ68CB4Z0z8w== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1663261163; a=rsa-sha256; cv=none; b=Cg6PH7/Tw+j+ZzbYnRBRNdJx+2XHbYpzakBximFfTnTBOUKPl5maZUykXr7djfQYN4ZAr7 r4nDb7g3bGdRusjOur/wyKlTtqqEfiWxri0Vr1sch8Ixb9f9vRyk2u8mTNDVeKZx9m1iKm 67D21NBZCNWkojCTBV8y3hWeSwZC7+8cMIQNX909b8BSngVK6Idu56y54csiyte1TU04II p6owLD5ynU4+eUQKtwcqCGhxjCsUg8kvi6v/jvGILP/FAUtbinTsH7E18pP8Y0n9lAoKHv gusZwH3gqCTOzYew3hNQbXDXqdkriYnsbOQe+JhXT6MOJrhYMj1g6XgV94GZKQ== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch stable/13 has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=f42139db63963da134b9075382cac239a52fd940 commit f42139db63963da134b9075382cac239a52fd940 Author: Doug Moore AuthorDate: 2022-08-25 07:26:04 +0000 Commit: Doug Moore CommitDate: 2022-09-15 16:58:31 +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 (cherry picked from commit b6ce129d24ffe393c43378b1c922d1e56ea2be67) --- 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 1f0a260e25a7..88d15bda4177 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); \