diff options
| -rw-r--r-- | src/ringct/multiexp.cc | 88 | ||||
| -rw-r--r-- | src/ringct/multiexp.h | 12 |
2 files changed, 55 insertions, 45 deletions
diff --git a/src/ringct/multiexp.cc b/src/ringct/multiexp.cc index 67814682a..46950b883 100644 --- a/src/ringct/multiexp.cc +++ b/src/ringct/multiexp.cc @@ -57,28 +57,28 @@ extern "C" // 1 1 52.8 70.4 70.2 // Pippenger: -// 1 2 3 4 5 6 7 8 9 bestN -// 2 555 598 621 804 1038 1733 2486 5020 8304 1 -// 4 783 747 800 1006 1428 2132 3285 5185 9806 2 -// 8 1174 1071 1095 1286 1640 2398 3869 6378 12080 2 -// 16 2279 1874 1745 1739 2144 2831 4209 6964 12007 4 -// 32 3910 3706 2588 2477 2782 3467 4856 7489 12618 4 -// 64 7184 5429 4710 4368 4010 4672 6027 8559 13684 5 -// 128 14097 10574 8452 7297 6841 6718 8615 10580 15641 6 -// 256 27715 20800 16000 13550 11875 11400 11505 14090 18460 6 -// 512 55100 41250 31740 26570 22030 19830 20760 21380 25215 6 -// 1024 111520 79000 61080 49720 43080 38320 37600 35040 36750 8 -// 2048 219480 162680 122120 102080 83760 70360 66600 63920 66160 8 -// 4096 453320 323080 247240 210200 180040 150240 132440 114920 110560 9 - -// 2 4 8 16 32 64 128 256 512 1024 2048 4096 -// Bos Coster 858 994 1316 1949 3183 5512 9865 17830 33485 63160 124280 246320 -// Straus 226 341 548 980 1870 3538 7039 14490 29020 57200 118640 233640 -// Straus/cached 226 315 485 785 1514 2858 5753 11065 22970 45120 98880 194840 -// Pippenger 555 747 1071 1739 2477 4010 6718 11400 19830 35040 63920 110560 - -// Best/cached Straus Straus Straus Straus Straus Straus Straus Straus Pip Pip Pip Pip -// Best/uncached Straus Straus Straus Straus Straus Straus Pip Pip Pip Pip Pip Pip +// 1 2 3 4 5 6 7 8 9 bestN +// 2 555 598 621 804 1038 1733 2486 5020 8304 1 +// 4 783 747 800 1006 1428 2132 3285 5185 9806 2 +// 8 1174 1071 1095 1286 1640 2398 3869 6378 12080 2 +// 16 2279 1874 1745 1739 2144 2831 4209 6964 12007 4 +// 32 3910 3706 2588 2477 2782 3467 4856 7489 12618 4 +// 64 7184 5429 4710 4368 4010 4672 6027 8559 13684 5 +// 128 14097 10574 8452 7297 6841 6718 8615 10580 15641 6 +// 256 27715 20800 16000 13550 11875 11400 11505 14090 18460 6 +// 512 55100 41250 31740 26570 22030 19830 20760 21380 25215 6 +// 1024 111520 79000 61080 49720 43080 38320 37600 35040 36750 8 +// 2048 219480 162680 122120 102080 83760 70360 66600 63920 66160 8 +// 4096 453320 323080 247240 210200 180040 150240 132440 114920 110560 9 + +// 2 4 8 16 32 64 128 256 512 1024 2048 4096 +// Bos Coster 858 994 1316 1949 3183 5512 9865 17830 33485 63160 124280 246320 +// Straus 226 341 548 980 1870 3538 7039 14490 29020 57200 118640 233640 +// Straus/cached 226 315 485 785 1514 2858 5753 11065 22970 45120 98880 194840 +// Pippenger 555 747 1071 1739 2477 4010 6718 11400 19830 35040 63920 110560 + +// Best/cached Straus Straus Straus Straus Straus Straus Straus Straus Pip Pip Pip Pip +// Best/uncached Straus Straus Straus Straus Straus Straus Pip Pip Pip Pip Pip Pip // New timings: // Pippenger: @@ -443,7 +443,7 @@ size_t straus_get_cache_size(const std::shared_ptr<straus_cached_data> &cache) return sz; } -rct::key straus(const std::vector<MultiexpData> &data, const std::shared_ptr<straus_cached_data> &cache, size_t STEP) +ge_p3 straus_p3(const std::vector<MultiexpData> &data, const std::shared_ptr<straus_cached_data> &cache, size_t STEP) { CHECK_AND_ASSERT_THROW_MES(cache == NULL || cache->size >= data.size(), "Cache is too small"); MULTIEXP_PERF(PERF_TIMER_UNIT(straus, 1000000)); @@ -554,7 +554,13 @@ skipfirst: ge_p1p1_to_p3(&res_p3, &p1); } + return res_p3; +} + +rct::key straus(const std::vector<MultiexpData> &data, const std::shared_ptr<straus_cached_data> &cache, size_t STEP) +{ rct::key res; + const ge_p3 res_p3 = straus_p3(data, cache, STEP); ge_p3_tobytes(res.bytes, &res_p3); return res; } @@ -571,14 +577,6 @@ size_t get_pippenger_c(size_t N) return 9; } -struct pippenger_cached_data -{ - size_t size; - ge_cached *cached; - pippenger_cached_data(): size(0), cached(NULL) {} - ~pippenger_cached_data() { aligned_free(cached); } -}; - std::shared_ptr<pippenger_cached_data> pippenger_init_cache(const std::vector<MultiexpData> &data, size_t start_offset, size_t N) { MULTIEXP_PERF(PERF_TIMER_START_UNIT(pippenger_init_cache, 1000000)); @@ -586,13 +584,11 @@ std::shared_ptr<pippenger_cached_data> pippenger_init_cache(const std::vector<Mu if (N == 0) N = data.size() - start_offset; CHECK_AND_ASSERT_THROW_MES(N <= data.size() - start_offset, "Bad cache base data"); - std::shared_ptr<pippenger_cached_data> cache(new pippenger_cached_data()); + std::shared_ptr<pippenger_cached_data> cache = std::make_shared<pippenger_cached_data>(); - cache->size = N; - cache->cached = (ge_cached*)aligned_realloc(cache->cached, N * sizeof(ge_cached), 4096); - CHECK_AND_ASSERT_THROW_MES(cache->cached, "Out of memory"); + cache->resize(N); for (size_t i = 0; i < N; ++i) - ge_p3_to_cached(&cache->cached[i], &data[i+start_offset].point); + ge_p3_to_cached(&(*cache)[i], &data[i+start_offset].point); MULTIEXP_PERF(PERF_TIMER_STOP(pippenger_init_cache)); return cache; @@ -600,14 +596,14 @@ std::shared_ptr<pippenger_cached_data> pippenger_init_cache(const std::vector<Mu size_t pippenger_get_cache_size(const std::shared_ptr<pippenger_cached_data> &cache) { - return cache->size * sizeof(*cache->cached); + return cache->size() * sizeof(ge_cached); } -rct::key pippenger(const std::vector<MultiexpData> &data, const std::shared_ptr<pippenger_cached_data> &cache, size_t cache_size, size_t c) +ge_p3 pippenger_p3(const std::vector<MultiexpData> &data, const std::shared_ptr<pippenger_cached_data> &cache, size_t cache_size, size_t c) { if (cache != NULL && cache_size == 0) - cache_size = cache->size; - CHECK_AND_ASSERT_THROW_MES(cache == NULL || cache_size <= cache->size, "Cache is too small"); + cache_size = cache->size(); + CHECK_AND_ASSERT_THROW_MES(cache == NULL || cache_size <= cache->size(), "Cache is too small"); if (c == 0) c = get_pippenger_c(data.size()); CHECK_AND_ASSERT_THROW_MES(c <= 9, "c is too large"); @@ -661,9 +657,9 @@ rct::key pippenger(const std::vector<MultiexpData> &data, const std::shared_ptr< if (buckets_init[bucket]) { if (i < cache_size) - add(buckets[bucket], local_cache->cached[i]); + add(buckets[bucket], (*local_cache)[i]); else - add(buckets[bucket], local_cache_2->cached[i - cache_size]); + add(buckets[bucket], (*local_cache_2)[i - cache_size]); } else { @@ -700,8 +696,14 @@ rct::key pippenger(const std::vector<MultiexpData> &data, const std::shared_ptr< } } + return result; +} + +rct::key pippenger(const std::vector<MultiexpData> &data, const std::shared_ptr<pippenger_cached_data> &cache, const size_t cache_size, const size_t c) +{ rct::key res; - ge_p3_tobytes(res.bytes, &result); + const ge_p3 result_p3 = pippenger_p3(data, cache, cache_size, c); + ge_p3_tobytes(res.bytes, &result_p3); return res; } diff --git a/src/ringct/multiexp.h b/src/ringct/multiexp.h index 788516c0b..d9a240637 100644 --- a/src/ringct/multiexp.h +++ b/src/ringct/multiexp.h @@ -35,10 +35,16 @@ #define MULTIEXP_H #include <vector> +extern "C" +{ +#include "crypto/crypto-ops.h" +} #include "crypto/crypto.h" #include "rctTypes.h" #include "misc_log_ex.h" +#include <boost/align/aligned_allocator.hpp> + namespace rct { @@ -55,17 +61,19 @@ struct MultiexpData { }; struct straus_cached_data; -struct pippenger_cached_data; +using pippenger_cached_data = std::vector<ge_cached, boost::alignment::aligned_allocator<ge_cached, 4096>>; rct::key bos_coster_heap_conv(std::vector<MultiexpData> data); rct::key bos_coster_heap_conv_robust(std::vector<MultiexpData> data); std::shared_ptr<straus_cached_data> straus_init_cache(const std::vector<MultiexpData> &data, size_t N =0); size_t straus_get_cache_size(const std::shared_ptr<straus_cached_data> &cache); +ge_p3 straus_p3(const std::vector<MultiexpData> &data, const std::shared_ptr<straus_cached_data> &cache = NULL, size_t STEP = 0); rct::key straus(const std::vector<MultiexpData> &data, const std::shared_ptr<straus_cached_data> &cache = NULL, size_t STEP = 0); std::shared_ptr<pippenger_cached_data> pippenger_init_cache(const std::vector<MultiexpData> &data, size_t start_offset = 0, size_t N =0); size_t pippenger_get_cache_size(const std::shared_ptr<pippenger_cached_data> &cache); size_t get_pippenger_c(size_t N); -rct::key pippenger(const std::vector<MultiexpData> &data, const std::shared_ptr<pippenger_cached_data> &cache = NULL, size_t cache_size = 0, size_t c = 0); +ge_p3 pippenger_p3(const std::vector<MultiexpData> &data, const std::shared_ptr<pippenger_cached_data> &cache = NULL, size_t cache_size = 0, size_t c = 0); +rct::key pippenger(const std::vector<MultiexpData> &data, const std::shared_ptr<pippenger_cached_data> &cache = NULL, const size_t cache_size = 0, const size_t c = 0); } |