From patchwork Thu Apr 14 04:12:31 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 52902 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 14B233858430 for ; Thu, 14 Apr 2022 04:16:36 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 14B233858430 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1649909796; bh=5SQyRzZaAlxxr8eojHh7UsVRyYEJlv+o47sox7yK5h4=; 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=Uxm2nVZReovMrwj9kmQCFH0psiLGsTPIjef72N3g1Q74aLqGFEeR7LdVxpufUuSsM d/cu5krxymV5n2LiNOfw8ztt9ca04wS/9dhVnvpUOijqxHi45sYLcmxPycNPpUMSDq Xn4/CEUW6h9yyWFZKKDK+V9vcCTFGnWN1L9fHphs= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-il1-x136.google.com (mail-il1-x136.google.com [IPv6:2607:f8b0:4864:20::136]) by sourceware.org (Postfix) with ESMTPS id 7E5463857C4A for ; Thu, 14 Apr 2022 04:12:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 7E5463857C4A Received: by mail-il1-x136.google.com with SMTP id e1so2406964ile.2 for ; Wed, 13 Apr 2022 21:12:43 -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=5SQyRzZaAlxxr8eojHh7UsVRyYEJlv+o47sox7yK5h4=; b=BcxUOOnm+Qz7CmTosU9PR5K45jN6wp/glo8TPYQqZwhfw+GYY4vcFMnZIEjYDcjDcm jxLVkw7Sl0txQReDIM/pybBKMZ8/fgQvpecScB2iRCOWGbWJUdOm/Bhl45l5RJiQ6PdS OWDpt1+WUWZrUOtPePPILPZOa8tX0xvTG0TcExJdEYLPJpSqsB+3qEy4FOpLgTUg7I2A ycM9wp3jaXr3otMSz0QfpU4t1VEP4+1EbKqNgNu/9GOnNEa+tvmHl0Pns173L3kpHf6j 46nTBvM6lWVU26wiBzdkYeVxzY7ZU1gGJjRNQfCnBMRvar8/nC4JeseArbC56y9PXu9o RzRw== X-Gm-Message-State: AOAM531HREpXsGveyzfKxV6D9CCpOqB0Ix56VhcYitZCzbnDHRgeo1A5 iETP7ZGSz0Q8dFwUkn6eKivx3BXjxHM= X-Google-Smtp-Source: ABdhPJxoux7gLqsn8nJMxsC7z9Crp9E7NnsXglfeCnx4wtNh0b7X9xbt+oECPhj0cilaRL1ik3M4Kw== X-Received: by 2002:a05:6e02:1a4f:b0:2c6:6499:9d1b with SMTP id u15-20020a056e021a4f00b002c664999d1bmr361256ilv.119.1649909562653; Wed, 13 Apr 2022 21:12:42 -0700 (PDT) Received: from localhost.localdomain (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.googlemail.com with ESMTPSA id t18-20020a056e02011200b002cbe6ce18e5sm113120ilm.40.2022.04.13.21.12.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 13 Apr 2022 21:12:42 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v1 6/6] elf: Optimize __dl_new_hash in dl-hash.h Date: Wed, 13 Apr 2022 23:12:31 -0500 Message-Id: <20220414041231.926415-6-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220414041231.926415-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-12.3 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, T_SCC_BODY_TEXT_LINE 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 --- sysdeps/generic/dl-hash.h | 28 ++++++++++++++++++++++++---- 1 file changed, 24 insertions(+), 4 deletions(-) diff --git a/sysdeps/generic/dl-hash.h b/sysdeps/generic/dl-hash.h index c041074352..425ab0876e 100644 --- a/sysdeps/generic/dl-hash.h +++ b/sysdeps/generic/dl-hash.h @@ -21,6 +21,9 @@ #include +/* For __glibc_unlikely. */ +#include + #ifndef __HAS_DL_ELF_HASH /* This is the hashing function specified by the ELF ABI. In the first five operations no overflow is possible so we optimized it a @@ -76,12 +79,29 @@ _dl_elf_hash (const char *name_arg) #endif /* !__HAS_DL_ELF_HASH */ 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; + } }