From a6657b9f4b22afbdb1c98ce462d74665856a6f05 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Mon, 21 Dec 2020 09:49:41 +0100 Subject: Optimized cdeq_X_insert_range. Added crand_uniform_fast() method (slightly biased for very large ranges only). --- examples/queue.c | 12 +++++++++--- stc/cdeq.h | 17 +++++++++-------- stc/crand.h | 38 ++++++++++++++++++++++---------------- 3 files changed, 40 insertions(+), 27 deletions(-) diff --git a/examples/queue.c b/examples/queue.c index 2499a9ab..f4847ebd 100644 --- a/examples/queue.c +++ b/examples/queue.c @@ -1,12 +1,18 @@ #include #include +#include #include +#if 1 using_clist(i, int); -using_cqueue(i, clist_i); // min-heap (increasing values) +using_cqueue(i, clist_i); +#else +using_cdeq(i, int); +using_cqueue(i, cdeq_i); +#endif int main() { - int n = 10000000; + int n = 100000000; crand_uniform_t dist; crand_t rng = crand_init(1234); dist = crand_uniform_init(0, n); @@ -15,7 +21,7 @@ int main() { // Push ten million random numbers onto the queue. c_forrange (n) - cqueue_i_push(&queue, crand_uniform(&rng, &dist)); + cqueue_i_push(&queue, crand_uniform_fast(&rng, &dist)); // Push or pop on the queue ten million times printf("%d\n", n); diff --git a/stc/cdeq.h b/stc/cdeq.h index e2cde0dc..09537a38 100644 --- a/stc/cdeq.h +++ b/stc/cdeq.h @@ -239,14 +239,14 @@ if (len + n > cap) { \ cap = (len + n + 6)*3/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); \ self->data = self->base + nfront; \ - rep[0] = len; \ - rep[1] = cap; \ + return _deq_##X##_expand(self, n, at_front); \ } \ size_t unused = cap - (len + n); \ - size_t pos = at_front ? c_maxf(unused*0.7, (float) unused - nback) + n \ - : c_minf(unused*0.3, nfront); \ + size_t pos = at_front ? c_maxf(unused*0.9, (float) unused - nback) + n \ + : c_minf(unused*0.1, nfront); \ memmove(self->base + pos, self->data, len*sizeof(Value)); \ self->data = self->base + pos; \ } \ @@ -284,11 +284,12 @@ cdeq_##X##_insert_range_p(cdeq_##X* self, cdeq_##X##_value_t* pos, \ const cdeq_##X##_value_t* first, const cdeq_##X##_value_t* finish) { \ size_t n = finish - first, idx = pos - self->data, size = cdeq_size(*self); \ - bool at_front = (pos == self->data); \ + bool at_front = (idx < size/2); \ _cdeq_##X##_expand(self, n, at_front); \ - if (at_front) \ - pos = (self->data -= n); \ - else { \ + if (at_front) { \ + memmove(self->data - n, self->data, idx*sizeof(Value)); \ + pos = (self->data -= n) + idx; \ + } else { \ pos = self->data + idx; \ memmove(pos + n, pos, (size - idx)*sizeof(Value)); \ } \ diff --git a/stc/crand.h b/stc/crand.h index 54fbcc10..3652851c 100644 --- a/stc/crand.h +++ b/stc/crand.h @@ -32,7 +32,7 @@ int main() { crand_uniform_t dist1 = crand_uniform_init(1, 6); crand_uniformf_t dist2 = crand_uniformf_init(1.0, 10.0); crand_normalf_t dist3 = crand_normalf_init(1.0, 10.0); - + uint64_t i = crand_next(&rng); int64_t iu = crand_uniform(&rng, &dist1); double xu = crand_uniformf(&rng, &dist2); @@ -72,6 +72,25 @@ STC_INLINE double crand_uniformf(crand_t* rng, crand_uniformf_t* dist) { return crand_nextf(rng)*dist->range + dist->lower; } +#if defined(__SIZEOF_INT128__) + #define cmul128(a, b, lo, hi) \ + do { __uint128_t _z = (__uint128_t)(a) * (b); \ + *(lo) = (uint64_t)_z, *(hi) = _z >> 64; } while(0) +#elif defined(_MSC_VER) && defined(_WIN64) + #include + #define cmul128(a, b, lo, hi) (*(lo) = _umul128(a, b, hi), (void)0) +#elif defined(__x86_64__) + #define cmul128(a, b, lo, hi) \ + asm("mulq %[rhs]" : "=a" (*(lo)), "=d" (*(hi)) \ + : [lhs] "0" (a), [rhs] "rm" (b)) +#endif + +STC_INLINE int64_t crand_uniform_fast(crand_t* rng, crand_uniform_t* d) { + uint64_t lo, hi; + cmul128(crand_next(rng), d->range, &lo, &hi); + return d->lower + hi; +} + /* double normal distributed RNG. */ STC_INLINE crand_normalf_t crand_normalf_init(double mean, double stddev) { crand_normalf_t dist = {mean, stddev, 0.0, false}; return dist; @@ -87,7 +106,7 @@ STC_API double crand_normalf(crand_t* rng, crand_normalf_t* dist); * 256bit state, updates only 192bit per rng. * 2^63 unique threads with a minimum 2^64 period lengths each. * 2^127 minimum period length for single thread (double loop). - * Passes PractRand tested up to 8TB output, Vigna's Hamming weight test, + * Passes PractRand tested up to 8TB output, Vigna's Hamming weight test, * and simple correlation tests, i.e. interleaved streams with one-bit diff state. */ @@ -115,21 +134,8 @@ STC_DEF crand_uniform_t crand_uniform_init(int64_t low, int64_t high) { return dist; } -#if defined(__SIZEOF_INT128__) - #define cmul128(a, b, lo, hi) \ - do { __uint128_t _z = (__uint128_t)(a) * (b); \ - *(lo) = (uint64_t)_z, *(hi) = _z >> 64; } while(0) -#elif defined(_MSC_VER) && defined(_WIN64) - #include - #define cmul128(a, b, lo, hi) (*(lo) = _umul128(a, b, hi), (void)0) -#elif defined(__x86_64__) - #define cmul128(a, b, lo, hi) \ - asm("mulq %[rhs]" : "=a" (*(lo)), "=d" (*(hi)) \ - : [lhs] "0" (a), [rhs] "rm" (b)) -#endif - STC_DEF int64_t crand_uniform(crand_t* rng, crand_uniform_t* d) { - uint64_t lo, hi; + uint64_t lo, hi; do { cmul128(crand_next(rng), d->range, &lo, &hi); } while (lo < d->threshold); -- cgit v1.2.3