diff options
author | moneromooo-monero <moneromooo-monero@users.noreply.github.com> | 2018-05-29 12:39:00 +0100 |
---|---|---|
committer | moneromooo-monero <moneromooo-monero@users.noreply.github.com> | 2018-09-11 13:38:02 +0000 |
commit | 0b05a0fa74512970ceba3c15ed2cbf027ef7b6da (patch) | |
tree | 8d124229d8b6df177a1e5d37e18681803a221c45 /src | |
parent | add pippenger unit tests (diff) | |
download | monero-0b05a0fa74512970ceba3c15ed2cbf027ef7b6da.tar.xz |
Add Pippenger cache and limit Straus cache size
Diffstat (limited to 'src')
-rw-r--r-- | src/ringct/bulletproofs.cc | 29 | ||||
-rw-r--r-- | src/ringct/multiexp.cc | 76 | ||||
-rw-r--r-- | src/ringct/multiexp.h | 7 |
3 files changed, 82 insertions, 30 deletions
diff --git a/src/ringct/bulletproofs.cc b/src/ringct/bulletproofs.cc index 83005eaa4..4eb6d6d5b 100644 --- a/src/ringct/bulletproofs.cc +++ b/src/ringct/bulletproofs.cc @@ -49,6 +49,9 @@ extern "C" #define PERF_TIMER_START_BP(x) PERF_TIMER_START_UNIT(x, 1000000) +#define STRAUS_SIZE_LIMIT 128 +#define PIPPENGER_SIZE_LIMIT 0 + namespace rct { @@ -61,8 +64,8 @@ static constexpr size_t maxN = 64; static constexpr size_t maxM = BULLETPROOF_MAX_OUTPUTS; static rct::key Hi[maxN*maxM], Gi[maxN*maxM]; static ge_p3 Hi_p3[maxN*maxM], Gi_p3[maxN*maxM]; -static ge_dsmp Gprecomp[maxN*maxM], Hprecomp[maxN*maxM]; -static std::shared_ptr<straus_cached_data> HiGi_cache; +static std::shared_ptr<straus_cached_data> straus_HiGi_cache; +static std::shared_ptr<pippenger_cached_data> pippenger_HiGi_cache; static const rct::key TWO = { {0x02, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 } }; static const rct::keyV oneN = vector_dup(rct::identity(), maxN); static const rct::keyV twoN = vector_powers(TWO, maxN); @@ -73,9 +76,12 @@ static inline rct::key multiexp(const std::vector<MultiexpData> &data, bool HiGi { static const size_t STEP = getenv("STRAUS_STEP") ? atoi(getenv("STRAUS_STEP")) : 0; if (HiGi) - return data.size() <= 256 ? straus(data, HiGi_cache, STEP) : pippenger(data, get_pippenger_c(data.size())); + { + static_assert(128 <= STRAUS_SIZE_LIMIT, "Straus in precalc mode can only be calculated till STRAUS_SIZE_LIMIT"); + return data.size() <= 128 ? straus(data, straus_HiGi_cache, STEP) : pippenger(data, pippenger_HiGi_cache, get_pippenger_c(data.size())); + } else - return data.size() <= 64 ? straus(data, NULL, STEP) : pippenger(data, get_pippenger_c(data.size())); + return data.size() <= 64 ? straus(data, NULL, STEP) : pippenger(data, NULL, get_pippenger_c(data.size())); } //addKeys3acc_p3 @@ -123,18 +129,23 @@ static void init_exponents() for (size_t i = 0; i < maxN*maxM; ++i) { Hi[i] = get_exponent(rct::H, i * 2); - rct::precomp(Hprecomp[i], Hi[i]); CHECK_AND_ASSERT_THROW_MES(ge_frombytes_vartime(&Hi_p3[i], Hi[i].bytes) == 0, "ge_frombytes_vartime failed"); Gi[i] = get_exponent(rct::H, i * 2 + 1); - rct::precomp(Gprecomp[i], Gi[i]); CHECK_AND_ASSERT_THROW_MES(ge_frombytes_vartime(&Gi_p3[i], Gi[i].bytes) == 0, "ge_frombytes_vartime failed"); data.push_back({rct::zero(), Gi[i]}); data.push_back({rct::zero(), Hi[i]}); } - HiGi_cache = straus_init_cache(data); - size_t cache_size = (sizeof(Hi)+sizeof(Hprecomp)+sizeof(Hi_p3))*2 + straus_get_cache_size(HiGi_cache); - MINFO("cache size: " << cache_size/1024 << " kB"); + + straus_HiGi_cache = straus_init_cache(data, STRAUS_SIZE_LIMIT); + pippenger_HiGi_cache = pippenger_init_cache(data, PIPPENGER_SIZE_LIMIT); + + MINFO("Hi/Gi cache size: " << (sizeof(Hi)+sizeof(Gi))/1024 << " kB"); + MINFO("Hi_p3/Gi_p3 cache size: " << (sizeof(Hi_p3)+sizeof(Gi_p3))/1024 << " kB"); + MINFO("Straus cache size: " << straus_get_cache_size(straus_HiGi_cache)/1024 << " kB"); + MINFO("Pippenger cache size: " << pippenger_get_cache_size(pippenger_HiGi_cache)/1024 << " kB"); + size_t cache_size = (sizeof(Hi)+sizeof(Hi_p3))*2 + straus_get_cache_size(straus_HiGi_cache) + pippenger_get_cache_size(pippenger_HiGi_cache); + MINFO("Total cache size: " << cache_size/1024 << "kB"); init_done = true; } diff --git a/src/ringct/multiexp.cc b/src/ringct/multiexp.cc index fd2d1cbd7..f9ef9e422 100644 --- a/src/ringct/multiexp.cc +++ b/src/ringct/multiexp.cc @@ -343,9 +343,12 @@ struct straus_cached_data #endif #endif -std::shared_ptr<straus_cached_data> straus_init_cache(const std::vector<MultiexpData> &data) +std::shared_ptr<straus_cached_data> straus_init_cache(const std::vector<MultiexpData> &data, size_t N) { MULTIEXP_PERF(PERF_TIMER_START_UNIT(multiples, 1000000)); + if (N == 0) + N = data.size(); + CHECK_AND_ASSERT_THROW_MES(N <= data.size(), "Bad cache base data"); ge_cached cached; ge_p1p1 p1; ge_p3 p3; @@ -353,9 +356,10 @@ std::shared_ptr<straus_cached_data> straus_init_cache(const std::vector<Multiexp #ifdef RAW_MEMORY_BLOCK const size_t offset = cache->size; - cache->multiples = (ge_cached*)aligned_realloc(cache->multiples, sizeof(ge_cached) * ((1<<STRAUS_C)-1) * std::max(offset, data.size()), 4096); - cache->size = data.size(); - for (size_t j=offset;j<data.size();++j) + cache->multiples = (ge_cached*)aligned_realloc(cache->multiples, sizeof(ge_cached) * ((1<<STRAUS_C)-1) * std::max(offset, N), 4096); + CHECK_AND_ASSERT_THROW_MES(cache->multiples, "Out of memory"); + cache->size = N; + for (size_t j=offset;j<N;++j) { ge_p3_to_cached(&CACHE_OFFSET(cache, j, 1), &data[j].point); for (size_t i=2;i<1<<STRAUS_C;++i) @@ -368,8 +372,8 @@ std::shared_ptr<straus_cached_data> straus_init_cache(const std::vector<Multiexp #else #ifdef ALTERNATE_LAYOUT const size_t offset = cache->multiples.size(); - cache->multiples.resize(std::max(offset, data.size())); - for (size_t i = offset; i < data.size(); ++i) + cache->multiples.resize(std::max(offset, N)); + for (size_t i = offset; i < N; ++i) { cache->multiples[i].resize((1<<STRAUS_C)-1); ge_p3_to_cached(&cache->multiples[i][0], &data[i].point); @@ -383,12 +387,12 @@ std::shared_ptr<straus_cached_data> straus_init_cache(const std::vector<Multiexp #else cache->multiples.resize(1<<STRAUS_C); size_t offset = cache->multiples[1].size(); - cache->multiples[1].resize(std::max(offset, data.size())); - for (size_t i = offset; i < data.size(); ++i) + cache->multiples[1].resize(std::max(offset, N)); + for (size_t i = offset; i < N; ++i) ge_p3_to_cached(&cache->multiples[1][i], &data[i].point); for (size_t i=2;i<1<<STRAUS_C;++i) - cache->multiples[i].resize(std::max(offset, data.size())); - for (size_t j=offset;j<data.size();++j) + cache->multiples[i].resize(std::max(offset, N)); + for (size_t j=offset;j<N;++j) { for (size_t i=2;i<1<<STRAUS_C;++i) { @@ -418,6 +422,7 @@ size_t straus_get_cache_size(const std::shared_ptr<straus_cached_data> &cache) rct::key straus(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)); bool HiGi = cache != NULL; STEP = STEP ? STEP : 192; @@ -533,7 +538,8 @@ skipfirst: size_t get_pippenger_c(size_t N) { -// 2:1, 4:2, 8:2, 16:3, 32:4, 64:4, 128:5, 256:6, 512:7, 1024:7, 2048:8, 4096:9 +// uncached: 2:1, 4:2, 8:2, 16:3, 32:4, 64:4, 128:5, 256:6, 512:7, 1024:7, 2048:8, 4096:9 +// cached: 2:1, 4:2, 8:2, 16:3, 32:4, 64:4, 128:5, 256:6, 512:7, 1024:7, 2048:8, 4096:9 if (N <= 2) return 1; if (N <= 8) return 2; if (N <= 16) return 3; @@ -545,23 +551,55 @@ size_t get_pippenger_c(size_t N) return 9; } -rct::key pippenger(const std::vector<MultiexpData> &data, size_t c) +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 N) +{ + MULTIEXP_PERF(PERF_TIMER_START_UNIT(pippenger_init_cache, 1000000)); + if (N == 0) + N = data.size(); + CHECK_AND_ASSERT_THROW_MES(N <= data.size(), "Bad cache base data"); + ge_cached cached; + std::shared_ptr<pippenger_cached_data> cache(new 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"); + for (size_t i = 0; i < N; ++i) + ge_p3_to_cached(&cache->cached[i], &data[i].point); + + MULTIEXP_PERF(PERF_TIMER_STOP(pippenger_init_cache)); + return cache; +} + +size_t pippenger_get_cache_size(const std::shared_ptr<pippenger_cached_data> &cache) +{ + return cache->size * sizeof(*cache->cached); +} + +rct::key pippenger(const std::vector<MultiexpData> &data, const std::shared_ptr<pippenger_cached_data> &cache, size_t c) +{ + CHECK_AND_ASSERT_THROW_MES(cache == NULL || cache->size >= data.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"); ge_p3 result = ge_p3_identity; std::unique_ptr<ge_p3[]> buckets{new ge_p3[1<<c]}; - std::unique_ptr<ge_cached[]> cached_points{new ge_cached[data.size()]}; - - for (size_t i = 0; i < data.size(); ++i) - { - ge_p3_to_cached(&cached_points[i], &data[i].point); - } + std::shared_ptr<pippenger_cached_data> local_cache = cache == NULL ? pippenger_init_cache(data) : cache; rct::key maxscalar = rct::zero(); for (size_t i = 0; i < data.size(); ++i) + { if (maxscalar < data[i].scalar) maxscalar = data[i].scalar; + } size_t groups = 0; while (groups < 256 && pow2(groups) < maxscalar) ++groups; @@ -598,7 +636,7 @@ rct::key pippenger(const std::vector<MultiexpData> &data, size_t c) CHECK_AND_ASSERT_THROW_MES(bucket < (1u<<c), "bucket overflow"); if (memcmp(&buckets[bucket], &ge_p3_identity, sizeof(ge_p3))) { - add(buckets[bucket], cached_points[i]); + add(buckets[bucket], local_cache->cached[i]); } else buckets[bucket] = data[i].point; diff --git a/src/ringct/multiexp.h b/src/ringct/multiexp.h index 2ed8db279..559ab664a 100644 --- a/src/ringct/multiexp.h +++ b/src/ringct/multiexp.h @@ -54,14 +54,17 @@ struct MultiexpData { }; struct straus_cached_data; +struct pippenger_cached_data; 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); +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); 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 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, size_t c); +rct::key pippenger(const std::vector<MultiexpData> &data, const std::shared_ptr<pippenger_cached_data> &cache = NULL, size_t c = 0); } |