diff options
Diffstat (limited to 'libguile/whippet/api/gc-histogram.h')
-rw-r--r-- | libguile/whippet/api/gc-histogram.h | 82 |
1 files changed, 82 insertions, 0 deletions
diff --git a/libguile/whippet/api/gc-histogram.h b/libguile/whippet/api/gc-histogram.h new file mode 100644 index 000000000..0761a630f --- /dev/null +++ b/libguile/whippet/api/gc-histogram.h @@ -0,0 +1,82 @@ +#ifndef GC_HISTOGRAM_H +#define GC_HISTOGRAM_H + +#include "gc-assert.h" + +#include <stdint.h> + +static inline size_t gc_histogram_bucket(uint64_t max_value_bits, + uint64_t precision, + uint64_t val) { + uint64_t major = val < (1ULL << precision) + ? 0ULL + : 64ULL - __builtin_clzl(val) - precision; + uint64_t minor = val < (1 << precision) + ? val + : (val >> (major - 1ULL)) & ((1ULL << precision) - 1ULL); + uint64_t idx = (major << precision) | minor; + if (idx >= (max_value_bits << precision)) + idx = max_value_bits << precision; + return idx; +} + +static inline uint64_t gc_histogram_bucket_min_val(uint64_t precision, + size_t idx) { + uint64_t major = idx >> precision; + uint64_t minor = idx & ((1ULL << precision) - 1ULL); + uint64_t min_val = major + ? ((1ULL << precision) | minor) << (major - 1ULL) + : minor; + return min_val; +} + +#define GC_DEFINE_HISTOGRAM(name, max_value_bits, precision) \ + struct name { uint32_t buckets[((max_value_bits) << (precision)) + 1]; }; \ + static inline size_t name##_size(void) { \ + return ((max_value_bits) << (precision)) + 1; \ + } \ + static inline uint64_t name##_bucket_min_val(size_t idx) { \ + GC_ASSERT(idx < name##_size()); \ + return gc_histogram_bucket_min_val((precision), idx); \ + } \ + static inline struct name make_##name(void) { \ + return (struct name) { { 0, }}; \ + } \ + static inline void name##_record(struct name *h, uint64_t val) { \ + h->buckets[gc_histogram_bucket((max_value_bits), (precision), val)]++; \ + } \ + static inline uint64_t name##_ref(struct name *h, size_t idx) { \ + GC_ASSERT(idx < name##_size()); \ + return h->buckets[idx]; \ + } \ + static inline uint64_t name##_min(struct name *h) { \ + for (size_t bucket = 0; bucket < name##_size(); bucket++) \ + if (h->buckets[bucket]) return name##_bucket_min_val(bucket); \ + return -1; \ + } \ + static inline uint64_t name##_max(struct name *h) { \ + if (h->buckets[name##_size()-1]) return -1LL; \ + for (ssize_t bucket = name##_size() - 1; bucket >= 0; bucket--) \ + if (h->buckets[bucket]) return name##_bucket_min_val(bucket+1); \ + return 0; \ + } \ + static inline uint64_t name##_count(struct name *h) { \ + uint64_t sum = 0; \ + for (size_t bucket = 0; bucket < name##_size(); bucket++) \ + sum += h->buckets[bucket]; \ + return sum; \ + } \ + static inline uint64_t name##_percentile(struct name *h, double p) { \ + uint64_t n = name##_count(h) * p; \ + uint64_t sum = 0; \ + for (size_t bucket = 0; bucket + 1 < name##_size(); bucket++) { \ + sum += h->buckets[bucket]; \ + if (sum >= n) return name##_bucket_min_val(bucket+1); \ + } \ + return -1ULL; \ + } \ + static inline uint64_t name##_median(struct name *h) { \ + return name##_percentile(h, 0.5); \ + } + +#endif // GC_HISTOGRAM_H |