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 [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 414553858C51 for ; Tue, 21 Jun 2022 17:12:36 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 414553858C51 Received: from mail-ej1-f70.google.com (mail-ej1-f70.google.com [209.85.218.70]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-216-ixoovmbaNTWD4l52bLkTrw-1; Tue, 21 Jun 2022 13:12:35 -0400 X-MC-Unique: ixoovmbaNTWD4l52bLkTrw-1 Received: by mail-ej1-f70.google.com with SMTP id k7-20020a1709062a4700b006fe92440164so5162761eje.23 for ; Tue, 21 Jun 2022 10:12:34 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=aR6pTRv433NoiITmJhxG8OtaDJVDrPSg0CIbWcc+hZ0=; b=RMWVK8s4HLyfd2A/ZxzFAIwwdywcMCM9MVT+TcRgT9rr1Po9ot1S5ScDwO1sHEjmIY p7QmXwqQt01Gcpv8a++EpN2dyaNffVw/oqch0y3c0JWTRk9rONrVocIVifMeau+LGTUL e8476hqRgjOW1R0dEZQs8Pday7RFVcdCbdbEJldtrutKz8/2960mTQFg8e2pvc5OkEO9 +nZog4XzuZPZUwx6WKyKN3QcNvH2ik/qWDOKxWH7trkt0oEC4Ja4qo9TfxXfESWF4nFo bO2AK1y+5mxm8gY8oXyghB4r0cnyosuTq8thnaDgOYVrtXXI+nvMqYYUGU5Am1Lscnr4 USog== X-Gm-Message-State: AJIora8UHRa66/mQqdYgZIzDOtSCCiF6YBzr7MYmif7wHFP1GAuIEqCj FTXguHtqfMOAtq+SWE+PnkHMf9dNIVR54lq2G05a7NeuHhYr8/jF7X9riXRnUpCs9t+ekOtyv9T qq1JcqN3eyMH607e9IQuO8207HANoCxo= X-Received: by 2002:a17:906:8301:b0:6e4:896d:59b1 with SMTP id j1-20020a170906830100b006e4896d59b1mr25784981ejx.396.1655831553846; Tue, 21 Jun 2022 10:12:33 -0700 (PDT) X-Google-Smtp-Source: AGRyM1sCuI2jzuibxiel/I8oG8OkpUDSKGQIb2/5oCS008Xp3b8Rk59ukLRIJU4dMDYTVP0yTwCOb4hfoYB+5yXcY/I= X-Received: by 2002:a17:906:8301:b0:6e4:896d:59b1 with SMTP id j1-20020a170906830100b006e4896d59b1mr25784891ejx.396.1655831552640; Tue, 21 Jun 2022 10:12:32 -0700 (PDT) MIME-Version: 1.0 References: <8df25ff1-5b70-4030-768b-965f92870eb9@gmail.com> In-Reply-To: <8df25ff1-5b70-4030-768b-965f92870eb9@gmail.com> From: Jonathan Wakely Date: Tue, 21 Jun 2022 18:12:21 +0100 Message-ID: Subject: Re: [PATCH] Enhance _Hashtable for range insertion 0/5 To: =?UTF-8?Q?Fran=C3=A7ois_Dumont?= Cc: "libstdc++@gcc.gnu.org" , gcc-patches X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-7.2 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, KAM_NUMSUBJECT, RCVD_IN_DNSWL_LOW, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 21 Jun 2022 17:12:38 -0000 On Mon, 20 Jun 2022 at 17:58, Fran=C3=A7ois Dumont via Libstdc++ wrote: > > Hi > > Here is a series of patch to enhance _Hashtable behavior mostly in the > context of range insertion. I also start considering the problem of > memory fragmentation in this container with 2 objectives: > > - It is easier to find out when you're done with the elements of a > bucket if the last node of the bucket N is the before-begin node of > bucket N + 1. > > - It is faster to loop through nodes of a bucket if those node are close > in memory, ultimately we should have addressof(Node + 1) =3D=3D > addressof(Node) + 1 Have these changes been profiled or benchmarked? Is it measurably faster? By how much? > [1/5] Make more use of user hints as both insertion and allocation hints. > > [2/5] Introduce a new method to check if we are still looping through > the same bucket's nodes > > [3/5] Consider that all initializer_list elements are going to be inserte= d > > [4/5] Introduce a before-begin cache policy to remember which bucket is > currently pointing on it > > [5/5] Prealloc nodes on _Hashtable copy and introduce a new assignment > method which replicate buckets data structure > > Fran=C3=A7ois >