From patchwork Mon Apr 25 15:58:14 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 53197 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 6D1993857820 for ; Mon, 25 Apr 2022 16:02:19 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6D1993857820 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1650902539; bh=ayvLBWaAmUglkXeAb9jA6PrIj3L3vSsibSoKqZXxkDY=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=Z/vZvGUW0jXfklGKj4RI3BZUIAiWEIgZgc+7Pu4YlSqN4yBmNVI0Icy1qaXLw1m1x 02RdPQcraEOP8sc7/RLB/2OiOsKpN7UBwudRDUXtp+TWuR2PdWHsYJ4h0XhOaNTrhU Wzs9QUC9RQsVO8+UL1VEznTQvhDFDFdg2ECM5KEY= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd2c.google.com (mail-io1-xd2c.google.com [IPv6:2607:f8b0:4864:20::d2c]) by sourceware.org (Postfix) with ESMTPS id 8AD5E385842E for ; Mon, 25 Apr 2022 15:58:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8AD5E385842E Received: by mail-io1-xd2c.google.com with SMTP id e194so16290984iof.11 for ; Mon, 25 Apr 2022 08:58: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:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=ayvLBWaAmUglkXeAb9jA6PrIj3L3vSsibSoKqZXxkDY=; b=pC53cIaebZDICqJL5vq4RglRxnmmCcLYNGyITIOTowYu5KWEC10TGNjEYcgukkTvWw yzl9XiU/Kh3DF+4gw+cEaqJZw88u/XxaGQed1Il0KUA77/oqOTscAtm52R9GlfWEDolY IiBg+TLXR8A/YXvmainZDNJOHR9A9/VjrjxGoB1xv4fJd/FSgNcDTkj/PI54T8M0VQVK rjqc3Co5tjASkXZTxwLt6mZCq4uZsdaJmHYpGiFhVfl7GnMK5FQRxfYaKUqbyB1Jydyf QWyvaszAuY3u4jXOkuy5HfYuMIDbnxo2AcUbGe/74laAeK44HNjbnoYpyhvbmDFjMAbj Dumw== X-Gm-Message-State: AOAM530oCmPL1CsB+PtYkjp32FISAsH0FSaqBisIru7PRKKUFNNM1l32 VgURRF+0WkpGQEFa4E/20jpV24nJrng= X-Google-Smtp-Source: ABdhPJwPZNI8eCthOc8kQrTpdslaxBKixhmO0yvB+HgCJoB4oM2u6QzJauYyeMyqsskvm5zNL25M3g== X-Received: by 2002:a6b:ee12:0:b0:64d:2f8f:15bb with SMTP id i18-20020a6bee12000000b0064d2f8f15bbmr7155853ioh.16.1650902304758; Mon, 25 Apr 2022 08:58:24 -0700 (PDT) Received: from localhost.localdomain ([173.245.202.37]) by smtp.googlemail.com with ESMTPSA id d3-20020a056e020c0300b002c7b42b4b0esm6519897ile.65.2022.04.25.08.58.24 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 25 Apr 2022 08:58:24 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v3 6/6] elf: Optimize _dl_new_hash in dl-new-hash.h Date: Mon, 25 Apr 2022 10:58:14 -0500 Message-Id: <20220425155814.3558359-6-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220425155814.3558359-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220425155814.3558359-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Noah Goldstein via Libc-alpha From: Noah Goldstein Reply-To: Noah Goldstein Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" Unroll slightly so some of the multiples can be pipelined on out-order machines. Unrolling further started to induce slowdowns for sizes [0, 4] but can help the loop so if larger sizes are the target further unrolling can be beneficial. Results for _dl_new_hash Benchmarked on Tigerlake: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz Time as Geometric Mean of N=25 runs Geometric of all benchmark New / Old: 0.791 type, length, New Time, Old Time, New Time / Old Time fixed, 0, 0.641, 0.658, 0.974 fixed, 1, 1.888, 1.883, 1.003 fixed, 2, 2.712, 2.833, 0.957 fixed, 3, 3.314, 3.739, 0.886 fixed, 4, 4.316, 4.866, 0.887 fixed, 5, 5.16, 5.966, 0.865 fixed, 6, 5.986, 7.241, 0.827 fixed, 7, 7.264, 8.435, 0.861 fixed, 8, 8.052, 9.846, 0.818 fixed, 9, 9.369, 11.316, 0.828 fixed, 10, 10.256, 12.925, 0.794 fixed, 11, 12.191, 14.546, 0.838 fixed, 12, 12.667, 15.92, 0.796 fixed, 13, 14.442, 17.465, 0.827 fixed, 14, 14.808, 18.981, 0.78 fixed, 15, 16.244, 20.565, 0.79 fixed, 16, 17.166, 22.044, 0.779 fixed, 32, 35.447, 50.558, 0.701 fixed, 64, 86.479, 134.529, 0.643 fixed, 128, 155.453, 287.527, 0.541 fixed, 256, 302.57, 593.64, 0.51 random, 2, 11.168, 10.61, 1.053 random, 4, 13.308, 13.53, 0.984 random, 8, 16.579, 19.437, 0.853 random, 16, 21.292, 24.776, 0.859 random, 32, 30.56, 35.906, 0.851 random, 64, 49.249, 68.577, 0.718 random, 128, 81.845, 140.664, 0.582 random, 256, 152.517, 292.204, 0.522 --- elf/dl-new-hash.h | 27 +++++++++++++++++++++++---- 1 file changed, 23 insertions(+), 4 deletions(-) diff --git a/elf/dl-new-hash.h b/elf/dl-new-hash.h index 52eef4e417..b0026706bd 100644 --- a/elf/dl-new-hash.h +++ b/elf/dl-new-hash.h @@ -20,14 +20,33 @@ #define _DL_NEW_HASH_H 1 #include +/* For __glibc_unlikely. */ +#include static uint32_t +__attribute__ ((unused)) _dl_new_hash (const char *s) { - uint32_t h = 5381; - for (unsigned char c = *s; c != '\0'; c = *++s) - h = h * 33 + c; - return h; + unsigned int h = 5381; + unsigned char c0, c1; + for (;;) + { + c0 = *s; + /* Unlikely length zero string so evens will be slightly less + common. */ + if (__glibc_unlikely (c0 == 0)) + { + return h; + } + + c1 = *(s + 1); + if (c1 == 0) + { + return h * 33 + c0; + } + h = 33 * 33 * h + 33 * c0 + c1; + s += 2; + } }