From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [63.128.21.124]) by sourceware.org (Postfix) with ESMTP id 385913857C67 for ; Mon, 26 Oct 2020 09:52:10 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 385913857C67 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-362-cPlhDxX2Od6GVamXtBoIZw-1; Mon, 26 Oct 2020 05:52:07 -0400 X-MC-Unique: cPlhDxX2Od6GVamXtBoIZw-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id DBE211868411 for ; Mon, 26 Oct 2020 09:52:06 +0000 (UTC) Received: from calimero.vinschen.de (ovpn-113-110.ams2.redhat.com [10.36.113.110]) by smtp.corp.redhat.com (Postfix) with ESMTPS id ADC0A5B4AF for ; Mon, 26 Oct 2020 09:52:06 +0000 (UTC) Received: by calimero.vinschen.de (Postfix, from userid 500) id 58006A81051; Mon, 26 Oct 2020 10:52:05 +0100 (CET) Date: Mon, 26 Oct 2020 10:52:05 +0100 From: Corinna Vinschen To: newlib@sourceware.org Subject: Re: [PATCH 00/11] Synchronize with FreeBSD Message-ID: <20201026095205.GA5492@calimero.vinschen.de> Reply-To: newlib@sourceware.org Mail-Followup-To: newlib@sourceware.org References: <20201019160522.15408-1-sebastian.huber@embedded-brains.de> MIME-Version: 1.0 In-Reply-To: <20201019160522.15408-1-sebastian.huber@embedded-brains.de> X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8 Content-Disposition: inline X-Spam-Status: No, score=-7.0 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H5, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: newlib@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Newlib mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 26 Oct 2020 09:52:11 -0000 On Oct 19 18:05, Sebastian Huber wrote: > This patch set adds some changes after the last synchronization point with > FreeBSD to Newlib. In a simple benchmark, the node insert/extract performance > improved. > > In an intermediate step of this patch set the node color member is removed. > Later it is restored. I propose to keep the patch series as is to have the > same change history as FreeBSD. > > FreeBSD also changed the implementation to so that the node color is stored in > the parent pointer in follow up patches. In addition, they changed the > algorithm from red-black to weak AVL. These changes are NOT INCLUDED, since > they break the ABI/API. I did some rough benchmarking and was not immediately > convinced that the new implementation in FreeBSD is better. > > dougm (10): > Correct the use of RB_AUGMENT in the RB_TREE > For the case when RB_REMOVE requires a nontrivial > RB_REMOVE invokes RB_REMOVE_COLOR either when > Remove from RB_REMOVE_COLOR some null checks > To reduce the size of an rb_node, drop the color > Restore an RB_COLOR macro, for the benefit of > Fixup r361997 by balancing parens. Duh. > Linuxkpi uses the rb-tree structures > In concluding RB_REMOVE_COLOR, in the case when > Define RB_SET_PARENT to do all assignments > > trasz (1): > Add RB_REINSERT(3), a low overhead alternative to > > newlib/libc/include/sys/tree.h | 273 ++++++++++++++++----------------- > 1 file changed, 130 insertions(+), 143 deletions(-) > > -- > 2.26.2 Please go ahead. Thanks, Corinna