From e2de45078c5e668ed9fd0515eb8face9170b9f70 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Tue, 29 Dec 2020 23:15:47 +0100 Subject: Another optimization on cdeq. Updated cdeq_benchmark.cpp --- benchmarks/cdeq_benchmark.cpp | 75 +++++++++++++++++++++++++++---------------- stc/cdeq.h | 6 ++-- 2 files changed, 51 insertions(+), 30 deletions(-) diff --git a/benchmarks/cdeq_benchmark.cpp b/benchmarks/cdeq_benchmark.cpp index 6a376d2a..6680ec2c 100644 --- a/benchmarks/cdeq_benchmark.cpp +++ b/benchmarks/cdeq_benchmark.cpp @@ -4,52 +4,73 @@ #include #include -enum {N = 200000000, M = 10000, P = 5000, R = 50}; +enum {N = 1000000000, M = 12345, P = 5000, R = 2000}; using_cdeq(i, int); void test1() { clock_t t1 = clock(), t2, t3; stc64_t rng = stc64_init(0); - std::deque deq; - for (size_t i = 1; i < N; i++) { - deq.push_front(stc64_rand(&rng)); - if (i % M == 0) - for (int j = 0; j < P; j++) - deq.pop_back(); + { + std::deque deq; + for (size_t i = 1; i < N; i++) { + deq.push_front(stc64_rand(&rng)); + if (i % M == 0) + for (int j = 5; j < M; j++) + deq.pop_back(); + } + size_t n = deq.size(); + t2 = clock(); + printf("std pushf/popb : %5.2f sec, sz=%zu\n", (float)(t2 - t1) / CLOCKS_PER_SEC, n); + fflush(stdout); + size_t sum = 0; + c_forrange (R) c_forrange (i, n) + sum += deq[i]; + t3 = clock(); + printf("std access : %5.2f sec, sum=%zu\n", (float)(t3 - t2) / CLOCKS_PER_SEC, sum); + } + std::deque deq; + for (size_t i = 1; i < N/10; i++) { + if (i & 1) deq.push_front(stc64_rand(&rng)); + else deq.push_back(stc64_rand(&rng)); } - size_t n = deq.size(); t2 = clock(); - printf("std::deque push/pop: %5.2f sec, sz=%zu", (float)(t2 - t1) / CLOCKS_PER_SEC, n); - fflush(stdout); - size_t sum = 0; - c_forrange (R) c_forrange (i, n) - sum += deq[i]; - t3 = clock(); - printf(" sum: %5.2f sec, val=%zu\n", (float)(t3 - t2) / CLOCKS_PER_SEC, sum); + printf("std pushf/pushb : %5.2f sec\n", (float)(t2 - t3) / CLOCKS_PER_SEC); } void test2() { clock_t t1 = clock(), t2, t3; stc64_t rng = stc64_init(0); + { + cdeq_i deq = cdeq_inits; + for (size_t i = 1; i < N; i++) { + cdeq_i_push_front(&deq, stc64_rand(&rng)); + if (i % M == 0) + for (int j = 5; j < M; j++) + cdeq_i_pop_back(&deq); + } + size_t n = cdeq_i_size(deq); + t2 = clock(); + printf("stc pushf/popb : %5.2f sec, sz=%zu\n", (float)(t2 - t1) / CLOCKS_PER_SEC, n); + size_t sum = 0; + c_forrange (R) c_forrange (i, n) + sum += deq.data[i]; + t3 = clock(); + printf("stc access : %5.2f sec, sum=%zu\n", (float)(t3 - t2) / CLOCKS_PER_SEC, sum); + cdeq_i_del(&deq); + } cdeq_i deq = cdeq_inits; - for (size_t i = 1; i < N; i++) { - cdeq_i_push_front(&deq, stc64_rand(&rng)); - if (i % M == 0) - for (int j = 0; j < P; j++) - cdeq_i_pop_back(&deq); + for (size_t i = 1; i < N/10; i++) { + if (i & 1) cdeq_i_push_front(&deq, stc64_rand(&rng)); + else cdeq_i_push_back(&deq, stc64_rand(&rng)); } - size_t n = cdeq_i_size(deq); t2 = clock(); - printf("stc/cdeq_i push/pop: %5.2f sec, sz=%zu", (float)(t2 - t1) / CLOCKS_PER_SEC, n); - size_t sum = 0; - c_forrange (R) c_forrange (i, n) - sum += deq.data[i]; - t3 = clock(); - printf(" sum: %5.2f sec, val=%zu\n", (float)(t3 - t2) / CLOCKS_PER_SEC, sum); + printf("stc pushf/pushb : %5.2f sec\n", (float)(t2 - t3) / CLOCKS_PER_SEC); + cdeq_i_del(&deq); } int main() { test1(); + puts(""); test2(); } diff --git a/stc/cdeq.h b/stc/cdeq.h index 5cf35300..682a962b 100644 --- a/stc/cdeq.h +++ b/stc/cdeq.h @@ -237,7 +237,7 @@ if (at_front && nfront >= n || !at_front && nback >= n) \ return; \ if ((len + n)*1.1 > cap) { \ - cap = (len + n + 6)*1.5; \ + cap = (len + n + 6)*2; \ size_t* rep = (size_t *) c_realloc(_cdeq_alloced(self->base), 2*sizeof(size_t) + cap*sizeof(Value)); \ rep[0] = len, rep[1] = cap; \ self->base = (cdeq_##X##_value_t *) (rep + 2); \ @@ -245,8 +245,8 @@ return _cdeq_##X##_expand(self, n, at_front); \ } \ size_t unused = cap - (len + n); \ - size_t pos = at_front ? c_maxf(unused*0.9, (float) unused - nback) + n \ - : c_minf(unused*0.1, nfront); \ + size_t pos = at_front ? c_maxf(unused*0.6, (float) unused - nback) + n \ + : c_minf(unused*0.4, nfront); \ memmove(self->base + pos, self->data, len*sizeof(Value)); \ self->data = self->base + pos; \ } \ -- cgit v1.2.3