From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pj1-x1032.google.com (mail-pj1-x1032.google.com [IPv6:2607:f8b0:4864:20::1032]) by sourceware.org (Postfix) with ESMTPS id AAAE2385842B for ; Wed, 27 Apr 2022 16:20:17 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org AAAE2385842B Received: by mail-pj1-x1032.google.com with SMTP id l11-20020a17090a49cb00b001d923a9ca99so2162379pjm.1 for ; Wed, 27 Apr 2022 09:20:17 -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=f1uQcd9jPxVsEJgrC5lXmNN2ckphVFPIW5oNfEn4My0=; b=OwvkBdJUrnVQhulW3q7rv/FljeW9OZp6dyOcQxDtEyuH/yS1teyBhs7gOjd+r+NssJ dcpMLHheLnMZ/iCyEQWvyIyB5Z7W4OzCExw2SEWDTmqmosO/pATjBv4aGd3PlBgp7gH3 ZS14NzRiwsaEo8jKWwt6y+OHsn7REUvP3AVvsW+ATBxMyi971W9T0h5+TQgEuHvHEvnU SXZOEJVOsKtPQg/ui24NXSWyvcgke8ql1NbDjlRTsFBIfHpAA3xtk5AbO5xiqGfprCo+ dv19bth327j8yJXb9CaIEccxthFve8b+lPRjJM/RjHEQYeLW49XS6dyFY9rAo/vov2KM c8YQ== X-Gm-Message-State: AOAM532VwDaN0wOLrUj/LnWKb9bj2y0V+i6JVr5MpKplY/tVViuAuHrd Qx34aiJS7S+0vFTOHBGOd99O8nrZ27E= X-Google-Smtp-Source: ABdhPJzkfN19DMvO5VgMoXnmOZY+v959TmZzgTSL14X3/ZBTlF7xKGgYbKHxCvYmTGTinewlS7Ab1w== X-Received: by 2002:a17:902:e393:b0:15c:f1c1:c527 with SMTP id g19-20020a170902e39300b0015cf1c1c527mr22051753ple.22.1651076416542; Wed, 27 Apr 2022 09:20:16 -0700 (PDT) Received: from localhost.localdomain ([64.145.94.63]) by smtp.googlemail.com with ESMTPSA id j13-20020a17090a2a8d00b001cd4989fed3sm7565645pjd.31.2022.04.27.09.20.15 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 27 Apr 2022 09:20:16 -0700 (PDT) From: Noah Goldstein To: libc-alpha@sourceware.org Subject: [PATCH v4 6/6] elf: Optimize _dl_new_hash in dl-new-hash.h Date: Wed, 27 Apr 2022 11:20:02 -0500 Message-Id: <20220427162002.2180312-6-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220427162002.2180312-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220427162002.2180312-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit 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-List-Received-Date: Wed, 27 Apr 2022 16:20:19 -0000 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 | 26 ++++++++++++++++++++++---- 1 file changed, 22 insertions(+), 4 deletions(-) diff --git a/elf/dl-new-hash.h b/elf/dl-new-hash.h index 40d88c81f9..79a2d79465 100644 --- a/elf/dl-new-hash.h +++ b/elf/dl-new-hash.h @@ -20,15 +20,33 @@ #define _DL_NEW_HASH_H 1 #include +/* For __glibc_unlikely. */ +#include static inline 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; + } } -- 2.25.1