#include "test/jemalloc_test.h"

/******************************************************************************/

/*
* General purpose tool for examining random number distributions.
*
* Input -
* (a) a random number generator, and
* (b) the buckets:
*     (1) number of buckets,
*     (2) width of each bucket, in log scale,
*     (3) expected mean and stddev of the count of random numbers in each
*         bucket, and
* (c) number of iterations to invoke the generator.
*
* The program generates the specified amount of random numbers, and assess how
* well they conform to the expectations: for each bucket, output -
* (a) the (given) expected mean and stddev,
* (b) the actual count and any interesting level of deviation:
*     (1) ~68% buckets should show no interesting deviation, meaning a
*         deviation less than stddev from the expectation;
*     (2) ~27% buckets should show '+' / '-', meaning a deviation in the range
*         of [stddev, 2 * stddev) from the expectation;
*     (3) ~4% buckets should show '++' / '--', meaning a deviation in the
*         range of [2 * stddev, 3 * stddev) from the expectation; and
*     (4) less than 0.3% buckets should show more than two '+'s / '-'s.
*
* Technical remarks:
* (a) The generator is expected to output uint64_t numbers, so you might need
*     to define a wrapper.
* (b) The buckets must be of equal width and the lowest bucket starts at
*     [0, 2^lg_bucket_width - 1).
* (c) Any generated number >= n_bucket * 2^lg_bucket_width will be counted
*     towards the last bucket; the expected mean and stddev provided should
*     also reflect that.
* (d) The number of iterations is advised to be determined so that the bucket
*     with the minimal expected proportion gets a sufficient count.
*/

static void
fill(size_t a[], const size_t n, const size_t k) {
       for (size_t i = 0; i < n; ++i) {
               a[i] = k;
       }
}

static void
collect_buckets(uint64_t (*gen)(void *), void *opaque, size_t buckets[],
   const size_t n_bucket, const size_t lg_bucket_width, const size_t n_iter) {
       for (size_t i = 0; i < n_iter; ++i) {
               uint64_t num = gen(opaque);
               uint64_t bucket_id = num >> lg_bucket_width;
               if (bucket_id >= n_bucket) {
                       bucket_id = n_bucket - 1;
               }
               ++buckets[bucket_id];
       }
}

static void
print_buckets(const size_t buckets[], const size_t means[],
   const size_t stddevs[], const size_t n_bucket) {
       for (size_t i = 0; i < n_bucket; ++i) {
               malloc_printf("%zu:\tmean = %zu,\tstddev = %zu,\tbucket = %zu",
                   i, means[i], stddevs[i], buckets[i]);

               /* Make sure there's no overflow. */
               assert(buckets[i] + stddevs[i] >= stddevs[i]);
               assert(means[i] + stddevs[i] >= stddevs[i]);

               if (buckets[i] + stddevs[i] <= means[i]) {
                       malloc_write(" ");
                       for (size_t t = means[i] - buckets[i]; t >= stddevs[i];
                           t -= stddevs[i]) {
                               malloc_write("-");
                       }
               } else if (buckets[i] >= means[i] + stddevs[i]) {
                       malloc_write(" ");
                       for (size_t t = buckets[i] - means[i]; t >= stddevs[i];
                           t -= stddevs[i]) {
                               malloc_write("+");
                       }
               }
               malloc_write("\n");
       }
}

static void
bucket_analysis(uint64_t (*gen)(void *), void *opaque, size_t buckets[],
   const size_t means[], const size_t stddevs[], const size_t n_bucket,
   const size_t lg_bucket_width, const size_t n_iter) {
       for (size_t i = 1; i <= 3; ++i) {
               malloc_printf("round %zu\n", i);
               fill(buckets, n_bucket, 0);
               collect_buckets(gen, opaque, buckets, n_bucket,
                   lg_bucket_width, n_iter);
               print_buckets(buckets, means, stddevs, n_bucket);
       }
}

/* (Recommended) minimal bucket mean. */
#define MIN_BUCKET_MEAN 10000

/******************************************************************************/

/* Uniform random number generator. */

typedef struct uniform_gen_arg_s uniform_gen_arg_t;
struct uniform_gen_arg_s {
       uint64_t state;
       const unsigned lg_range;
};

static uint64_t
uniform_gen(void *opaque) {
       uniform_gen_arg_t *arg = (uniform_gen_arg_t *)opaque;
       return prng_lg_range_u64(&arg->state, arg->lg_range);
}

