From patchwork Thu Nov 19 17:57:00 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Lewis Hyatt X-Patchwork-Id: 1403212 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=pass (p=none dis=none) header.from=gcc.gnu.org Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=nxETwMtO; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4CcS7C56vtz9s1l for ; Fri, 20 Nov 2020 04:57:11 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 20D1839A6818; Thu, 19 Nov 2020 17:57:06 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 20D1839A6818 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1605808626; bh=aLk4CsAiZwR6H18jLgFWk9C2x7YkIVHZ/boxrohyXwk=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=nxETwMtOS4V4NFjvdunSZFW7e+iGwsKkfJp9z3HV28hnGCs6H32WuJy4ZAM7HNBJH ZdV9FKYX/vKw3qtBWiJGOLsYZeqR38CjWC0A53VaSjF8YE4++nePNXvl+cIuuEcDRm EBUXSqAFl62+UtdS8wrbKS477KDCXygUFcmLbEJM= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-qv1-xf2f.google.com (mail-qv1-xf2f.google.com [IPv6:2607:f8b0:4864:20::f2f]) by sourceware.org (Postfix) with ESMTPS id 69B5D3851C27; Thu, 19 Nov 2020 17:57:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 69B5D3851C27 Received: by mail-qv1-xf2f.google.com with SMTP id x13so3291977qvk.8; Thu, 19 Nov 2020 09:57:03 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:mime-version :content-disposition; bh=aLk4CsAiZwR6H18jLgFWk9C2x7YkIVHZ/boxrohyXwk=; b=rqGvA21cbV2geGikq2Z2lUpM5w59Cr0JXjsXuMhk3/og2tKRqnKaHGbalNjLY6z0q4 023YQeSFjHr1+M+RT5MlEVAXM7T4Lwj91YF7fK22zPshxBfBGvKEGkLtpsqjBe617eLf O+gEXVNulMQuFfWr+IDJ86rs0w/X0xByDmT/lJIbpiT+/KjAkwNXsLlmdR6pFHXh5tHD 2/+OzVdMNiu4CzxvDaR9IvdxQpHFHWJVpODIsMgWKvgAfznSH8vout6URS+hAv2aFpO0 7YkIHU2kU8c1FLX5pb96tcanAjO0ki83UxX6cYEOcbnibaPcrlJ2pQPHk5Gx000PzbT8 ThuA== X-Gm-Message-State: AOAM530Y13T4fdhGHkmpLS+Gwy5XOE1Cz4kjAASwy+C842CUZJ+AVGDS xOEU62P31SEFcnsNdJrfWuz5wC84SjQ= X-Google-Smtp-Source: ABdhPJwvY8WxK7O7TJ6Wc7tqbuH8kILfmMaAFnVHTg9gLcz1Qo2SjYigUOjlACh8rm8xAXb8rPlKCA== X-Received: by 2002:a0c:99c6:: with SMTP id y6mr11861444qve.60.1605808622775; Thu, 19 Nov 2020 09:57:02 -0800 (PST) Received: from ldh-imac.local (944c6a92.cst.lightpath.net. [148.76.106.146]) by smtp.gmail.com with ESMTPSA id 72sm342087qtg.69.2020.11.19.09.57.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 19 Nov 2020 09:57:02 -0800 (PST) Date: Thu, 19 Nov 2020 12:57:00 -0500 To: gcc-patches@gcc.gnu.org Subject: libstdc++: Avoid zero-probability events in discrete_distribution [PR61369] Message-ID: <20201119175700.GA73944@ldh-imac.local> MIME-Version: 1.0 Content-Disposition: inline X-Spam-Status: No, score=-3039.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Lewis Hyatt via Gcc-patches From: Lewis Hyatt Reply-To: Lewis Hyatt Cc: libstdc++@gcc.gnu.org Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" Hello- PR61369 (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61369) points out that std::discrete_distribution can return an event even if it has 0 probability, and proposes a simple fix. It seems that this fix was never applied, because there was an expectation of redoing this code anyway to use a more efficient algorithm (PR57925). Given that this new algorithm has not been implemented so far, would it make sense to apply the simple fix to address this issue? The attached patch does this. One question about the patch, a slight annoyance is that only std::lower_bound() is currently available in random.tcc, as this file includes only bits/stl_algobase.h and not bits/stl_algo.h (via including ). Is there a preference between simply including stl_algo.h, or moving upper_bound to stl_algobase.h, where lower_bound is? I noticed that in C++20 mode, includes stl_algo.h already, so I figured it would be fine to just include it in random.tcc unconditionally. bootstrap + testing were done on x86-64 GNU/Linux, all tests the same before + after plus 2 new passes from the new test. Thanks for taking a look! -Lewis From: Lewis Hyatt Date: Wed, 18 Nov 2020 17:12:51 -0500 Subject: [PATCH] libstdc++: Avoid zero-probability events in discrete_distribution [PR61369] Fixes PR61369, as recommended by the PR's submitter, by replacing lower_bound() with upper_bound(). Currently, if there is an initial subset of events with probability 0, the first of them will be returned with non-zero probability (if the underlying RNG returns exactly 0). Switching to upper_bound() ensures that this will not happen. libstdc++-v3/ChangeLog: PR libstdc++/61369 * include/bits/random.tcc: Include bits/stl_algo.h. (discrete_distribution::operator()): Use upper_bound rather than lower_bound. * testsuite/26_numerics/random/pr60037-neg.cc: Adapt to new line numbering in random.tcc. * testsuite/26_numerics/random/discrete_distribution/pr61369.cc: New test. diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc index 3205442f2f6..14fe4f39c7b 100644 --- a/libstdc++-v3/include/bits/random.tcc +++ b/libstdc++-v3/include/bits/random.tcc @@ -31,6 +31,7 @@ #define _RANDOM_TCC 1 #include // std::accumulate and std::partial_sum +#include // std::upper_bound namespace std _GLIBCXX_VISIBILITY(default) { @@ -2706,7 +2707,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __aurng(__urng); const double __p = __aurng(); - auto __pos = std::lower_bound(__param._M_cp.begin(), + auto __pos = std::upper_bound(__param._M_cp.begin(), __param._M_cp.end(), __p); return __pos - __param._M_cp.begin(); diff --git a/libstdc++-v3/testsuite/26_numerics/random/discrete_distribution/pr61369.cc b/libstdc++-v3/testsuite/26_numerics/random/discrete_distribution/pr61369.cc new file mode 100644 index 00000000000..f8fa97e293e --- /dev/null +++ b/libstdc++-v3/testsuite/26_numerics/random/discrete_distribution/pr61369.cc @@ -0,0 +1,55 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-do run { target c++11 } } +// { dg-require-cstdint "" } + +#include +#include +#include +#include + +class not_so_random +{ +public: + using result_type = std::uint64_t; + + static constexpr result_type + min() + { return 0u; } + + static constexpr result_type + max() + { return std::numeric_limits::max(); } + + result_type + operator()() const + { return 0u; } +}; + +void +test01() +{ + std::discrete_distribution<> u{0.0, 0.5, 0.5}; + not_so_random rng; + VERIFY( u(rng) > 0 ); +} + +int main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc b/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc index ba252ef34fe..4d00d1846c4 100644 --- a/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc +++ b/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc @@ -12,4 +12,4 @@ auto x = std::generate_canonical