Add Pippenger cache and limit Straus cache size

2 files changed, 135 insertions, 9 deletions

diff --git a/tests/performance_tests/main.cpp b/tests/performance_tests/main.cpp
index de9f0e647..142e544dd 100644
--- a/tests/performance_tests/main.cpp
+++ b/tests/performance_tests/main.cpp
@@ -281,16 +281,137 @@ int main(int argc, char** argv)
   TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 2, 1);
   TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 4, 2);
   TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 8, 2);
-  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 16, 4);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 16, 3);
   TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 32, 4);
-  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 64, 5);
-  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 128, 6);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 64, 4);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 128, 5);
   TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 256, 6);
-  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 512, 6);
-  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 1024, 8);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 512, 7);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 1024, 7);
   TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 2048, 8);
   TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 4096, 9);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2, 1);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4, 2);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 8, 2);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 16, 3);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 32, 4);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 64, 4);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 128, 5);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 256, 6);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 512, 7);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 1024, 7);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2048, 8);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4096, 9);
 #else
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2, 1);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2, 2);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2, 3);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2, 4);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2, 5);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2, 6);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2, 7);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2, 8);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2, 9);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4, 1);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4, 2);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4, 3);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4, 4);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4, 5);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4, 6);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4, 7);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4, 8);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4, 9);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 8, 1);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 8, 2);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 8, 3);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 8, 4);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 8, 5);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 8, 6);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 8, 7);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 8, 8);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 8, 9);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 16, 1);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 16, 2);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 16, 3);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 16, 4);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 16, 5);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 16, 6);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 16, 7);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 16, 8);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 16, 9);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 32, 1);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 32, 2);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 32, 3);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 32, 4);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 32, 5);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 32, 6);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 32, 7);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 32, 8);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 32, 9);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 64, 1);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 64, 2);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 64, 3);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 64, 4);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 64, 5);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 64, 6);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 64, 7);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 64, 8);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 64, 9);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 128, 1);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 128, 2);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 128, 3);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 128, 4);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 128, 5);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 128, 6);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 128, 7);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 128, 8);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 128, 9);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 256, 1);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 256, 2);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 256, 3);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 256, 4);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 256, 5);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 256, 6);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 256, 7);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 256, 8);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 256, 9);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 512, 1);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 512, 2);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 512, 3);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 512, 4);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 512, 5);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 512, 6);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 512, 7);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 512, 8);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 512, 9);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 1024, 1);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 1024, 2);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 1024, 3);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 1024, 4);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 1024, 5);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 1024, 6);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 1024, 7);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 1024, 8);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 1024, 9);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2048, 1);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2048, 2);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2048, 3);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2048, 4);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2048, 5);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2048, 6);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2048, 7);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2048, 8);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 2048, 9);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4096, 1);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4096, 2);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4096, 3);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4096, 4);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4096, 5);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4096, 6);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4096, 7);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4096, 8);
+  TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger_cached, 4096, 9);
+
   TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 2, 1);
   TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 2, 2);
   TEST_PERFORMANCE3(filter, p, test_multiexp, multiexp_pippenger, 2, 3);
diff --git a/tests/performance_tests/multiexp.h b/tests/performance_tests/multiexp.h
index 294e74116..b8b87b3a6 100644
--- a/tests/performance_tests/multiexp.h
+++ b/tests/performance_tests/multiexp.h
@@ -40,6 +40,7 @@ enum test_multiexp_algorithm
   multiexp_straus,
   multiexp_straus_cached,
   multiexp_pippenger,
+  multiexp_pippenger_cached,
 };
 
 template<test_multiexp_algorithm algorithm, size_t npoints, size_t c=0>
@@ -61,7 +62,8 @@ public:
       rct::key kn = rct::scalarmultKey(point, data[n].scalar);
       res = rct::addKeys(res, kn);
     }
-    cache = rct::straus_init_cache(data);
+    straus_cache = rct::straus_init_cache(data);
+    pippenger_cache = rct::pippenger_init_cache(data);
     return true;
   }
 
@@ -74,9 +76,11 @@ public:
       case multiexp_straus:
         return res == straus(data);
       case multiexp_straus_cached:
-        return res == straus(data, cache);
+        return res == straus(data, straus_cache);
       case multiexp_pippenger:
-        return res == pippenger(data, c);
+        return res == pippenger(data, NULL, c);
+      case multiexp_pippenger_cached:
+        return res == pippenger(data, pippenger_cache, c);
       default:
         return false;
     }
@@ -84,6 +88,7 @@ public:
 
 private:
   std::vector<rct::MultiexpData> data;
-  std::shared_ptr<rct::straus_cached_data> cache;
+  std::shared_ptr<rct::straus_cached_data> straus_cache;
+  std::shared_ptr<rct::pippenger_cached_data> pippenger_cache;
   rct::key res;
 };