From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id C48A8385781D for ; Thu, 19 Nov 2020 19:17:10 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org C48A8385781D Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-579-fsrObcA8OKq4bDO61EhUtA-1; Thu, 19 Nov 2020 14:16:54 -0500 X-MC-Unique: fsrObcA8OKq4bDO61EhUtA-1 Received: from smtp.corp.redhat.com (int-mx05.intmail.prod.int.phx2.redhat.com [10.5.11.15]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 8C61B1005E5B; Thu, 19 Nov 2020 19:16:53 +0000 (UTC) Received: from localhost (unknown [10.33.36.170]) by smtp.corp.redhat.com (Postfix) with ESMTP id 3D4D85D6B1; Thu, 19 Nov 2020 19:16:53 +0000 (UTC) Date: Thu, 19 Nov 2020 19:16:52 +0000 From: Jonathan Wakely To: Lewis Hyatt Cc: gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org Subject: Re: libstdc++: Avoid zero-probability events in discrete_distribution [PR61369] Message-ID: <20201119191652.GG1312820@redhat.com> References: <20201119175700.GA73944@ldh-imac.local> MIME-Version: 1.0 In-Reply-To: <20201119175700.GA73944@ldh-imac.local> X-Clacks-Overhead: GNU Terry Pratchett X-Scanned-By: MIMEDefang 2.79 on 10.5.11.15 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=us-ascii; format=flowed Content-Disposition: inline X-Spam-Status: No, score=-14.0 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=unavailable autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 19 Nov 2020 19:17:12 -0000 On 19/11/20 12:57 -0500, Lewis Hyatt via Libstdc++ wrote: >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. But the increase in header sizes in C++20 is a regression: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92546 Anyway, I'll review this patch tomorrow, thanks for sending it. >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 > // { dg-error "static assertion failed: template argument must be a floating point type" "" { target *-*-* } 167 } > >-// { dg-error "static assertion failed: template argument must be a floating point type" "" { target *-*-* } 3346 } >+// { dg-error "static assertion failed: template argument must be a floating point type" "" { target *-*-* } 3347 }