summaryrefslogtreecommitdiff
path: root/libguile/whippet/api/gc-histogram.h
diff options
context:
space:
mode:
authorAndy Wingo <wingo@pobox.com>2025-04-11 14:10:41 +0200
committerAndy Wingo <wingo@pobox.com>2025-04-11 14:10:41 +0200
commitdb181e67ff482ab08cbdb0c1a88997b3a886f900 (patch)
tree6d16fbca515ae3cf506a9d16dbc89c472446e5d9 /libguile/whippet/api/gc-histogram.h
parentaf96820e072d18c49ac03e80c6f3466d568dc77d (diff)
parentf909438596f63ecd44c5b9a28385260714857361 (diff)
downloadguile-db181e67ff482ab08cbdb0c1a88997b3a886f900.tar.gz
Merged Whippet into libguile/whippet
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