TEST_BEGIN(test_uniform) {
#define LG_N_BUCKET 5
#define N_BUCKET (1 << LG_N_BUCKET)

#define QUOTIENT_CEIL(n, d) (((n) - 1) / (d) + 1)

       const unsigned lg_range_test = 25;

       /*
        * Mathematical tricks to guarantee that both mean and stddev are
        * integers, and that the minimal bucket mean is at least
        * MIN_BUCKET_MEAN.
        */
       const size_t q = 1 << QUOTIENT_CEIL(LG_CEIL(QUOTIENT_CEIL(
           MIN_BUCKET_MEAN, N_BUCKET * (N_BUCKET - 1))), 2);
       const size_t stddev = (N_BUCKET - 1) * q;
       const size_t mean = N_BUCKET * stddev * q;
       const size_t n_iter = N_BUCKET * mean;

       size_t means[N_BUCKET];
       fill(means, N_BUCKET, mean);
       size_t stddevs[N_BUCKET];
       fill(stddevs, N_BUCKET, stddev);

       uniform_gen_arg_t arg = {(uint64_t)(uintptr_t)&lg_range_test,
           lg_range_test};
       size_t buckets[N_BUCKET];
       assert_zu_ge(lg_range_test, LG_N_BUCKET, "");
       const size_t lg_bucket_width = lg_range_test - LG_N_BUCKET;

       bucket_analysis(uniform_gen, &arg, buckets, means, stddevs,
           N_BUCKET, lg_bucket_width, n_iter);

#undef LG_N_BUCKET
#undef N_BUCKET
#undef QUOTIENT_CEIL
}
TEST_END

/******************************************************************************/

/* Geometric random number generator; compiled only when prof is on. */

#ifdef JEMALLOC_PROF

/*
* Fills geometric proportions and returns the minimal proportion.  See
* comments in test_prof_sample for explanations for n_divide.
*/
static double
fill_geometric_proportions(double proportions[], const size_t n_bucket,
   const size_t n_divide) {
       assert(n_bucket > 0);
       assert(n_divide > 0);
       double x = 1.;
       for (size_t i = 0; i < n_bucket; ++i) {
               if (i == n_bucket - 1) {
                       proportions[i] = x;
               } else {
                       double y = x * exp(-1. / n_divide);
                       proportions[i] = x - y;
                       x = y;
               }
       }
       /*
        * The minimal proportion is the smaller one of the last two
        * proportions for geometric distribution.
        */
       double min_proportion = proportions[n_bucket - 1];
       if (n_bucket >= 2 && proportions[n_bucket - 2] < min_proportion) {
               min_proportion = proportions[n_bucket - 2];
       }
       return min_proportion;
}

static size_t
round_to_nearest(const double x) {
       return (size_t)(x + .5);
}

static void
fill_references(size_t means[], size_t stddevs[], const double proportions[],
   const size_t n_bucket, const size_t n_iter) {
       for (size_t i = 0; i < n_bucket; ++i) {
               double x = n_iter * proportions[i];
               means[i] = round_to_nearest(x);
               stddevs[i] = round_to_nearest(sqrt(x * (1. - proportions[i])));
       }
}

static uint64_t
prof_sample_gen(void *opaque) {
       return prof_sample_new_event_wait((tsd_t *)opaque) - 1;
}

#endif /* JEMALLOC_PROF */

TEST_BEGIN(test_prof_sample) {
       test_skip_if(!config_prof);
#ifdef JEMALLOC_PROF

/* Number of divisions within [0, mean). */
#define LG_N_DIVIDE 3
#define N_DIVIDE (1 << LG_N_DIVIDE)

/* Coverage of buckets in terms of multiples of mean. */
#define LG_N_MULTIPLY 2
#define N_GEO_BUCKET (N_DIVIDE << LG_N_MULTIPLY)

       test_skip_if(!opt_prof);

       size_t lg_prof_sample_test = 25;

       size_t lg_prof_sample_orig = lg_prof_sample;
       assert_d_eq(mallctl("prof.reset", NULL, NULL, &lg_prof_sample_test,
           sizeof(size_t)), 0, "");
       malloc_printf("lg_prof_sample = %zu\n", lg_prof_sample_test);

       double proportions[N_GEO_BUCKET + 1];
       const double min_proportion = fill_geometric_proportions(proportions,
           N_GEO_BUCKET + 1, N_DIVIDE);
       const size_t n_iter = round_to_nearest(MIN_BUCKET_MEAN /
           min_proportion);
       size_t means[N_GEO_BUCKET + 1];
       size_t stddevs[N_GEO_BUCKET + 1];
       fill_references(means, stddevs, proportions, N_GEO_BUCKET + 1, n_iter);

       tsd_t *tsd = tsd_fetch();
       assert_ptr_not_null(tsd, "");
       size_t buckets[N_GEO_BUCKET + 1];
       assert_zu_ge(lg_prof_sample, LG_N_DIVIDE, "");
       const size_t lg_bucket_width = lg_prof_sample - LG_N_DIVIDE;

       bucket_analysis(prof_sample_gen, tsd, buckets, means, stddevs,
           N_GEO_BUCKET + 1, lg_bucket_width, n_iter);

       assert_d_eq(mallctl("prof.reset", NULL, NULL, &lg_prof_sample_orig,
           sizeof(size_t)), 0, "");

#undef LG_N_DIVIDE
#undef N_DIVIDE
#undef LG_N_MULTIPLY
#undef N_GEO_BUCKET

#endif /* JEMALLOC_PROF */
}
TEST_END

/******************************************************************************/

int
main(void) {
       return test_no_reentrancy(
           test_uniform,
           test_prof_sample);
}

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.