* Re: sort_heap complexity guarantee [not found] ` <alpine.DEB.2.11.1410052245150.5366@stedding.saclay.inria.fr> @ 2014-10-06 21:00 ` François Dumont 2014-10-06 21:05 ` Daniel Krügler ` (2 more replies) 0 siblings, 3 replies; 9+ messages in thread From: François Dumont @ 2014-10-06 21:00 UTC (permalink / raw) To: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 1954 bytes --] On 05/10/2014 22:54, Marc Glisse wrote: > On Sun, 5 Oct 2014, François Dumont wrote: > >> I took a look at PR 61217 regarding pop_heap complexity guarantee. >> Looks like we have no test to check complexity of our algos so I >> start writing some starting with the heap operations. I found no >> issue with make_heap, push_heap and pop_heap despite what the bug >> report is saying however the attached testcase for sort_heap is failing. >> >> Standard is saying std::sort_heap shall use less than N * log(N) >> comparisons but with my test using 1000 random values the test is >> showing: >> >> 8687 comparisons on 6907.76 max allowed >> >> Is this a known issue of sort_heap ? Do you confirm that the test >> is valid ? > > I would first look for confirmation that the standard didn't just > forget a big-O or something. I would expect an implementation as n > calls to pop_heap to be legal, and if pop_heap makes 2*log(n) > comparisons, that naively sums to too much. And I don't expect the > standard to contain an advanced amortized analysis or anything like > that... > Good point, with n calls to pop_heap it means that limit must be 2*log(1) + 2*log(2) +... + 2*log(n) which is 2*log(n!) and which is also necessarily < 2*n*log(n). I guess Standard comittee has forgotten the factor 2 in the limit so this is what I am using as limit in the final test, unless someone prefer the stricter 2*log(n!) ? Ok to commit those new tests ? 2014-10-06 François Dumont <fdumont@gcc.gnu.org> * testsuite/util/testsuite_counter_type.h (counter_type::operator<(const counter_type&)): Update less_compare_count when called. * testsuite/25_algorithms/make_heap/complexity.cc: New. * testsuite/25_algorithms/pop_heap/complexity.cc: New. * testsuite/25_algorithms/push_heap/complexity.cc: New. * testsuite/25_algorithms/sort_heap/complexity.cc: New. Tested under Linux x86_64. François [-- Attachment #2: complexity.patch --] [-- Type: text/x-patch, Size: 7666 bytes --] Index: testsuite/25_algorithms/make_heap/complexity.cc =================================================================== --- testsuite/25_algorithms/make_heap/complexity.cc (revision 0) +++ testsuite/25_algorithms/make_heap/complexity.cc (working copy) @@ -0,0 +1,50 @@ +// Copyright (C) 2014 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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++11" } + +#include <random> +#include <vector> +#include <algorithm> + +#include <testsuite_counter_type.h> +#include <testsuite_hooks.h> + +void test01() +{ + using __gnu_test::counter_type; + const std::size_t nb_values = 1000; + + std::random_device dev; + std::uniform_int_distribution<int> dist; + std::vector<counter_type> values; + values.reserve(nb_values); + for (std::size_t i = 0; i != nb_values; ++i) + values.push_back(dist(dev)); + + counter_type::reset(); + + std::make_heap(values.begin(), values.end()); + + VERIFY( counter_type::less_compare_count <= 3.0 * nb_values ); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/25_algorithms/pop_heap/complexity.cc =================================================================== --- testsuite/25_algorithms/pop_heap/complexity.cc (revision 0) +++ testsuite/25_algorithms/pop_heap/complexity.cc (working copy) @@ -0,0 +1,53 @@ +// Copyright (C) 2014 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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++11" } + +#include <cmath> +#include <random> +#include <vector> +#include <algorithm> + +#include <testsuite_counter_type.h> +#include <testsuite_hooks.h> + +void test01() +{ + using __gnu_test::counter_type; + const std::size_t nb_values = 1000; + + std::random_device dev; + std::uniform_int_distribution<int> dist; + std::vector<counter_type> values; + values.reserve(nb_values); + for (std::size_t i = 0; i != nb_values; ++i) + values.push_back(dist(dev)); + + std::make_heap(values.begin(), values.end()); + + counter_type::reset(); + + std::pop_heap(values.begin(), values.end()); + + VERIFY( counter_type::less_compare_count <= 2.0 * std::log(nb_values) ); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/25_algorithms/push_heap/complexity.cc =================================================================== --- testsuite/25_algorithms/push_heap/complexity.cc (revision 0) +++ testsuite/25_algorithms/push_heap/complexity.cc (working copy) @@ -0,0 +1,54 @@ +// Copyright (C) 2014 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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++11" } + +#include <cmath> +#include <random> +#include <vector> +#include <algorithm> + +#include <testsuite_counter_type.h> +#include <testsuite_hooks.h> + +void test01() +{ + using __gnu_test::counter_type; + const std::size_t nb_values = 1000; + + std::random_device dev; + std::uniform_int_distribution<int> dist; + std::vector<counter_type> values; + values.reserve(nb_values); + for (std::size_t i = 0; i != nb_values; ++i) + values.push_back(dist(dev)); + + std::make_heap(values.begin(), values.end()); + values.push_back(dist(dev)); + + counter_type::reset(); + + std::push_heap(values.begin(), values.end()); + + VERIFY( counter_type::less_compare_count <= std::log(values.size()) ); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/25_algorithms/sort_heap/complexity.cc =================================================================== --- testsuite/25_algorithms/sort_heap/complexity.cc (revision 0) +++ testsuite/25_algorithms/sort_heap/complexity.cc (working copy) @@ -0,0 +1,53 @@ +// Copyright (C) 2014 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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++11" } + +#include <cmath> +#include <random> +#include <vector> +#include <algorithm> + +#include <testsuite_counter_type.h> +#include <testsuite_hooks.h> + +void test01() +{ + using __gnu_test::counter_type; + const std::size_t nb_values = 1000; + + std::random_device dev; + std::uniform_int_distribution<int> dist; + std::vector<counter_type> values; + values.reserve(nb_values); + for (std::size_t i = 0; i != nb_values; ++i) + values.push_back(dist(dev)); + + std::make_heap(values.begin(), values.end()); + + counter_type::reset(); + + std::sort_heap(values.begin(), values.end()); + + VERIFY( counter_type::less_compare_count <= 2.0 * nb_values * std::log(nb_values) ); +} + +int main() +{ + test01(); + return 0; +} Index: testsuite/util/testsuite_counter_type.h =================================================================== --- testsuite/util/testsuite_counter_type.h (revision 215958) +++ testsuite/util/testsuite_counter_type.h (working copy) @@ -95,7 +95,10 @@ { return val == rhs.val; } bool operator<(const counter_type& rhs) const - { return val < rhs.val; } + { + ++less_compare_count; + return val < rhs.val; + } }; int counter_type::default_count = 0; ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: sort_heap complexity guarantee 2014-10-06 21:00 ` sort_heap complexity guarantee François Dumont @ 2014-10-06 21:05 ` Daniel Krügler 2014-10-07 21:11 ` François Dumont 2014-10-08 8:43 ` Jonathan Wakely 2014-10-18 8:03 ` Marc Glisse 2 siblings, 1 reply; 9+ messages in thread From: Daniel Krügler @ 2014-10-06 21:05 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches 2014-10-06 23:00 GMT+02:00 François Dumont <frs.dumont@gmail.com>: > On 05/10/2014 22:54, Marc Glisse wrote: >> >> On Sun, 5 Oct 2014, François Dumont wrote: >> >>> I took a look at PR 61217 regarding pop_heap complexity guarantee. >>> Looks like we have no test to check complexity of our algos so I start >>> writing some starting with the heap operations. I found no issue with >>> make_heap, push_heap and pop_heap despite what the bug report is saying >>> however the attached testcase for sort_heap is failing. >>> >>> Standard is saying std::sort_heap shall use less than N * log(N) >>> comparisons but with my test using 1000 random values the test is showing: >>> >>> 8687 comparisons on 6907.76 max allowed >>> >>> Is this a known issue of sort_heap ? Do you confirm that the test is >>> valid ? >> >> I would first look for confirmation that the standard didn't just forget a >> big-O or something. I would expect an implementation as n calls to pop_heap >> to be legal, and if pop_heap makes 2*log(n) comparisons, that naively sums >> to too much. And I don't expect the standard to contain an advanced >> amortized analysis or anything like that... >> > Good point, with n calls to pop_heap it means that limit must be 2*log(1) + > 2*log(2) +... + 2*log(n) which is 2*log(n!) and which is also necessarily < > 2*n*log(n). I guess Standard comittee has forgotten the factor 2 in the > limit so this is what I am using as limit in the final test, unless someone > prefer the stricter 2*log(n!) ? François, could you please submit a corresponding LWG issue by sending an email using the recipe described here: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#submit_issue ? Thanks, - Daniel ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: sort_heap complexity guarantee 2014-10-06 21:05 ` Daniel Krügler @ 2014-10-07 21:11 ` François Dumont 2014-10-07 21:13 ` Daniel Krügler 0 siblings, 1 reply; 9+ messages in thread From: François Dumont @ 2014-10-07 21:11 UTC (permalink / raw) To: Daniel Krügler; +Cc: libstdc++, gcc-patches On 06/10/2014 23:05, Daniel Krügler wrote: > 2014-10-06 23:00 GMT+02:00 François Dumont <frs.dumont@gmail.com>: >> On 05/10/2014 22:54, Marc Glisse wrote: >>> On Sun, 5 Oct 2014, François Dumont wrote: >>> >>>> I took a look at PR 61217 regarding pop_heap complexity guarantee. >>>> Looks like we have no test to check complexity of our algos so I start >>>> writing some starting with the heap operations. I found no issue with >>>> make_heap, push_heap and pop_heap despite what the bug report is saying >>>> however the attached testcase for sort_heap is failing. >>>> >>>> Standard is saying std::sort_heap shall use less than N * log(N) >>>> comparisons but with my test using 1000 random values the test is showing: >>>> >>>> 8687 comparisons on 6907.76 max allowed >>>> >>>> Is this a known issue of sort_heap ? Do you confirm that the test is >>>> valid ? >>> I would first look for confirmation that the standard didn't just forget a >>> big-O or something. I would expect an implementation as n calls to pop_heap >>> to be legal, and if pop_heap makes 2*log(n) comparisons, that naively sums >>> to too much. And I don't expect the standard to contain an advanced >>> amortized analysis or anything like that... >>> >> Good point, with n calls to pop_heap it means that limit must be 2*log(1) + >> 2*log(2) +... + 2*log(n) which is 2*log(n!) and which is also necessarily < >> 2*n*log(n). I guess Standard comittee has forgotten the factor 2 in the >> limit so this is what I am using as limit in the final test, unless someone >> prefer the stricter 2*log(n!) ? > François, could you please submit a corresponding LWG issue by sending > an email using the recipe described here: > > http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#submit_issue > > ? > I just did requesting to use 2N log(N). And is it ok to commit those ? François ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: sort_heap complexity guarantee 2014-10-07 21:11 ` François Dumont @ 2014-10-07 21:13 ` Daniel Krügler 0 siblings, 0 replies; 9+ messages in thread From: Daniel Krügler @ 2014-10-07 21:13 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches 2014-10-07 23:11 GMT+02:00 François Dumont <frs.dumont@gmail.com>: > On 06/10/2014 23:05, Daniel Krügler wrote: >> François, could you please submit a corresponding LWG issue by sending >> an email using the recipe described here: >> >> http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#submit_issue >> >> ? >> > I just did requesting to use 2N log(N). > > And is it ok to commit those ? Looks fine to me - Thanks! - Daniel ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: sort_heap complexity guarantee 2014-10-06 21:00 ` sort_heap complexity guarantee François Dumont 2014-10-06 21:05 ` Daniel Krügler @ 2014-10-08 8:43 ` Jonathan Wakely 2014-10-18 8:03 ` Marc Glisse 2 siblings, 0 replies; 9+ messages in thread From: Jonathan Wakely @ 2014-10-08 8:43 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On 06/10/14 23:00 +0200, François Dumont wrote: >Good point, with n calls to pop_heap it means that limit must be >2*log(1) + 2*log(2) +... + 2*log(n) which is 2*log(n!) and which is >also necessarily < 2*n*log(n). I guess Standard comittee has forgotten >the factor 2 in the limit so this is what I am using as limit in the >final test, unless someone prefer the stricter 2*log(n!) ? > >Ok to commit those new tests ? Yes please - thanks. ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: sort_heap complexity guarantee 2014-10-06 21:00 ` sort_heap complexity guarantee François Dumont 2014-10-06 21:05 ` Daniel Krügler 2014-10-08 8:43 ` Jonathan Wakely @ 2014-10-18 8:03 ` Marc Glisse [not found] ` <54456EEC.9000707@gmail.com> 2 siblings, 1 reply; 9+ messages in thread From: Marc Glisse @ 2014-10-18 8:03 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On Mon, 6 Oct 2014, François Dumont wrote: > * testsuite/25_algorithms/push_heap/complexity.cc: New. This test is randomly failing in about 1% to 2% of cases. -- Marc Glisse ^ permalink raw reply [flat|nested] 9+ messages in thread
[parent not found: <54456EEC.9000707@gmail.com>]
[parent not found: <alpine.DEB.2.11.1410202237520.19590@stedding.saclay.inria.fr>]
* Re: sort_heap complexity guarantee [not found] ` <alpine.DEB.2.11.1410202237520.19590@stedding.saclay.inria.fr> @ 2014-10-22 21:13 ` François Dumont 2014-10-22 23:53 ` Jonathan Wakely 2014-10-23 0:18 ` Paolo Carlini 0 siblings, 2 replies; 9+ messages in thread From: François Dumont @ 2014-10-22 21:13 UTC (permalink / raw) To: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 1135 bytes --] Then I think we need this patch which also fix other issues. 2014-10-22 François Dumont <fdumont@gcc.gnu.org> * testsuite/25_algorithms/make_heap/complexity.cc: Add missing test variable. * testsuite/25_algorithms/sort_heap/complexity.cc: Likewise and use log2. * testsuite/25_algorithms/pop_heap/complexity.cc: Likewise and require normal mode. * testsuite/25_algorithms/push_heap/complexity.cc: Likewise. Tested under Linux x86_64. Ok to commit ? François On 20/10/2014 22:48, Marc Glisse wrote: > On Mon, 20 Oct 2014, François Dumont wrote: > >> On 18/10/2014 09:24, Marc Glisse wrote: >>> On Mon, 6 Oct 2014, François Dumont wrote: >>> >>>> * testsuite/25_algorithms/push_heap/complexity.cc: New. >>> >>> This test is randomly failing in about 1% to 2% of cases. >>> >> Is it for a particular platform ? I just run it thousands of times on >> my Linux and never experimented any failure. > > x86_64-linux-gnu, debian testing > > Here is a deterministic version. > > By the way, when the standard says "log" and there isn't an implicit > O(), it usually means "log2". > [-- Attachment #2: complexity.patch --] [-- Type: text/x-patch, Size: 2827 bytes --] Index: testsuite/25_algorithms/make_heap/complexity.cc =================================================================== --- testsuite/25_algorithms/make_heap/complexity.cc (revision 216348) +++ testsuite/25_algorithms/make_heap/complexity.cc (working copy) @@ -26,6 +26,8 @@ void test01() { + bool test __attribute__((unused)) = true; + using __gnu_test::counter_type; const std::size_t nb_values = 1000; Index: testsuite/25_algorithms/pop_heap/complexity.cc =================================================================== --- testsuite/25_algorithms/pop_heap/complexity.cc (revision 216348) +++ testsuite/25_algorithms/pop_heap/complexity.cc (working copy) @@ -15,6 +15,7 @@ // with this library; see the file COPYING3. If not see // <http://www.gnu.org/licenses/>. +// { dg-require-normal-mode "" } // { dg-options "-std=gnu++11" } #include <cmath> @@ -27,6 +28,8 @@ void test01() { + bool test __attribute__((unused)) = true; + using __gnu_test::counter_type; const std::size_t nb_values = 1000; @@ -43,7 +46,7 @@ std::pop_heap(values.begin(), values.end()); - VERIFY( counter_type::less_compare_count <= 2.0 * std::log(nb_values) ); + VERIFY( counter_type::less_compare_count <= 2.0 * std::log2(nb_values) ); } int main() Index: testsuite/25_algorithms/push_heap/complexity.cc =================================================================== --- testsuite/25_algorithms/push_heap/complexity.cc (revision 216348) +++ testsuite/25_algorithms/push_heap/complexity.cc (working copy) @@ -15,6 +15,7 @@ // with this library; see the file COPYING3. If not see // <http://www.gnu.org/licenses/>. +// { dg-require-normal-mode "" } // { dg-options "-std=gnu++11" } #include <cmath> @@ -27,6 +28,8 @@ void test01() { + bool test __attribute__((unused)) = true; + using __gnu_test::counter_type; const std::size_t nb_values = 1000; @@ -44,7 +47,7 @@ std::push_heap(values.begin(), values.end()); - VERIFY( counter_type::less_compare_count <= std::log(values.size()) ); + VERIFY( counter_type::less_compare_count <= std::log2(values.size()) ); } int main() Index: testsuite/25_algorithms/sort_heap/complexity.cc =================================================================== --- testsuite/25_algorithms/sort_heap/complexity.cc (revision 216348) +++ testsuite/25_algorithms/sort_heap/complexity.cc (working copy) @@ -27,6 +27,8 @@ void test01() { + bool test __attribute__((unused)) = true; + using __gnu_test::counter_type; const std::size_t nb_values = 1000; @@ -43,7 +45,7 @@ std::sort_heap(values.begin(), values.end()); - VERIFY( counter_type::less_compare_count <= 2.0 * nb_values * std::log(nb_values) ); + VERIFY( counter_type::less_compare_count <= 2.0 * nb_values * std::log2(nb_values) ); } int main() ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: sort_heap complexity guarantee 2014-10-22 21:13 ` François Dumont @ 2014-10-22 23:53 ` Jonathan Wakely 2014-10-23 0:18 ` Paolo Carlini 1 sibling, 0 replies; 9+ messages in thread From: Jonathan Wakely @ 2014-10-22 23:53 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On 22/10/14 23:05 +0200, François Dumont wrote: >Then I think we need this patch which also fix other issues. > >2014-10-22 François Dumont <fdumont@gcc.gnu.org> > > * testsuite/25_algorithms/make_heap/complexity.cc: Add missing test > variable. > * testsuite/25_algorithms/sort_heap/complexity.cc: Likewise and use > log2. > * testsuite/25_algorithms/pop_heap/complexity.cc: Likewise and require > normal mode. > * testsuite/25_algorithms/push_heap/complexity.cc: Likewise. > >Tested under Linux x86_64. > >Ok to commit ? Yes, looks good - thanks. ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: sort_heap complexity guarantee 2014-10-22 21:13 ` François Dumont 2014-10-22 23:53 ` Jonathan Wakely @ 2014-10-23 0:18 ` Paolo Carlini 1 sibling, 0 replies; 9+ messages in thread From: Paolo Carlini @ 2014-10-23 0:18 UTC (permalink / raw) To: François Dumont, libstdc++, gcc-patches Hi, On 10/22/2014 11:05 PM, François Dumont wrote: > + VERIFY( counter_type::less_compare_count <= 2.0 * std::log2(nb_values) ); Nit: log2 isn't in C89, thus we shouldn't use it unconditionally, ie, if the test isn't guarded by { dg-require-cmath "" }. Thus, either the latter, or just express log_2 in terms of log / log10. Paolo. ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2014-10-22 23:53 UTC | newest] Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- [not found] <5431A354.2050404@gmail.com> [not found] ` <alpine.DEB.2.11.1410052245150.5366@stedding.saclay.inria.fr> 2014-10-06 21:00 ` sort_heap complexity guarantee François Dumont 2014-10-06 21:05 ` Daniel Krügler 2014-10-07 21:11 ` François Dumont 2014-10-07 21:13 ` Daniel Krügler 2014-10-08 8:43 ` Jonathan Wakely 2014-10-18 8:03 ` Marc Glisse [not found] ` <54456EEC.9000707@gmail.com> [not found] ` <alpine.DEB.2.11.1410202237520.19590@stedding.saclay.inria.fr> 2014-10-22 21:13 ` François Dumont 2014-10-22 23:53 ` Jonathan Wakely 2014-10-23 0:18 ` Paolo Carlini
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).