-
Notifications
You must be signed in to change notification settings - Fork 7
/
adaptive-heap-sizer.h
168 lines (156 loc) · 6.38 KB
/
adaptive-heap-sizer.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#ifndef ADAPTIVE_HEAP_SIZER_H
#define ADAPTIVE_HEAP_SIZER_H
#include <math.h>
#include <pthread.h>
#include <stdlib.h>
#include <string.h>
#include "assert.h"
#include "background-thread.h"
#include "debug.h"
#include "gc-config.h"
#include "gc-platform.h"
#include "heap-sizer.h"
// This is the MemBalancer algorithm from "Optimal Heap Limits for Reducing
// Browser Memory Use" by Marisa Kirisame, Pranav Shenoy, and Pavel Panchekha
// (https://arxiv.org/abs/2204.10455).
//
// This implementation differs slightly in that the constant "c" of the paper
// has been extracted outside the radical, and notionally reversed: it is a
// unitless "expansiveness" parameter whose domain is [0,+∞]. Also there are
// minimum and maximum heap size multipliers, and a minimum amount of free
// space. The initial collection rate is an informed guess. The initial
// allocation rate estimate is high, considering that allocation rates are often
// high on program startup.
struct gc_adaptive_heap_sizer {
uint64_t (*get_allocation_counter)(struct gc_heap *heap);
void (*set_heap_size)(struct gc_heap *heap, size_t size);
struct gc_heap *heap;
uint64_t smoothed_pause_time;
uint64_t smoothed_live_bytes;
uint64_t live_bytes;
double smoothed_allocation_rate;
double collection_smoothing_factor;
double allocation_smoothing_factor;
double minimum_multiplier;
double maximum_multiplier;
double minimum_free_space;
double expansiveness;
#if GC_PARALLEL
pthread_mutex_t lock;
#endif
int background_task_id;
uint64_t last_bytes_allocated;
uint64_t last_heartbeat;
};
static void
gc_adaptive_heap_sizer_lock(struct gc_adaptive_heap_sizer *sizer) {
#if GC_PARALLEL
pthread_mutex_lock(&sizer->lock);
#endif
}
static void
gc_adaptive_heap_sizer_unlock(struct gc_adaptive_heap_sizer *sizer) {
#if GC_PARALLEL
pthread_mutex_unlock(&sizer->lock);
#endif
}
// With lock
static uint64_t
gc_adaptive_heap_sizer_calculate_size(struct gc_adaptive_heap_sizer *sizer) {
double allocation_rate = sizer->smoothed_allocation_rate;
double collection_rate =
(double)sizer->smoothed_pause_time / (double)sizer->smoothed_live_bytes;
double radicand = sizer->live_bytes * allocation_rate / collection_rate;
double multiplier = 1.0 + sizer->expansiveness * sqrt(radicand);
if (isnan(multiplier) || multiplier < sizer->minimum_multiplier)
multiplier = sizer->minimum_multiplier;
else if (multiplier > sizer->maximum_multiplier)
multiplier = sizer->maximum_multiplier;
uint64_t size = sizer->live_bytes * multiplier;
if (size - sizer->live_bytes < sizer->minimum_free_space)
size = sizer->live_bytes + sizer->minimum_free_space;
return size;
}
static uint64_t
gc_adaptive_heap_sizer_set_expansiveness(struct gc_adaptive_heap_sizer *sizer,
double expansiveness) {
gc_adaptive_heap_sizer_lock(sizer);
sizer->expansiveness = expansiveness;
uint64_t heap_size = gc_adaptive_heap_sizer_calculate_size(sizer);
gc_adaptive_heap_sizer_unlock(sizer);
return heap_size;
}
static void
gc_adaptive_heap_sizer_on_gc(struct gc_adaptive_heap_sizer *sizer,
size_t live_bytes, uint64_t pause_ns,
void (*set_heap_size)(struct gc_heap*, size_t)) {
gc_adaptive_heap_sizer_lock(sizer);
sizer->live_bytes = live_bytes;
sizer->smoothed_live_bytes *= 1.0 - sizer->collection_smoothing_factor;
sizer->smoothed_live_bytes += sizer->collection_smoothing_factor * live_bytes;
sizer->smoothed_pause_time *= 1.0 - sizer->collection_smoothing_factor;
sizer->smoothed_pause_time += sizer->collection_smoothing_factor * pause_ns;
set_heap_size(sizer->heap, gc_adaptive_heap_sizer_calculate_size(sizer));
gc_adaptive_heap_sizer_unlock(sizer);
}
static void
gc_adaptive_heap_sizer_background_task(void *data) {
struct gc_adaptive_heap_sizer *sizer = data;
gc_adaptive_heap_sizer_lock(sizer);
uint64_t bytes_allocated =
sizer->get_allocation_counter(sizer->heap);
uint64_t heartbeat = gc_platform_monotonic_nanoseconds();
double rate = (double) (bytes_allocated - sizer->last_bytes_allocated) /
(double) (heartbeat - sizer->last_heartbeat);
// Just smooth the rate, under the assumption that the denominator is almost
// always 1.
sizer->smoothed_allocation_rate *= 1.0 - sizer->allocation_smoothing_factor;
sizer->smoothed_allocation_rate += rate * sizer->allocation_smoothing_factor;
sizer->last_heartbeat = heartbeat;
sizer->last_bytes_allocated = bytes_allocated;
sizer->set_heap_size(sizer->heap,
gc_adaptive_heap_sizer_calculate_size(sizer));
gc_adaptive_heap_sizer_unlock(sizer);
}
static struct gc_adaptive_heap_sizer*
gc_make_adaptive_heap_sizer(struct gc_heap *heap, double expansiveness,
uint64_t (*get_allocation_counter)(struct gc_heap*),
void (*set_heap_size)(struct gc_heap*, size_t),
struct gc_background_thread *thread) {
struct gc_adaptive_heap_sizer *sizer;
sizer = malloc(sizeof(*sizer));
if (!sizer)
GC_CRASH();
memset(sizer, 0, sizeof(*sizer));
sizer->get_allocation_counter = get_allocation_counter;
sizer->set_heap_size = set_heap_size;
sizer->heap = heap;
// Baseline estimate of GC speed: 10 MB/ms, or 10 bytes/ns. However since we
// observe this speed by separately noisy measurements, we have to provide
// defaults for numerator and denominator; estimate 2ms for initial GC pauses
// for 20 MB of live data during program startup.
sizer->smoothed_pause_time = 2 * 1000 * 1000;
sizer->smoothed_live_bytes = 20 * 1024 * 1024;
// Baseline estimate of allocation rate during startup: 50 MB in 10ms, or 5
// bytes/ns.
sizer->smoothed_allocation_rate = 5;
sizer->collection_smoothing_factor = 0.5;
sizer->allocation_smoothing_factor = 0.95;
sizer->minimum_multiplier = 1.1;
sizer->maximum_multiplier = 5;
sizer->minimum_free_space = 4 * 1024 * 1024;
sizer->expansiveness = expansiveness;
sizer->last_bytes_allocated = get_allocation_counter(heap);
sizer->last_heartbeat = gc_platform_monotonic_nanoseconds();
#if GC_PARALLEL
pthread_mutex_init(&thread->lock, NULL);
sizer->background_task_id =
gc_background_thread_add_task(thread, GC_BACKGROUND_TASK_MIDDLE,
gc_adaptive_heap_sizer_background_task,
sizer);
#else
sizer->background_task_id = -1;
#endif
return sizer;
}
#endif // ADAPTIVE_HEAP_SIZER_H