From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x52e.google.com (mail-ed1-x52e.google.com [IPv6:2a00:1450:4864:20::52e]) by sourceware.org (Postfix) with ESMTPS id 851DE3858C2C; Mon, 20 Jun 2022 16:57:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 851DE3858C2C Received: by mail-ed1-x52e.google.com with SMTP id eo8so16023514edb.0; Mon, 20 Jun 2022 09:57:25 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent:from :subject:to:cc:content-language:content-transfer-encoding; bh=fYwrr2IhoklETldo6muWoSaUvaomqXaYjJ/638KF4qw=; b=5crVdW+XpVqPCGzIsWSqtNhg7xTpQKHhVMpQrXEPz/0T7A+RZC7B8ziWzY3zjFmV9C tCsIgQxPbBlExHmfC0mei34H5lUGmMK35OebL0onXyswN+Q80Aobuam1l1a9OONhOyVP R86uBcvtL24UZ12Qq7VLqw/8U3MWgd8RRxRRIC1LPKThFyMjS5jskG6XbIvIG/YhSeCF nol08uN8QBhAFfKC1nurlBAkcPgl9DBoOb627OVbg1UDSxN0PLiVvqDSwOl9Qb+xzt8r b0ThaZi/xQdlXtqpbOlf3cQdsKROSg0ZNCrXJjkXWZr54acd6lR4mk0Ql0wk56LRiUpI pygQ== X-Gm-Message-State: AJIora8f/dCXt7NVIpXFAb4IT71l3xcl+aCcWJccTXUMgO1lmXZxcQ0N YZ/s7B+82UUL6r0jwzvo9c+Rsl28Z9U= X-Google-Smtp-Source: AGRyM1sNZxEkPKAa5xWG+fCUeX9Jv6ofVsbU9Y6mzh7s7RGJXahVqei6pGG0uuwusR8WIRzB+veXdw== X-Received: by 2002:a05:6402:329a:b0:435:8935:e95d with SMTP id f26-20020a056402329a00b004358935e95dmr4632783eda.257.1655744243664; Mon, 20 Jun 2022 09:57:23 -0700 (PDT) Received: from [10.126.3.254] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id gg19-20020a170906899300b00715705dd23asm6228518ejc.89.2022.06.20.09.57.21 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 20 Jun 2022 09:57:23 -0700 (PDT) Message-ID: <8df25ff1-5b70-4030-768b-965f92870eb9@gmail.com> Date: Mon, 20 Jun 2022 18:57:19 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.9.1 From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Subject: [PATCH] Enhance _Hashtable for range insertion 0/5 To: "libstdc++@gcc.gnu.org" Cc: gcc-patches Content-Language: fr Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-0.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, KAM_NUMSUBJECT, RCVD_IN_BARRACUDACENTRAL, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=no 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: Mon, 20 Jun 2022 16:57:28 -0000 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) == addressof(Node) + 1 [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 inserted [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çois