From patchwork Fri Aug 31 20:42:32 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: 145691 Delivered-To: patch@linaro.org Received: by 2002:a2e:1648:0:0:0:0:0 with SMTP id 8-v6csp1210305ljw; Fri, 31 Aug 2018 13:43:09 -0700 (PDT) X-Google-Smtp-Source: ANB0VdaAP4/unVOTCPlRzYK2azOeMCRAzK7GR4YzBWBvX9LLxq0Cx/o7kQR5wYN2OFYFn38smQH2 X-Received: by 2002:a62:280a:: with SMTP id o10-v6mr17549513pfo.129.1535748189585; Fri, 31 Aug 2018 13:43:09 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1535748189; cv=none; d=google.com; s=arc-20160816; b=IwGgRBzNInHhQWoCtjIVJfFtCA1VPfMgIBa9yoaqRerpoMQqI90/RwbBhfGXEsXb9y cPgqGSyJae0UqpkaZ6QMJtSV7geHLeuaIOPqVXMSzp2g4/U4qISj76ZWrV6LWmq8axSZ ODfXuqCowjW/XbS+ZYS9BMKm98CxZpaBUX2A2UKpFRi0FTdQC8NslB7/oIhzQfr6XfC3 Rufo7vJgKXv1iMR/ikHjYiqjA2bP3+ZKCiDGwGmkfEs6atdfitltbjkNZ3qZMvSiX0WT AsTMRoApyC8LsE+Rw5NtMXLEVgprH9DLVXHjJSS8FbDhaVMDOcv0AX6W/Z+K0Zi4lTDf 76Fw== 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 :dkim-signature: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=3OAapWYG61530zC9wJnnE1vm2sV/0r5pO7729wZYFWE=; b=dml07VROJyuctFP+08svNB+w9JqB3tWqYrsRC3wrIogi3lj0HuFd7pbM++ASs9kf9Y LKl6zZ4qHEyet75jFrSUITlpjo06L6Y52O7Jxl8tqXkvblNZCBJmplwGbjl+pz1gnarG O/B7JXxDQyoIEhYaknnumgss+CQtxdHaDHRU3FcNC7ohgHGWAuhZOi1c+E0zi/sONYxA w9DX5LkbuPlretBG7BW4SdERn4ny4BjcI2jiw46fB6r4NhATA+b/e5H5cFDl7n2H04kW ylMD4hTK40jRbEN9mINTAyw9ZN7Dn/ln1gdXaFFR4wOIyHGyqfwzlmGb+jed1Wietzfx YgwQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=rTxyjBuO; dkim=pass header.i=@linaro.org header.s=google header.b=AQxePXhD; spf=pass (google.com: domain of libc-alpha-return-95623-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="libc-alpha-return-95623-patch=linaro.org@sourceware.org"; dmarc=pass (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 c133-v6si11114678pfb.296.2018.08.31.13.43.09 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 31 Aug 2018 13:43:09 -0700 (PDT) Received-SPF: pass (google.com: domain of libc-alpha-return-95623-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=rTxyjBuO; dkim=pass header.i=@linaro.org header.s=google header.b=AQxePXhD; spf=pass (google.com: domain of libc-alpha-return-95623-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="libc-alpha-return-95623-patch=linaro.org@sourceware.org"; dmarc=pass (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=Yk6q4oPRKIP0NUkG4HPbM5xLch8VzcP NGlB+4Bj6wQZJy8nWsKjfdoPYSaJcqpje069di5olD3Y1CMc4maQHCOZk/Fcf++q erGFJK44h7KREO+GYnyO4jbDH3wD+rxXPji81TIf51MnB29QmOk1MXN6OGy64DRv E0RvsScR4LMs= 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=5R2fV5aR3SXPfNVFOFxefoKnsY0=; b=rTxyj BuOluQeVskLG14m6qGZl7otz551y1se9vx8CEZ+0tF/I3HHzzo8dfzUPPHt9FaNN 1glrB6tJjgLH4/K32iOpGQ0SgIJk7XQQlfijoZS6n64C2pssVmzPM/qPue1Twug0 mIeKggFZ4ZFrihWApXMAtes/vy0SDgijSxHfIg= Received: (qmail 53915 invoked by alias); 31 Aug 2018 20:42: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 53803 invoked by uid 89); 31 Aug 2018 20:42:50 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.5 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SEM_URI, SEM_URIRED, SPF_PASS autolearn=ham version=3.3.2 spammy=HX-Received:sk:b15-v6m, 1024 X-HELO: mail-qt0-f182.google.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:subject:date:message-id:in-reply-to:references; bh=3OAapWYG61530zC9wJnnE1vm2sV/0r5pO7729wZYFWE=; b=AQxePXhDMUt5ErJv6w3Ovob4vS2Ido66mNtfXLCex904zV7S/6voXEXEeTfI5l+HA0 A3+q1BM8LLkgWIyNuvWS63pwBJ0rchbRozuLuAi9WYkQR3VSVVzSrrW0LNdYpciviRV2 NthETA5miNHelAiUiurStH1SnrBQiibqKRWGo= Return-Path: From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH v2 1/7] stdlib: Adjust tst-qsort{2} to libsupport Date: Fri, 31 Aug 2018 17:42:32 -0300 Message-Id: <20180831204238.10626-2-adhemerval.zanella@linaro.org> In-Reply-To: <20180831204238.10626-1-adhemerval.zanella@linaro.org> References: <20180831204238.10626-1-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.17.1 diff --git a/stdlib/tst-qsort.c b/stdlib/tst-qsort.c index 2b26e74d0b..c3230fd10e 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 10d16852b0..595875dcae 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 Fri Aug 31 20:42:33 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: 145692 Delivered-To: patch@linaro.org Received: by 2002:a2e:1648:0:0:0:0:0 with SMTP id 8-v6csp1210451ljw; Fri, 31 Aug 2018 13:43:21 -0700 (PDT) X-Google-Smtp-Source: ANB0VdaW8qVRdbip9PYIVgN2wJeQkFCLn4Ryu18GPxEvdNFTJwLXvK1JdNkGDdLSc7fpU4ptXFSF X-Received: by 2002:a63:740f:: with SMTP id p15-v6mr16276050pgc.395.1535748201692; Fri, 31 Aug 2018 13:43:21 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1535748201; cv=none; d=google.com; s=arc-20160816; b=AGZdFTcomAVVeNLDt0dLD4QrE/CwhUzirdVoXJCL+Z+uuWF2X6UY5cLFMWgmxMw2DU 1t93+lRhZ3BxEqf1jvm5Fk3z9YQABbVq+GGt/zvGO0Kmu3TQQqAu4UbR167MzrBzC3OH fcnX8haKVfFBlvNMaAJWj7L3mm3kFLhOWrBsMFUnApFsGggMxNYysrgE0vKqwOAjeZqb bzxIHJySac0WI7NCJ/V5UUP1i7frrkO+XxA5IVymPT94zhqIynyZ0okUywEjs8MF5Y7n SEy/KIt6L+jx0sYRRZTqXPgW1JSPwAScLvdIJJcbTkgnkJgmwwqCOw+gRQa5RI5d7hb4 J+sw== 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 :dkim-signature: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=yZyyjfojeCu0/fTxm4tkjc7oXIDo6lf0EW8Sb8YJY18=; b=Fb+916fjjNg/w/i+qH0DzqGntMbGQjCIBAhRxNcewVs0OE9D42cX7KCszfHAUWzMY8 r5zYEivjrPNTi0ozfvdXyy4K4FhDuyZ77NMjaZPbyHdUhmdFwKrh1BdmxDDpgmvLZrLn OZptRQHWAtFg/3a2Yo9qfU63HWE8KoLXz1NdiDjxKbeq5hZmrNh6KFbWLvjKhp9yQLVU 5kxeeTcW6/wIa86IiDbmvN3jINDP9iTeDzrl5TzottBWhXwJ9HRTBBH/xZkpTJ8OVP1K ZrxLHYJ/FHr5OJkUFYhFfB/eHc6lpZ8wsQ5G11x2NVYTmK7YZ4GYTkJ0R2a3ErOpHzHU K+Dg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=vBhZWtLt; dkim=pass header.i=@linaro.org header.s=google header.b=DDmzFIdt; spf=pass (google.com: domain of libc-alpha-return-95624-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="libc-alpha-return-95624-patch=linaro.org@sourceware.org"; dmarc=pass (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 az1-v6si3371719plb.513.2018.08.31.13.43.21 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 31 Aug 2018 13:43:21 -0700 (PDT) Received-SPF: pass (google.com: domain of libc-alpha-return-95624-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=vBhZWtLt; dkim=pass header.i=@linaro.org header.s=google header.b=DDmzFIdt; spf=pass (google.com: domain of libc-alpha-return-95624-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="libc-alpha-return-95624-patch=linaro.org@sourceware.org"; dmarc=pass (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=x/wGEPDLx5IhvARgCpRF3ylh+pvU5W6 1osxq4yvEX5S6xil9NhYuk8y3LdcuzsuA4ZD5jY9MCN6yCo3n8Ma9iN7zYT4ypzg Sj8aIrRGuJGrkeTBI8ngcwk0VZLrbRDwVIYq66lUye6wsCGtRn+wFBsPZQ4sRfQg 7tzncnFBaCMs= 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=LwBI2xo+mx/9qGOBqcqBtSgoNIM=; b=vBhZW tLtJCwRswh3i+MNdQh0FiSB2gsaQ1qcE4T05mm7p3Q4fOk9WADbqiOrz/+kW9bJW N8NIDfaLXg8ZN0YHALxrJ1RAAlU7H8fKEIoBBPjPuxAX7A9hdyIxRrG5IkyNYkew crBLCzXfth1irAffeICRrTPBWoDP5a8GA78+eQ= Received: (qmail 54226 invoked by alias); 31 Aug 2018 20:42:53 -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 54107 invoked by uid 89); 31 Aug 2018 20:42:52 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.6 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, SEM_URI, SEM_URIRED, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mail-qt0-f193.google.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:subject:date:message-id:in-reply-to:references; bh=yZyyjfojeCu0/fTxm4tkjc7oXIDo6lf0EW8Sb8YJY18=; b=DDmzFIdt1/eqmH4PgBAsT7jcCixVQ9IdaxV6XZKF8cJk3pgngHbB6BVripTACCwNfY a8Eq94F0816z5FXROj1KkwytE/nv0w8bxwRpAFkv4vQzedOOZ4P1FB13bXTz8NFHyiVl S7+iL+ReJM6uow3Jj5Sn8EKmiv9xIVJN4PiCI= Return-Path: From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH v2 2/7] support: Add pseudo-random number generator interface Date: Fri, 31 Aug 2018 17:42:33 -0300 Message-Id: <20180831204238.10626-3-adhemerval.zanella@linaro.org> In-Reply-To: <20180831204238.10626-1-adhemerval.zanella@linaro.org> References: <20180831204238.10626-1-adhemerval.zanella@linaro.org> This is based on POSIX mrand48 and the interfaces provided is just wrapping around common usages (buffer fill and uniform distribution). Although better PNRGs exists, the already in place POSIXs one is used for simplicity and a better de factor one is being discussed for inclusion (arc4random based on AES-CTR). Ideally it would replace the mrand48 usage for this interface. 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/Makefile | 3 +- support/support_random.c | 90 ++++++++++++++++++++++++++++++++++++++++ support/support_random.h | 59 ++++++++++++++++++++++++++ 3 files changed, 151 insertions(+), 1 deletion(-) create mode 100644 support/support_random.c create mode 100644 support/support_random.h -- 2.17.1 diff --git a/support/Makefile b/support/Makefile index 9063046c23..db46be606e 100644 --- a/support/Makefile +++ b/support/Makefile @@ -56,6 +56,7 @@ libsupport-routines = \ support_openpty \ support_quote_blob \ support_record_failure \ + support_random \ support_run_diff \ support_shared_allocate \ support_test_compare_blob \ @@ -161,7 +162,7 @@ tests = \ tst-support_record_failure \ tst-test_compare \ tst-test_compare_blob \ - tst-xreadlink \ + tst-xreadlink ifeq ($(run-built-tests),yes) tests-special = \ diff --git a/support/support_random.c b/support/support_random.c new file mode 100644 index 0000000000..5feee1a213 --- /dev/null +++ b/support/support_random.c @@ -0,0 +1,90 @@ +/* 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 + +#include +#include +#include + +void +support_random_seed (support_random_state *state, uint32_t seed) +{ + unsigned short int seed16v[3] = { 0 }; + memcpy (seed16v, &seed, sizeof (seed)); + seed48_r (seed16v, state); +} + +void +support_random_rseed (support_random_state *state) +{ + unsigned short int buf[3]; + size_t len = sizeof buf; + + ssize_t ret = getrandom (buf, len, 0); + if (ret != len) + { + int fd = xopen ("/dev/urandom", O_RDONLY, 0); + uintptr_t pbuf = (uintptr_t) buf; + uintptr_t pend = pbuf + len; + while (pbuf < pend) + { + ret = read (fd, buf, pend - pbuf); + if (ret <= 0) + FAIL_EXIT1 ("read %zu bytes from /dev/urandom failed: %m", + pend - pbuf); + pbuf += ret; + } + close (fd); + } + + seed48_r (buf, state); +} + +uint32_t +support_random_u32 (support_random_state *state) +{ + long int rl; + mrand48_r (state, &rl); + return rl; +} + +void +support_random_buf (support_random_state *state, void *buf, size_t nbytes) +{ + size_t nw = nbytes / sizeof (uint32_t); + for (size_t i = 0; i < nw; i++) + { + uint32_t r = support_random_u32 (state); + memcpy (buf, &r, sizeof (uint32_t)); + buf = (void*)((uintptr_t)buf + sizeof (uint32_t)); + } + + size_t nb = nbytes % sizeof (uint32_t); + if (nb != 0) + { + uint32_t r = support_random_u32 (state); + memcpy (buf, &r, nb); + } +} diff --git a/support/support_random.h b/support/support_random.h new file mode 100644 index 0000000000..8224c2b774 --- /dev/null +++ b/support/support_random.h @@ -0,0 +1,59 @@ +/* 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 + +typedef struct drand48_data support_random_state; + +void support_random_seed (support_random_state *state, uint32_t seed); +void support_random_rseed (support_random_state *state); + +uint32_t support_random_u32 (support_random_state *state); +void support_random_buf (support_random_state *state, void *buf, + size_t nbytes); + +/* Scales the number NUMBER to the uniformly distributed closed internal + [min, max]. */ +static inline uint32_t +support_random_uniform_distribution (support_random_state *state, + uint32_t min, uint32_t max) +{ + uint32_t ret; + uint32_t range = max - min; + /* It assumes the input random number RANDOM range is as larger or equal + than the RANGE, so the result will either returned or downscaled. */ + if (range != UINT32_MAX) + { + uint32_t urange = range + 1; /* range can be 0. */ + uint32_t scaling = UINT32_MAX / urange; + uint32_t past = urange * scaling; + do + ret = support_random_u32 (state); + while (ret >= past); + ret /= scaling; + } + else + ret = support_random_u32 (state); + return ret + min; +} + +#endif From patchwork Fri Aug 31 20:42:34 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: 145693 Delivered-To: patch@linaro.org Received: by 2002:a2e:1648:0:0:0:0:0 with SMTP id 8-v6csp1210605ljw; Fri, 31 Aug 2018 13:43:32 -0700 (PDT) X-Google-Smtp-Source: ANB0VdZMLdbkjjdGglL6Wi2NiyPyyfKbJzKtzVI4rIvC8KOuQcIWRdRSNp0QTg1+SgKYR2aToZ6s X-Received: by 2002:a63:6881:: with SMTP id d123-v6mr1427378pgc.298.1535748212476; Fri, 31 Aug 2018 13:43:32 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1535748212; cv=none; d=google.com; s=arc-20160816; b=Hgkjy/2uG8HpyQTAtqpevOliAABDMGY/iNTvZ7/hSGF0jbYP2jvrKtuAwe9o7oXO/I o+xJ+FGkNTh1byJAhKMtLa0y1m5g3XhedpLvaZ+2Q4eH8nLWI8yU4crGAlDHkNCRqK6D 5MxLuFvNHteNyizDqyp5zYCaxNe/fCCbJaGTllHJat39F+p616qRLl6nlStzKPHSn6OU HuSFHZiSonIGnD2Sfzc9Tp+p/Uwq1B/JkIYvKH4C/EtpoUDSSMnYKq45/Q9DZc2SIdfL uVRZAZukQf0ZQ+XcMgWkSmqaNlzGwisYAYDbl8/n19bc822xMyqHyiBn++bM7q8mOflH JQmg== 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 :dkim-signature: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=Paz/YzMnHGsRPUgnAJSqcZ82axddFW42Aewr1lAuDGw=; b=LcuN4NmW2tgFn9sMVS9Utp4FjR2kxcGb+q85LW/UexB3d3V3SXhLw15+3zvCSy1ZG5 I9RIbHLtpRpqYn/Ai1QEOilUtaH+poX/rPflc9CoceXLcOivrDT/zlprXm71yMPzlncZ Bn4nrrisgUO2o9yKSWoKwgS0lPTlkSD7GWRpuNtuJk1GSFDJcoJQWRAj7+YMIRVZA39l NkytteYhJL/tGgGSny0KR7KhlETPdxtbzdYxBZbsnCokUKCw/7HN796WNZ3pKu8ah1JD 8SiqFCBLDT30sYZTuC0/2Nto60QZbR3WVsSGqnRP9GAHdubmwgevpxGxr+BvDDv2+6C0 r8DQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=kTyzttjo; dkim=pass header.i=@linaro.org header.s=google header.b=XjJ6c0KX; spf=pass (google.com: domain of libc-alpha-return-95625-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="libc-alpha-return-95625-patch=linaro.org@sourceware.org"; dmarc=pass (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 w5-v6si9791120pge.395.2018.08.31.13.43.32 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 31 Aug 2018 13:43:32 -0700 (PDT) Received-SPF: pass (google.com: domain of libc-alpha-return-95625-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=kTyzttjo; dkim=pass header.i=@linaro.org header.s=google header.b=XjJ6c0KX; spf=pass (google.com: domain of libc-alpha-return-95625-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="libc-alpha-return-95625-patch=linaro.org@sourceware.org"; dmarc=pass (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=m1K7cJ5lzVoYMdzFKVTzyu1mi15xpwj b62hBqSo9e2hkpRfz89DD5DNvExx74NtNcwctnV1S3M5toooHbEfGyk7qWvkmhUo 6lgpbxaVPbzBkwNVWiPQwZw32yxuoii+4zPvUroCtDFaG3lXGWAcY8l7y7TqA0pf aTmGdvjbKIyo= 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=JwiJ1if+dtkU/+4St5UARrDmNRs=; b=kTyzt tjoQu5L1yDHMDd3DT/odRJrW//ZGtmLJWnJN/TNHFea86srnEAecYt4djSuEKorG CWLfIYsjHvvMuJifnV07mmTvStlFtALY24l74BUgtx9p7uDNz7lNdRF2vSaarKKG 1voxkC4hITyHZcHi3Cf2a08jintJVdqBfH0cu0= Received: (qmail 54488 invoked by alias); 31 Aug 2018 20:42:55 -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 54385 invoked by uid 89); 31 Aug 2018 20:42:54 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.6 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, SEM_URI, SEM_URIRED, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mail-qt0-f170.google.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:subject:date:message-id:in-reply-to:references; bh=Paz/YzMnHGsRPUgnAJSqcZ82axddFW42Aewr1lAuDGw=; b=XjJ6c0KX9iQNc4Hwu66JbyHM+cuJ5+bAIYNQxtqmp5y0EBd4ePz6Fm9FE3RIe9XuPA Prr/j3YjrP50G7VSxx/6CjpeW1M1FCiMVyIV7APtU3A9VUx6E3nt5V+e2qM+19qptUtN sA2FHkhCsLI4a5hJBoN25nYTaR0PU+oOkDUMI= Return-Path: From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH v2 3/7] stdlib: Add more qsort{_r} coverage Date: Fri, 31 Aug 2018 17:42:34 -0300 Message-Id: <20180831204238.10626-4-adhemerval.zanella@linaro.org> In-Reply-To: <20180831204238.10626-1-adhemerval.zanella@linaro.org> References: <20180831204238.10626-1-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 | 235 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 236 insertions(+), 1 deletion(-) create mode 100644 stdlib/tst-qsort3.c -- 2.17.1 diff --git a/stdlib/Makefile b/stdlib/Makefile index 01194bbf7c..4e012a865a 100644 --- a/stdlib/Makefile +++ b/stdlib/Makefile @@ -87,7 +87,7 @@ tests := tst-strtol tst-strtod testmb testrand testsort testdiv \ tst-makecontext-align test-bz22786 tst-strtod-nan-sign \ tst-swapcontext1 tst-setcontext4 tst-setcontext5 \ tst-setcontext6 tst-setcontext7 tst-setcontext8 \ - tst-setcontext9 + tst-setcontext9 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 0000000000..26db0c2da6 --- /dev/null +++ b/stdlib/tst-qsort3.c @@ -0,0 +1,235 @@ +/* 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 +#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 support_random_state rand_state; + +static void * +create_array (size_t nmemb, size_t type_size) +{ + size_t size = nmemb * type_size; + uint8_t *array = xmalloc (size); + support_random_buf (&rand_state, array, size); + 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; +static bool seed_set = false; + +#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; + seed_set = true; + } + break; + } +} + +#define CMDLINE_PROCESS cmdline_process_function + + +static int +do_test (void) +{ + if (test_verbose > 0) + printf ("info: seed=0x%08x\n", seed); + if (seed_set) + support_random_seed (&rand_state, seed); + else + support_random_rseed (&rand_state); + + 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 Fri Aug 31 20:42:35 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: 145694 Delivered-To: patch@linaro.org Received: by 2002:a2e:1648:0:0:0:0:0 with SMTP id 8-v6csp1210749ljw; Fri, 31 Aug 2018 13:43:42 -0700 (PDT) X-Google-Smtp-Source: ANB0VdbhB6ExCM3pvGzWjC0u8bS8Y60OpbYc+Dz2jHb6YV4VK91khWaxToPIw6nhzpVaf+Me0NOQ X-Received: by 2002:a63:2acc:: with SMTP id q195-v6mr15783699pgq.291.1535748222781; Fri, 31 Aug 2018 13:43:42 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1535748222; cv=none; d=google.com; s=arc-20160816; b=PM8XG3RdnWJX4C2A5S16Cy7jbi6ackq7YFZqaZXfCF40UXT/Q7A41cLAZXNEbYkEhU SKT24db7jMPVe3hco7My6YHfKCDcwa93EP7B+PeDL8Gg7OJT7GjRmCctS5x8OugZYQUf utfi10XEFAwQoG41z/ltskq6l2axZvw9lWL7gJy7ShIcu1Eyyu0wbc/kQbCzC48bW7dB /2gYwDDwZBXlhRTWI0EtYX2AZHp2jNQH/lc85qbNNs0QHw+CMNmHtOg3FDMYLGZ9TjK6 y8uVumqT04NCAlNM7XlVEX9Dm2iwMt5lztqmp44Dr0OcWRou4mH3RVqqag+S9eo5Jja4 ObAA== 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 :dkim-signature: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=gIGdsJKAY/w6kSPwvl/sSu58GHtwLuQ2sxH+HuqLams=; b=w0waI7Nh3sDFDVavEVUx1a6O/JLeGFxUdRdQ31zcG6ixURiNj6OxqyTJWi7trQJUjz v3fkkKYhacEi4ovRHp3n27M5OXUhbd+0vzPxih7stJ8x1mAsnMfey3gm9RE6iPivi3b1 NTHtF/xpZCTsUUjH+nIUclLlA6xXa1LFj2u9rh6WX81FgSHs4X8Nyp3f3qN6OlqezRmJ 7CQH+3YofX+xped3Ly8DeCw+tlVanjqF/n5EQcrgOiytrwStNLfjTVdnf+WP8hYW75I5 XQDECLvJ5oMyRwAPhfNEzOuiLIdBWxoh6s8li5j4ioh2V+Dt+a0xNaDxgaIcOI3tB6I2 07qA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=AlpNGvug; dkim=pass header.i=@linaro.org header.s=google header.b=i8Zvi2BB; spf=pass (google.com: domain of libc-alpha-return-95626-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="libc-alpha-return-95626-patch=linaro.org@sourceware.org"; dmarc=pass (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 a6-v6si10144230pgc.659.2018.08.31.13.43.42 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 31 Aug 2018 13:43:42 -0700 (PDT) Received-SPF: pass (google.com: domain of libc-alpha-return-95626-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=AlpNGvug; dkim=pass header.i=@linaro.org header.s=google header.b=i8Zvi2BB; spf=pass (google.com: domain of libc-alpha-return-95626-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="libc-alpha-return-95626-patch=linaro.org@sourceware.org"; dmarc=pass (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=F6CWvzLcrIPxsXcxKs399a0VF9Pf3ss Vt6UTVKUBWEcqLXh2bt2psagzjD2FbAEqaKkwI5+B93RRkLqLaVWraKcK7034vS9 3lqvvaNldXepPKEdYzPcfRuq9ijfNAsvc8S/C25jPwcpnMjfQRdvCLmC+QHUZHih 6A0PbhEsXG3w= 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=rkfyq2RG6jN0RksNb534XL2yH98=; b=AlpNG vugW6sIofrwX9Qp0SCFAfwy68DJgLz8ubwwpZ4grJlO/3+veIPAUN1cDfsRdS+24 geXyflBpELslYNMn0u+2HqAJgToZ0+duXeeF83PSx6MT220SgAAQNVaLGVccGYVH 5fAeDKDzXgIbtds/UIaURmo8AsvCt9twlCiZ2c= Received: (qmail 54801 invoked by alias); 31 Aug 2018 20:42:57 -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 54691 invoked by uid 89); 31 Aug 2018 20:42:56 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.6 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, SEM_URI, SEM_URIRED, SPF_PASS autolearn=ham version=3.3.2 spammy=HX-Received:sk:u5-v6mr X-HELO: mail-qt0-f170.google.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:subject:date:message-id:in-reply-to:references; bh=gIGdsJKAY/w6kSPwvl/sSu58GHtwLuQ2sxH+HuqLams=; b=i8Zvi2BBkNwj2y3+q+eSy4OGqm9nbQEWDBEdjwZapcHz6ZSk71uWn60ufaliXSi9zv i369pVVB+OjNZHvut3OaQ/Ujlk95XPOPuNH8QOctGLv+qzdqanO9RQE2MwRo6u06l3Zs MpHrt3b5Y96SjTc7AbHAt6jgzX6NfyJY+vUec= Return-Path: From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH v2 4/7] benchtests: Add bench-qsort Date: Fri, 31 Aug 2018 17:42:35 -0300 Message-Id: <20180831204238.10626-5-adhemerval.zanella@linaro.org> In-Reply-To: <20180831204238.10626-1-adhemerval.zanella@linaro.org> References: <20180831204238.10626-1-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 L1 32kb, L2 256kb, and L3 4096Kb. 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 | 343 +++++++++++++++++++++++++++++++++++++++ 2 files changed, 344 insertions(+), 1 deletion(-) create mode 100644 benchtests/bench-qsort.c -- 2.17.1 diff --git a/benchtests/Makefile b/benchtests/Makefile index bcd6a9c26d..796ea910ae 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 0000000000..5394aac5e2 --- /dev/null +++ b/benchtests/bench-qsort.c @@ -0,0 +1,343 @@ +/* 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(A) (sizeof (A) / sizeof ((A)[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; +}; +static struct array_t 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 support_random_state rand_state; + +static void * +create_array (size_t nmemb, size_t type_size, arraytype_t type, + seq_element_t seq) +{ + assert (nmemb < UINT32_MAX); + 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 = support_random_uniform_distribution (&rand_state, + 0, nmemb - 1); + support_random_buf (&rand_state, arr (array, pos, type_size), + type_size); + } + } + break; + + case Unsorted: + support_random_buf (&rand_state, array, size); + break; + + case Repeated: + { + support_random_buf (&rand_state, array, size); + + void *randelem = xmalloc (type_size); + support_random_buf (&rand_state, 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 = support_random_uniform_distribution (&rand_state, + 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: + { + uint64_t 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) + support_random_seed (&rand_state, seed); + else + support_random_rseed (&rand_state); + + 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 Fri Aug 31 20:42:36 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: 145696 Delivered-To: patch@linaro.org Received: by 2002:a2e:1648:0:0:0:0:0 with SMTP id 8-v6csp1210986ljw; Fri, 31 Aug 2018 13:44:01 -0700 (PDT) X-Google-Smtp-Source: ANB0VdZVDgr+pCesdXXe6LDoXyXvKu4I00Sr7ZO8WOGmSZBMyBi/cyXEzztXBVfDFEcY5v7gkS2K X-Received: by 2002:a63:9a19:: with SMTP id o25-v6mr16435230pge.39.1535748241597; Fri, 31 Aug 2018 13:44:01 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1535748241; cv=none; d=google.com; s=arc-20160816; b=YkVexl0WgTGF3G9G83HOq4V07+4/lqcd/XGBzam/6j9RE/hAORoxhbSEzzd/QH/0SV AJaGYHtSe5ctjKmj/Z13HNEW7b20eZNtnTCpy6afEOw4U1QypWd9OsFZwdhzKxzoXWjM KXlNO2YZeLR28npYA2g8eNeFsUCLjDTtBAZfvwIguMsH863W2or0+fp8GtNRcjv2ovCv jtib9SlTREhaN81T7Jo9mfpRPI2Cd+aRCew61oCKP9IE+SwUPoAXXSf8yggCdekCZOG4 wdVEvR+gR+1ybfbOO2zAxUnr5ZML5QaZabYF3i3tFH+Qr7UcwSwVOmLD3KQ55/Y6O2iM T/RA== 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 :dkim-signature: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=uCtF5zLbivX9+6Ksu/PvFhozvTZbblF7X/4ATlKacjk=; b=uLNxY6hoEMdpT1zIGnWyzsPkF5PVlmcDFcKzTk4sgkAOii4UTiJyyZhPHb3b2hr/sW HqOfgrB34VIb41o5onefick3j6728jDLtpbvINRx+y8AZdiFY1YKLPgux9huiFEQIlQU BeoFlXxNCPF/zJqj+VLTur4bVKCmrz4T+r3HOh++v9pZWj+97SzQSsqTLCUERspD0jt4 RxEj+2hzXrMq+Kj6a087ePJ+COq5wQPeRRD4kqPQ468mxoi0zv2l9h97Rv9AN4laAlUo FGRIIGvxgOFGRYfGrsucmi3p5VBTAqKdzRGVV1r54OpK/4e79XctRfbp7cj/NUz+DgxY 9dpQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=MTo3u6of; dkim=pass header.i=@linaro.org header.s=google header.b=co6Ed1vg; spf=pass (google.com: domain of libc-alpha-return-95628-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="libc-alpha-return-95628-patch=linaro.org@sourceware.org"; dmarc=pass (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 q3-v6si9557063pgv.652.2018.08.31.13.44.01 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 31 Aug 2018 13:44:01 -0700 (PDT) Received-SPF: pass (google.com: domain of libc-alpha-return-95628-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=MTo3u6of; dkim=pass header.i=@linaro.org header.s=google header.b=co6Ed1vg; spf=pass (google.com: domain of libc-alpha-return-95628-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="libc-alpha-return-95628-patch=linaro.org@sourceware.org"; dmarc=pass (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=O3wqSe6M0USVsuyEVc/piYFv1vmfQMk 5KjcHOop9VBy/BP3hRblCp4tljDrChRWbc6l69bZi94lGODVf9j9SYnkni0ZrK3d Cx4P2jBM8EekYuALucIGitJDntJGi30QjGLkwwJPuxAgYUZIrBhRviH4R7Aa3S/d yt02HjmVcZuo= 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=7PtU0fx6yI1DV/zKSvbnvYWBoiU=; b=MTo3u 6ofIisxuXWyxU8jf4VliVH645o1gJ9mIYscg5N2uMFxvVYbbbJpY6xWZ/+l+42OK 8pB4GQ7QH31FGpbcXHkMYnW0OEbV2EBJGq/ybr3lfK+U/j6pXRErczPY0Izphwsi Bu+wsw7ycWjXCq7ROfFDRuwE7kZHIoYUjzjQl8= Received: (qmail 55275 invoked by alias); 31 Aug 2018 20:43:01 -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 54954 invoked by uid 89); 31 Aug 2018 20:42:58 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.7 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, SEM_URI, SEM_URIRED, SPF_PASS autolearn=ham version=3.3.2 spammy=Engineering, thereby, sorts, pt X-HELO: mail-qk1-f179.google.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:subject:date:message-id:in-reply-to:references; bh=uCtF5zLbivX9+6Ksu/PvFhozvTZbblF7X/4ATlKacjk=; b=co6Ed1vg+hLghXaBpZE7XoVzGf9xFXTI0bmwhM8XRgTUjrd+5mDnkrxBcmXfTG7ZKm XytR1Gjn1nB3WfRjQHzklAjb+ao/Q800hQIx2554aXJCf3n6sAyCJzYnUi/TJvGrExhT m4tn2w0E7rupDD/YgUvDE3LxvXzn5YAfI9OIE= Return-Path: From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH v2 5/7] stdlib: Remove use of mergesort on qsort Date: Fri, 31 Aug 2018 17:42:36 -0300 Message-Id: <20180831204238.10626-6-adhemerval.zanella@linaro.org> In-Reply-To: <20180831204238.10626-1-adhemerval.zanella@linaro.org> References: <20180831204238.10626-1-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 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.1.1) shows the performance difference between mergesort (base) and quicksort (patched): Results for member size 4 MostlySorted nmemb | base | patched | diff 32 | 1791 | 2145 | 19.77 4096 | 530267 | 902724 | 70.24 32768 | 5319819 | 7844403 | 47.46 524288 | 105147020 | 152809379 | 45.33 Repeated nmemb | base | patched | diff 32 | 1988 | 2222 | 11.77 4096 | 898057 | 1029244 | 14.61 32768 | 8890765 | 10057897 | 13.13 524288 | 178316071 | 197150076 | 10.56 Sorted nmemb | base | patched | diff 32 | 1511 | 1461 | -3.31 4096 | 277733 | 357884 | 28.86 32768 | 2634360 | 3468080 | 31.65 524288 | 49793076 | 67584959 | 35.73 Unsorted nmemb | base | patched | diff 32 | 2070 | 2385 | 15.22 4096 | 941830 | 1146892 | 21.77 32768 | 9492371 | 10799397 | 13.77 524288 | 191355021 | 212098446 | 10.84 Results for member size 8 MostlySorted nmemb | base | patched | diff 32 | 1763 | 2676 | 51.79 4096 | 510794 | 907769 | 77.72 32768 | 5075103 | 8605499 | 69.56 524288 | 103741137 | 154255341 | 48.69 Repeated nmemb | base | patched | diff 32 | 1908 | 2230 | 16.88 4096 | 904798 | 1129157 | 24.80 32768 | 8954918 | 10775229 | 20.33 524288 | 179825532 | 212935649 | 18.41 Sorted nmemb | base | patched | diff 32 | 1316 | 1193 | -9.35 4096 | 261069 | 308152 | 18.03 32768 | 2449581 | 3022480 | 23.39 524288 | 47772793 | 60029109 | 25.66 Unsorted nmemb | base | patched | diff 32 | 2011 | 2814 | 39.93 4096 | 953723 | 1198160 | 25.63 32768 | 9539278 | 11678920 | 22.43 524288 | 193690362 | 229161344 | 18.31 Results for member size 32 MostlySorted nmemb | base | patched | diff 32 | 4686 | 5073 | 8.26 4096 | 1688822 | 1572437 | -6.89 32768 | 17633569 | 14170732 | -19.64 524288 | 375170630 | 267001863 | -28.83 Repeated nmemb | base | patched | diff 32 | 5138 | 5592 | 8.84 4096 | 2187509 | 1890849 | -13.56 32768 | 22271793 | 18284219 | -17.90 524288 | 468956765 | 361847282 | -22.84 Sorted nmemb | base | patched | diff 32 | 3581 | 1179 | -67.08 4096 | 938145 | 308793 | -67.08 32768 | 9553669 | 3017486 | -68.42 524288 | 194239124 | 63986145 | -67.06 Unsorted nmemb | base | patched | diff 32 | 5235 | 6591 | 25.90 4096 | 2227377 | 1990681 | -10.63 32768 | 22875769 | 19127569 | -16.39 524288 | 484156353 | 375072780 | -22.53 The result shows an increase in latency, as expected. Some performance difference is also due the fact mergesort uses a slight improved swap operation than quicksort (which a following patch addresses it). This change also renders the BZ #21719 fix unrequired (since it is meant to fix the sorted input performance degradation for mergesort). The manual is also updated to indicate the function is now 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 | 3 +- stdlib/msort.c | 310 --------------------------------------------- stdlib/qsort.c | 15 ++- 6 files changed, 18 insertions(+), 322 deletions(-) delete mode 100644 stdlib/msort.c -- 2.17.1 diff --git a/manual/argp.texi b/manual/argp.texi index 0023441812..b77ad68285 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 dabb959f9e..15d3b7820c 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 57dad7a56d..148d451701 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 4e012a865a..2c28033196 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 \ @@ -139,7 +139,6 @@ 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-system.os = -fomit-frame-pointer diff --git a/stdlib/msort.c b/stdlib/msort.c deleted file mode 100644 index 266c2538c0..0000000000 --- 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 264a06b8a9..b3a5102cac 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 Fri Aug 31 20:42:37 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: 145695 Delivered-To: patch@linaro.org Received: by 2002:a2e:1648:0:0:0:0:0 with SMTP id 8-v6csp1210862ljw; Fri, 31 Aug 2018 13:43:51 -0700 (PDT) X-Google-Smtp-Source: ANB0Vdbs/sbAmGJ23lMaBsHDAAFVZdA4y1ENDAGRjJli/eZS+/uIaM6QBVYNxy7AVpDP8dKrvBjM X-Received: by 2002:a62:59d5:: with SMTP id k82-v6mr17530996pfj.143.1535748231336; Fri, 31 Aug 2018 13:43:51 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1535748231; cv=none; d=google.com; s=arc-20160816; b=uq1cE80HV6HdbaDuTKs2Vl1HDVRB5dc44+x1YX6zUq7crB3tgWsejJPxTpELq6krMA LxhSsNgvTS6PgRLVL1nnN68kEu8qV9uXUjsfXjJZw38cPGu5qgjoEq0KjhvQzhlyAGdH ouQXwO7OROOCMd/+CsMPDC06BppGxKv8LOWh/4yHd0JNrFvhKCPgl2jqKTpdENUR71O/ v6ugaew7uW5Kz4K1qlN0w3F+JMGaQ9DBx0ehz6z/64+lhN+H5/AVkScPnEpHDdlqoIq6 wKLQCu9fhWLKRlxLda8KIfipwYRinFCeWsEKXuCzGJeERD/qJ4//Y/mVQV8/V/EIFvdc gGkQ== 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 :dkim-signature: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=q7pnXEEMiqN2PDA8YBltfzoiv3QoQJAFNeMjPmUwloA=; b=snlHSuViEsNi7Qfbg78hyKDgqZ81Otta+FAhN8wJWRShx8LKZBt9oy7dXBoujVzjTn i+F6Afu+lTIVGyahutTV2b6TFv47C9AvXJchLs5HWnvJ4tWXfX14JInmLfg2c7Hk22/p VSUj/V0KZGPPnOfpTxzNoufTeYRXtiYStd+vBALtnZctI6a0hVSnVRGDQLQtjnKY51JV PRiCnG/RNSVE1hRHx6DzQwrP/A+vOO/etXuAWQ1Najmj43xWKxRKCYUaofYnNdsCBSCn ds7Y7cexvllHHjk2Jne4/w/alkd3tvmxP+7B7gnHYTUUjdY76Lc2kBEE3U/wJ4KES0NI W8kw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=Ft6ZYzpy; dkim=pass header.i=@linaro.org header.s=google header.b=KiZeEg2D; spf=pass (google.com: domain of libc-alpha-return-95627-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="libc-alpha-return-95627-patch=linaro.org@sourceware.org"; dmarc=pass (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 p1-v6si11314431pfb.280.2018.08.31.13.43.50 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 31 Aug 2018 13:43:51 -0700 (PDT) Received-SPF: pass (google.com: domain of libc-alpha-return-95627-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=Ft6ZYzpy; dkim=pass header.i=@linaro.org header.s=google header.b=KiZeEg2D; spf=pass (google.com: domain of libc-alpha-return-95627-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="libc-alpha-return-95627-patch=linaro.org@sourceware.org"; dmarc=pass (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=OxDzPJ5NpsXN1m1Pnqm/M5QPKe/Ufca Nrc7Du1MHi50S/BFGwocXX6Y7O+NseMApdr6qCT5eWYhEZst1dkvDhYA0F2aIy7u bZBVH5AH646SskztCh65WI3PtCFv+UmdKkpBEsUBlug8FvhcNDj5MNj1eV9G3qga jfcaJnZtFjeI= 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=DXeVBh7WnTK5zUgMZ4vsiDthQ0g=; b=Ft6ZY zpythXzpF5zPLjyvty9oXfFHBAjwEjzT8OABx+o+h04ympsh8XkcX3XGXG/gU9vr c/6zO12x15K678qhjp09mPJKrizGOtWRtc3/yOKcDmnT+vWUJVt/6+17pCQ84olt /5GV1XIFChlkgzvpQOiiZmdMA66fu3w4P0G+so= Received: (qmail 54928 invoked by alias); 31 Aug 2018 20:42:58 -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 54813 invoked by uid 89); 31 Aug 2018 20:42:57 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.7 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, SEM_URI, SEM_URIRED, SPF_PASS autolearn=ham version=3.3.2 spammy=mid, 1300, 1965, HX-Received:sk:z5-v6mr X-HELO: mail-qk1-f172.google.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:subject:date:message-id:in-reply-to:references; bh=q7pnXEEMiqN2PDA8YBltfzoiv3QoQJAFNeMjPmUwloA=; b=KiZeEg2DD2BxCqVo0FhSa/gKDfjca1cEqZCoEKxhi0Zxdmmi8N1EvIg0UsehjUAiI2 aJboqMrEIvFA5Vx3QX8FqRUdASlHLP9wH8/pKl3RTe3N9NbrLIlO4GTfW2sdoy0f9U0I 5KaGCtdrcv1cycl+TDuJf6ou/nmnqRH/zgkpQ= Return-Path: From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH v2 6/7] stdlib: Optimization qsort{_r} swap implementation Date: Fri, 31 Aug 2018 17:42:37 -0300 Message-Id: <20180831204238.10626-7-adhemerval.zanella@linaro.org> In-Reply-To: <20180831204238.10626-1-adhemerval.zanella@linaro.org> References: <20180831204238.10626-1-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 MostlySorted nmemb | base | patched | diff 32 | 2145 | 2012 | -6.20 4096 | 902724 | 789329 | -12.56 32768 | 7844403 | 7871853 | 0.35 524288 | 152809379 | 151037732 | -1.16 Repeated nmemb | base | patched | diff 32 | 2222 | 2017 | -9.23 4096 | 1029244 | 948784 | -7.82 32768 | 10057897 | 9242215 | -8.11 524288 | 197150076 | 182508235 | -7.43 Sorted nmemb | base | patched | diff 32 | 1461 | 1332 | -8.83 4096 | 357884 | 351388 | -1.82 32768 | 3468080 | 3556735 | 2.56 524288 | 67584959 | 67278267 | -0.45 Unsorted nmemb | base | patched | diff 32 | 2385 | 2009 | -15.77 4096 | 1146892 | 1039794 | -9.34 32768 | 10799397 | 10116859 | -6.32 524288 | 212098446 | 198713626 | -6.31 Results for member size 8 MostlySorted nmemb | base | patched | diff 32 | 2676 | 1965 | -26.57 4096 | 907769 | 762125 | -16.04 32768 | 8605499 | 7017240 | -18.46 524288 | 154255341 | 129564606 | -16.01 Repeated nmemb | base | patched | diff 32 | 2230 | 1998 | -10.40 4096 | 1129157 | 970507 | -14.05 32768 | 10775229 | 9173248 | -14.87 524288 | 212935649 | 179637006 | -15.64 Sorted nmemb | base | patched | diff 32 | 1193 | 1205 | 1.01 4096 | 308152 | 308174 | 0.01 32768 | 3022480 | 3018157 | -0.14 524288 | 60029109 | 59608087 | -0.70 Unsorted nmemb | base | patched | diff 32 | 2814 | 2575 | -8.49 4096 | 1198160 | 1040231 | -13.18 32768 | 11678920 | 10160881 | -13.00 524288 | 229161344 | 197305501 | -13.90 Results for member size 32 MostlySorted nmemb | base | patched | diff 32 | 5073 | 4474 | -11.81 4096 | 1572437 | 1185956 | -24.58 32768 | 14170732 | 10710788 | -24.42 524288 | 267001863 | 196553161 | -26.39 Repeated nmemb | base | patched | diff 32 | 5592 | 4670 | -16.49 4096 | 1890849 | 1351979 | -28.50 32768 | 18284219 | 12917614 | -29.35 524288 | 361847282 | 258020738 | -28.69 Sorted nmemb | base | patched | diff 32 | 1179 | 1221 | 3.56 4096 | 308793 | 308146 | -0.21 32768 | 3017486 | 3120670 | 3.42 524288 | 63986145 | 64995508 | 1.58 Unsorted nmemb | base | patched | diff 32 | 6591 | 3975 | -39.69 4096 | 1990681 | 1470465 | -26.13 32768 | 19127569 | 14109425 | -26.24 524288 | 375072780 | 276687595 | -26.23 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 | 83 +++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 65 insertions(+), 18 deletions(-) -- 2.17.1 diff --git a/stdlib/qsort.c b/stdlib/qsort.c index b3a5102cac..c3fb0e862f 100644 --- a/stdlib/qsort.c +++ b/stdlib/qsort.c @@ -23,20 +23,65 @@ #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 * restrict a, void * restrict b, size_t size) +{ + uint32_t *ua = a, *ub = b, tmp = *ua; + *ua = *ub, *ub = tmp; +} + +static void +swap_u64 (void * restrict a, void * restrict b, size_t size) +{ + uint64_t *ua = a, *ub = b, tmp = *ua; + *ua = *ub, *ub = tmp; +} + +static void +swap_generic (void * restrict a, void * restrict b, size_t size) +{ + /* Use multiple small memcpys with constant size to enable inlining + on most targets. */ + enum { + SWAP_GENERIC_SIZE = 32 + }; + unsigned char tmp[SWAP_GENERIC_SIZE]; + while (size > SWAP_GENERIC_SIZE) + { + memcpy (tmp, a, SWAP_GENERIC_SIZE); + a = memcpy (a, b, SWAP_GENERIC_SIZE) + SWAP_GENERIC_SIZE; + b = memcpy (b, tmp, SWAP_GENERIC_SIZE) + SWAP_GENERIC_SIZE; + size -= SWAP_GENERIC_SIZE; + } + memcpy (tmp, a, size); + memcpy (a, b, size); + memcpy (b, tmp, size); +} + +static inline swap_t +select_swap_func (const void *base, size_t size) +{ + if (size == sizeof (uint32_t) + && check_alignment (base, _Alignof (uint32_t))) + return swap_u32; + else if (size == sizeof (uint64_t) + && check_alignment (base, _Alignof (uint64_t))) + 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 +141,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 +166,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 +191,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 +263,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 Fri Aug 31 20:42:38 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: 145697 Delivered-To: patch@linaro.org Received: by 2002:a2e:1648:0:0:0:0:0 with SMTP id 8-v6csp1211177ljw; Fri, 31 Aug 2018 13:44:13 -0700 (PDT) X-Google-Smtp-Source: ANB0VdbGTbbj69CHh97twfGY2F5pZ8S18aVgFiK8nBsP7oGs/TG9+quM8pbRQAOlLMP5HQJfDITC X-Received: by 2002:a63:df4e:: with SMTP id h14-v6mr16076439pgj.300.1535748252942; Fri, 31 Aug 2018 13:44:12 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1535748252; cv=none; d=google.com; s=arc-20160816; b=amz26w3ghLU4RU0U99hBzf0Fc+0Qmnn/9y0yNGDmQVAoPU/Teowruri3cfnDlGM6g6 yAKGoBgJrafGHsg4hnKaKzuRDXy36LiBGdKJUw1npim4RE8ljFghWzG498PGIN/hX6+j 6b/C2HXnjyuGEnqptsjIWwvXN4Y9oAj/7HuLsfxX+ttAOPc3LUdEHLICQosMlVF1iNon ceojJt4sFebwbwE+D1jwlAitJV4LG0TZVG9kOqhqKC5YWteAJ9ViOXLU/75Wy2r8hMAq oQEySN7187+76ZoU6txpZOWOrZu0pejKgMOLo2sndKM+1KHn0ZEu0HeREXWo+Of7Lu/8 wAkA== 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 :dkim-signature: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=gXrM1sfLY361hdTN6kTJzer5iMeBHUpFmUS075NDvLg=; b=oBAsoMHhiNuC7Y9qtM4LtoCNJd+7aJJYeDIG0y5bqyUcMpe3gRnbDC2Gm+/3/G0oIz Eaxkq1sekC4VcCKrAgKZBB731EDSX7Hj6MJoLVNUdepN+xoZ1dE75Hi0yf9rfEEtLoK+ XHfVzeECHBga1eKlY/yBzHb+94hD0x2jDQurMzgzxmdbwpoLV8ag6o29VzQ4fCueUVPQ S/U+U36uV3VoOfHE41ubCFYOCsLHlm7G9/YBDjIJCK1b9ueTMgkP/YHY3Xiwg5xdCjI4 U4WhRvowlsdVq4s0ZRTvbQ6i5rENBbMx6iTUPunrWsmS1epotQDMHCPZZRs0nt0cpuTf lFFQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=pHuyDMEn; dkim=pass header.i=@linaro.org header.s=google header.b=caOjF9Hx; spf=pass (google.com: domain of libc-alpha-return-95629-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="libc-alpha-return-95629-patch=linaro.org@sourceware.org"; dmarc=pass (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 x7-v6si8474408pgi.465.2018.08.31.13.44.12 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 31 Aug 2018 13:44:12 -0700 (PDT) Received-SPF: pass (google.com: domain of libc-alpha-return-95629-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=pHuyDMEn; dkim=pass header.i=@linaro.org header.s=google header.b=caOjF9Hx; spf=pass (google.com: domain of libc-alpha-return-95629-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="libc-alpha-return-95629-patch=linaro.org@sourceware.org"; dmarc=pass (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=K7iG+ZCvAFBV7q3CgHJBwkO54cV1fqM JYaxYL9Tctjeb2hsoSTymBdf4bQIssVG4XVFhY/CuoDYukKM968BlREsGH4zzPfl y7WTWLHMpCSB6DuSugV6pXXDFuJzDJaVWFmzNtt48k8r1CDvlypEwdyJadsDCPTI dGLf297R63RM= 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=liYck7On5g8EFExAaZqNciwb0Xs=; b=pHuyD MEnU7EFCmDH5i4rex3/mfgUQiizNZMJaJBOSZEJqH/Bwz9kJlB4ZbrlbP28XGlmt TA1aeBAeLss2jsA8LfcaGeNtU01xwrHP1IPE/yO4bpC0poUYLOXpD6XEV5zUowYK vpIZ4gS4X3f3Conu4P32cs5zcOOMt4YA6IrO1Y= Received: (qmail 55450 invoked by alias); 31 Aug 2018 20:43:02 -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 55334 invoked by uid 89); 31 Aug 2018 20:43:01 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.7 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, SEM_URI, SEM_URIRED, SPF_PASS autolearn=ham version=3.3.2 spammy=mid, Engineering, famous, sorts X-HELO: mail-qk1-f179.google.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:subject:date:message-id:in-reply-to:references; bh=gXrM1sfLY361hdTN6kTJzer5iMeBHUpFmUS075NDvLg=; b=caOjF9HxyTzAXwLRvQHMhHZLoj5xSC0HA/mAkxefGAUPmirQCfxr+SU3MyF0gtIkJ3 DlE8efsphgbIIywf92nLtX5jBWAJ4+E3c15gj+35hY4OSxNJzIlLJrqzoWLijQHOobZN S82R6mOdFWECwakSPMfFz8aw0f6h371gaVyBo= Return-Path: From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH v2 7/7] stdlib: Remove undefined behavior from qsort implementation Date: Fri, 31 Aug 2018 17:42:38 -0300 Message-Id: <20180831204238.10626-8-adhemerval.zanella@linaro.org> In-Reply-To: <20180831204238.10626-1-adhemerval.zanella@linaro.org> References: <20180831204238.10626-1-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.1.1) shows a slight better performance for qsort: Results for member size 4 MostlySorted nmemb | base | patched | diff 32 | 2012 | 1962 | -2.49 4096 | 789329 | 733319 | -7.10 32768 | 7871853 | 6888903 | -12.49 524288 | 151037732 | 132290195 | -12.41 Repeated nmemb | base | patched | diff 32 | 2017 | 2101 | 4.16 4096 | 948784 | 917065 | -3.34 32768 | 9242215 | 8824654 | -4.52 524288 | 182508235 | 174457327 | -4.41 Sorted nmemb | base | patched | diff 32 | 1332 | 1323 | -0.68 4096 | 351388 | 334323 | -4.86 32768 | 3556735 | 3342922 | -6.01 524288 | 67278267 | 67018557 | -0.39 Unsorted nmemb | base | patched | diff 32 | 2009 | 2267 | 12.84 4096 | 1039794 | 967586 | -6.94 32768 | 10116859 | 9561046 | -5.49 524288 | 198713626 | 188618808 | -5.08 Results for member size 8 MostlySorted nmemb | base | patched | diff 32 | 1965 | 1895 | -3.56 4096 | 762125 | 737046 | -3.29 32768 | 7017240 | 7503068 | 6.92 524288 | 129564606 | 145792996 | 12.53 Repeated nmemb | base | patched | diff 32 | 1998 | 2392 | 19.72 4096 | 970507 | 941746 | -2.96 32768 | 9173248 | 8846305 | -3.56 524288 | 179637006 | 172015349 | -4.24 Sorted nmemb | base | patched | diff 32 | 1205 | 1154 | -4.23 4096 | 308174 | 302059 | -1.98 32768 | 3018157 | 2957746 | -2.00 524288 | 59608087 | 59248485 | -0.60 Unsorted nmemb | base | patched | diff 32 | 2575 | 2014 | -21.79 4096 | 1040231 | 1014879 | -2.44 32768 | 10160881 | 9719416 | -4.34 524288 | 197305501 | 188728948 | -4.35 Results for member size 32 MostlySorted nmemb | base | patched | diff 32 | 4474 | 3054 | -31.74 4096 | 1185956 | 1093125 | -7.83 32768 | 10710788 | 10672711 | -0.36 524288 | 196553161 | 187567373 | -4.57 Repeated nmemb | base | patched | diff 32 | 4670 | 4084 | -12.55 4096 | 1351979 | 1334757 | -1.27 32768 | 12917614 | 12764998 | -1.18 524288 | 258020738 | 251722513 | -2.44 Sorted nmemb | base | patched | diff 32 | 1221 | 1232 | 0.90 4096 | 308146 | 301690 | -2.10 32768 | 3120670 | 2967993 | -4.89 524288 | 64995508 | 64345690 | -1.00 Unsorted nmemb | base | patched | diff 32 | 3975 | 3927 | -1.21 4096 | 1470465 | 1483229 | 0.87 32768 | 14109425 | 13819034 | -2.06 524288 | 276687595 | 272021523 | -1.69 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.17.1 diff --git a/stdlib/qsort.c b/stdlib/qsort.c index c3fb0e862f..10b805930a 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); @@ -104,202 +100,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 0000000000..666b1958ab --- /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