From owner-freebsd-current@freebsd.org Fri Jul 10 17:28:19 2020 Return-Path: <owner-freebsd-current@freebsd.org> Delivered-To: freebsd-current@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id B70D536EBE5 for <freebsd-current@mailman.nyi.freebsd.org>; Fri, 10 Jul 2020 17:28:19 +0000 (UTC) (envelope-from unkadoug@gmail.com) Received: from mail-qk1-x730.google.com (mail-qk1-x730.google.com [IPv6:2607:f8b0:4864:20::730]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (2048 bits) client-digest SHA256) (Client CN "smtp.gmail.com", Issuer "GTS CA 1O1" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4B3Kkp5VDbz4shw for <freebsd-current@freebsd.org>; Fri, 10 Jul 2020 17:28:18 +0000 (UTC) (envelope-from unkadoug@gmail.com) Received: by mail-qk1-x730.google.com with SMTP id b4so6001490qkn.11 for <freebsd-current@freebsd.org>; Fri, 10 Jul 2020 10:28:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:subject:message-id:date:user-agent:mime-version :content-transfer-encoding:content-language; bh=ftO8u8nuGKtqUXqMb4vAxVWDv+yFvrxJBOi1rWm9BSc=; b=hGnf57z6UlQ4NYZy7TETmEUZfB/oimeuGvlZpTNMMz3UC6NgwO8v6ib/JcjoW3a4qK 0jF0fNEdVvpSQaadWX2qDiy1OlQJdSuVA+fe+Yc9LKwjD6bZeZPelvnRIZllgxTjoBv1 uJ6fKyWGVgT94nwUQ8OILzY84ZKLRD7UBQjqNpn9yODIso/kq+J4FnAegCbkS7LIPS1O IHzJYF+D06tjtxdtI+mngEsYbOowkc6Q4MHH6VaoDPlyoOJS4sjzP9l2n5tE4TBemBjH OkTq0b3KrtnXvbt0JoPacsOloZi9waAM7ToGFrXBrdthqgy3Looo4hreHpU/Fj4gxo+r 3hyw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:message-id:date:user-agent :mime-version:content-transfer-encoding:content-language; bh=ftO8u8nuGKtqUXqMb4vAxVWDv+yFvrxJBOi1rWm9BSc=; b=LEOyvzjd3yzwCqTLYg/6qhSKi7D1hvonO0vbGAFIQeCDLSjb2WPhYRxNpicfK66lIU FjpMRISJ0SPNG1o0no/7PJj3NAkeZmb7da/LmpyNMrDvcQ5Lfn+QVu1BA+YVFZXXylbl lOlbiU1oW2NExTA4S7t7E/ZsqSaCJDRtbONHdeIxA/L8dk6Q6xf9ljQwYb3R3zX+LCZR fJlAh5qoSGmMNllm/YDycrGv4T87phgO/O5DbunfigDCjhg+2e36UGgOgj1LnbcqYyu8 Yn2E5p0ryTwQlCFksPkLnzPohTIdbba7kaI+0rouUfQQR7s7YO9h+RPf0aZ7Pv79oU9e QY7g== X-Gm-Message-State: AOAM5300q7J0vzHaEBHwBd358Mhi9W4AyqChjSlymOcopRakxDdc3ZDl dwBWIp3bV2JVuz7LEnZvInd+qm5kMs8= X-Google-Smtp-Source: ABdhPJyKUhMqz4OZi0EOQtxa8HIembaFflKYuWXkf/4bZazUA3C647oGC5iuWB2zYkKUCVB9aIK/aw== X-Received: by 2002:a37:8905:: with SMTP id l5mr66475133qkd.302.1594402097417; Fri, 10 Jul 2020 10:28:17 -0700 (PDT) Received: from 108-254-203-202.lightspeed.hstntx.sbcglobal.net (108-254-203-202.lightspeed.hstntx.sbcglobal.net. [108.254.203.202]) by smtp.gmail.com with ESMTPSA id u22sm8540569qtb.23.2020.07.10.10.28.16 for <freebsd-current@freebsd.org> (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 10 Jul 2020 10:28:17 -0700 (PDT) From: Doug Moore <unkadoug@gmail.com> X-Google-Original-From: Doug Moore <dougm@freebsd.org> To: freebsd-current@freebsd.org Subject: A proposal to redefine RB trees Message-ID: <b749d0d9-0b83-b6d3-2214-cd9adb764db0@freebsd.org> Date: Fri, 10 Jul 2020 12:28:16 -0500 User-Agent: Mozilla/5.0 (X11; FreeBSD i386; rv:68.0) Gecko/20100101 Thunderbird/68.9.0 MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Content-Language: en-US X-Rspamd-Queue-Id: 4B3Kkp5VDbz4shw X-Spamd-Bar: -- Authentication-Results: mx1.freebsd.org; dkim=pass header.d=gmail.com header.s=20161025 header.b=hGnf57z6; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (mx1.freebsd.org: domain of unkadoug@gmail.com designates 2607:f8b0:4864:20::730 as permitted sender) smtp.mailfrom=unkadoug@gmail.com X-Spamd-Result: default: False [-2.15 / 15.00]; ARC_NA(0.00)[]; RCVD_VIA_SMTP_AUTH(0.00)[]; R_DKIM_ALLOW(-0.20)[gmail.com:s=20161025]; NEURAL_HAM_MEDIUM(-1.00)[-0.997]; FROM_HAS_DN(0.00)[]; R_SPF_ALLOW(-0.20)[+ip6:2607:f8b0:4000::/36:c]; FREEMAIL_FROM(0.00)[gmail.com]; MIME_GOOD(-0.10)[text/plain]; PREVIOUSLY_DELIVERED(0.00)[freebsd-current@freebsd.org]; TO_DN_NONE(0.00)[]; RCPT_COUNT_ONE(0.00)[1]; NEURAL_HAM_LONG(-1.01)[-1.015]; RCVD_COUNT_THREE(0.00)[3]; MID_RHS_MATCH_TO(1.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; DKIM_TRACE(0.00)[gmail.com:+]; DMARC_POLICY_ALLOW(-0.50)[gmail.com,none]; RCVD_IN_DNSWL_NONE(0.00)[2607:f8b0:4864:20::730:from]; NEURAL_HAM_SHORT(-0.14)[-0.139]; FROM_EQ_ENVFROM(0.00)[]; MIME_TRACE(0.00)[0:+]; FREEMAIL_ENVFROM(0.00)[gmail.com]; ASN(0.00)[asn:15169, ipnet:2607:f8b0::/32, country:US]; RCVD_TLS_ALL(0.00)[]; DWL_DNSWL_NONE(0.00)[gmail.com:dkim] X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.33 Precedence: list List-Id: Discussions about the use of FreeBSD-current <freebsd-current.freebsd.org> List-Unsubscribe: <https://lists.freebsd.org/mailman/options/freebsd-current>, <mailto:freebsd-current-request@freebsd.org?subject=unsubscribe> List-Archive: <http://lists.freebsd.org/pipermail/freebsd-current/> List-Post: <mailto:freebsd-current@freebsd.org> List-Help: <mailto:freebsd-current-request@freebsd.org?subject=help> List-Subscribe: <https://lists.freebsd.org/mailman/listinfo/freebsd-current>, <mailto:freebsd-current-request@freebsd.org?subject=subscribe> X-List-Received-Date: Fri, 10 Jul 2020 17:28:19 -0000 I have a change ready to commit at https://reviews.freebsd.org/D25480 that would redefine the tree-balancing criteria for the RB tree macros, changing them from red-black trees to the weak-AVL trees described in the paper "Rank-balanced trees" by Haeupler, Sen and Tarjan. By happy coincidence (or the authors' deliberate scheme), the letters RB can represent "Rank-balanced" as easily as "red-black", so no global renaming is required. This change does not add or remove fields. It does keep a tighter balance constraint than red-black trees, so that in conditions where balancing really matters (for example, when inserting tree nodes in sorted order), weak-avl trees produce a better balanced tree and faster lookups. That same tighter balance constraint means that an insert operation is more likely to lead to restructuring of the tree than before, for which there is a small performance cost. The original paper at http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf provides more analysis of the relative benefits of weak-avl trees. Are there any objections? Doug Moore (dougm@freebsd.org)