diff mbox

sort_heap complexity guarantee

Message ID 54481C33.3070400@gmail.com
State New
Headers show

Commit Message

François Dumont Oct. 22, 2014, 9:05 p.m. UTC 
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".
>

Comments

Jonathan Wakely Oct. 22, 2014, 11:04 p.m. UTC | #1 
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.
Paolo Carlini Oct. 22, 2014, 11:53 p.m. UTC | #2 
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.
diff mbox

Patch

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()