Optimized cdeq_X_insert_range. Added crand_uniform_fast() method (slightly biased for very large ranges only).

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 <stc/crand.h>

 #include <stc/cqueue.h>

+#include <stc/cdeq.h>

 #include <stdio.h>

 

+#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 <intrin.h>

+    #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 <intrin.h>

-    #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);