From patchwork Thu Apr 14 04:12:26 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 52897 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 04BE93857342 for ; Thu, 14 Apr 2022 04:13:01 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 04BE93857342 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1649909581; bh=TvP1wMqM9A6UwmlxuuTkre8bdPZHmmxJRY7Yn9d97IE=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=s33ZCQHiRLA9x39XX1DD1GgGU1S2ESHqrcE7Zww5rjEgyybcurwPOWulaz2JsYKZO B86IyU4mpYp6J1fw1e8cYGfjWss7c04nluQxcGE72KZJeMlR8sCv/Ks7LfBWZ+SYxB yHT6737Ty5QqkhDt0THIgXXLT8EJLnyN8sZVUPiE= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-il1-x131.google.com (mail-il1-x131.google.com [IPv6:2607:f8b0:4864:20::131]) by sourceware.org (Postfix) with ESMTPS id 8BA4E3858C53 for ; Thu, 14 Apr 2022 04:12:39 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8BA4E3858C53 Received: by mail-il1-x131.google.com with SMTP id x9so2402206ilc.3 for ; Wed, 13 Apr 2022 21:12:39 -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:mime-version :content-transfer-encoding; bh=TvP1wMqM9A6UwmlxuuTkre8bdPZHmmxJRY7Yn9d97IE=; b=Y4ekXm36uvhJw39SeiMY+0nN9AFKpklAfkv95SN9A1IhkhDdJFwg4APRF/8BYKWTQG BkcbkuFvMp7LWg6bWJs6nxsXLaUi8x25di1vZC9+n5WJ0v+gs9kwvDPyyDkeVO+Y13yC Ss4e2RmdcGT0uQ9HwNIbprtDpU18einFpbaNrmkMxSdSM1094j+085sG2SbYcxyVZtj/ bc+NYfzZySN0bbRECmiACTokYFhV1eCrPNMDQVaYCZ/Wr6cueqxtI5XKCP3MKEgldKrs 3Ynb5EtSlfr2Llm/6HUW7PL7bOwb06OO3aIWrRAmkb3d3V8N8lWIjlKVELsaqbdDFDFR KPrQ== X-Gm-Message-State: AOAM532L9/mX9mtRsMQK1UCkbsM5cU66MQruZwoMMexnAHzSUWtb3fYq wYmRMZSWqCTQ1syZuGzpjyToVqEvIDQ= X-Google-Smtp-Source: ABdhPJzkwpA11Hw/S0dIndw1F6AtkjJfZTGJIzJMywMxUAcfbtHfnKmTF5VuBLO6+zKWaiGHVC6UqA== X-Received: by 2002:a92:d7d0:0:b0:2ca:33ba:8bde with SMTP id g16-20020a92d7d0000000b002ca33ba8bdemr378343ilq.121.1649909557642; Wed, 13 Apr 2022 21:12:37 -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.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 13 Apr 2022 21:12:37 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v1 1/6] elf: Refactor dl_new_hash so it can be tested / benchmarked Date: Wed, 13 Apr 2022 23:12:26 -0500 Message-Id: <20220414041231.926415-1-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 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" No change to the code other than moving it to sysdeps/generic/dl-hash.h. Changed name so its now in the reserved namespace. --- sysdeps/generic/dl-hash.h | 13 +++++++++++++ sysdeps/i386/i686/dl-hash.h | 3 +++ 2 files changed, 16 insertions(+) diff --git a/sysdeps/generic/dl-hash.h b/sysdeps/generic/dl-hash.h index 9bc7e3bd67..c041074352 100644 --- a/sysdeps/generic/dl-hash.h +++ b/sysdeps/generic/dl-hash.h @@ -19,7 +19,9 @@ #ifndef _DL_HASH_H #define _DL_HASH_H 1 +#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 bit. */ @@ -71,5 +73,16 @@ _dl_elf_hash (const char *name_arg) } return hash; } +#endif /* !__HAS_DL_ELF_HASH */ + +static uint32_t +__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; +} + #endif /* dl-hash.h */ diff --git a/sysdeps/i386/i686/dl-hash.h b/sysdeps/i386/i686/dl-hash.h index c124480e77..d18370350d 100644 --- a/sysdeps/i386/i686/dl-hash.h +++ b/sysdeps/i386/i686/dl-hash.h @@ -75,4 +75,7 @@ _dl_elf_hash (const char *name) return result; } +#define __HAS_DL_ELF_HASH 1 +#include + #endif /* dl-hash.h */ From patchwork Thu Apr 14 04:12:27 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 52898 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 B5ED73857C48 for ; Thu, 14 Apr 2022 04:13:42 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B5ED73857C48 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1649909622; bh=WJXlLvR5TcJFE6G+iQNileTnVzXL51/T9Y6jKYoPvX4=; 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=aWhxmwdZUvRWfkZYIIGlab4a8fNIZni7PwzJlfUAJiB/mjpCZ/G4jEuPt4NbODLV+ FSV1g/3RrjqFAv1TgXB9Fvxjj/lHWa/PyFDNRSxegWWX6+veBBlKDPQsLHpNfzyyqX JOoKgzbiqS/y0axk+unJYemeObIbdul0NrYeJfd8= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd2a.google.com (mail-io1-xd2a.google.com [IPv6:2607:f8b0:4864:20::d2a]) by sourceware.org (Postfix) with ESMTPS id 8B8293858C83 for ; Thu, 14 Apr 2022 04:12:39 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8B8293858C83 Received: by mail-io1-xd2a.google.com with SMTP id p135so4170785iod.2 for ; Wed, 13 Apr 2022 21:12:39 -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=WJXlLvR5TcJFE6G+iQNileTnVzXL51/T9Y6jKYoPvX4=; b=sxXJsaT12dcj1ihU4WHOV9+pmXROiYML9azhpdHzpm9L/RJwQ6eLkWB6HYG1f+uTnO rETifgg0HEgljWi3FG7FPyCaLOTtQdSbPnYqeFs+tKAWiaWqt4wqqpzJSqNihoFOA9tl FusGp/J5Qb1u8DHlMapbeXSqURVr/9kosutRnrhxOL0TD89SyL3jsgWHYJjj7OpY3PL8 5+dHRMN1Fn5tptexQcfEt+XRTAOG2l51itjtdwVAThaoH6iOxhV0Dj9A+FfmMyIdTbmj 4PbyeynLfX3Sp5vqCda62h8fyeWbQn7qzeugSxMvIoO6kNReUs4Zxy67W1IFboJ/UZAC dKdA== X-Gm-Message-State: AOAM531PckoXrNBGnfKkcjd9++FS5MeAVpkYAA2I36H7qp2epkUDvEg9 5BYK0T3sJGozYF9SF0EDqDGMuYmIyA0= X-Google-Smtp-Source: ABdhPJzViS+mAADBBJChjhQDu0XWqP3kqtJ0uI3Zs6I25xiAIU9FFToInRM5x5zmj4a/lrUBPH6o6w== X-Received: by 2002:a05:6602:15cf:b0:614:52d4:952 with SMTP id f15-20020a05660215cf00b0061452d40952mr400652iow.185.1649909558727; Wed, 13 Apr 2022 21:12:38 -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.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 13 Apr 2022 21:12:38 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v1 2/6] elf: Add tests for the hash functions in dl-hash.h Date: Wed, 13 Apr 2022 23:12:27 -0500 Message-Id: <20220414041231.926415-2-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, KAM_SHORT, 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" If we want to further optimize the functions tests are needed. --- elf/Makefile | 1 + elf/tst-dl-hash.c | 146 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 147 insertions(+) create mode 100644 elf/tst-dl-hash.c diff --git a/elf/Makefile b/elf/Makefile index c96924e9c2..9c76673a40 100644 --- a/elf/Makefile +++ b/elf/Makefile @@ -309,6 +309,7 @@ tests := \ tst-array4 \ tst-array5 \ tst-auxv \ + tst-dl-hash \ tst-leaks1 \ tst-stringtable \ tst-tls9 \ diff --git a/elf/tst-dl-hash.c b/elf/tst-dl-hash.c new file mode 100644 index 0000000000..10b0cef045 --- /dev/null +++ b/elf/tst-dl-hash.c @@ -0,0 +1,146 @@ +/* Copyright (C) 2022 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ +/* Simple implementation of ELF ABI hash function. */ + +#include +#include +#include +#include +#include + +typedef unsigned int (*hash_f) (const char *); + +static unsigned int +simple_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; +} + +static unsigned int +simple_dl_elf_hash (const char *name_arg) +{ + unsigned long int hash = 0; + for (unsigned char c = *name_arg; c != '\0'; c = *(++name_arg)) + { + unsigned long int hi; + hash = (hash << 4) + c; + hi = hash & 0xf0000000; + hash ^= hi >> 24; + hash &= 0x0fffffff; + } + return hash; +} + +static int +do_fill_test (size_t len, int fill, const char *name, hash_f testf, + hash_f expecf) +{ + uint32_t expec, res; + char buf[len + 1]; + memset (buf, fill, len); + buf[len] = '\0'; + + expec = expecf (buf); + res = testf (buf); + if (expec != res) + { + printf ("FAIL: fill(%d) %s(%lu), %x != %x\n", fill, name, len, expec, + res); + return 1; + } + + return 0; +} + +static int +do_fill_tests (size_t len, int fill) +{ + if (do_fill_test (len, fill, "dl_new_hash", &__dl_new_hash, + &simple_dl_new_hash)) + { + return 1; + } + return do_fill_test (len, fill, "dl_elf_hash", &_dl_elf_hash, + &simple_dl_elf_hash); +} + +static int +do_rand_test (size_t len, const char *name, hash_f testf, hash_f expecf) +{ + uint32_t expec, res; + size_t i; + char buf[len + 1]; + char v; + for (i = 0; i < len; ++i) + { + v = random (); + if (v == 0) + { + v = 1; + } + buf[i] = v; + } + buf[len] = '\0'; + + expec = expecf (buf); + res = testf (buf); + if (expec != res) + { + printf ("FAIL: random %s(%lu), %x != %x\n", name, len, expec, res); + return 1; + } + + return 0; +} + +static int +do_rand_tests (size_t len) +{ + if (do_rand_test (len, "dl_new_hash", &__dl_new_hash, &simple_dl_new_hash)) + { + return 1; + } + return do_rand_test (len, "dl_elf_hash", &_dl_elf_hash, &simple_dl_elf_hash); +} + +static int +do_test (void) +{ + size_t i, j; + for (i = 0; i < 100; ++i) + { + for (j = 0; j < 8192; ++j) + { + if (do_rand_tests (i)) + { + return 1; + } + + if (do_fill_tests (i, -1) || do_fill_tests (i, 1) + || do_fill_tests (i, 0x80) || do_fill_tests (i, 0x88)) + { + return 1; + } + } + } + return 0; +} + +#include From patchwork Thu Apr 14 04:12:28 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 52899 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 AA1F73857C41 for ; Thu, 14 Apr 2022 04:14:24 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org AA1F73857C41 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1649909664; bh=o1M+bfH9sSLiKv6gt/iLVrzinZ9WovJTWSt1Zi9ep5c=; 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=wnGJMYXM+NtF12Rz5rJ3rdwB/bEfav0u7mGAUm8qfrDDpsmfYc/AZWP3jDd5aFGxG n7LaAfCgpAxLPJpHsnMR12rc4mQmDphb6GxMBb60ErDZ4wKMzFZys4EiXDNaTY/HEn omHy99dbLyoWJZ/L3dKG3Ax900JRt8is9GM/KRlc= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd36.google.com (mail-io1-xd36.google.com [IPv6:2607:f8b0:4864:20::d36]) by sourceware.org (Postfix) with ESMTPS id 63C833858C2C for ; Thu, 14 Apr 2022 04:12:40 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 63C833858C2C Received: by mail-io1-xd36.google.com with SMTP id z186so132946iof.9 for ; Wed, 13 Apr 2022 21:12:40 -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=o1M+bfH9sSLiKv6gt/iLVrzinZ9WovJTWSt1Zi9ep5c=; b=OlDADt3shkKcvSjx/pnLmTF7XDKzUSjSj9W+pbII8xEQ20GRCxmkDNJs28kv8QTIE/ St81eH6bxBa7grwrufPTgF2ygIBLnN46ck/DzxVSKn8VyShAfLmCRdIDp68cBfBNLnmU HfCWG9tmSSravzFafz5d3C0smmKQwEv7dkD89OMSuWAaY4nNIZx6a8UNeiEQ9x3ArKEL Gzihxi02kIVwF3WhupTldWgLKxrMvsuiRlB+QowJJzqwKhC/OPsh5iR7OX0xhOI9iC6+ +bjncGcy0gbWfEBwUpDgiHrJCYr++rztTz+Z/tzTapwLOxJVrI9WZz1JOJEJL3YVPZWz 6Tog== X-Gm-Message-State: AOAM533hzO+D+zKbBC+AU+m5qvQJ+EQS9hnByF0YTYh9irtjx/eoJtC5 eVagVPzTR/Wq9nfXelgsFdamhE2RYMU= X-Google-Smtp-Source: ABdhPJw3NXws09n1MVv+i7Cj3/Fag61Eus3Bsf7yggDy2JaCWbsEgrt2PKF1qzqQAM4DJ0RmF+KWeg== X-Received: by 2002:a05:6638:2047:b0:323:7f2c:f5c4 with SMTP id t7-20020a056638204700b003237f2cf5c4mr391403jaj.88.1649909559617; Wed, 13 Apr 2022 21:12:39 -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.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 13 Apr 2022 21:12:39 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v1 3/6] nss: Add tests for the nss_hash in nss_hash.h Date: Wed, 13 Apr 2022 23:12:28 -0500 Message-Id: <20220414041231.926415-3-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, KAM_SHORT, 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" If we want to further optimize the function tests are needed. --- nss/Makefile | 1 + nss/tst-nss-hash.c | 105 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 106 insertions(+) create mode 100644 nss/tst-nss-hash.c diff --git a/nss/Makefile b/nss/Makefile index d8b06b44fb..a978e3927a 100644 --- a/nss/Makefile +++ b/nss/Makefile @@ -62,6 +62,7 @@ tests := \ test-digits-dots \ test-netdb \ tst-nss-getpwent \ + tst-nss-hash \ tst-nss-test1 \ tst-nss-test2 \ tst-nss-test4 \ diff --git a/nss/tst-nss-hash.c b/nss/tst-nss-hash.c new file mode 100644 index 0000000000..9612eec909 --- /dev/null +++ b/nss/tst-nss-hash.c @@ -0,0 +1,105 @@ +/* Test __nss_hash + Copyright (C) 2017-2022 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#include +#include +#include +#include + +uint32_t __nss_hash (const void *__key, size_t __length); + +/* Simplist implementation of __nss_hash. */ +static uint32_t +simple_nss_hash (const void *keyarg, size_t len) +{ + const unsigned char *key; + size_t i; + uint32_t h = 0; + key = keyarg; + + for (i = 0; i < len; ++i) + { + h = *key++ + 65599 * h; + } + return h; +} + +static int +do_fill_tests (size_t len, int fill) +{ + uint32_t expec, res; + char buf[len]; + memset (buf, fill, len); + + expec = simple_nss_hash (buf, len); + res = __nss_hash (buf, len); + if (expec != res) + { + printf ("FAIL: fill(%d) (%lu), %x != %x\n", fill, len, expec, res); + return 1; + } + + return 0; +} + +static int +do_rand_tests (size_t len) +{ + uint32_t expec, res; + size_t i; + char buf[len]; + for (i = 0; i < len; ++i) + { + buf[i] = random (); + } + + expec = simple_nss_hash (buf, len); + res = __nss_hash (buf, len); + if (expec != res) + { + printf ("FAIL: random (%lu), %x != %x\n", len, expec, res); + return 1; + } + + return 0; +} + +static int +do_test (void) +{ + size_t i, j; + for (i = 0; i < 100; ++i) + { + for (j = 0; j < 8192; ++j) + { + if (do_rand_tests (i)) + { + return 1; + } + if (do_fill_tests (i, -1) || do_fill_tests (i, 1) + || do_fill_tests (i, 0x80) || do_fill_tests (i, 0x88)) + { + return 1; + } + } + } + return 0; +} + +#include From patchwork Thu Apr 14 04:12:29 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 52901 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 C9C2D3857343 for ; Thu, 14 Apr 2022 04:15:53 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C9C2D3857343 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1649909753; bh=wMqXadhXJPmDVh79Z2DyvkffYQrNIjX9qWrKvCk5bwc=; 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=DWfPF88O3nCzwhEobh3+M1sf15khv38WoRx5VKmIAd/Vc4314WxsKx0cN9Y1VPV8A F/nRXaGtAa69lgQcVuaghYpjbm6K5q2GMPlhCgbjbDskQwc3G9GnbcUbJ3hwv3FISo eJmUDi1AOXfUwtYZVmWQR+CSPeylt4xk7zOKcEPQ= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-il1-x130.google.com (mail-il1-x130.google.com [IPv6:2607:f8b0:4864:20::130]) by sourceware.org (Postfix) with ESMTPS id 09F993858C83 for ; Thu, 14 Apr 2022 04:12:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 09F993858C83 Received: by mail-il1-x130.google.com with SMTP id d3so2387833ilr.10 for ; Wed, 13 Apr 2022 21:12:42 -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=wMqXadhXJPmDVh79Z2DyvkffYQrNIjX9qWrKvCk5bwc=; b=n8ugWu5IJjT95eTluatd8b3PSO1PXi2YaIhpLZek2vVbnoiIXtzJUBI4YwH/U27Nsv E4RMCCaKH0kRxLnNh+YkjGnGsNUm0hSEpRE+1l8XqjlCDsAzQTuQKYdTP9Wv9++vU81A reaBFoLzCC7KegLfr6oDOGILNhYH3W8D6aqulJphlveJ1mtdrA3a3Y17gJx4pmh3yZFb qvFOlLG7jgo4Djum8ulxH4SJ6t1ZNA+sGVUWrb+UOaw+1DQs4blQ/epSj9NuuK+xaqWB Xc1F8LoaChUuiZ10KdKUl9SYNM947P1SHG/eOki0T5dtOsKvU09ak1KfUq/0Ft9A/l6W 715w== X-Gm-Message-State: AOAM533cLBCchV0gbpGrypMtXoz0GX4JnEk/eEf1crDWhFBJZ7LwLXGU HfAyuXjyPamfL2CC927qGJtWOXtpK2Y= X-Google-Smtp-Source: ABdhPJzjzRoFYe0v6dzO89V9e0+AS2NXrGjOp2KrC6zPsmUx7mkj1uj9bQyiVCkHM04UmTisavfElg== X-Received: by 2002:a92:ca45:0:b0:2ca:810e:7855 with SMTP id q5-20020a92ca45000000b002ca810e7855mr374517ilo.303.1649909560805; Wed, 13 Apr 2022 21:12:40 -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.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 13 Apr 2022 21:12:40 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v1 4/6] benchtests: Add benchtests for dl_elf_hash, dl_new_hash and nss_hash Date: Wed, 13 Apr 2022 23:12:29 -0500 Message-Id: <20220414041231.926415-4-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, KAM_SHORT, 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" Benchtests are for throughput and include random / fixed size benchmarks. --- benchtests/Makefile | 25 ++++- benchtests/README | 9 +- benchtests/bench-dl-elf-hash.c | 23 ++++ benchtests/bench-dl-new-hash.c | 23 ++++ benchtests/bench-hash-funcs.c | 196 +++++++++++++++++++++++++++++++++ benchtests/bench-nss-hash.c | 24 ++++ 6 files changed, 292 insertions(+), 8 deletions(-) create mode 100644 benchtests/bench-dl-elf-hash.c create mode 100644 benchtests/bench-dl-new-hash.c create mode 100644 benchtests/bench-hash-funcs.c create mode 100644 benchtests/bench-nss-hash.c diff --git a/benchtests/Makefile b/benchtests/Makefile index 8dfca592fd..aa508a6c4f 100644 --- a/benchtests/Makefile +++ b/benchtests/Makefile @@ -230,6 +230,12 @@ LOCALES := \ include ../gen-locales.mk endif +hash-benchset := \ + dl-elf-hash \ + dl-new-hash \ + nss-hash \ +# hash-benchset + stdlib-benchset := strtod stdio-common-benchset := sprintf @@ -238,7 +244,7 @@ math-benchset := math-inlines ifeq (${BENCHSET},) benchset := $(string-benchset-all) $(stdlib-benchset) $(stdio-common-benchset) \ - $(math-benchset) + $(math-benchset) $(hash-benchset) else benchset := $(foreach B,$(filter %-benchset,${BENCHSET}), ${${B}}) endif @@ -357,9 +363,20 @@ bench-clean: # Validate the passed in BENCHSET ifneq ($(strip ${BENCHSET}),) -VALIDBENCHSETNAMES := bench-pthread bench-math bench-string string-benchset \ - wcsmbs-benchset stdlib-benchset stdio-common-benchset math-benchset \ - malloc-thread malloc-simple +VALIDBENCHSETNAMES := \ + bench-math \ + bench-pthread \ + bench-string \ + hash-benchset \ + malloc-simple \ + malloc-thread \ + math-benchset \ + stdio-common-benchset \ + stdlib-benchset \ + string-benchset \ + wcsmbs-benchset \ +# VALIDBENCHSETNAMES + INVALIDBENCHSETNAMES := $(filter-out ${VALIDBENCHSETNAMES},${BENCHSET}) ifneq (${INVALIDBENCHSETNAMES},) $(info The following values in BENCHSET are invalid: ${INVALIDBENCHSETNAMES}) diff --git a/benchtests/README b/benchtests/README index 4d83a05b4b..998ba9b2b4 100644 --- a/benchtests/README +++ b/benchtests/README @@ -84,12 +84,13 @@ where BENCHSET may be a space-separated list of the following values: bench-math bench-pthread bench-string + hash-benchset + malloc-thread + math-benchset + stdio-common-benchset + stdlib-benchset string-benchset wcsmbs-benchset - stdlib-benchset - stdio-common-benchset - math-benchset - malloc-thread Adding a function to benchtests: =============================== diff --git a/benchtests/bench-dl-elf-hash.c b/benchtests/bench-dl-elf-hash.c new file mode 100644 index 0000000000..b293ee1d1b --- /dev/null +++ b/benchtests/bench-dl-elf-hash.c @@ -0,0 +1,23 @@ +/* Measure __dl_new_hash runtime + Copyright (C) 2013-2022 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#define TEST_FUNC(x, y) _dl_elf_hash (x) +#define TEST_NAME "_dl_elf_hash" + +#include "bench-hash-funcs.c" diff --git a/benchtests/bench-dl-new-hash.c b/benchtests/bench-dl-new-hash.c new file mode 100644 index 0000000000..7030a13bae --- /dev/null +++ b/benchtests/bench-dl-new-hash.c @@ -0,0 +1,23 @@ +/* Measure __dl_new_hash runtime + Copyright (C) 2013-2022 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#define TEST_FUNC(x, y) __dl_new_hash (x) +#define TEST_NAME "__dl_new_hash" + +#include "bench-hash-funcs.c" diff --git a/benchtests/bench-hash-funcs.c b/benchtests/bench-hash-funcs.c new file mode 100644 index 0000000000..e2e6895afd --- /dev/null +++ b/benchtests/bench-hash-funcs.c @@ -0,0 +1,196 @@ +/* Measure hash functions runtime. + Copyright (C) 2013-2022 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#define TEST_MAIN +#ifndef TEST_FUNC +# error "No TEST_FUNC provided!" +#endif + +#ifndef TEST_NAME +# define STRINGIFY_PRIMITIVE(x) # x +# define STRINGIFY(x) STRINGIFY_PRIMITIVE (x) + +# define TEST_NAME STRINGIFY (TEST_FUNC) +#endif + +#include "json-lib.h" +#include "bench-timing.h" + +#include +#include +#include + +#define DO_NOT_OPTIMIZE_OUT(x) __asm__ volatile("" : : "r,m"(x) : "memory") + +enum +{ + NFIXED_ITERS = 1048576, + NRAND_BUFS = 16384, + NRAND_ITERS = 2048, + RAND_BENCH_MAX_LEN = 256 +}; + +static double __attribute__ ((noinline, noclone)) +do_one_test_kernel (const char *s, size_t len) +{ + + unsigned int iters; + timing_t start, stop, cur; + + /* Warmup. */ + for (iters = NFIXED_ITERS / 32; iters; --iters) + { + DO_NOT_OPTIMIZE_OUT (TEST_FUNC (s, len)); + } + + TIMING_NOW (start); + for (iters = NFIXED_ITERS; iters; --iters) + { + DO_NOT_OPTIMIZE_OUT (TEST_FUNC (s, len)); + } + TIMING_NOW (stop); + + TIMING_DIFF (cur, start, stop); + + (void) (len); + return (double) cur / (double) NFIXED_ITERS; +} + +static void +do_one_test (json_ctx_t *json_ctx, size_t len) +{ + char buf[len + 1]; + memset (buf, -1, len); + buf[len] = '\0'; + + json_element_object_begin (json_ctx); + + json_attr_string (json_ctx, "type", "fixed"); + json_attr_uint (json_ctx, "length", len); + json_attr_double (json_ctx, "time", do_one_test_kernel (buf, len)); + + json_element_object_end (json_ctx); +} +static double +do_rand_test_kernel (char const *bufs, unsigned int const *sizes) +{ + unsigned int i, iters; + size_t offset; + timing_t start, stop, cur; + + /* Warmup. */ + for (i = 0, offset = 0; i < NRAND_BUFS; ++i, offset += RAND_BENCH_MAX_LEN) + { + DO_NOT_OPTIMIZE_OUT (TEST_FUNC (bufs + offset, sizes[i])); + } + + TIMING_NOW (start); + for (iters = NRAND_ITERS; iters; --iters) + { + for (i = 0, offset = 0; i < NRAND_BUFS; + ++i, offset += RAND_BENCH_MAX_LEN) + { + DO_NOT_OPTIMIZE_OUT (TEST_FUNC (bufs + offset, sizes[i])); + } + } + TIMING_NOW (stop); + + TIMING_DIFF (cur, start, stop); + + (void) (sizes); + return (double) cur / (double) (NRAND_ITERS * NRAND_BUFS); +} + +static void __attribute__ ((noinline, noclone)) +do_rand_test (json_ctx_t *json_ctx) +{ + size_t i, sz, offset; + char *bufs; + unsigned int *sizes; + + bufs = (char *) calloc (NRAND_BUFS, RAND_BENCH_MAX_LEN); + sizes = (unsigned int *) calloc (NRAND_BUFS, sizeof (unsigned int)); + if (bufs == NULL || sizes == NULL) + { + fprintf (stderr, "Failed to allocate bufs for random test\n"); + goto done; + } + + for (sz = 2; sz <= RAND_BENCH_MAX_LEN; sz += sz) + { + json_element_object_begin (json_ctx); + json_attr_string (json_ctx, "type", "random"); + json_attr_uint (json_ctx, "length", sz); + + for (i = 0, offset = 0; i < NRAND_BUFS; + ++i, offset += RAND_BENCH_MAX_LEN) + { + sizes[i] = random () % sz; + memset (bufs + offset, -1, sizes[i]); + bufs[offset + sizes[i]] = '\0'; + } + + json_attr_double (json_ctx, "time", do_rand_test_kernel (bufs, sizes)); + json_element_object_end (json_ctx); + } + +done: + if (bufs) + { + free (bufs); + } + if (sizes) + { + free (sizes); + } +} + +static int +do_test (void) +{ + int i; + json_ctx_t json_ctx; + + json_init (&json_ctx, 0, stdout); + json_document_begin (&json_ctx); + json_attr_string (&json_ctx, "timing_type", TIMING_TYPE); + json_attr_object_begin (&json_ctx, "functions"); + json_attr_object_begin (&json_ctx, TEST_NAME); + json_array_begin (&json_ctx, "results"); + + for (i = 0; i < 16; ++i) + { + do_one_test (&json_ctx, i); + } + + for (i = 16; i <= 256; i += i) + { + do_one_test (&json_ctx, i); + } + + do_rand_test (&json_ctx); + + json_array_end (&json_ctx); + json_attr_object_end (&json_ctx); + json_attr_object_end (&json_ctx); + json_document_end (&json_ctx); + + return 0; +} + +#include diff --git a/benchtests/bench-nss-hash.c b/benchtests/bench-nss-hash.c new file mode 100644 index 0000000000..5ed0d3e6bf --- /dev/null +++ b/benchtests/bench-nss-hash.c @@ -0,0 +1,24 @@ +/* Measure __nss_hash runtime + Copyright (C) 2013-2022 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#define TEST_FUNC __nss_hash + +uint32_t __nss_hash (const void *__key, size_t __length); + +#include "bench-hash-funcs.c" From patchwork Thu Apr 14 04:12:30 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 52900 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 B5DF53858025 for ; Thu, 14 Apr 2022 04:15:11 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B5DF53858025 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1649909711; bh=zj2NFHnTeLyhxkSHLGu3uAgkctu3K3V0M2ge6pbE41w=; 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=rxvXW+70eukgDBN8tqxhyN2gZP5hFW08ZUxS6xGRYZVXbjHGxYdjAjzB4eYt43CTT SacMAMc9CF8F3R6VLyekL5hbEbrwsMMzRFOtFbMcLPjs9q4TXo0qt6q3vrNHUmsw9I mDLBOjb9Z7T3qjeQ+sUGu7k021MKYcgA878FrZ38= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd2d.google.com (mail-io1-xd2d.google.com [IPv6:2607:f8b0:4864:20::d2d]) by sourceware.org (Postfix) with ESMTPS id 7C3863858C2C for ; Thu, 14 Apr 2022 04:12:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 7C3863858C2C Received: by mail-io1-xd2d.google.com with SMTP id e22so4135319ioe.11 for ; Wed, 13 Apr 2022 21:12:42 -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=zj2NFHnTeLyhxkSHLGu3uAgkctu3K3V0M2ge6pbE41w=; b=hUqDfkC6OtMqP1By1+VTRV5YxdhB6i7axyDuzQZLxYMqmWak/mHry+I9T/ZKp9Sz2J WSTfENJcXR9u3fYlvD8GLn4ee8WrKlWD7RJp3E2XsPeHNEk6AYbW91Pc5Vu7+QNE6iHO WpJ9uAb3wbL3l+4RFQXcib7yUQWv71Cuk2zbl9yeRIXJkdemKMCTrUftDWnLh7N4uG1q +PANqS60MkQJjQQb8fm8Dv45nvCjauTA8BcfT+cm135Z037OscY2+KA1CKZhJggD7H2A ydNe5OCPsUhTkff2LB8lxwjW4znNhLpTcHlwCl/PW9y3Q9dp/hBAWGnHzC2zyFZ3fXFe wHig== X-Gm-Message-State: AOAM533Jb+MvdCO2+Bt4efrfBQSnrJRcPPP1fHO8iMv6lt/b+kdsEW43 AzvwMxu3X/RQYQXIJhQkIX8TXe9a4nY= X-Google-Smtp-Source: ABdhPJyetYnIouGbZP8FsbFaOnfu18Tqt5Gn74EtY5nyh5iBnGKquscvMias1zFKRV/0OF5tOApwkQ== X-Received: by 2002:a6b:ee12:0:b0:64d:2f8f:15bb with SMTP id i18-20020a6bee12000000b0064d2f8f15bbmr421420ioh.16.1649909561738; Wed, 13 Apr 2022 21:12:41 -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.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 13 Apr 2022 21:12:41 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v1 5/6] nss: Optimize nss_hash in nss_hash.c Date: Wed, 13 Apr 2022 23:12:30 -0500 Message-Id: <20220414041231.926415-5-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=-11.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, LIKELY_SPAM_BODY, 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" The prior unrolling didn't really do much as it left the dependency chain between iterations. Unrolled the loop for 4 so 4x multiplies could be pipelined in out-of-order machines. Results for __nss_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.845 type, length, New Time, Old Time, New Time / Old Time fixed, 0, 4.019, 3.729, 1.078 fixed, 1, 4.95, 5.707, 0.867 fixed, 2, 5.152, 5.657, 0.911 fixed, 3, 4.641, 5.721, 0.811 fixed, 4, 5.551, 5.81, 0.955 fixed, 5, 6.525, 6.552, 0.996 fixed, 6, 6.711, 6.561, 1.023 fixed, 7, 6.715, 6.767, 0.992 fixed, 8, 7.874, 7.915, 0.995 fixed, 9, 8.888, 9.767, 0.91 fixed, 10, 8.959, 9.762, 0.918 fixed, 11, 9.188, 9.987, 0.92 fixed, 12, 9.708, 10.618, 0.914 fixed, 13, 10.393, 11.14, 0.933 fixed, 14, 10.628, 12.097, 0.879 fixed, 15, 10.982, 12.965, 0.847 fixed, 16, 11.851, 14.429, 0.821 fixed, 32, 24.334, 34.414, 0.707 fixed, 64, 55.618, 86.688, 0.642 fixed, 128, 118.261, 224.36, 0.527 fixed, 256, 256.183, 538.629, 0.476 random, 2, 11.194, 11.556, 0.969 random, 4, 17.516, 17.205, 1.018 random, 8, 23.501, 20.985, 1.12 random, 16, 28.131, 29.212, 0.963 random, 32, 35.436, 38.662, 0.917 random, 64, 45.74, 58.868, 0.777 random, 128, 75.394, 121.963, 0.618 random, 256, 139.524, 260.726, 0.535 --- nss/nss_hash.c | 79 +++++++++++++++++++++++++++----------------------- 1 file changed, 42 insertions(+), 37 deletions(-) diff --git a/nss/nss_hash.c b/nss/nss_hash.c index 27a348ea9b..c6a375f386 100644 --- a/nss/nss_hash.c +++ b/nss/nss_hash.c @@ -19,58 +19,63 @@ /* This is from libc/db/hash/hash_func.c, hash3 is static there */ /* - * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte + * This is INCREDIBLY ugly, but fast. We break the string up into 4 byte * units. On the first time through the loop we get the "leftover bytes" - * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle - * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If - * this routine is heavily used enough, it's worth the ugly coding. + * (len % 4). On every other iteration, we perform a 4x unrolled version + * HASHC. Further unrolling does not appear to help. * * OZ's original sdbm hash */ uint32_t __nss_hash (const void *keyarg, size_t len) { + enum + { + HASH_CONST_P0 = 1, /* (uint32_t)(65599 ^ 0). */ + HASH_CONST_P1 = 65599, /* (uint32_t)(65599 ^ 1). */ + HASH_CONST_P2 = 8261505, /* (uint32_t)(65599 ^ 2). */ + HASH_CONST_P3 = 780587199, /* (uint32_t)(65599 ^ 3). */ + HASH_CONST_P4 = 1139564289 /* (uint32_t)(65599 ^ 4). */ + }; + const unsigned char *key; - size_t loop; uint32_t h; -#define HASHC h = *key++ + 65599 * h +#define HASHC h = *key++ + HASH_CONST_P1 * h h = 0; key = keyarg; if (len > 0) { - loop = (len + 8 - 1) >> 3; - switch (len & (8 - 1)) - { - case 0: - do - { - HASHC; - /* FALLTHROUGH */ - case 7: - HASHC; - /* FALLTHROUGH */ - case 6: - HASHC; - /* FALLTHROUGH */ - case 5: - HASHC; - /* FALLTHROUGH */ - case 4: - HASHC; - /* FALLTHROUGH */ - case 3: - HASHC; - /* FALLTHROUGH */ - case 2: - HASHC; - /* FALLTHROUGH */ - case 1: - HASHC; - } - while (--loop); - } + switch ((len & (4 - 1))) + { + case 0: + /* h starts out as zero so no need to include the multiply. */ + h = *key++; + /* FALLTHROUGH */ + case 3: + HASHC; + /* FALLTHROUGH */ + case 2: + HASHC; + /* FALLTHROUGH */ + case 1: + HASHC; + /* FALLTHROUGH */ + } + + uint32_t c0, c1, c2, c3; + for (--len; len >= 4; len -= 4) + { + c0 = (unsigned char) *(key + 0); + c1 = (unsigned char) *(key + 1); + c2 = (unsigned char) *(key + 2); + c3 = (unsigned char) *(key + 3); + h = HASH_CONST_P4 * h + HASH_CONST_P3 * c0 + HASH_CONST_P2 * c1 + + HASH_CONST_P1 * c2 + HASH_CONST_P0 * c3; + + key += 4; + } } return h; } 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; + } }