summaryrefslogtreecommitdiff
path: root/libguile/whippet/api/gc-histogram.h
diff options
context:
space:
mode:
Diffstat (limited to 'libguile/whippet/api/gc-histogram.h')
-rw-r--r--libguile/whippet/api/gc-histogram.h82
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