[lmi-commits] [lmi] master 7473332: Efficiently determine whether a vector<double> is all boolean-valued

[Greg Chicares]

branch: master
commit 747333211e5cadceb9c3d417930081d240228472
Author: Gregory W. Chicares <gchicares@sbcglobal.net>
Commit: Gregory W. Chicares <gchicares@sbcglobal.net>

    Efficiently determine whether a vector<double> is all boolean-valued
    
    For x86_64-pc-linux-gnu gcc-10.2, PETE is fastest:
      mete_eq0a 2.024e-07 s mean;          0 us least of 49399 runs
      mete_eq0b 2.014e-07 s mean;          0 us least of 49661 runs
      mete_eq0c 1.745e-07 s mean;          0 us least of 57313 runs
      mete_eq1a 1.408e-07 s mean;          0 us least of 71035 runs
      mete_eq1b 1.423e-07 s mean;          0 us least of 70268 runs
      mete_eq1c 2.118e-07 s mean;          0 us least of 47224 runs
      mete_eq1x 2.038e-07 s mean;          0 us least of 49067 runs
    while for i686-w64-mingw32 gcc-8.3, all take about the same time.
    
    The crucial conclusion is that writing code as close as possible to
    C++ extended with an APL declaration like the standard asm-declaration:
      APL {"∧/X∨.=0 1"};   // More idiomatic. (APL '=' means C '=='.)
      APL {"∧/(X=1)∨X=0"}; // Doesn't require constructing vector{0, 1}.
    by using PETE
      ∧/   (X=1)                      ∨  X=0
      AllOf(EqualTo(true, bit_valued) || EqualTo(false, bit_valued));
    incurs no speed penalty in the particular case studied (determining
    whether a 100-element vector<double> is all boolean-valued).
    
    It's curious that
      ∧/(X=1)∨(X=0)  ⍝ all are either =1 or =0
    is faster than
      ~∨/(X≠1)∧(X≠0) ⍝ none is both   ≠1 and ≠0
    and perhaps less surprising that
      ∧/X=~~X        ⍝ each equals its boolean NOT(NOT)
    is not the fastest.
---
 et_vector_test.cpp | 97 +++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 92 insertions(+), 5 deletions(-)

diff --git a/et_vector_test.cpp b/et_vector_test.cpp
index e3f34e4..181c288 100644
--- a/et_vector_test.cpp
+++ b/et_vector_test.cpp
@@ -23,9 +23,94 @@
 
 #include "ssize_lmi.hpp"
 #include "test_tools.hpp"
+#include "timer.hpp"
 
 #include <functional>                   // multiplies(), negate(), plus()
 
+// A vector of boolean values, represented as double, such as
+// might result from querying lmi's database.
+static std::vector<double> const bit_valued =
+    {0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0
+    ,1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0
+    ,0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0
+    ,1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0
+    ,0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0
+    ,1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0
+    ,0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0
+    ,1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0
+    ,0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0
+    ,1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0
+    };
+
+bool mete_eq0a()
+{
+    for(auto const& i : bit_valued)
+        {
+        if(false != i && true != i)
+            return false;
+        }
+    return true;
+}
+
+bool mete_eq0b()
+{
+    for(auto const& i : bit_valued)
+        {
+        if(0.0 != i && 1.0 != i)
+            return false;
+        }
+    return true;
+}
+
+bool mete_eq0c()
+{
+    for(auto const& i : bit_valued)
+        {
+        if(i != !!i)
+            return false;
+        }
+    return true;
+}
+
+bool mete_eq1a()
+{
+    return AllOf(EqualTo(true, bit_valued) || EqualTo(false, bit_valued));
+}
+
+bool mete_eq1b()
+{
+    return AllOf(EqualTo(1.0, bit_valued) || EqualTo(0.0, bit_valued));
+}
+
+bool mete_eq1c()
+{
+    return AllOf(EqualTo(bit_valued, !!bit_valued));
+}
+
+bool mete_eq1x()
+{
+    return !AnyOf(UnequalTo(true, bit_valued) && UnequalTo(false, bit_valued));
+}
+
+void assay_speed()
+{
+    LMI_TEST_EQUAL(true, mete_eq0a());
+    LMI_TEST_EQUAL(true, mete_eq0b());
+    LMI_TEST_EQUAL(true, mete_eq0c());
+    LMI_TEST_EQUAL(true, mete_eq1a());
+    LMI_TEST_EQUAL(true, mete_eq1b());
+    LMI_TEST_EQUAL(true, mete_eq1c());
+    LMI_TEST_EQUAL(true, mete_eq1x());
+    std::cout << "Speed tests:\n";
+    std::cout << "  mete_eq0a " << TimeAnAliquot(mete_eq0a) << '\n';
+    std::cout << "  mete_eq0b " << TimeAnAliquot(mete_eq0b) << '\n';
+    std::cout << "  mete_eq0c " << TimeAnAliquot(mete_eq0c) << '\n';
+    std::cout << "  mete_eq1a " << TimeAnAliquot(mete_eq1a) << '\n';
+    std::cout << "  mete_eq1b " << TimeAnAliquot(mete_eq1b) << '\n';
+    std::cout << "  mete_eq1c " << TimeAnAliquot(mete_eq1c) << '\n';
+    std::cout << "  mete_eq1x " << TimeAnAliquot(mete_eq1x) << '\n';
+}
+
 int test_main(int, char*[])
 {
     {
@@ -210,12 +295,14 @@ int test_main(int, char*[])
     // using NOT NOT to turn values into booleans, but, using PETE
     // with std::vector, "!!V" returns a vector<bool>; ET !! perhaps
     // boolean operators should therefore be amended to return 'int'.
-    LMI_TEST_EQUAL(true , AllOf(EqualTo(true, v0) ||  EqualTo(false, v0)));
-    LMI_TEST_EQUAL(true , AllOf(EqualTo(true, v1) ||  EqualTo(false, v1)));
-    LMI_TEST_EQUAL(true , AllOf(EqualTo(true, v2) ||  EqualTo(false, v2)));
-    LMI_TEST_EQUAL(false, AllOf(EqualTo(true, v3) ||  EqualTo(false, v3)));
-    LMI_TEST_EQUAL(false, AllOf(EqualTo(true, v4) ||  EqualTo(false, v4)));
+    LMI_TEST_EQUAL(true , AllOf(EqualTo(true, v0) || EqualTo(false, v0)));
+    LMI_TEST_EQUAL(true , AllOf(EqualTo(true, v1) || EqualTo(false, v1)));
+    LMI_TEST_EQUAL(true , AllOf(EqualTo(true, v2) || EqualTo(false, v2)));
+    LMI_TEST_EQUAL(false, AllOf(EqualTo(true, v3) || EqualTo(false, v3)));
+    LMI_TEST_EQUAL(false, AllOf(EqualTo(true, v4) || EqualTo(false, v4)));
     }
 
+    assay_speed();
+
     return 0;
 }