diff options
| author | Tyge Løvset <[email protected]> | 2020-12-29 23:15:47 +0100 |
|---|---|---|
| committer | Tyge Løvset <[email protected]> | 2020-12-29 23:15:47 +0100 |
| commit | e2de45078c5e668ed9fd0515eb8face9170b9f70 (patch) | |
| tree | 6ae99ca100efc1bb727d2bc790957d5466cedd26 | |
| parent | e2b025c880727885c612c455f7e8550a1047c394 (diff) | |
| download | STC-modified-e2de45078c5e668ed9fd0515eb8face9170b9f70.tar.gz STC-modified-e2de45078c5e668ed9fd0515eb8face9170b9f70.zip | |
Another optimization on cdeq. Updated cdeq_benchmark.cpp
| -rw-r--r-- | benchmarks/cdeq_benchmark.cpp | 75 | ||||
| -rw-r--r-- | 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 <stc/cdeq.h>
#include <stc/crand.h>
-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<int> 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<int> 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<int> 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();
}
@@ -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; \
} \
|