This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: sort_heap complexity guarantee


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".


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

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]