From patchwork Thu Jan 18 17:53:16 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella Netto X-Patchwork-Id: 124996 Delivered-To: patch@linaro.org Received: by 10.46.64.27 with SMTP id n27csp228311lja; Thu, 18 Jan 2018 09:53:52 -0800 (PST) X-Google-Smtp-Source: ACJfBosHVBxlWNMJ5OWHmjNYz1IqDL2qShY5rcjk7HdpWngGZIL1cXXoivaaocX215wrctjePTlz X-Received: by 2002:a17:902:d90a:: with SMTP id c10-v6mr175875plz.200.1516298032645; Thu, 18 Jan 2018 09:53:52 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1516298032; cv=none; d=google.com; s=arc-20160816; b=OFQG34o1git+06WJU77winVg3IBh7k+b+JD2sAdeAofi6dsf4kDNUewn6yPYtpwxhW j2ocQt4w59oG63ukM427QyU4s/AsuXK1QghifDFnYlL/WDGy/6Z5sJ8lmWsxziEv99rc OH2bS0HS/vlMFp1vEdSoPgtyBrPHOiUp/3xZzxjKykbIie9fzQlNWAJ+pSI0+CqxGYRV gto/XNOBqpFP2YIP1uqqnksFhr5W/qN65V18NTBfpG3/tAou96seYXQrPl37YIfBsdu6 oo3L9t1p5wuK2e3Zwmkrn/wollWgNFxijgrYCSs2PK9HMk7SWlfjPrQluNxdQCd7n+N4 OImw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=references:in-reply-to:message-id:date:subject:to:from:delivered-to :sender:list-help:list-post:list-archive:list-subscribe :list-unsubscribe:list-id:precedence:mailing-list:dkim-signature :domainkey-signature:arc-authentication-results; bh=2KqttKVz2kzitFzn0WgJ5D+8o8IB1V2pE3mMpog+3uo=; b=wcET3FXTrY3BC/ZOxOibfRFbPqL4OimZZuWCvA8SCgapmt4gOPI5nTrDhQuwXT0qT9 FUOkOA0QE0JAehJbL1mtiUcP4UYWSE/C0t9L83VYWnrraxHfbzqUz7ZG4BjHW2T3ZHOZ Kcvh1EWTV/aNsA1+6Z+gXDteiKK+EeUQZobBx5A2zqh8LdCnm4Lr+6Rui7jZJrQ0tafi HyCfglwgS+WtHB8zgbdbgL6XD95faa3j87h73HwFlBtxpGqcceSRoXWDHaN9gAALTDIH NQg5nWYSFcawtid5Adda0h5dyJeIjM/vpmOqtr/nhQMXl2fqu2Wv0WR3PTb86381p4KL jZtg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=yyAfebZT; spf=pass (google.com: domain of libc-alpha-return-89323-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89323-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id b36-v6si76063pli.740.2018.01.18.09.53.52 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 18 Jan 2018 09:53:52 -0800 (PST) Received-SPF: pass (google.com: domain of libc-alpha-return-89323-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=yyAfebZT; spf=pass (google.com: domain of libc-alpha-return-89323-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89323-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; q=dns; s=default; b=arV3/MOHA0yvZXEgJUEtZlwgGFRDKrx 4DA96YPrOrQ+9RIFGFO8rqYydD4wtSps9sdjYwv34jlQE6B/oiffqbUFyhaLvMiS nb3tUWLTOa7/Eox+iTuPlpLunhjjAfG0Ap4mAoqtvR30jdx06qu/Ba5HtfO2EORJ YFryPEzViBbU= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; s=default; bh=yu2bd+3ySBTMNQKVzc9wW8RJDFs=; b=yyAfe bZThe4qY3u8sGvf+fXv/UCNBSYywupkcWJ+cKMThVzeut/pzH2/TGX/7jDatp4GZ wSShGMyVNuircbO9XE79tozfmcQn/sYOrF3Z0v001W0ueW37F5oOFVhjZ/w+ZpQT ZJdZ09wOZk+ZZtQFvM44h2X3POa3uC50syr4zs= Received: (qmail 78648 invoked by alias); 18 Jan 2018 17:53:34 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 78617 invoked by uid 89); 18 Jan 2018 17:53:33 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-25.8 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=Hx-spam-relays-external:209.85.216.193, H*RU:209.85.216.193 X-HELO: mail-qt0-f193.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=2KqttKVz2kzitFzn0WgJ5D+8o8IB1V2pE3mMpog+3uo=; b=EpJUI1urOPThPPwa1paLhCSy0oTW7Dno9XNPdH6GYd1t8Lz4Z524v+k/deQUYcw+Qs 70fg+FvJPJvXMKpUsOFnx+KliyTY4OXtPPJDMV5eJuQe7+UuzTmUuG3aOZQbGIVSuBx4 mOXZaIWdo9JcubEJdKkB9gqBBRLfH5+drl05cxHKgQP7AHd6mPElJZ7b3GNrpxlySXcf 6cibIjtdOZuOinxo+3fnDz7l6Bvv2/rRi8Mm3lbSaOT3pQvs3jz/46X2qqQqXSE64pqQ Yzj1BsGpi0cGUDc2ANB9q6/K2PtHhJrDnqlDtsLpEoTGHqKMdMZIcBPiCDxj7s0gigxq B90A== X-Gm-Message-State: AKwxytc3qD85BYMtgLbupuQFc+KFp2VET1kooT1fJjIMjT0ydxfrqxrs WRrznyHPfsFXGnFXcKXjlrASMtK3al8= X-Received: by 10.200.15.141 with SMTP id b13mr26769245qtk.301.1516298010632; Thu, 18 Jan 2018 09:53:30 -0800 (PST) From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH 1/7] stdlib: Adjust tst-qsort{2} to libsupport Date: Thu, 18 Jan 2018 15:53:16 -0200 Message-Id: <1516298002-4618-2-git-send-email-adhemerval.zanella@linaro.org> In-Reply-To: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> References: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> * stdlib/tst-qsort.c: Use libsupport. * stdlib/tst-qsort2.c: Likewise. --- stdlib/tst-qsort.c | 45 ++++++++++++++++++++++----------------------- stdlib/tst-qsort2.c | 44 +++++++++++++++++++++----------------------- 2 files changed, 43 insertions(+), 46 deletions(-) -- 2.7.4 diff --git a/stdlib/tst-qsort.c b/stdlib/tst-qsort.c index 2b26e74..c3230fd 100644 --- a/stdlib/tst-qsort.c +++ b/stdlib/tst-qsort.c @@ -3,6 +3,8 @@ #include #include +#include + struct big { char c[4 * 1024]; }; struct big *array; @@ -10,7 +12,7 @@ struct big *array_end; static int align_check; -int +static int compare (void const *a1, void const *b1) { struct big const *a = a1; @@ -19,37 +21,34 @@ compare (void const *a1, void const *b1) if (!align_check) align_check = TEST_STACK_ALIGN () ? -1 : 1; - if (! (array <= a && a < array_end - && array <= b && b < array_end)) - { - exit (EXIT_FAILURE); - } - return b->c[0] - a->c[0]; + TEST_VERIFY_EXIT (array <= a && a < array_end + && array <= b && b < array_end); + + return (b->c[0] - a->c[0]) > 0; } int -main (int argc, char **argv) +do_test (void) { - size_t i; - size_t array_members = argv[1] ? atoi (argv[1]) : 50; - array = (struct big *) malloc (array_members * sizeof *array); - if (array == NULL) + const size_t sizes[] = { 8, 16, 24, 48, 96, 192, 384 }; + const size_t sizes_len = sizeof (sizes) / sizeof (sizes[0]); + + for (size_t s = 0; s < sizes_len; s++) { - puts ("no memory"); - exit (EXIT_FAILURE); - } + array = (struct big *) malloc (sizes[s] * sizeof *array); + TEST_VERIFY_EXIT (array != NULL); - array_end = array + array_members; - for (i = 0; i < array_members; i++) - array[i].c[0] = i % 128; + array_end = array + sizes[s]; + for (size_t i = 0; i < sizes[s]; i++) + array[i].c[0] = i % 128; - qsort (array, array_members, sizeof *array, compare); + qsort (array, sizes[s], sizeof *array, compare); + TEST_VERIFY_EXIT (align_check != -1); - if (align_check == -1) - { - puts ("stack not sufficiently aligned"); - exit (EXIT_FAILURE); + free (array); } return 0; } + +#include diff --git a/stdlib/tst-qsort2.c b/stdlib/tst-qsort2.c index 10d1685..595875d 100644 --- a/stdlib/tst-qsort2.c +++ b/stdlib/tst-qsort2.c @@ -1,11 +1,13 @@ #include #include -char *array; -char *array_end; -size_t member_size; +#include -int +static char *array; +static char *array_end; +static size_t member_size; + +static int compare (const void *a1, const void *b1) { const char *a = a1; @@ -25,7 +27,7 @@ compare (const void *a1, const void *b1) return 0; } -int +static int test (size_t nmemb, size_t size) { array = malloc (nmemb * size); @@ -66,24 +68,20 @@ test (size_t nmemb, size_t size) return 0; } -int -main (int argc, char **argv) +static int +do_test (void) { - int ret = 0; - if (argc >= 3) - ret |= test (atoi (argv[1]), atoi (argv[2])); - else - { - ret |= test (10000, 1); - ret |= test (200000, 2); - ret |= test (2000000, 3); - ret |= test (2132310, 4); - ret |= test (1202730, 7); - ret |= test (1184710, 8); - ret |= test (272710, 12); - ret |= test (14170, 32); - ret |= test (4170, 320); - } + test (10000, 1); + test (200000, 2); + test (2000000, 3); + test (2132310, 4); + test (1202730, 7); + test (1184710, 8); + test (272710, 12); + test (14170, 32); + test (4170, 320); - return ret; + return 0; } + +#include From patchwork Thu Jan 18 17:53:17 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella Netto X-Patchwork-Id: 124997 Delivered-To: patch@linaro.org Received: by 10.46.64.27 with SMTP id n27csp228376lja; Thu, 18 Jan 2018 09:54:02 -0800 (PST) X-Google-Smtp-Source: ACJfBovmle+nMWnAsgFiiy7u03xzS5JRgj9AhRpLPd/bK1lZLDScDjH8cYV3TuRV63U7djSWNVyv X-Received: by 10.99.174.69 with SMTP id e5mr5135105pgp.263.1516298042113; Thu, 18 Jan 2018 09:54:02 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1516298042; cv=none; d=google.com; s=arc-20160816; b=yhsFx2QITqbRpLlpqjwUjzEWlw2Mh7NITsEl7oi1HWDowNV1g1wn4StePngZirmh4S fuUg7u40XG5H3rugCVI+7AyagSNOdV91jzcXTC9sMzIrxpKbVDMz97JPdY0wXtAPJfRl bIvxodwexzUAZg+DIxPi7pg+cmePdNvSNydJUcK53XaX2vCILhM8C3dNY2M+Xu+6vdaL 4/ipeLJYvIpTDC54+X7821gXbigpXAcXCPNR89EFzsgoAJ/uV94JZAKlvcH1CUk8vXjT rSGbKU4xyF6WBz0udjFLa1xPqmpeswQzCD5SL+xvURjm9+fmSJIR/ckKtUgyw0YGPzvz A8Xg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=references:in-reply-to:message-id:date:subject:to:from:delivered-to :sender:list-help:list-post:list-archive:list-subscribe :list-unsubscribe:list-id:precedence:mailing-list:dkim-signature :domainkey-signature:arc-authentication-results; bh=7/UrN+Z7YLg2t9nWAm9sKbom6Ldx+mR6o2YzX5+fMzM=; b=hbhr0En89cm55t9SBh14P9uDv54Bgb5vvr/R4UZ+D5eEYkPNrbqsrgsAmZAGgfPos2 wcZgzsBiwzgxIyuysI5keO3jP0R5s/sczXh+/Rfd+i/SP6I2+8teUSRTdpQCaH9X1BLC 2hvm6C2lfGbEonZNc6L1Bdn45QzqFhtVvLpK6FZzOKO4H2LSZRZrF1CxdWnOCMD4BZSW q//4TZhq0O3PRSN6zttkarNWw2mmRDWZmHTcBw5oZvhFxw7JkPQbuMjHhBmnigA06loj vEYCdyQasud4Nm2JhFl7HdgpPCEk9KoASMrxZ7mfU/mDkGChuzrIOC5AqIKLcubEph6I G9kg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=TS8sP3Sv; spf=pass (google.com: domain of libc-alpha-return-89324-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89324-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id k4-v6si76099pll.223.2018.01.18.09.54.01 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 18 Jan 2018 09:54:02 -0800 (PST) Received-SPF: pass (google.com: domain of libc-alpha-return-89324-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=TS8sP3Sv; spf=pass (google.com: domain of libc-alpha-return-89324-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89324-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; q=dns; s=default; b=UtAjhN1ZlFv7xhvzD0cIukyE0D9Gk15 WoC9CMBIlVDBtoDRZ4XFoYJj9mKn02O3viuS8fygkuy+r9j0ABbabx6a803pjMxa 5Ji1shQu0BqVYG7mXly9kRPEmcgUOWBolts5lSSKmF7/CDuWuR908bxw7FxED/nw pn5WlkU2ZIsQ= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; s=default; bh=6fxE11i9Z0QUg5YUCnkVaZmKk5I=; b=TS8sP 3Sv6+SgJmN8sRupuaBns/1jkZaCBejxXyfYRLOP1K/4AU6jMXrAWBkIivwQcBbQY c/PK5YSmiLEWAhzrZYNCX/174A0Ip3/6mLlfCVK1KtUDC0As7YoO2YtnNeyJ/yuP vNfsv9ibg7q/mHpaFSylrBLdmVpCxB32bL6vpI= Received: (qmail 79229 invoked by alias); 18 Jan 2018 17:53:38 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 79119 invoked by uid 89); 18 Jan 2018 17:53:37 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.0 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=Computer, uniform, aimed, stat.h X-HELO: mail-qt0-f194.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=7/UrN+Z7YLg2t9nWAm9sKbom6Ldx+mR6o2YzX5+fMzM=; b=uUR2J/+5jxl/ASWWqnKBprMFeDovjfdcWw8zOCF28mBmHPc5hziRENhSqkYqi+ozSB tH4QbUV5Lx5oaHoD+5BoQH/9MPAypoEHS+qo4n2Ogbe4frd/0wDK24KcX2OARzyrMzdP 5PgUU2WcSt0fY+Fm9aqSbQiQmKt4BnF/WUzH2cTCYCGfhU2X0koCJTHtpiw3HjK6GIWd zu77B6nIr+aFCJS6VaL8/25YSPSiFO3mVWG/T6TGzLd/wgUnPNGT7RVqAZA2RqovvxfN VT1zZyevTTho0ErfqrT+CPEevB7C3oM04xXDMNFil3sd+KynKHnBas9bssAnG3Z5HgEL IJTg== X-Gm-Message-State: AKwxyteUyQx1VNTE9N0FnavpQ+onUoOYsdAVYskj2m+mUSTnIkOS7agg JUJ5e75eWZcZJZL7s2IF5Txz/SLm46w= X-Received: by 10.200.48.166 with SMTP id v35mr38346663qta.296.1516298012099; Thu, 18 Jan 2018 09:53:32 -0800 (PST) From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH 2/7] support: Add Mersenne Twister pseudo-random number generator Date: Thu, 18 Jan 2018 15:53:17 -0200 Message-Id: <1516298002-4618-3-git-send-email-adhemerval.zanella@linaro.org> In-Reply-To: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> References: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> This patch adds support routines for pseudo-random number generation based on Mersenne Twister. The libstc++ version is used as based and both 32 and 64 bits are provided. It is used on following qsort tests and benchmarks. I decided to use a Mersenne Twister (MT) instead of random_r internal implementation, which uses a linear feedback shift register approach with trinomials, because: - it is used extensivelly in other implementations (like c+11); - it has a quite larger period (2^219937-1) than the type 4 variation of random (2^63 - 1); - it does not have the RAND_MAX limitation. Checked on x86_64-linux-gnu. * support/Makefile (libsupport-routines): Add support_random. (tests): Add tst-support_random. * support/support_random.c: New file. * support/support_random.h: Likewise. * support/tst-support_random.c: Likewise. --- support/Makefile | 2 + support/support_random.c | 219 +++++++++++++++++++++++++++++++++++++++++++ support/support_random.h | 109 +++++++++++++++++++++ support/tst-support_random.c | 87 +++++++++++++++++ 4 files changed, 417 insertions(+) create mode 100644 support/support_random.c create mode 100644 support/support_random.h create mode 100644 support/tst-support_random.c -- 2.7.4 diff --git a/support/Makefile b/support/Makefile index 1bda81e..8efe577 100644 --- a/support/Makefile +++ b/support/Makefile @@ -53,6 +53,7 @@ libsupport-routines = \ support_format_netent \ support_isolate_in_subprocess \ support_record_failure \ + support_random \ support_run_diff \ support_shared_allocate \ support_test_compare_failure \ @@ -153,6 +154,7 @@ tests = \ tst-support_record_failure \ tst-test_compare \ tst-xreadlink \ + tst-support_random ifeq ($(run-built-tests),yes) tests-special = \ diff --git a/support/support_random.c b/support/support_random.c new file mode 100644 index 0000000..f3037a5 --- /dev/null +++ b/support/support_random.c @@ -0,0 +1,219 @@ +/* Function for pseudo-random number generation. + Copyright (C) 2018 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 +#include +#include + +int +random_seed (void *buf, size_t len) +{ + ssize_t ret = getrandom (buf, len, 0); + if (ret == len) + return 0; + + int fd = open ("/dev/urandom", O_RDONLY); + if (fd < 0) + return -1; + void *end = buf + len; + while (buf < end) + { + ssize_t ret = read (fd, buf, end - buf); + if (ret <= 0) + break; + buf += ret; + } + close (fd); + return buf == end ? 0 : -1; +} + +/* The classic Mersenne Twister. Reference: + M. Matsumoto and T. Nishimura, Mersenne Twister: A 623-Dimensionally + Equidistributed Uniform Pseudo-Random Number Generator, ACM Transactions + on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30. + + This version is based on libstdc++ std::mt19937{_64}. */ + +static const size_t mt32_word_size = 32; +static const size_t mt32_mask_bits = 31; +static const size_t mt32_state_size = MT32_STATE_SIZE; +static const size_t mt32_shift_size = 397; +static const uint32_t mt32_xor_mask = 0x9908b0dfUL; +static const size_t mt32_tempering_u = 11; +static const uint32_t mt32_tempering_d = 0xffffffffUL; +static const size_t mt32_tempering_s = 7; +static const uint32_t mt32_tempering_b = 0x9d2c5680UL; +static const size_t mt32_tempering_t = 15; +static const uint32_t mt32_tempering_c = 0xefc60000UL; +static const size_t mt32_tempering_l = 18; +static const uint32_t mt32_init_multiplier = 1812433253UL; +static const uint32_t mt32_default_seed = 5489u; + +static void +mt32_gen_rand (struct mt19937_32 *state) +{ + const uint32_t upper_mask = (uint32_t)-1 << mt32_mask_bits; + const uint32_t lower_mask = ~upper_mask; + + for (size_t k = 0; k < (mt32_state_size - mt32_shift_size); k++) + { + uint32_t y = ((state->mt[k] & upper_mask) + | (state->mt[k + 1] & lower_mask)); + state->mt[k] = (state->mt[k + mt32_shift_size] ^ (y >> 1) + ^ ((y & 0x01) ? mt32_xor_mask : 0)); + } + + for (size_t k = (mt32_state_size - mt32_shift_size); + k < (mt32_state_size - 1); k++) + { + uint32_t y = ((state->mt[k] & upper_mask) + | (state->mt[k + 1] & lower_mask)); + state->mt[k] = (state->mt[k + (mt32_shift_size - mt32_state_size)] + ^ (y >> 1) ^ ((y & 0x01) ? mt32_xor_mask : 0)); + } + + uint32_t y = ((state->mt[mt32_state_size - 1] & upper_mask) + | (state->mt[0] & lower_mask)); + state->mt[mt32_state_size - 1] = (state->mt[mt32_shift_size -1] ^ (y >> 1) + ^ (( y & 0x01) ? mt32_xor_mask : 0)); + state->p = 0; +} + +void +mt32_seed (struct mt19937_32 *state, uint32_t seed) +{ + /* Generators based on linear-feedback shift-register techniques can not + handle all zero initial state (they will output zero continually). In + such cases we use the default initial state). */ + if (seed == 0x0) + seed = mt32_default_seed; + + state->mt[0] = mt32_default_seed; + for (size_t i = 1; i < mt32_state_size; i++) + { + uint32_t x = state->mt[i - 1]; + x ^= x >> (mt32_word_size - 2); + x *= mt32_init_multiplier; + x += i; + state->mt[i] = x; + } + state->p = mt32_state_size; +} + +uint32_t +mt32_rand (struct mt19937_32 *state) +{ + /* Reload the vector - cost is O(n) amortized over n calls. */ + if (state->p >= mt32_state_size) + mt32_gen_rand (state); + + /* Calculate o(x(i)). */ + uint32_t z = state->mt[state->p++]; + z ^= (z >> mt32_tempering_u) & mt32_tempering_d; + z ^= (z << mt32_tempering_s) & mt32_tempering_b; + z ^= (z << mt32_tempering_t) & mt32_tempering_c; + z ^= (z >> mt32_tempering_l); + return z; +} + + +static const size_t mt64_word_size = 64; +static const size_t mt64_mask_bits = 31; +static const size_t mt64_state_size = MT64_STATE_SIZE; +static const size_t mt64_shift_size = 156; +static const uint64_t mt64_xor_mask = 0xb5026f5aa96619e9ULL; +static const size_t mt64_tempering_u = 29; +static const uint64_t mt64_tempering_d = 0x5555555555555555ULL; +static const size_t mt64_tempering_s = 17; +static const uint64_t mt64_tempering_b = 0x71d67fffeda60000ULL; +static const size_t mt64_tempering_t = 37; +static const uint64_t mt64_tempering_c = 0xfff7eee000000000ULL; +static const size_t mt64_tempering_l = 43; +static const uint64_t mt64_init_multiplier = 6364136223846793005ULL; +static const uint64_t mt64_default_seed = 5489u; + +static void +mt64_gen_rand (struct mt19937_64 *state) +{ + const uint64_t upper_mask = (uint64_t)-1 << mt64_mask_bits; + const uint64_t lower_mask = ~upper_mask; + + for (size_t k = 0; k < (mt64_state_size - mt64_shift_size); k++) + { + uint64_t y = ((state->mt[k] & upper_mask) + | (state->mt[k + 1] & lower_mask)); + state->mt[k] = (state->mt[k + mt64_shift_size] ^ (y >> 1) + ^ ((y & 0x01) ? mt64_xor_mask : 0)); + } + + for (size_t k = (mt64_state_size - mt64_shift_size); + k < (mt64_state_size - 1); k++) + { + uint64_t y = ((state->mt[k] & upper_mask) + | (state->mt[k + 1] & lower_mask)); + state->mt[k] = (state->mt[k + (mt64_shift_size - mt64_state_size)] + ^ (y >> 1) ^ ((y & 0x01) ? mt64_xor_mask : 0)); + } + + uint64_t y = ((state->mt[mt64_state_size - 1] & upper_mask) + | (state->mt[0] & lower_mask)); + state->mt[mt64_state_size - 1] = (state->mt[mt64_shift_size -1] ^ (y >> 1) + ^ (( y & 0x01) ? mt64_xor_mask : 0)); + state->p = 0; +} + +void +mt64_seed (struct mt19937_64 *state, uint64_t seed) +{ + /* Generators based on linear-feedback shift-register techniques can not + handle all zero initial state (they will output zero continually). In + such cases we use the default initial state). */ + if (seed == 0x0) + seed = mt64_default_seed; + + state->mt[0] = mt64_default_seed; + for (size_t i = 1; i < mt64_state_size; i++) + { + uint64_t x = state->mt[i - 1]; + x ^= x >> (mt64_word_size - 2); + x *= mt64_init_multiplier; + x += i; + state->mt[i] = x; + } + state->p = mt64_state_size; +} + +uint64_t +mt64_rand (struct mt19937_64 *state) +{ + /* Reload the vector - cost is O(n) amortized over n calls. */ + if (state->p >= mt64_state_size) + mt64_gen_rand (state); + + /* Calculate o(x(i)). */ + uint64_t z = state->mt[state->p++]; + z ^= (z >> mt64_tempering_u) & mt64_tempering_d; + z ^= (z << mt64_tempering_s) & mt64_tempering_b; + z ^= (z << mt64_tempering_t) & mt64_tempering_c; + z ^= (z >> mt64_tempering_l); + return z; +} diff --git a/support/support_random.h b/support/support_random.h new file mode 100644 index 0000000..9d58d51 --- /dev/null +++ b/support/support_random.h @@ -0,0 +1,109 @@ +/* Function for pseudo-random number generation. + Copyright (C) 2018 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 + . */ + +#ifndef SUPPORT_MT_RAND_H +#define SUPPORT_MT_RAND_H + +#include +#include +#include + +/* Obtain a random seed at BUF with size of LEN from system random device. + It will used getrandom or '/dev/urandom' device case getrandom fails. */ +int random_seed (void *buf, size_t len); + +/* A Mersenne Twister implementation for both uint32_t and uint64_t aimed for + fast pseudo-random number generation where rand() is not suffice (due + mainly low entropy). + + The usual way to use is: + + uint32_t seed; + random_seed (&seed, sizeof (uint32_t)); + + mt19937_32 mt; + mt32_seed (&mt, seed); + + uint32_t random_number = mt32_rand (&mt); + + If seed is 0 the default one (5489u) is used instead. Usually the seed + should be obtained for a more robust random generation (getrandom or + from /dev/{u}random). */ + +enum { + MT32_STATE_SIZE = 624, + MT64_STATE_SIZE = 312 +}; + +struct mt19937_32 +{ + uint32_t mt[MT32_STATE_SIZE]; + size_t p; +}; + +struct mt19937_64 +{ + uint64_t mt[MT64_STATE_SIZE]; + size_t p; +}; + +/* Initialize the mersenne twister STATE with SEED. If seed is zero the + default seed is used (5489u). */ +void mt32_seed (struct mt19937_32 *state, uint32_t seed); +void mt64_seed (struct mt19937_64 *state, uint64_t seed); +/* Output a pseudo-number from mersenned twister STATE. */ +uint32_t mt32_rand (struct mt19937_32 *state); +uint64_t mt64_rand (struct mt19937_64 *state); + +/* Scales the number NUMBER to the uniformly distributed closed internal + [min, max]. */ +static inline int32_t +uniform_uint32_distribution (int32_t random, uint32_t min, uint32_t max) +{ + assert (max >= min); + uint32_t range = max - min; + /* It assumed that the input random number RANDOM is as larger or equal + than the RANGE, so the result will always be downscaled. */ + if (range != UINT32_MAX) + { + uint32_t urange = range + 1; /* range can be 0. */ + uint32_t scaling = UINT32_MAX / urange; + random /= scaling; + } + return random + min; +} + +/* Scales the number NUMBER to the uniformly distributed closed internal + [min, max]. */ +static inline uint64_t +uniform_uint64_distribution (uint64_t random, uint64_t min, uint64_t max) +{ + assert (max >= min); + uint64_t range = max - min; + /* It assumed that the input random number RANDOM is as larger or equal + than the RANGE, so the result will always be downscaled. */ + if (range != UINT64_MAX) + { + uint64_t urange = range + 1; /* range can be 0. */ + uint64_t scaling = UINT64_MAX / urange; + random /= scaling; + } + return random + min; +} + +#endif diff --git a/support/tst-support_random.c b/support/tst-support_random.c new file mode 100644 index 0000000..3068ca9 --- /dev/null +++ b/support/tst-support_random.c @@ -0,0 +1,87 @@ +/* Test the Mersenne Twister random functions. + Copyright (C) 2017 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 + +static int +do_test (void) +{ + { + struct mt19937_32 mt32; + mt32_seed (&mt32, 0); + for (int i = 0; i < 9999; ++i) + mt32_rand (&mt32); + TEST_VERIFY (mt32_rand (&mt32) == 4123659995ul); + } + + { + struct mt19937_64 mt64; + mt64_seed (&mt64, 0); + for (int i = 0; i < 9999; ++i) + mt64_rand (&mt64); + TEST_VERIFY (mt64_rand (&mt64) == UINT64_C(9981545732273789042)); + } + +#define CHECK_UNIFORM_32(min, max) \ + ({ \ + uint32_t v = uniform_uint32_distribution (mt32_rand (&mt32), min, max); \ + TEST_VERIFY (v >= min && v <= max); \ + }) + + { + struct mt19937_32 mt32; + uint32_t seed; + random_seed (&seed, sizeof (seed)); + mt32_seed (&mt32, seed); + + CHECK_UNIFORM_32 (0, 100); + CHECK_UNIFORM_32 (100, 200); + CHECK_UNIFORM_32 (100, 1<<10); + CHECK_UNIFORM_32 (1<<10, UINT16_MAX); + CHECK_UNIFORM_32 (UINT16_MAX, UINT32_MAX); + } + +#define CHECK_UNIFORM_64(min, max) \ + ({ \ + uint64_t v = uniform_uint64_distribution (mt64_rand (&mt64), min, max); \ + TEST_VERIFY (v >= min && v <= max); \ + }) + + { + struct mt19937_64 mt64; + uint64_t seed; + random_seed (&seed, sizeof (seed)); + mt64_seed (&mt64, seed); + + CHECK_UNIFORM_64 (0, 100); + CHECK_UNIFORM_64 (100, 200); + CHECK_UNIFORM_64 (100, 1<<10); + CHECK_UNIFORM_64 (1<<10, UINT16_MAX); + CHECK_UNIFORM_64 (UINT16_MAX, UINT32_MAX); + CHECK_UNIFORM_64 (UINT64_C(1)<<33, UINT64_C(1)<<34); + CHECK_UNIFORM_64 (UINT64_C(1)<<34, UINT64_MAX); + } + + return 0; +} + +#include From patchwork Thu Jan 18 17:53:18 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella Netto X-Patchwork-Id: 124998 Delivered-To: patch@linaro.org Received: by 10.46.64.27 with SMTP id n27csp228435lja; Thu, 18 Jan 2018 09:54:11 -0800 (PST) X-Google-Smtp-Source: ACJfBosuPL5OBhcVZ93t1PERsNQOAu6k8MWwAj00jhnlcO5Y3EP88FMRdrEViLzsNg+nnB+bSWHS X-Received: by 10.98.172.7 with SMTP id v7mr21296524pfe.66.1516298051334; Thu, 18 Jan 2018 09:54:11 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1516298051; cv=none; d=google.com; s=arc-20160816; b=AkSRBvZktJXKeo/bHBLeqnwXkX158uX741ZZ13sohQNR+uW8fEZbmXR+KQ1ohg6ajc f8FuM7v5BlQ2Z424w6O0O1l6VoiIkIPF63hvxjbMaqXJi1jtz83xnm7dFwFeeCYpRD4c KdlnVPEcEK0XXs15F+faUbLdncW7RrDBJ9P307Dd0D1s4gX+fQyJioyawZb8o3hHBBBe yNlEw3RJ/sklsv0W9T81Tw4/Ao5RPkImgFysQKbXLfQ81f5/Y5AZFa3n2NbRAdUyLQfv skV82cbs4B+WB2Thk0jVn2RJS2BgJfL0Ab6K9XsCMOD2Ez0VrPoaYREm4/kEKf7twpFi 2CoQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=references:in-reply-to:message-id:date:subject:to:from:delivered-to :sender:list-help:list-post:list-archive:list-subscribe :list-unsubscribe:list-id:precedence:mailing-list:dkim-signature :domainkey-signature:arc-authentication-results; bh=QggD3hAev+rxfF0BB0PdXJ0Q1EVQyi19vfKiLrAPRMA=; b=FB5JLHoxs3XCA/4tUFCDm3ceEtjfiaU0UD1bygym0wBJjUw/7V0RAW2dMU/kFtTZxd P+zbI/ZTYbUoJPWFsVAqqlvEVXsOryXLuD7PQ3VmGA0lbvRfNTmHCTBb6AGWth/NwqPU kIBwQAWB1Owd1vX8x22tiFrbfGjxfZfTrnlOx+m45GSTM5xqGcJQ/mki7NnX1FFP/qkg 9blpl07Qa4zeXXYCmqsDd+65XZZSTdKJJr9cpVSWgvTTiiBD/u4Uay5oGQdMP0SHNtRL MUg9vHAiSTHd5zZA5D9ZrZbRk4LDkE8bEDGoxowARwLyLdXrz0T4G+O8XMPEh+uUa9kC OpmA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=UBfLSOSw; spf=pass (google.com: domain of libc-alpha-return-89325-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89325-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id i1-v6si76126plt.121.2018.01.18.09.54.10 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 18 Jan 2018 09:54:11 -0800 (PST) Received-SPF: pass (google.com: domain of libc-alpha-return-89325-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=UBfLSOSw; spf=pass (google.com: domain of libc-alpha-return-89325-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89325-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; q=dns; s=default; b=NTEPX+0SMAUS8K5h0yjSzSJ5BjfIqc4 pDQgieUxkaIw4fUe+hXZB0yzZBURWAKcZq7iasjBMmPJrsN+ik8CS+JmrK15+uIQ IsJo2j/jV4ZNS3lNQihWPSyZpCXOztVKBwcrFRbJs4dKROkM/ZjS/YVf8dQeMPSD ZNrYT2FYQ9aY= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; s=default; bh=1FkYefPP6Ogc6HU7HYQROrtX5dA=; b=UBfLS OSwoWLx5kNL/A1cpIgVeWRFS0f4tWkIQ/ahMtz4zYXhSN32SurP07SXr7/R8rvqb g5jgoLr9sb5m1JPPzqvoZQPjCHm8EZrZP2Ph3R0d9Epi7c0ZpKteg0Mp+aL7c15U xt9HW0vAYRgtimny9Fa1AjWKqqfS7kEyHpbumA= Received: (qmail 79498 invoked by alias); 18 Jan 2018 17:53:40 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 79378 invoked by uid 89); 18 Jan 2018 17:53:39 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.7 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 spammy=10001, positions, LOCALES X-HELO: mail-qt0-f179.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=QggD3hAev+rxfF0BB0PdXJ0Q1EVQyi19vfKiLrAPRMA=; b=icbgpPkfrZKbQI31mTXkXpFqQanqY+zw5CkWpE7d0xtO9FA75ICXw5iaLptWVSOIRz sN8OOTs47TfVJArCQIQUwSzyz3CUx6PzGm3SlHC2ceamoxorrIeMnyh4m1pxWyjYAWYB NUkEZeISxzl0Fu+OU1myYQb6M8fCkP6wNV5WY7HLorLOnz1N932+rEPOhgmWe4FdfoU/ LaTWugjjOhtwh55Nrjob/oIkZcsT2qFwHkM2IgkOJt9xiorvrEo4tRDKQAv8TzjvC8f3 JBjOfk9h2Ea5bQW1DgaIgMsMm+JqyxE2xlc4q4nFzewUDfqwtQ5TlJTua+XaZ8gEJy/3 9GKg== X-Gm-Message-State: AKwxytdzPpbp/e1cz/JVuYyV/sDutx1/Xjlom68dzhktt1hVKCPPTdNp xTNmBaJTMMzU6+sYYW3qjS7/2nD7MnU= X-Received: by 10.200.7.67 with SMTP id k3mr30694318qth.68.1516298013520; Thu, 18 Jan 2018 09:53:33 -0800 (PST) From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH 3/7] benchtests: Add bench-qsort Date: Thu, 18 Jan 2018 15:53:18 -0200 Message-Id: <1516298002-4618-4-git-send-email-adhemerval.zanella@linaro.org> In-Reply-To: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> References: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> This patch adds a qsort benchmark. I tried to model the benchmark taking in consideration the possible input variation in both internal element size, element numbers, and internal state for 1. real word cases and 2. possible scenarios based on hardware characteristics. For 1. I tracked qsort usage (using a simple preload library to dump its usage and a script to pos-process it) on both GCC bootstrap and Firefox. GCC 8 bootstrap build shows 51786641 call to qsort with the following characterics: Key: number of elements: key=2 : 39.74 key=3 : 19.23 key=4 : 9.77 key=1 : 8.44 key=0 : 6.60 key=5 : 4.40 key=7 : 2.37 key=6 : 2.25 key=9 : 1.48 key=8 : 0.97 Key: element size in bytes: key=8 : 91.74 key=32 : 3.62 key=4 : 2.42 key=40 : 1.20 key=16 : 0.67 key=24 : 0.30 key=48 : 0.05 key=56 : 0.00 key=1 : 0.00 Key: total size (number of elements * element size): key=16 : 35.98 key=24 : 18.67 key=32 : 9.79 key=8 : 8.28 key=0 : 6.60 key=40 : 4.21 key=64 : 3.15 key=48 : 2.24 key=56 : 2.15 key=80 : 1.45 So for GCC: - 80% of total qsort usage are done with 10 elements of less. - All usages are done element size of maximum of 56 bytes. - 90% of calls are done with array of maximum size of 80 bytes or less. The Firefox usage was done with 2 hours of usage, with first 10 minutes activelly openning and closing different types of sites. It resulted in 21042 calls with following characteristics: Key: number of elements: key=7 : 24.40 key=1 : 10.44 key=3 : 6.33 key=4 : 5.81 key=2 : 5.46 key=6 : 4.80 key=17 : 4.54 key=0 : 3.07 key=5 : 3.05 key=9 : 2.51 key=12 : 2.06 Key: element size in bytes: key=8 : 94.49 key=28 : 4.40 key=2 : 0.70 key=16 : 0.19 key=36 : 0.07 key=12 : 0.07 key=40 : 0.07 key=24 : 0.03 Key: total size (number of elements * element size): key=56 : 24.20 key=8 : 10.27 key=24 : 6.36 key=32 : 5.86 key=16 : 5.46 key=48 : 4.80 key=476 : 3.75 key=0 : 3.07 key=40 : 3.05 key=72 : 2.50 So for Firefox: - 72% of total qsort usage are done with 18 elements of less. - All usages are done element size of maximum of 40 bytes. - 70% of calls are done with array of maximum size of 476 bytes or less. For 2. I used the idea of a machine with 3 levels of cache with sizes 32kb (L1), 256kb (L2), and 4096 (L3). It resulted in a benchmark with following traits: * It checks four types of input arrays: sorted, mostly sorted, unsorted, and repeated. For 'sorted' the array is already sorted, 'mostly sorted' the array will have a certain number of random elements with random values (current ratio used is 20%), for 'unsorted' the array will contain random elements from full range based on used type, and for 'repeated' the array will have random elements with a certain number (current ratio is 20%) of a repeated element distributed randomly. * Three elements sizes are checked: uint32_t, uint64_t, and an element with 32 bytes (but using the uint64_t comparison checks). These element sizes are used to 1. to avoid include the comparison function itself and/or memory copy in sort benchmark itself, and 2. because key of size_t are the most used for both GCC and Firefox. * Five different element numbers: 64 (which cover mostly of used element sizes for both GCC and Firefox), 4096/8192 (which cover 32 KB of L1 for 32 and 64 bits), 32768/65536 (L2 with 256 KB), and 24288/1048576 (L3 with 4 MB). The sizes are configurable by --nelem option. Checked on x86_64-linux-gnu * benchtests/Makefile (stdlib-benchset): Add qsort. * benchtests/bench-qsort.c: New file. --- benchtests/Makefile | 2 +- benchtests/bench-qsort.c | 352 +++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 353 insertions(+), 1 deletion(-) create mode 100644 benchtests/bench-qsort.c -- 2.7.4 diff --git a/benchtests/Makefile b/benchtests/Makefile index ff99d25..6d6a5e9 100644 --- a/benchtests/Makefile +++ b/benchtests/Makefile @@ -66,7 +66,7 @@ LOCALES := en_US.UTF-8 tr_TR.UTF-8 cs_CZ.UTF-8 fa_IR.UTF-8 fr_FR.UTF-8 \ include ../gen-locales.mk endif -stdlib-benchset := strtod +stdlib-benchset := strtod qsort stdio-common-benchset := sprintf diff --git a/benchtests/bench-qsort.c b/benchtests/bench-qsort.c new file mode 100644 index 0000000..097459b --- /dev/null +++ b/benchtests/bench-qsort.c @@ -0,0 +1,352 @@ +/* Measure qsort function. + Copyright (C) 2018 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 +#include + +#include "json-lib.h" +#include "bench-timing.h" +#include "bench-util.h" + +#include +#include +#include + +#define ARRAY_SIZE(__array) (sizeof (__array) / sizeof (__array[0])) + +/* Type of inputs arrays: + - Sorted: array already sorted in placed. + - MostlySorted: sorted array with 'MostlySortedRatio * size' elements + in random positions set to random values. + - Unsorted: all elements in array set to random values. + - Repeated: random array with 'RepeatedRation' elements in random + positions set to an unique value. */ +typedef enum { + Sorted = 0, + MostlySorted = 1, + Unsorted = 2, + Repeated = 3, +} arraytype_t; + +/* Ratio of total of elements which will randomized. */ +static const double MostlySortedRatio = 0.2; + +/* Ratio of total of elements which will be repeated. */ +static const double RepeatedRatio = 0.2; + +struct array_t +{ + arraytype_t type; + const char *name; +} arraytypes[] = +{ + { Sorted, "Sorted" }, + { Unsorted, "Unsorted" }, + { MostlySorted, "MostlySorted" }, + { Repeated, "Repeated" }, +}; + + +typedef int (*cmpfunc_t)(const void *, const void *); +typedef void (*seq_element_t) (void *, size_t); + +static inline void * +arr (void *base, size_t idx, size_t size) +{ + return (void*)((uintptr_t)base + (idx * size)); +} + +static struct mt19937_64 mt; + +/* Fill the BUFFER with size SIZE in bytes with random uint64_t obtained from + the global MT state. */ +static inline void +fill_rand (void *buffer, size_t size) +{ + uint8_t *array = (uint8_t*)(buffer); + for (size_t i = 0; i < size; i++) + array[i] = uniform_uint64_distribution (mt64_rand (&mt), 0, UINT8_MAX); +} + +static void * +create_array (size_t nmemb, size_t type_size, arraytype_t type, + seq_element_t seq) +{ + size_t size = nmemb * type_size; + void *array = xmalloc (size); + + switch (type) + { + case Sorted: + for (size_t i = 0; i < nmemb; i++) + seq (arr (array, i, type_size), i); + break; + + case MostlySorted: + { + for (size_t i = 0; i < nmemb; i++) + seq (arr (array, i, type_size), i); + + /* Change UNSORTED elements (based on MostlySortedRatio ratio) + in the sorted array. */ + size_t unsorted = (size_t)(nmemb * MostlySortedRatio); + for (size_t i = 0; i < unsorted; i++) + { + size_t pos = uniform_uint64_distribution (mt64_rand (&mt), 0, + nmemb - 1); + fill_rand (arr (array, pos, type_size), type_size); + } + } + break; + + case Unsorted: + fill_rand (array, size); + break; + + case Repeated: + { + fill_rand (array, size); + + void *randelem = xmalloc (type_size); + fill_rand (randelem, type_size); + + /* Repeat REPEATED elements (based on RepeatRatio ratio) in the random + array. */ + size_t repeated = (size_t)(nmemb * RepeatedRatio); + for (size_t i = 0; i < repeated; i++) + { + size_t pos = uniform_uint64_distribution (mt64_rand (&mt), 0, + nmemb - 1); + memcpy (arr (array, pos, type_size), randelem, type_size); + } + free (randelem); + } + break; + } + + return array; +} + +/* Functions for uint32_t type. */ +static int +cmp_uint32_t (const void *a, const void *b) +{ + uint32_t ia = *(uint32_t*)a; + uint32_t ib = *(uint32_t*)b; + return (ia > ib) - (ia < ib); +} + +static void +seq_uint32_t (void *base, size_t idx) +{ + *(uint32_t *)base = idx; +} + +/* Functions for uint64_t type. */ +static int +cmp_uint64_t (const void *a, const void *b) +{ + uint64_t ia = *(uint64_t*)a; + uint64_t ib = *(uint64_t*)b; + return (ia > ib) - (ia < ib); +} + +static void +seq_uint64_t (void *base, size_t idx) +{ + *(uint64_t *)base = idx; +} + +/* Number of elements of determined type to be measured. */ +static const size_t default_elem[] = +{ + 256/sizeof(size_t), /* 64/128 which covers mostly used element number + on GCC build. */ + 32768/sizeof(size_t), /* 4096/8192 to fit on a L1 with 32 KB. */ + 262144/sizeof(size_t), /* 32768/65536 to fit on a L2 with 256 KB. */ + 4194304/sizeof(size_t), /* 524288/1048576 to fix on a L3 with 4 MB. */ +}; + + +#define OPT_NELEM 10000 +#define OPT_SEED 10001 +#define CMDLINE_OPTIONS \ + { "nelem", required_argument, NULL, OPT_NELEM }, \ + { "seed", required_argument, NULL, OPT_SEED }, + +static const size_t max_nelem = 16; +static size_t *elems = NULL; +static size_t nelem = 0; +static uint64_t seed = 0; +static bool seed_set = false; + +static void __attribute__ ((used)) +cmdline_process_function (int c) +{ + switch (c) + { + /* Handle the --nelem option to run different sizes than DEFAULT_ELEM. + The elements sizes as passed with a ':' as the delimiter, for + instance --nelem 32:128:1024 will ran 32, 128, and 1024 elements. */ + case OPT_NELEM: + { + elems = xmalloc (max_nelem * sizeof (size_t)); + nelem = 0; + + char *saveptr; + char *token; + token = strtok_r (optarg, ":", &saveptr); + if (token == NULL) + { + printf ("error: invalid --nelem value\n"); + exit (EXIT_FAILURE); + } + do + { + if (nelem == max_nelem) + { + printf ("error: invalid --nelem value (max elem)\n"); + exit (EXIT_FAILURE); + } + elems[nelem++] = atol (token); + token = strtok_r (saveptr, ":", &saveptr); + } while (token != NULL); + } + break; + + /* handle the --seed option to use a different seed than a random one. + The SEED used should be a uint64_t number. */ + case OPT_SEED: + { + unsigned long int value = strtoull (optarg, NULL, 0); + if (errno == ERANGE || value > UINT64_MAX) + { + printf ("error: seed should be a value in range of " + "[0, UINT64_MAX]\n"); + exit (EXIT_FAILURE); + } + seed = value; + seed_set = true; + } + } +} + +#define CMDLINE_PROCESS cmdline_process_function + +static const size_t inner_loop_iters = 16; + +struct run_t +{ + size_t type_size; + cmpfunc_t cmp; + seq_element_t seq; +}; +static const struct run_t runs[] = +{ + { sizeof (uint32_t), cmp_uint32_t, seq_uint32_t }, + { sizeof (uint64_t), cmp_uint64_t, seq_uint64_t }, + { 32, cmp_uint64_t, seq_uint64_t }, +}; + +static int +do_test (void) +{ + if (!seed_set) + { + /* Use default seed in case of error. */ + random_seed (&seed, sizeof (seed)); + } + mt64_seed (&mt, seed); + + 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, "qsort"); + json_attr_uint (&json_ctx, "seed", seed); + + json_array_begin (&json_ctx, "results"); + + const size_t *welem = elems == NULL ? default_elem : elems; + const size_t wnelem = elems == NULL ? ARRAY_SIZE (default_elem) + : nelem; + + for (int j = 0; j < ARRAY_SIZE (runs); j++) + { + for (int i = 0; i < ARRAY_SIZE (arraytypes); i++) + { + for (int k = 0; k < wnelem; k++) + { + json_element_object_begin (&json_ctx); + + size_t nmemb = welem[k]; + size_t ts = runs[j].type_size; + size_t arraysize = nmemb * ts; + + json_attr_uint (&json_ctx, "nmemb", nmemb); + json_attr_uint (&json_ctx, "type_size", ts); + json_attr_string (&json_ctx, "property", arraytypes[i].name); + + void *base = create_array (nmemb, ts, arraytypes[i].type, runs[j].seq); + void *work = xmalloc (arraysize); + + timing_t total; + TIMING_INIT (total); + + for (int n = 0; n < inner_loop_iters; n++) + { + memcpy (work, base, arraysize); + + timing_t start, end, diff; + TIMING_NOW (start); + qsort (work, nmemb, ts, runs[j].cmp); + TIMING_NOW (end); + + TIMING_DIFF (diff, start, end); + TIMING_ACCUM (total, diff); + } + + json_attr_uint (&json_ctx, "timings", + (double) total / (double) inner_loop_iters); + json_element_object_end (&json_ctx); + + free (base); + free (work); + } + } + } + + json_array_end (&json_ctx); + + json_attr_object_end (&json_ctx); + json_attr_object_end (&json_ctx); + json_document_end (&json_ctx); + + return 0; +} + +#define TIMEOUT 600 +#include From patchwork Thu Jan 18 17:53:19 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella Netto X-Patchwork-Id: 124999 Delivered-To: patch@linaro.org Received: by 10.46.64.27 with SMTP id n27csp228476lja; Thu, 18 Jan 2018 09:54:21 -0800 (PST) X-Google-Smtp-Source: ACJfBouK8U2kNuz+dSlPRKrmaJ7OUq8MVECzrKtSgvuzduPsXXyKLRUzMlcydw2RcGvzMHIdKcOD X-Received: by 10.101.89.3 with SMTP id f3mr25523422pgu.372.1516298060897; Thu, 18 Jan 2018 09:54:20 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1516298060; cv=none; d=google.com; s=arc-20160816; b=bmEevi7WqWNdf2fyMOP5UwwEoiW7b5V1twlGZpTSXVT1vud/MZOBv23ZTgKN30RdHk YU2P06ZlHESKT5yNmhFORvwwhH2rr/fdhS50/1HTAxku20NZ3oqUvd2fp3+0hqdnFz1T byIXT68UZo1bwqPMPlaRgMg+S8fkLM14DtZCDx9Z2bGdYhxbsYnnMQQ1mf9hojmMivij WCEP2tqw1jXI+INJI437JPwk8lbAcETAS4WonlUd8Cg2A2UmNh7FGMGLara3Ditq/5Dw IzjGDs+84yDAaetx0ul7Vhv+ZxkEkm+QoaiZbcqebulrbSiP61gUcG/UtwqVuu4SqFPa wvVA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=references:in-reply-to:message-id:date:subject:to:from:delivered-to :sender:list-help:list-post:list-archive:list-subscribe :list-unsubscribe:list-id:precedence:mailing-list:dkim-signature :domainkey-signature:arc-authentication-results; bh=uqx+aF1SgpMl+64rQmiJEefbCQmc9yel89nbkbgspxo=; b=WiMg1Z8AzjUkbppYpdF/DesrvkUFCqs+kWKo7m8kranV0X64Gc31WI3UaHMhIOYwEM oOryqHOxWx/nWscpbUYLHN4yr3vYDxaQYVEWwU+geTdNc1lUUZPfGazT8J2k0UrlikG2 f08V6w1oDC+4jBm6a4kFg+YJ6oYHybQUcBsOrP/MpSIJJnvqLMms9TH139QGAOYEhDd1 2kmvKcOP66u2PWYp6XM4mRAusgZgWcAaX4gynTYdCdx9vaOSXp1eOdNmON68jX4TLwwt JtnIxz3fGnUfKVqkDcAJ4u8n//qPe0mmKi7ysUUQSa9Ah9IK5EvqeBbeQAUWlYJfLL/p 6t5A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=K+FbnYtP; spf=pass (google.com: domain of libc-alpha-return-89326-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89326-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id k28si6533619pgf.251.2018.01.18.09.54.20 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 18 Jan 2018 09:54:20 -0800 (PST) Received-SPF: pass (google.com: domain of libc-alpha-return-89326-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=K+FbnYtP; spf=pass (google.com: domain of libc-alpha-return-89326-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89326-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; q=dns; s=default; b=ttFTF53r44OPEHzCMwn6EZaZmRxxkpR e7Cv/MzG0MEMNvYVdtV4FStf1gO7EMAl7oz+l1sjlG7vB4vYrMV8kpOypBTuSqXi 6quXgYhcoJYCjtCtA4YQH4/qk3w4qahNxIOc6HUvXQgfTZBY/Z/P114gJhjC/WvO TKBnGlIxwzgg= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; s=default; bh=z0pIBuRx1c6u+jdiZ9PKfpKAM74=; b=K+Fbn YtPjKFD2dD4PLWuc/ikYqNg3P2XTCALVkr9BhmXs9g11PtXXmtWdwiwD8bKjBiH0 eHGsnSOtx3iB5CX/clT6Obh9RYB7Z8NhpSFKfdjdK+kLwFw7UamNvJAYySLc135Y 1LbCArfR6tPZA13yhdywVovY5C0ugBQhymXtrw= Received: (qmail 79548 invoked by alias); 18 Jan 2018 17:53:40 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 79422 invoked by uid 89); 18 Jan 2018 17:53:39 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.2 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mail-qt0-f172.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=uqx+aF1SgpMl+64rQmiJEefbCQmc9yel89nbkbgspxo=; b=qnyG0cidKCL0rRT3WA0bAfBu508uUQmirBBEA8vMa8Nimt0klo3Dy8ar2/Fq9j3eUu 0XXsFVJ9hYICjmN/6YbBqyiXMXDlfDI/tzQIbUztHA4Mv5D71hD4SGhkvxVge67I1h6+ xzQ1NrG2RQ/IOcOwOgOBS2jOSfP1RG8Ln3zk3k/xxCGU8YjYhOpCee3nvoEiiEHng19n CJ2Rh+hhb5fohVoVwpifvYE9LfEo1oPNFEfWJaFJb/cglaVlm4I9C2sIMPUXi67+hvlS 1Uq4yQnfp/anZ0tGlwlTarZju782qkmIfYXqpIPcGZUG1SAwyAby2ayoyObyFgnMaM5b e0zQ== X-Gm-Message-State: AKwxytf3TesmFQrvhubvAE2di7MGJygu/ynAZka+yIdYgirRWwf9nPqQ tFR9uk9RvZEeqr28HPDv7S4tTBDDSrg= X-Received: by 10.55.113.199 with SMTP id m190mr26532391qkc.320.1516298015202; Thu, 18 Jan 2018 09:53:35 -0800 (PST) From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH 4/7] stdlib: Add more qsort{_r} coverage Date: Thu, 18 Jan 2018 15:53:19 -0200 Message-Id: <1516298002-4618-5-git-send-email-adhemerval.zanella@linaro.org> In-Reply-To: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> References: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> This patch adds a qsort and qsort_t (which glibc current lacks coverage). The test check with random input (created using support random) with different internal types (uint8_t, uint16_t, uint32_t, and uint64_t) and with different set of element numbers (from 0 to 262144). Checked on x86_64-linux-gnu. * stdlib/tst-qsort3.c: New file. * stdlib/Makefile (tests): Add tst-qsort3. --- stdlib/Makefile | 2 +- stdlib/tst-qsort3.c | 231 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 232 insertions(+), 1 deletion(-) create mode 100644 stdlib/tst-qsort3.c -- 2.7.4 diff --git a/stdlib/Makefile b/stdlib/Makefile index 7c363a6..6ef20a7 100644 --- a/stdlib/Makefile +++ b/stdlib/Makefile @@ -84,7 +84,7 @@ tests := tst-strtol tst-strtod testmb testrand testsort testdiv \ tst-cxa_atexit tst-on_exit test-atexit-race \ test-at_quick_exit-race test-cxa_atexit-race \ test-on_exit-race test-dlclose-exit-race \ - tst-makecontext-align + tst-makecontext-align tst-qsort3 tests-internal := tst-strtod1i tst-strtod3 tst-strtod4 tst-strtod5i \ tst-tls-atexit tst-tls-atexit-nodelete diff --git a/stdlib/tst-qsort3.c b/stdlib/tst-qsort3.c new file mode 100644 index 0000000..e6ddb60 --- /dev/null +++ b/stdlib/tst-qsort3.c @@ -0,0 +1,231 @@ +/* qsort(_r) generic tests. + Copyright (C) 2017 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 + +#include +#include +#include +#include + +/* Functions used to check qsort. */ +static int +uint8_t_cmp (const void *a, const void *b) +{ + uint8_t ia = *(uint8_t*)a; + uint8_t ib = *(uint8_t*)b; + return (ia > ib) - (ia < ib); +} + +static int +uint16_t_cmp (const void *a, const void *b) +{ + uint16_t ia = *(uint16_t*)a; + uint16_t ib = *(uint16_t*)b; + return (ia > ib) - (ia < ib); +} + +static int +uint32_t_cmp (const void *a, const void *b) +{ + uint32_t ia = *(uint32_t*)a; + uint32_t ib = *(uint32_t*)b; + return (ia > ib) - (ia < ib); +} + +static int +uint64_t_cmp (const void *a, const void *b) +{ + uint64_t ia = *(uint64_t*)a; + uint64_t ib = *(uint64_t*)b; + return (ia > ib) - (ia < ib); +} + +/* Function used to check qsort_r. */ + +enum type_cmp_t +{ + UINT8_CMP_T = 0, + UINT16_CMP_T = 1, + UINT32_CMP_T = 2, + UINT64_CMP_T = 3, +}; + +static enum type_cmp_t +uint_t_cmp_type (size_t sz) +{ + switch (sz) + { + case sizeof (uint8_t): return UINT8_CMP_T; + case sizeof (uint16_t): return UINT16_CMP_T; + case sizeof (uint64_t): return UINT64_CMP_T; + case sizeof (uint32_t): + default: return UINT32_CMP_T; + } +} + +static int +uint_t_cmp (const void *a, const void *b, void *arg) +{ + enum type_cmp_t type = *(enum type_cmp_t*) arg; + switch (type) + { + case UINT8_CMP_T: return uint8_t_cmp (a, b); + case UINT16_CMP_T: return uint16_t_cmp (a, b); + case UINT64_CMP_T: return uint64_t_cmp (a, b); + case UINT32_CMP_T: + default: return uint32_t_cmp (a, b); + } +} + +static struct mt19937_32 mt; + +static void * +create_array (size_t nmemb, size_t type_size) +{ + size_t size = nmemb * type_size; + uint8_t *array = xmalloc (size); + + for (size_t i = 0; i < size; i++) + array[i] = uniform_uint32_distribution (mt32_rand (&mt), 0, UINT8_MAX); + + return array; +} + +typedef int (*cmpfunc_t)(const void *, const void *); + +static void +check_array (void *array, size_t nmemb, size_t type_size, + cmpfunc_t cmpfunc) +{ + for (size_t i = 1; i < nmemb; i++) + { + void *array_i = (void*)((uintptr_t)array + i * type_size); + void *array_i_1 = (void*)((uintptr_t)array + (i-1) * type_size); + int ret; + TEST_VERIFY ((ret = cmpfunc (array_i, array_i_1)) >= 0); + if (ret < 0) + break; + } +} + +static uint32_t seed; + +#define OPT_SEED 10000 +#define CMDLINE_OPTIONS \ + { "seed", required_argument, NULL, OPT_SEED }, + +static void __attribute__ ((used)) +cmdline_process_function (int c) +{ + switch (c) + { + case OPT_SEED: + { + unsigned long int value = strtoul (optarg, NULL, 0); + if (errno == ERANGE || value > UINT32_MAX) + { + printf ("error: seed should be a value in range of " + "[0, UINT32_MAX]\n"); + exit (EXIT_FAILURE); + } + seed = value; + } + break; + } +} + +#define CMDLINE_PROCESS cmdline_process_function + + +static int +do_test (void) +{ + mt32_seed (&mt, seed); + printf ("info: seed=0x%08x\n", seed); + + const size_t elem[] = { 0, 1, 64, 128, 4096, 16384, 262144 }; + const size_t nelem = sizeof (elem) / sizeof (elem[0]); + + struct test_t + { + size_t type_size; + cmpfunc_t cmpfunc; + } + tests[] = + { + { sizeof (uint8_t), uint8_t_cmp }, + { sizeof (uint16_t), uint16_t_cmp }, + { sizeof (uint32_t), uint32_t_cmp }, + { sizeof (uint64_t), uint64_t_cmp }, + /* Test swap with large elements. */ + { 32, uint32_t_cmp }, + }; + size_t ntests = sizeof (tests) / sizeof (tests[0]); + + for (size_t i = 0; i < ntests; i++) + { + size_t ts = tests[i].type_size; + if (test_verbose > 0) + printf ("info: testing qsort with type_size=%zu\n", ts); + for (size_t n = 0; n < nelem; n++) + { + size_t nmemb = elem[n]; + if (test_verbose > 0) + printf (" nmemb=%zu, total size=%zu\n", nmemb, nmemb * ts); + + void *array = create_array (nmemb, ts); + + qsort (array, nmemb, ts, tests[i].cmpfunc); + + check_array (array, nmemb, ts, tests[i].cmpfunc); + + free (array); + } + } + + for (size_t i = 0; i < ntests; i++) + { + size_t ts = tests[i].type_size; + if (test_verbose > 0) + printf ("info: testing qsort_r type_size=%zu\n", ts); + for (size_t n = 0; n < nelem; n++) + { + size_t nmemb = elem[n]; + if (test_verbose > 0) + printf (" nmemb=%zu, total size=%zu\n", nmemb, nmemb * ts); + + void *array = create_array (nmemb, ts); + + enum type_cmp_t type = uint_t_cmp_type (ts); + qsort_r (array, nmemb, ts, uint_t_cmp, &type); + + check_array (array, nmemb, ts, tests[i].cmpfunc); + + free (array); + } + } + + return 0; +} + +#include From patchwork Thu Jan 18 17:53:20 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella Netto X-Patchwork-Id: 125001 Delivered-To: patch@linaro.org Received: by 10.46.64.27 with SMTP id n27csp228606lja; Thu, 18 Jan 2018 09:54:43 -0800 (PST) X-Google-Smtp-Source: ACJfBosW3xHiO8SYkkBVRC2h3tpyFEvCA2f4xAno3PxFLAGI7338gUDUi3VfjD1Q+2KBeMD7f6hB X-Received: by 2002:a17:902:43:: with SMTP id 61-v6mr174877pla.73.1516298083439; Thu, 18 Jan 2018 09:54:43 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1516298083; cv=none; d=google.com; s=arc-20160816; b=RFoaHGhJiGzlcMMy6+kUJ4s3SDvXhtyI4IGSOM+QcJ18Si0iEWiXK/dtOPE8kBSUVn 6Gy/t8cUP9gYpzq7clqYlqb8ItAGtFwxtdZK7dKzK/ykwr7gablNPlcjghDloFAgobh2 cffYI+885hpQQPtZ3e5WwS5Y+bkPHh3bIZPdqCaG6fMHk6Zedhj5xzVxwgOoNuY+qxsN JyaqxLS6mETaV/CUAkMFlK16WTuuYjTvY2XepmYcjQ5GnCLft2tGUUKW6ESTShJ8a7vq TXuj8eCTRwoMC18VCnAR1pg7rsX8dSS2sOMssJzIvcXACB6S7Sm4qhOgHwDwIcC4Cf0e 1dPQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=references:in-reply-to:message-id:date:subject:to:from:delivered-to :sender:list-help:list-post:list-archive:list-subscribe :list-unsubscribe:list-id:precedence:mailing-list:dkim-signature :domainkey-signature:arc-authentication-results; bh=KEHpGdchErgE0wKtK4Md1ZzXe8xzo5yjs9zGFERBbWQ=; b=dLdvFelqu7XB0SomUubxD1Jt5EY/1rB47gVXDmHWegNrDi3lqnoij2Mcll6j3knKYF 3j3651UYgBlAryFUkK1RYSO1J48f1TwMl0HE96nOVPi/EqOdpp3uYcvZQA3pEb8Wrrq4 nUwAZztbzDfvphS+Usvi/M+wD9TZb+0VPB4qiVTeQlbXkGz8vJlu+SYNeH5e1TuqaHoQ gQYTVnKZ/TRRv2sGOdSReVz+5KqBD6DeEdCw1YLTpWH68A4K7ubRk3ZtKi0t0+1RVJpn 9OQXmLe7lPjFu1iTUK+S291eU/7e8zyNbkLYgjY3oMjQHCGZLj5ZpkRO5Kvcb8HqQR0i iMlA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=IrNTT2q4; spf=pass (google.com: domain of libc-alpha-return-89328-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89328-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id y68si7351746pfd.104.2018.01.18.09.54.43 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 18 Jan 2018 09:54:43 -0800 (PST) Received-SPF: pass (google.com: domain of libc-alpha-return-89328-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=IrNTT2q4; spf=pass (google.com: domain of libc-alpha-return-89328-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89328-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; q=dns; s=default; b=IKR5zxC6oJnocDyUuzMEKfyA/DK17lm 9krs5JLRNzaNkZw4+ltU+2HxkSYmDPIpuVXoCmfAS5t7FvP4mHWXVkt07xwLndlw FjxpZJJOXtPt+a5Z1PSWqVWu8zM2BQOzds8tyEgM6cv08mE1XNolujJA/prrQBo8 xQJWfRD/0n6Y= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; s=default; bh=AyueZ5TKg3HkvOdtr0QqBL4IBZY=; b=IrNTT 2q42boxWUcVx6LFUa75Kt5uYTC+aB7kME/XZJoMxngn5YV2CoJQp6pe3lBKNWq3/ WaRo6V88vkrAZZNmVT32Rbfei/Kpyj6k6mkQYUnuWgvFOsI9CeYOJlKehqW0g1i9 +7n1MM3NVPjW1O9c5f5QdMoNAdHRg//pqwHx/Y= Received: (qmail 80037 invoked by alias); 18 Jan 2018 17:53:43 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 79916 invoked by uid 89); 18 Jan 2018 17:53:43 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.3 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=Engineering, thereby X-HELO: mail-qt0-f171.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=KEHpGdchErgE0wKtK4Md1ZzXe8xzo5yjs9zGFERBbWQ=; b=TUILyYrIJEMvhAyUcmr+HlFldcdFXbkMgkoOaOR6S7undGVrtH38t24ElD5jgBvVmW qiO445Om5tRoil/knayRgOSrNPkoWY5MeYdTEWH1lP8mCBNOXJCfv+Rcex3tNvJcbi/g 5Eo5LpqZhl3uyXA4oulhcvFuyg0bP4OvL8MnqqQ7K2UfN41uyBksT/ZAFfhb38jG2q1E chpP1qVl4sZqEDi1X2qOLWx1no0Xb1nucWZcR7NYUNlJ66p4xdALTWhvH3qRFYun1mEA TKPtfwBZPNKvEeEN5ClU/EruCsZ3SKjqOXnqbnLewuzsJOiXM8bkfUPoiiatgIdCuk7a TVYw== X-Gm-Message-State: AKwxyteZThyfM+w/Z4KDIgdcO3m09ZRo1FeFG6cJRGP82Z+hIt+ffOGS igN0IqIuafVUMknBPXsYCnJmvIaMp8s= X-Received: by 10.200.24.202 with SMTP id o10mr28653355qtk.27.1516298016696; Thu, 18 Jan 2018 09:53:36 -0800 (PST) From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH 5/7] stdlib: Remove use of mergesort on qsort Date: Thu, 18 Jan 2018 15:53:20 -0200 Message-Id: <1516298002-4618-6-git-send-email-adhemerval.zanella@linaro.org> In-Reply-To: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> References: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> This patch removes the mergesort optimization on qsort{_r} implementation and use the quicksort instead. The mergesort implementation has some issues: - It is as-safe only for certain types sizes (if total size is less than 1 KB with large element sizes also forcing memory allocation) which contradicts the function documentation. Although not required by the C standard, it is preferable and doable to have a O(1) space qsort implementation. - The malloc for certain element size and element number adds arbitrary latency (might even be worse if malloc is interposed). - To avoid trigger swap from memory allocation the implementation relies on system information that might be virtualized (for instance VMs with overcommit memory) which might leads to potentially use of swap even if system advertise more memory than actually has. The check also have the downside of issuing syscalls where none is expected (although only once per execution). - The mergesort is suboptimal on already sorted array (BZ#21719). The quicksort implementation is already optimized to use constant extra space (due the limit of total number of elements from maximum VM size) and thus can be used to avoid the malloc usage issues. Using bench-qsort (i7-4790K, gcc 7.2.1) shows the performance difference between mergesort (base) and quicksort (patched): Results for member size 4 Sorted nmemb | base | patched | diff 32| 1447 | 1401 | -3.18 4096| 315978 | 351333 | 11.19 32768| 2559093 | 3369386 | 31.66 524288| 46228488 | 63192972 | 36.70 MostlySorted nmemb | base | patched | diff 32| 1974 | 2391 | 21.12 4096| 922332 | 1124074 | 21.87 32768| 9268671 | 11196607 | 20.80 524288| 186856297 | 215908169 | 15.55 Unsorted nmemb | base | patched | diff 32| 1978 | 4993 | 152.43 4096| 916413 | 1113860 | 21.55 32768| 9270003 | 11251293 | 21.37 524288| 187606088 | 217252237 | 15.80 Results for member size 8 Sorted nmemb | base | patched | diff 32| 1424 | 1296 | -8.99 4096| 299105 | 359418 | 20.16 32768| 2737859 | 3535229 | 29.12 524288| 53082807 | 69847251 | 31.58 MostlySorted nmemb | base | patched | diff 32| 2129 | 2745 | 28.93 4096| 969465 | 1222082 | 26.06 32768| 9605227 | 12244800 | 27.48 524288| 193353927 | 241557971 | 24.93 Unsorted nmemb | base | patched | diff 32| 2194 | 2972 | 35.46 4096| 958610 | 1314861 | 37.16 32768| 9664246 | 12397909 | 28.29 524288| 193758429 | 241789262 | 24.79 Results for member size 32 Sorted nmemb | base | patched | diff 32| 4477 | 1305 | -70.85 4096| 1109492 | 346332 | -68.78 32768| 11075976 | 3458244 | -68.78 524288| 230773658 | 72793445 | -68.46 MostlySorted nmemb | base | patched | diff 32| 5905 | 5435 | -7.96 4096| 2568895 | 2032260 | -20.89 32768| 24936755 | 19909035 | -20.16 524288| 526442900 | 390339319 | -25.85 Unsorted nmemb | base | patched | diff 32| 6004 | 5833 | -2.85 4096| 2437943 | 2022531 | -17.04 32768| 24789971 | 19842888 | -19.96 524288| 525898556 | 388838382 | -26.06 An increase in latency, however some performance difference is due the fact mergesort uses a slight improved swap operation than quicksort (which following patch addresses). This change also renders the BZ #21719 fix unrequired (since it is to fix the sorted input performance degradation for mergesort). The manual is also updated to indicate the function is not async-cancel safe. Checked on x86_64-linux-gnu. [BZ #21719] * stdlib/Makefile (routines): Remove msort. (CFLAGS-msort.c): Remove rule. * stdlib/msort.c: Remove file. * stdlib/qsort.c (_quicksort): Rename to __qsort_r and add weak_alias to qsort_r. (qsort): New symbol. * manual/argp.texi: Remove qsort @acu* annotation. * manual/locale.texi: Likewise. * manual/search.texi: Likewise. --- manual/argp.texi | 2 +- manual/locale.texi | 3 +- manual/search.texi | 7 +- stdlib/Makefile | 9 +- stdlib/msort.c | 310 ----------------------------------------------------- stdlib/qsort.c | 15 ++- 6 files changed, 21 insertions(+), 325 deletions(-) delete mode 100644 stdlib/msort.c -- 2.7.4 diff --git a/manual/argp.texi b/manual/argp.texi index 0023441..b77ad68 100644 --- a/manual/argp.texi +++ b/manual/argp.texi @@ -735,7 +735,7 @@ for options, bad phase of the moon, etc. @c hol_set_group ok @c hol_find_entry ok @c hol_sort @mtslocale @acucorrupt -@c qsort dup @acucorrupt +@c qsort dup @c hol_entry_qcmp @mtslocale @c hol_entry_cmp @mtslocale @c group_cmp ok diff --git a/manual/locale.texi b/manual/locale.texi index 60ad2a1..9e742e4 100644 --- a/manual/locale.texi +++ b/manual/locale.texi @@ -253,7 +253,7 @@ The symbols in this section are defined in the header file @file{locale.h}. @c calculate_head_size ok @c __munmap ok @c compute_hashval ok -@c qsort dup @acucorrupt +@c qsort dup @c rangecmp ok @c malloc @ascuheap @acsmem @c strdup @ascuheap @acsmem @@ -275,7 +275,6 @@ The symbols in this section are defined in the header file @file{locale.h}. @c realloc @ascuheap @acsmem @c realloc @ascuheap @acsmem @c fclose @ascuheap @asulock @acsmem @acsfd @aculock -@c qsort @ascuheap @acsmem @c alias_compare dup @c libc_lock_unlock @aculock @c _nl_explode_name @ascuheap @acsmem diff --git a/manual/search.texi b/manual/search.texi index 57dad7a..148d451 100644 --- a/manual/search.texi +++ b/manual/search.texi @@ -159,7 +159,7 @@ To sort an array using an arbitrary comparison function, use the @deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare}) @standards{ISO, stdlib.h} -@safety{@prelim{}@mtsafe{}@assafe{}@acunsafe{@acucorrupt{}}} +@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}} The @code{qsort} function sorts the array @var{array}. The array contains @var{count} elements, each of which is of size @var{size}. @@ -199,9 +199,8 @@ Functions}): The @code{qsort} function derives its name from the fact that it was originally implemented using the ``quick sort'' algorithm. -The implementation of @code{qsort} in this library might not be an -in-place sort and might thereby use an extra amount of memory to store -the array. +The implementation of @code{qsort} in this library is an in-place sort +and uses a constant extra space (allocated on the stack). @end deftypefun @node Search/Sort Example diff --git a/stdlib/Makefile b/stdlib/Makefile index 6ef20a7..a39a176 100644 --- a/stdlib/Makefile +++ b/stdlib/Makefile @@ -34,7 +34,7 @@ headers := stdlib.h bits/stdlib.h bits/stdlib-ldbl.h bits/stdlib-float.h \ routines := \ atof atoi atol atoll \ abort \ - bsearch qsort msort \ + bsearch qsort \ getenv putenv setenv secure-getenv \ exit on_exit atexit cxa_atexit cxa_finalize old_atexit \ quick_exit at_quick_exit cxa_at_quick_exit cxa_thread_atexit_impl \ @@ -135,10 +135,9 @@ extra-test-objs += tst-putenvmod.os generated += isomac isomac.out tst-putenvmod.so -CFLAGS-bsearch.c += $(uses-callbacks) -CFLAGS-msort.c += $(uses-callbacks) -CFLAGS-qsort.c += $(uses-callbacks) -CFLAGS-system.c += -fexceptions +CFLAGS-bsearch.c = $(uses-callbacks) +CFLAGS-qsort.c = $(uses-callbacks) +CFLAGS-system.c = -fexceptions CFLAGS-system.os = -fomit-frame-pointer CFLAGS-fmtmsg.c += -fexceptions diff --git a/stdlib/msort.c b/stdlib/msort.c deleted file mode 100644 index 266c253..0000000 --- a/stdlib/msort.c +++ /dev/null @@ -1,310 +0,0 @@ -/* An alternative to qsort, with an identical interface. - This file is part of the GNU C Library. - Copyright (C) 1992-2018 Free Software Foundation, Inc. - Written by Mike Haertel, September 1988. - - 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 -#include -#include -#include - -struct msort_param -{ - size_t s; - size_t var; - __compar_d_fn_t cmp; - void *arg; - char *t; -}; -static void msort_with_tmp (const struct msort_param *p, void *b, size_t n); - -static void -msort_with_tmp (const struct msort_param *p, void *b, size_t n) -{ - char *b1, *b2; - size_t n1, n2; - - if (n <= 1) - return; - - n1 = n / 2; - n2 = n - n1; - b1 = b; - b2 = (char *) b + (n1 * p->s); - - msort_with_tmp (p, b1, n1); - msort_with_tmp (p, b2, n2); - - char *tmp = p->t; - const size_t s = p->s; - __compar_d_fn_t cmp = p->cmp; - void *arg = p->arg; - switch (p->var) - { - case 0: - while (n1 > 0 && n2 > 0) - { - if ((*cmp) (b1, b2, arg) <= 0) - { - *(uint32_t *) tmp = *(uint32_t *) b1; - b1 += sizeof (uint32_t); - --n1; - } - else - { - *(uint32_t *) tmp = *(uint32_t *) b2; - b2 += sizeof (uint32_t); - --n2; - } - tmp += sizeof (uint32_t); - } - break; - case 1: - while (n1 > 0 && n2 > 0) - { - if ((*cmp) (b1, b2, arg) <= 0) - { - *(uint64_t *) tmp = *(uint64_t *) b1; - b1 += sizeof (uint64_t); - --n1; - } - else - { - *(uint64_t *) tmp = *(uint64_t *) b2; - b2 += sizeof (uint64_t); - --n2; - } - tmp += sizeof (uint64_t); - } - break; - case 2: - while (n1 > 0 && n2 > 0) - { - unsigned long *tmpl = (unsigned long *) tmp; - unsigned long *bl; - - tmp += s; - if ((*cmp) (b1, b2, arg) <= 0) - { - bl = (unsigned long *) b1; - b1 += s; - --n1; - } - else - { - bl = (unsigned long *) b2; - b2 += s; - --n2; - } - while (tmpl < (unsigned long *) tmp) - *tmpl++ = *bl++; - } - break; - case 3: - while (n1 > 0 && n2 > 0) - { - if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0) - { - *(void **) tmp = *(void **) b1; - b1 += sizeof (void *); - --n1; - } - else - { - *(void **) tmp = *(void **) b2; - b2 += sizeof (void *); - --n2; - } - tmp += sizeof (void *); - } - break; - default: - while (n1 > 0 && n2 > 0) - { - if ((*cmp) (b1, b2, arg) <= 0) - { - tmp = (char *) __mempcpy (tmp, b1, s); - b1 += s; - --n1; - } - else - { - tmp = (char *) __mempcpy (tmp, b2, s); - b2 += s; - --n2; - } - } - break; - } - - if (n1 > 0) - memcpy (tmp, b1, n1 * s); - memcpy (b, p->t, (n - n2) * s); -} - - -void -__qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg) -{ - size_t size = n * s; - char *tmp = NULL; - struct msort_param p; - - /* For large object sizes use indirect sorting. */ - if (s > 32) - size = 2 * n * sizeof (void *) + s; - - if (size < 1024) - /* The temporary array is small, so put it on the stack. */ - p.t = __alloca (size); - else - { - /* We should avoid allocating too much memory since this might - have to be backed up by swap space. */ - static long int phys_pages; - static int pagesize; - - if (pagesize == 0) - { - phys_pages = __sysconf (_SC_PHYS_PAGES); - - if (phys_pages == -1) - /* Error while determining the memory size. So let's - assume there is enough memory. Otherwise the - implementer should provide a complete implementation of - the `sysconf' function. */ - phys_pages = (long int) (~0ul >> 1); - - /* The following determines that we will never use more than - a quarter of the physical memory. */ - phys_pages /= 4; - - /* Make sure phys_pages is written to memory. */ - atomic_write_barrier (); - - pagesize = __sysconf (_SC_PAGESIZE); - } - - /* Just a comment here. We cannot compute - phys_pages * pagesize - and compare the needed amount of memory against this value. - The problem is that some systems might have more physical - memory then can be represented with a `size_t' value (when - measured in bytes. */ - - /* If the memory requirements are too high don't allocate memory. */ - if (size / pagesize > (size_t) phys_pages) - { - _quicksort (b, n, s, cmp, arg); - return; - } - - /* It's somewhat large, so malloc it. */ - int save = errno; - tmp = malloc (size); - __set_errno (save); - if (tmp == NULL) - { - /* Couldn't get space, so use the slower algorithm - that doesn't need a temporary array. */ - _quicksort (b, n, s, cmp, arg); - return; - } - p.t = tmp; - } - - p.s = s; - p.var = 4; - p.cmp = cmp; - p.arg = arg; - - if (s > 32) - { - /* Indirect sorting. */ - char *ip = (char *) b; - void **tp = (void **) (p.t + n * sizeof (void *)); - void **t = tp; - void *tmp_storage = (void *) (tp + n); - - while ((void *) t < tmp_storage) - { - *t++ = ip; - ip += s; - } - p.s = sizeof (void *); - p.var = 3; - msort_with_tmp (&p, p.t + n * sizeof (void *), n); - - /* tp[0] .. tp[n - 1] is now sorted, copy around entries of - the original array. Knuth vol. 3 (2nd ed.) exercise 5.2-10. */ - char *kp; - size_t i; - for (i = 0, ip = (char *) b; i < n; i++, ip += s) - if ((kp = tp[i]) != ip) - { - size_t j = i; - char *jp = ip; - memcpy (tmp_storage, ip, s); - - do - { - size_t k = (kp - (char *) b) / s; - tp[j] = jp; - memcpy (jp, kp, s); - j = k; - jp = kp; - kp = tp[k]; - } - while (kp != ip); - - tp[j] = jp; - memcpy (jp, tmp_storage, s); - } - } - else - { - if ((s & (sizeof (uint32_t) - 1)) == 0 - && ((char *) b - (char *) 0) % __alignof__ (uint32_t) == 0) - { - if (s == sizeof (uint32_t)) - p.var = 0; - else if (s == sizeof (uint64_t) - && ((char *) b - (char *) 0) % __alignof__ (uint64_t) == 0) - p.var = 1; - else if ((s & (sizeof (unsigned long) - 1)) == 0 - && ((char *) b - (char *) 0) - % __alignof__ (unsigned long) == 0) - p.var = 2; - } - msort_with_tmp (&p, b, n); - } - free (tmp); -} -libc_hidden_def (__qsort_r) -weak_alias (__qsort_r, qsort_r) - - -void -qsort (void *b, size_t n, size_t s, __compar_fn_t cmp) -{ - return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL); -} -libc_hidden_def (qsort) diff --git a/stdlib/qsort.c b/stdlib/qsort.c index 264a06b..b3a5102 100644 --- a/stdlib/qsort.c +++ b/stdlib/qsort.c @@ -20,7 +20,6 @@ Engineering a sort function; Jon Bentley and M. Douglas McIlroy; Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */ -#include #include #include #include @@ -86,8 +85,8 @@ typedef struct stack size is needed (actually O(1) in this case)! */ void -_quicksort (void *const pbase, size_t total_elems, size_t size, - __compar_d_fn_t cmp, void *arg) +__qsort_r (void *const pbase, size_t total_elems, size_t size, + __compar_d_fn_t cmp, void *arg) { char *base_ptr = (char *) pbase; @@ -247,3 +246,13 @@ _quicksort (void *const pbase, size_t total_elems, size_t size, } } } + +libc_hidden_def (__qsort_r) +weak_alias (__qsort_r, qsort_r) + +void +qsort (void *b, size_t n, size_t s, __compar_fn_t cmp) +{ + return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL); +} +libc_hidden_def (qsort) From patchwork Thu Jan 18 17:53:21 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella Netto X-Patchwork-Id: 125000 Delivered-To: patch@linaro.org Received: by 10.46.64.27 with SMTP id n27csp228548lja; Thu, 18 Jan 2018 09:54:33 -0800 (PST) X-Google-Smtp-Source: ACJfBovIyk5HxeuC3LD5fTIsaHgUaCUcd9kQR9t2aAQwh6PYZy7X+0bjWWdLkabbssMDwx5GXguO X-Received: by 10.98.225.7 with SMTP id q7mr6939446pfh.22.1516298072909; Thu, 18 Jan 2018 09:54:32 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1516298072; cv=none; d=google.com; s=arc-20160816; b=Glo+hPKxw0eS0C0c+Lmg+7vILAvLcx/F5Ri1VQFpqIiz9kDMXjSgWi1vX7/BmG4xeb NN019J0DZYpv9eCivg51SJVOLvMYrMrrDdGZrOmfZFIQo1A0D5XfTX1094eYKZWiygMa /kL+Q5bTeVykactUCfTf2YQAqOVews6yvU+S0BRNBp8vvbH9BrYeOBVEqVFia1eoo0K/ 1CV6X2JPPpklv7rlJdwrsvkM/NQQZ9alZIx4OIODnTOvGo5SzkCcPEV92IbZf2A9JKkV FnBnN/8xVhWxnYvrEsR4aM59eRyxXMC2Qm9B8L0bFQPiAeJAC9Q52rtf68w5Lh/7rtes ZG5A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=references:in-reply-to:message-id:date:subject:to:from:delivered-to :sender:list-help:list-post:list-archive:list-subscribe :list-unsubscribe:list-id:precedence:mailing-list:dkim-signature :domainkey-signature:arc-authentication-results; bh=R9hWCXWag6wiHTYJ1WPgdT1cVxJ7OO4Yn4vWhsaQhsg=; b=J/dZg876KWoFchcCxpNVbx/D8GKetcP2qhC1koO1Yw1Tckm2wUlbx6eOxRwfsf3b/p 5X58yWIjEIlf+sqrHwyyi13fO8SuOupzeRSETYwR7fGh94r6xt+u8YQ1644mK4fMu9YX jWskYV5STiiiX9vz/VDBfhGGfEEgJfk35H6AFiBHrRk+vvzOlyiDxeYBEtwUJzfskjlP vMlt/2AdEUnZtf0ik5OjCy2vyW1y4bQ2085Xn/n6MIgSaO6aJ8yEVUn8Nwo5vFo/RvSp 3Bs67Wa17WP0BL6XgpiruaVl+Jhda7H9elffJIg4Bq86e/k4YWeMRQD1bTsZN5kDW8fz 1edQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=VGgsy5i5; spf=pass (google.com: domain of libc-alpha-return-89327-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89327-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id z14si6456441pgo.298.2018.01.18.09.54.32 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 18 Jan 2018 09:54:32 -0800 (PST) Received-SPF: pass (google.com: domain of libc-alpha-return-89327-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=VGgsy5i5; spf=pass (google.com: domain of libc-alpha-return-89327-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89327-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; q=dns; s=default; b=D+Q2npHXmI60vGj4v8qM8e3noVvqjnA e46xOtrqOp0Xj8lNwW26WELDHW66Nzq6g5RnFTpVGIRp8a9ibotVImF9R2fw5KPZ qw8x4njkiJ6+FSKBH6DrgZDwhQpUkyXg8RGzuAw3cz+F3glsO42YJPamypf4uxsc zXfdYHSgXHXE= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; s=default; bh=BGJVDcxQ5ZKwiNAM7h7l+gwUO2I=; b=VGgsy 5i5v07oy8agFft3oSRlymO1bPfN3exhFOtPLhhgOqj1X8sF3EnyNkDHNfEh2a43u /zZ19f2IyxqJCL09W7qRXqIBnn5JOBz49kO2VUgsmRR1s5jJ9bwAjihjYT36dhtb oxQWzD2d4tpryCPcuBjlW9BqZ/preaWzsuaC1A= Received: (qmail 79878 invoked by alias); 18 Jan 2018 17:53:43 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 79784 invoked by uid 89); 18 Jan 2018 17:53:42 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.3 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mail-qt0-f194.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=R9hWCXWag6wiHTYJ1WPgdT1cVxJ7OO4Yn4vWhsaQhsg=; b=pZ47zC1rF0glkEruXZUg+2nPUe15Dcb0EqdRnSpAX5SOOd9kr39pesmMkvmafFu3Lc TPzf4l2qHibjiBE9Dd/xi5+E/e3G4YskOOVEwlis/ACwv51ax2mw2Fg2Owh2ZZevmc2v vy2WeeMvCUcTQUAuGFT6nX+074vEfaBnUmtKZsP48qVSld2kqfbkGaKFAh3bPm84VaJw O5og76hhPMjwX0KuPwOiA1A+QuKUgqF+JIeV8qynDNmT9NHZqBJ7r1ehLQMpQ93GWe64 VERKsch7oZhIEHm194+PNo+gatk+LSqyjuWg8Lz2n6WZCrcFrGjZJ0vtkduHY7DqGVwb 1QiQ== X-Gm-Message-State: AKwxytdhbrX6jZwbdQLgQfCSeNxF6SMVa8gtc+OzcpsADkUramd6EMB2 pBBoGAiwe66m8K8a6e5yuyUcEYMXpVg= X-Received: by 10.237.63.14 with SMTP id p14mr38271054qtf.225.1516298018289; Thu, 18 Jan 2018 09:53:38 -0800 (PST) From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH 6/7] stdlib: Optimization qsort{_r} swap implementation Date: Thu, 18 Jan 2018 15:53:21 -0200 Message-Id: <1516298002-4618-7-git-send-email-adhemerval.zanella@linaro.org> In-Reply-To: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> References: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> This patchs adds a optimized swap operation on qsort based in previous msort one. Instead of byte operation, three variants are provided: 1. Using uint32_t loads and stores. 2. Using uint64_t loads and stores. 3. Generic one with a temporary buffer and memcpy/mempcpy. The 1. and 2. option are selected only either if architecture defines _STRING_ARCH_unaligned or if base pointer is aligned to required type. This is due based on data for bench-qsort, usually programs calls qsort with array with multiple of machine word as element size. Benchmarking shows an increase performance: Results for member size 4 Sorted nmemb | base | patched | diff 32| 1401 | 1958 | 39.76 4096| 351333 | 368533 | 4.90 32768| 3369386 | 3131712 | -7.05 524288| 63192972 | 59807494 | -5.36 MostlySorted nmemb | base | patched | diff 32| 2391 | 2061 | -13.80 4096| 1124074 | 961816 | -14.43 32768| 11196607 | 9410438 | -15.95 524288| 215908169 | 185586732 | -14.04 Unsorted nmemb | base | patched | diff 32| 4993 | 2021 | -59.52 4096| 1113860 | 963126 | -13.53 32768| 11251293 | 9518795 | -15.40 524288| 217252237 | 185072278 | -14.81 Results for member size 8 Sorted nmemb | base | patched | diff 32| 1296 | 1267 | -2.24 4096| 359418 | 334852 | -6.83 32768| 3535229 | 3345157 | -5.38 524288| 69847251 | 67029358 | -4.03 MostlySorted nmemb | base | patched | diff 32| 2745 | 2340 | -14.75 4096| 1222082 | 1014314 | -17.00 32768| 12244800 | 9924706 | -18.95 524288| 241557971 | 196898760 | -18.49 Unsorted nmemb | base | patched | diff 32| 2972 | 2389 | -19.62 4096| 1314861 | 1024052 | -22.12 32768| 12397909 | 10120848 | -18.37 524288| 241789262 | 193414824 | -20.01 Results for member size 32 Sorted nmemb | base | patched | diff 32| 1305 | 1287 | -1.38 4096| 346332 | 347979 | 0.48 32768| 3458244 | 3408058 | -1.45 524288| 72793445 | 69973719 | -3.87 MostlySorted nmemb | base | patched | diff 32| 5435 | 4890 | -10.03 4096| 2032260 | 1688556 | -16.91 32768| 19909035 | 16419992 | -17.52 524288| 390339319 | 325921585 | -16.50 Unsorted nmemb | base | patched | diff 32| 5833 | 5351 | -8.26 4096| 2022531 | 1724961 | -14.71 32768| 19842888 | 16588545 | -16.40 524288| 388838382 | 324102703 | -16.65 Checked on x86_64-linux-gnu. [BZ #19305]. * stdlib/qsort.c (SWAP): Remove. (check_alignment, swap_u32, swap_u64, swap_generic, select_swap_func): New functions. (__qsort_r): --- stdlib/qsort.c | 77 ++++++++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 59 insertions(+), 18 deletions(-) -- 2.7.4 diff --git a/stdlib/qsort.c b/stdlib/qsort.c index b3a5102..2194003 100644 --- a/stdlib/qsort.c +++ b/stdlib/qsort.c @@ -23,20 +23,59 @@ #include #include #include +#include -/* Byte-wise swap two items of size SIZE. */ -#define SWAP(a, b, size) \ - do \ - { \ - size_t __size = (size); \ - char *__a = (a), *__b = (b); \ - do \ - { \ - char __tmp = *__a; \ - *__a++ = *__b; \ - *__b++ = __tmp; \ - } while (--__size > 0); \ - } while (0) +/* Swap SIZE bytes between addresses A and B. Helper to generic types + are provided as an optimization. */ + +typedef void (*swap_t)(void *, void *, size_t); + +static inline bool +check_alignment (const void *base, size_t align) +{ + return _STRING_ARCH_unaligned || ((uintptr_t)base % (align - 1)) == 0; +} + +static void +swap_u32 (void *a, void *b, size_t size) +{ + uint32_t tmp = *(uint32_t*) a; + *(uint32_t*) a = *(uint32_t*) b; + *(uint32_t*) b = tmp; +} + +static void +swap_u64 (void *a, void *b, size_t size) +{ + uint64_t tmp = *(uint64_t*) a; + *(uint64_t*) a = *(uint64_t*) b; + *(uint64_t*) b = tmp; +} + +static inline void +swap_generic (void *a, void *b, size_t size) +{ + unsigned char tmp[128]; + do + { + size_t s = size > sizeof (tmp) ? sizeof (tmp) : size; + memcpy (tmp, a, s); + a = __mempcpy (a, b, s); + b = __mempcpy (b, tmp, s); + size -= s; + } + while (size > 0); +} + +static inline swap_t +select_swap_func (const void *base, size_t size) +{ + if (size == 4 && check_alignment (base, 4)) + return swap_u32; + else if (size == 8 && check_alignment (base, 8)) + return swap_u64; + return swap_generic; +} /* Discontinue quicksort algorithm when partition gets below this size. This particular magic number was chosen to work best on a Sun 4/260. */ @@ -96,6 +135,8 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size, /* Avoid lossage with unsigned arithmetic below. */ return; + swap_t swap = select_swap_func (pbase, size); + if (total_elems > MAX_THRESH) { char *lo = base_ptr; @@ -119,13 +160,13 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size, char *mid = lo + size * ((hi - lo) / size >> 1); if ((*cmp) ((void *) mid, (void *) lo, arg) < 0) - SWAP (mid, lo, size); + swap (mid, lo, size); if ((*cmp) ((void *) hi, (void *) mid, arg) < 0) - SWAP (mid, hi, size); + swap (mid, hi, size); else goto jump_over; if ((*cmp) ((void *) mid, (void *) lo, arg) < 0) - SWAP (mid, lo, size); + swap (mid, lo, size); jump_over:; left_ptr = lo + size; @@ -144,7 +185,7 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size, if (left_ptr < right_ptr) { - SWAP (left_ptr, right_ptr, size); + swap (left_ptr, right_ptr, size); if (mid == left_ptr) mid = right_ptr; else if (mid == right_ptr) @@ -216,7 +257,7 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size, tmp_ptr = run_ptr; if (tmp_ptr != base_ptr) - SWAP (tmp_ptr, base_ptr, size); + swap (tmp_ptr, base_ptr, size); /* Insertion sort, running from left-hand-side up to right-hand-side. */ From patchwork Thu Jan 18 17:53:22 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella Netto X-Patchwork-Id: 125002 Delivered-To: patch@linaro.org Received: by 10.46.64.27 with SMTP id n27csp228696lja; Thu, 18 Jan 2018 09:54:55 -0800 (PST) X-Google-Smtp-Source: ACJfBotiBGXfxtTTevVbpMsZJSG0QUktn7M752ESG6cKs4RW+mw7gar5SveBI1h+BJGUm3HEC7nc X-Received: by 10.99.190.15 with SMTP id l15mr1952823pgf.197.1516298095576; Thu, 18 Jan 2018 09:54:55 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1516298095; cv=none; d=google.com; s=arc-20160816; b=oj4K/B0tvvWelTnGu8mjFauV9dQ5vTefu7WYFbxmppzuAl1mGwHhHnRQ4iM7adiF+b +e5hd+evPXveg3WBo/eaUaGq48yXbMgntxSftf9ixA42JlSlcQFvwX56ceb/JtpZJyxq h8ywSr60T9dl8O1uw/kWRAxmSGYd8Ob/IBgJNgLXuGJgBVb6fuE65upGWn6k2w0wm6En wIXV7Ipyksz/RphTUBVpsqvJHINMG8BmxsV7v1ArFOtywnDdurc31lGDmt9mcjM5eo9g 93n3y3q1CZoHHpsSawAM2KwLFF7rsyJ8uDKh1r5RCcAfmIK4MR1BKhHsJXZuZqK1E6UO GRbg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=references:in-reply-to:message-id:date:subject:to:from:delivered-to :sender:list-help:list-post:list-archive:list-subscribe :list-unsubscribe:list-id:precedence:mailing-list:dkim-signature :domainkey-signature:arc-authentication-results; bh=IdT9RlYq6g5g+/3nGTipN7RxHmzBewFzGCB7X9njZ4Q=; b=w1GcbAkG4+snc/d0604GNUy6Q9BwEbFcZ2jGjeXQJrhMROYHOq6Ojh7T7Afg6cbuHh Gim4DgGqOnr+cE4tzLeREuy0bkXygZ59Iy4bUe37Y61yNRp5VlHLt0SSqnE6Tiyjmfs7 2BAeYkyW3ZKCl45vlS+ga6JtKBTueE+i/bFzydJAqaXZGmBMKrAUOctDLRuZNBLQ8Ksu cIRz45GwEIEpfAPNLUMycPe89tg7464jSDAhSeGS6h/6AgBrnXPXGnJTu1jzIP/cU4CU KIoV/RItb8WLcs8I80eVZof4gk1q9szmXDYcs2kKQIzdaPrtvWTSZPYUI64pgXvvuaxs HWuQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=QpMj3i99; spf=pass (google.com: domain of libc-alpha-return-89329-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89329-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id c14si7397753pfj.132.2018.01.18.09.54.55 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 18 Jan 2018 09:54:55 -0800 (PST) Received-SPF: pass (google.com: domain of libc-alpha-return-89329-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=QpMj3i99; spf=pass (google.com: domain of libc-alpha-return-89329-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89329-patch=linaro.org@sourceware.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; q=dns; s=default; b=bF3wavdw3zIxGnO6G7wUZnqLdth4FRr F36AuhK7PQ0acdfwADor5F+UF7lmC5PTcebhU5O0sEBqfcZoVIfycPmwvlsxbP65 zOjMLkNMUJHZaM+ja7eTBMu/23zLzri7S6yM3BvxnSg55qVfCVU8TquC8FG/2TWa C3K2vbAwTUSc= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; s=default; bh=W0IBAEJY/IcmRc16eKQY/UazVfc=; b=QpMj3 i99k8Dt5nQEaV2jVrmWwJ4GbnyFs+F3f2d4EgQxi4K1cwo+sC3Dhf8HgtCQ6fMJx S1DbVcxrBmfPCkI20R2lXpoVKKXQXYT3iO3YGSLjzXPCQ+pnExwLeC5pkdMkkSal jRDgizalcXxoWif7oT5Zlqi1wgApyI8surnUhs= Received: (qmail 80972 invoked by alias); 18 Jan 2018 17:53:51 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 80431 invoked by uid 89); 18 Jan 2018 17:53:46 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.4 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=Engineering X-HELO: mail-qt0-f169.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=IdT9RlYq6g5g+/3nGTipN7RxHmzBewFzGCB7X9njZ4Q=; b=J1X9D3OJW2F+ItYDp754zdE0sZJPvK+98Jx9FmKJf2ne2YgnxnitRk4ohmCWd6Pt4Y Q/ZT/8oGshYsGZkjoC7qhqbf0jIEH9XZPKJzIINVcYcXsF5Q7uc5fPdZZk+cyLbBzYJZ 6MEfzYmkOZcG34CfTyBkX8sl3e00h21P1T89wcc4l6FkLt6Oh7ysGyXYXnUyaEiRz++u tGEcYIyOUF7tSqinp4D5If4ylYaRpIpgj7rmCcLygRTfZGs2QXKB7khiPq1YlHJKjWQa nbFYBMlOl1TJbjMGi2rhURlPsW/J0nS7nVNxoI9s60jUijpETjTagm1cC3mDtS3Xvynt zGBg== X-Gm-Message-State: AKwxytegpwge0h/uYsKTcoZMi4a8OMRsQ6EBnVA9XYixLi4GaaF0N8WY gRFD3ZyPSGB/UuKXKe+sWZoAcN5Gxqw= X-Received: by 10.200.42.233 with SMTP id c38mr26350852qta.310.1516298019824; Thu, 18 Jan 2018 09:53:39 -0800 (PST) From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH 7/7] stdlib: Remove undefined behavior from qsort implementation Date: Thu, 18 Jan 2018 15:53:22 -0200 Message-Id: <1516298002-4618-8-git-send-email-adhemerval.zanella@linaro.org> In-Reply-To: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> References: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> Internally qsort is implemented on top of __qsort_r by casting the function pointer to another type (__compar_fn_t tp __compar_d_fn_t) and passing a NULL extra argument. Casting function pointer with different types for subsequent function call is undefined-behaviour (C11 6.3.2.3): "[8] A pointer to a function of one type may be converted to a pointer to a function of another type and back again; the result shall compare equal to the original pointer. If a converted pointer is used to call a function whose type is not compatible with the referenced type, the behavior is undefined." Also 'compatible' in this case also does not apply according to 6.7.6.3 Function declarators (including prototypes): "[15] For two function types to be compatible, both shall specify compatible return types. (146) Moreover, the parameter type lists, if both are present, shall agree in the number of parameters and in use of the ellipsis terminator; corresponding parameters shall have compatible types. [...]" Although this works on all architectures glibc supports (mostly because it casts function pointers with similar calling conventions), I think it is worth to avoid it. This patch fixes it by adding a common implementation (qsort_common.c) which redefines the function based on the required types. For x86_64 (i7-4790K, gcc 7.2.1) shows a slight better performance for qsort: Results for member size 4 Sorted nmemb | base | patched | diff 32| 1304 | 1257 | -3.60 4096| 330707 | 302235 | -8.61 32768| 3300210 | 3020728 | -8.47 524288| 65673289 | 59306436 | -9.69 Repeated nmemb | base | patched | diff 32| 1885 | 1873 | -0.64 4096| 951490 | 904864 | -4.90 32768| 9272366 | 8542801 | -7.87 524288| 183337854 | 168426795 | -8.13 MostlySorted nmemb | base | patched | diff 32| 1836 | 1776 | -3.27 4096| 758359 | 709937 | -6.39 32768| 7199982 | 6855890 | -4.78 524288| 139242170 | 129385161 | -7.08 Unsorted nmemb | base | patched | diff 32| 2073 | 1941 | -6.37 4096| 1058383 | 969021 | -8.44 32768| 10310116 | 9462116 | -8.22 524288| 202427388 | 186560908 | -7.84 Results for member size 8 Sorted nmemb | base | patched | diff 32| 1224 | 1205 | -1.55 4096| 336100 | 325554 | -3.14 32768| 3539890 | 3264125 | -7.79 524288| 67268510 | 66107684 | -1.73 Repeated nmemb | base | patched | diff 32| 2096 | 2118 | 1.05 4096| 1015585 | 979114 | -3.59 32768| 9871981 | 9028606 | -8.54 524288| 189710172 | 174903867 | -7.80 MostlySorted nmemb | base | patched | diff 32| 2318 | 2346 | 1.21 4096| 805051 | 759158 | -5.70 32768| 8346363 | 7810444 | -6.42 524288| 143597264 | 135900146 | -5.36 Unsorted nmemb | base | patched | diff 32| 2364 | 2301 | -2.66 4096| 1076998 | 1014018 | -5.85 32768| 10442153 | 9888078 | -5.31 524288| 206235337 | 192479957 | -6.67 Results for member size 32 Sorted nmemb | base | patched | diff 32| 1214 | 1184 | -2.47 4096| 332449 | 325865 | -1.98 32768| 3313274 | 3331750 | 0.56 524288| 70786673 | 69067176 | -2.43 Repeated nmemb | base | patched | diff 32| 4913 | 4813 | -2.04 4096| 1693735 | 1624137 | -4.11 32768| 17054760 | 15896739 | -6.79 524288| 332149265 | 316328778 | -4.76 MostlySorted nmemb | base | patched | diff 32| 5490 | 5332 | -2.88 4096| 1394312 | 1312703 | -5.85 32768| 12743599 | 12360726 | -3.00 524288| 240249011 | 231603294 | -3.60 Unsorted nmemb | base | patched | diff 32| 6251 | 6047 | -3.26 4096| 1959306 | 1695241 | -13.48 32768| 17204840 | 16430388 | -4.50 524288| 342716199 | 329496913 | -3.86 Checked on x86_64-linux-gnu. * stdlib/qsort.c: Move common code to stdlib/qsort_common.c and parametrize the function definition based wether to use the '_r' variant. * stdlib/qsort_common.c: New file. --- stdlib/qsort.c | 208 ++-------------------------------------------- stdlib/qsort_common.c | 225 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 233 insertions(+), 200 deletions(-) create mode 100644 stdlib/qsort_common.c -- 2.7.4 diff --git a/stdlib/qsort.c b/stdlib/qsort.c index 2194003..03ab0e5 100644 --- a/stdlib/qsort.c +++ b/stdlib/qsort.c @@ -16,17 +16,13 @@ License along with the GNU C Library; if not, see . */ -/* If you consider tuning this algorithm, you should consult first: - Engineering a sort function; Jon Bentley and M. Douglas McIlroy; - Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */ - #include #include #include #include -/* Swap SIZE bytes between addresses A and B. Helper to generic types - are provided as an optimization. */ +/* Swap SIZE bytes between addresses A and B. These helpers are provided + along the generic one as an optimization. */ typedef void (*swap_t)(void *, void *, size_t); @@ -98,202 +94,14 @@ typedef struct #define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi))) #define STACK_NOT_EMPTY (stack < top) - -/* Order size using quicksort. This implementation incorporates - four optimizations discussed in Sedgewick: - - 1. Non-recursive, using an explicit stack of pointer that store the - next array partition to sort. To save time, this maximum amount - of space required to store an array of SIZE_MAX is allocated on the - stack. Assuming a 32-bit (64 bit) integer for size_t, this needs - only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes). - Pretty cheap, actually. - - 2. Chose the pivot element using a median-of-three decision tree. - This reduces the probability of selecting a bad pivot value and - eliminates certain extraneous comparisons. - - 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving - insertion sort to order the MAX_THRESH items within each partition. - This is a big win, since insertion sort is faster for small, mostly - sorted array segments. - - 4. The larger of the two sub-partitions is always pushed onto the - stack first, with the algorithm then concentrating on the - smaller partition. This *guarantees* no more than log (total_elems) - stack size is needed (actually O(1) in this case)! */ - -void -__qsort_r (void *const pbase, size_t total_elems, size_t size, - __compar_d_fn_t cmp, void *arg) -{ - char *base_ptr = (char *) pbase; - - const size_t max_thresh = MAX_THRESH * size; - - if (total_elems == 0) - /* Avoid lossage with unsigned arithmetic below. */ - return; - - swap_t swap = select_swap_func (pbase, size); - - if (total_elems > MAX_THRESH) - { - char *lo = base_ptr; - char *hi = &lo[size * (total_elems - 1)]; - stack_node stack[STACK_SIZE]; - stack_node *top = stack; - - PUSH (NULL, NULL); - - while (STACK_NOT_EMPTY) - { - char *left_ptr; - char *right_ptr; - - /* Select median value from among LO, MID, and HI. Rearrange - LO and HI so the three values are sorted. This lowers the - probability of picking a pathological pivot value and - skips a comparison for both the LEFT_PTR and RIGHT_PTR in - the while loops. */ - - char *mid = lo + size * ((hi - lo) / size >> 1); - - if ((*cmp) ((void *) mid, (void *) lo, arg) < 0) - swap (mid, lo, size); - if ((*cmp) ((void *) hi, (void *) mid, arg) < 0) - swap (mid, hi, size); - else - goto jump_over; - if ((*cmp) ((void *) mid, (void *) lo, arg) < 0) - swap (mid, lo, size); - jump_over:; - - left_ptr = lo + size; - right_ptr = hi - size; - - /* Here's the famous ``collapse the walls'' section of quicksort. - Gotta like those tight inner loops! They are the main reason - that this algorithm runs much faster than others. */ - do - { - while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0) - left_ptr += size; - - while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0) - right_ptr -= size; - - if (left_ptr < right_ptr) - { - swap (left_ptr, right_ptr, size); - if (mid == left_ptr) - mid = right_ptr; - else if (mid == right_ptr) - mid = left_ptr; - left_ptr += size; - right_ptr -= size; - } - else if (left_ptr == right_ptr) - { - left_ptr += size; - right_ptr -= size; - break; - } - } - while (left_ptr <= right_ptr); - - /* Set up pointers for next iteration. First determine whether - left and right partitions are below the threshold size. If so, - ignore one or both. Otherwise, push the larger partition's - bounds on the stack and continue sorting the smaller one. */ - - if ((size_t) (right_ptr - lo) <= max_thresh) - { - if ((size_t) (hi - left_ptr) <= max_thresh) - /* Ignore both small partitions. */ - POP (lo, hi); - else - /* Ignore small left partition. */ - lo = left_ptr; - } - else if ((size_t) (hi - left_ptr) <= max_thresh) - /* Ignore small right partition. */ - hi = right_ptr; - else if ((right_ptr - lo) > (hi - left_ptr)) - { - /* Push larger left partition indices. */ - PUSH (lo, right_ptr); - lo = left_ptr; - } - else - { - /* Push larger right partition indices. */ - PUSH (left_ptr, hi); - hi = right_ptr; - } - } - } - - /* Once the BASE_PTR array is partially sorted by quicksort the rest - is completely sorted using insertion sort, since this is efficient - for partitions below MAX_THRESH size. BASE_PTR points to the beginning - of the array to sort, and END_PTR points at the very last element in - the array (*not* one beyond it!). */ - -#define min(x, y) ((x) < (y) ? (x) : (y)) - - { - char *const end_ptr = &base_ptr[size * (total_elems - 1)]; - char *tmp_ptr = base_ptr; - char *thresh = min(end_ptr, base_ptr + max_thresh); - char *run_ptr; - - /* Find smallest element in first threshold and place it at the - array's beginning. This is the smallest array element, - and the operation speeds up insertion sort's inner loop. */ - - for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size) - if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0) - tmp_ptr = run_ptr; - - if (tmp_ptr != base_ptr) - swap (tmp_ptr, base_ptr, size); - - /* Insertion sort, running from left-hand-side up to right-hand-side. */ - - run_ptr = base_ptr + size; - while ((run_ptr += size) <= end_ptr) - { - tmp_ptr = run_ptr - size; - while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0) - tmp_ptr -= size; - - tmp_ptr += size; - if (tmp_ptr != run_ptr) - { - char *trav; - - trav = run_ptr + size; - while (--trav >= run_ptr) - { - char c = *trav; - char *hi, *lo; - - for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo) - *hi = *lo; - *hi = c; - } - } - } - } -} +#define R_VERSION +#define R_FUNC __qsort_r +#include libc_hidden_def (__qsort_r) weak_alias (__qsort_r, qsort_r) -void -qsort (void *b, size_t n, size_t s, __compar_fn_t cmp) -{ - return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL); -} +#define R_FUNC qsort +#include + libc_hidden_def (qsort) diff --git a/stdlib/qsort_common.c b/stdlib/qsort_common.c new file mode 100644 index 0000000..666b195 --- /dev/null +++ b/stdlib/qsort_common.c @@ -0,0 +1,225 @@ +/* Common implementation for both qsort and qsort_r. + Copyright (C) 2018 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 + . */ + +/* If you consider tuning this algorithm, you should consult first: + Engineering a sort function; Jon Bentley and M. Douglas McIlroy; + Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */ + +#ifdef R_VERSION +# define R_CMP_TYPE __compar_d_fn_t +# define R_CMP_ARG , void *arg +# define R_CMP(p1, p2) cmp (p1, p2, arg) +#else +# define R_CMP_TYPE __compar_fn_t +# define R_CMP_ARG +# define R_CMP(p1, p2) cmp (p1, p2) +#endif + +/* Order size using quicksort. This implementation incorporates + four optimizations discussed in Sedgewick: + + 1. Non-recursive, using an explicit stack of pointer that store the + next array partition to sort. To save time, this maximum amount + of space required to store an array of SIZE_MAX is allocated on the + stack. Assuming a 32-bit (64 bit) integer for size_t, this needs + only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes). + Pretty cheap, actually. + + 2. Chose the pivot element using a median-of-three decision tree. + This reduces the probability of selecting a bad pivot value and + eliminates certain extraneous comparisons. + + 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving + insertion sort to order the MAX_THRESH items within each partition. + This is a big win, since insertion sort is faster for small, mostly + sorted array segments. + + 4. The larger of the two sub-partitions is always pushed onto the + stack first, with the algorithm then concentrating on the + smaller partition. This *guarantees* no more than log (total_elems) + stack size is needed (actually O(1) in this case)! */ + +void +R_FUNC (void *pbase, size_t total_elems, size_t size, R_CMP_TYPE cmp R_CMP_ARG) +{ + if (total_elems == 0) + /* Avoid lossage with unsigned arithmetic below. */ + return; + + char *base_ptr = (char *) pbase; + + const size_t max_thresh = MAX_THRESH * size; + + swap_t swap = select_swap_func (pbase, size); + + if (total_elems > MAX_THRESH) + { + char *lo = base_ptr; + char *hi = &lo[size * (total_elems - 1)]; + stack_node stack[STACK_SIZE]; + stack_node *top = stack; + + PUSH (NULL, NULL); + + while (STACK_NOT_EMPTY) + { + char *left_ptr; + char *right_ptr; + + /* Select median value from among LO, MID, and HI. Rearrange + LO and HI so the three values are sorted. This lowers the + probability of picking a pathological pivot value and + skips a comparison for both the LEFT_PTR and RIGHT_PTR in + the while loops. */ + + char *mid = lo + size * ((hi - lo) / size >> 1); + + if (R_CMP ((void *) mid, (void *) lo) < 0) + swap (mid, lo, size); + if (R_CMP ((void *) hi, (void *) mid) < 0) + swap (mid, hi, size); + else + goto jump_over; + if (R_CMP ((void *) mid, (void *) lo) < 0) + swap (mid, lo, size); + jump_over:; + + left_ptr = lo + size; + right_ptr = hi - size; + + /* Here's the famous ``collapse the walls'' section of quicksort. + Gotta like those tight inner loops! They are the main reason + that this algorithm runs much faster than others. */ + do + { + while (R_CMP ((void *) left_ptr, (void *) mid) < 0) + left_ptr += size; + + while (R_CMP ((void *) mid, (void *) right_ptr) < 0) + right_ptr -= size; + + if (left_ptr < right_ptr) + { + swap (left_ptr, right_ptr, size); + if (mid == left_ptr) + mid = right_ptr; + else if (mid == right_ptr) + mid = left_ptr; + left_ptr += size; + right_ptr -= size; + } + else if (left_ptr == right_ptr) + { + left_ptr += size; + right_ptr -= size; + break; + } + } + while (left_ptr <= right_ptr); + + /* Set up pointers for next iteration. First determine whether + left and right partitions are below the threshold size. If so, + ignore one or both. Otherwise, push the larger partition's + bounds on the stack and continue sorting the smaller one. */ + + if ((size_t) (right_ptr - lo) <= max_thresh) + { + if ((size_t) (hi - left_ptr) <= max_thresh) + /* Ignore both small partitions. */ + POP (lo, hi); + else + /* Ignore small left partition. */ + lo = left_ptr; + } + else if ((size_t) (hi - left_ptr) <= max_thresh) + /* Ignore small right partition. */ + hi = right_ptr; + else if ((right_ptr - lo) > (hi - left_ptr)) + { + /* Push larger left partition indices. */ + PUSH (lo, right_ptr); + lo = left_ptr; + } + else + { + /* Push larger right partition indices. */ + PUSH (left_ptr, hi); + hi = right_ptr; + } + } + } + + /* Once the BASE_PTR array is partially sorted by quicksort the rest + is completely sorted using insertion sort, since this is efficient + for partitions below MAX_THRESH size. BASE_PTR points to the beginning + of the array to sort, and END_PTR points at the very last element in + the array (*not* one beyond it!). */ + + { + char *const end_ptr = &base_ptr[size * (total_elems - 1)]; + char *tmp_ptr = base_ptr; + char *thresh = end_ptr < base_ptr + max_thresh ? + end_ptr : base_ptr + max_thresh; + char *run_ptr; + + /* Find smallest element in first threshold and place it at the + array's beginning. This is the smallest array element, + and the operation speeds up insertion sort's inner loop. */ + + for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size) + if (R_CMP ((void *) run_ptr, (void *) tmp_ptr) < 0) + tmp_ptr = run_ptr; + + if (tmp_ptr != base_ptr) + swap (tmp_ptr, base_ptr, size); + + /* Insertion sort, running from left-hand-side up to right-hand-side. */ + + run_ptr = base_ptr + size; + while ((run_ptr += size) <= end_ptr) + { + tmp_ptr = run_ptr - size; + while (R_CMP ((void *) run_ptr, (void *) tmp_ptr) < 0) + tmp_ptr -= size; + + tmp_ptr += size; + if (tmp_ptr != run_ptr) + { + char *trav; + + trav = run_ptr + size; + while (--trav >= run_ptr) + { + char c = *trav; + char *hi, *lo; + + for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo) + *hi = *lo; + *hi = c; + } + } + } + } +} + +#undef R_NAME +#undef R_CMP_TYPE +#undef R_CMP_ARG +#undef R_CMP +#undef R_FUNC +#undef R_VERSION