wingo pushed a commit to branch wip-whippet
in repository guile.
commit 9c89672c886b0fd806e222baa5c52b0524003098
Author: Andy Wingo <wi...@igalia.com>
AuthorDate: Fri Mar 11 11:57:14 2022 +0100
Put a local mark queue in front of the work-stealing queue
---
mark-sweep.h | 10 +++----
parallel-marker.h | 83 ++++++++++++++++++++++++++++++++++++++++++++++---------
serial-marker.h | 6 ++--
3 files changed, 77 insertions(+), 22 deletions(-)
diff --git a/mark-sweep.h b/mark-sweep.h
index 6e0e82db6..6241d8ab6 100644
--- a/mark-sweep.h
+++ b/mark-sweep.h
@@ -144,11 +144,11 @@ static inline int mark_object(struct context *cx, struct
gcobj *obj) {
return 1;
}
-static void process(struct context *cx, struct gcobj *obj) {
+static void trace_one(struct gcobj *obj, void *mark_data) {
switch (tag_live_alloc_kind(obj->tag)) {
#define SCAN_OBJECT(name, Name, NAME) \
case ALLOC_KIND_##NAME: \
- visit_##name##_fields((Name*)obj, marker_visit, cx); \
+ visit_##name##_fields((Name*)obj, marker_visit, mark_data); \
break;
FOR_EACH_HEAP_OBJECT_KIND(SCAN_OBJECT)
#undef SCAN_OBJECT
@@ -168,7 +168,7 @@ static void collect(struct context *cx) {
marker_prepare(cx);
for (struct handle *h = cx->roots; h; h = h->next)
marker_visit_root(&h->v, cx);
- marker_trace(cx, process);
+ marker_trace(cx, trace_one);
marker_release(cx);
DEBUG("done marking\n");
cx->sweep = cx->heap_base;
@@ -290,9 +290,7 @@ static int sweep(struct context *cx) {
(limit - sweep) >> GRANULE_SIZE_LOG_2);
if (free_granules) {
size_t free_bytes = free_granules * GRANULE_SIZE;
- memset((void*)(sweep + GRANULE_SIZE),
- 0,
- free_bytes - GRANULE_SIZE);
+ clear_memory(sweep + GRANULE_SIZE, free_bytes - GRANULE_SIZE);
reclaim(cx, (void*)sweep, free_granules);
sweep += free_bytes;
to_reclaim -= free_granules;
diff --git a/parallel-marker.h b/parallel-marker.h
index e8da3e567..805522ae7 100644
--- a/parallel-marker.h
+++ b/parallel-marker.h
@@ -36,7 +36,7 @@ mark_buf_init(struct mark_buf *buf, unsigned log_size) {
MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
if (mem == MAP_FAILED) {
perror("Failed to grow work-stealing dequeue");
- DEBUG("Failed to allocate %zu bytes", size, );
+ DEBUG("Failed to allocate %zu bytes", size);
return 0;
}
buf->log_size = log_size;
@@ -220,10 +220,49 @@ mark_deque_steal(struct mark_deque *q) {
#undef STORE_RELEASE
#undef LOAD_CONSUME
+#define LOCAL_MARK_QUEUE_SIZE 64
+#define LOCAL_MARK_QUEUE_MASK 63
+struct local_mark_queue {
+ size_t read;
+ size_t write;
+ uintptr_t data[LOCAL_MARK_QUEUE_SIZE];
+};
+
+static inline void
+local_mark_queue_init(struct local_mark_queue *q) {
+ q->read = q->write = 0;
+}
+static inline void
+local_mark_queue_poison(struct local_mark_queue *q) {
+ q->read = 0; q->write = LOCAL_MARK_QUEUE_SIZE;
+}
+static inline int
+local_mark_queue_empty(struct local_mark_queue *q) {
+ return q->read == q->write;
+}
+static inline int
+local_mark_queue_full(struct local_mark_queue *q) {
+ return q->read + LOCAL_MARK_QUEUE_SIZE == q->write;
+}
+static inline void
+local_mark_queue_push(struct local_mark_queue *q, uintptr_t v) {
+ q->data[q->write++ & LOCAL_MARK_QUEUE_MASK] = v;
+}
+static inline uintptr_t
+local_mark_queue_pop(struct local_mark_queue *q) {
+ return q->data[q->read++ & LOCAL_MARK_QUEUE_MASK];
+}
+
struct marker {
struct mark_deque deque;
};
+struct local_marker {
+ struct local_mark_queue local;
+ struct mark_deque *deque;
+ struct context *cx;
+};
+
struct context;
static inline struct marker* context_marker(struct context *cx);
@@ -239,32 +278,50 @@ static void marker_release(struct context *cx) {
struct gcobj;
static inline void marker_visit(void **loc, void *mark_data) ALWAYS_INLINE;
static inline void marker_trace(struct context *cx,
- void (*)(struct context *, struct gcobj *))
+ void (*)(struct gcobj *, void *))
ALWAYS_INLINE;
static inline int mark_object(struct context *cx,
struct gcobj *obj) ALWAYS_INLINE;
static inline void
marker_visit(void **loc, void *mark_data) {
- struct context *cx = mark_data;
+ struct local_marker *mark = mark_data;
struct gcobj *obj = *loc;
- if (obj && mark_object(cx, obj))
- mark_deque_push(&context_marker(cx)->deque, (uintptr_t)obj);
+ if (obj && mark_object(mark->cx, obj)) {
+ if (!local_mark_queue_full(&mark->local))
+ local_mark_queue_push(&mark->local, (uintptr_t)obj);
+ else
+ mark_deque_push(mark->deque, (uintptr_t)obj);
+ }
}
static inline void
marker_visit_root(void **loc, struct context *cx) {
- marker_visit(loc, cx);
+ struct local_marker mark;
+ local_mark_queue_poison(&mark.local);
+ mark.deque = &context_marker(cx)->deque;
+ mark.cx = cx;
+ marker_visit(loc, &mark);
}
static inline void
marker_trace(struct context *cx,
- void (*process)(struct context *, struct gcobj *)) {
+ void (*trace_one)(struct gcobj *, void *)) {
+ struct local_marker mark;
+ local_mark_queue_init(&mark.local);
+ mark.deque = &context_marker(cx)->deque;
+ mark.cx = cx;
+
while (1) {
- uintptr_t addr = mark_deque_steal(&context_marker(cx)->deque);
- if (addr == mark_deque_empty)
- return;
- if (addr == mark_deque_abort)
- continue;
- process(cx, (struct gcobj*)addr);
+ uintptr_t addr;
+ if (!local_mark_queue_empty(&mark.local)) {
+ addr = local_mark_queue_pop(&mark.local);
+ } else {
+ addr = mark_deque_steal(mark.deque);
+ if (addr == mark_deque_empty)
+ break;
+ if (addr == mark_deque_abort)
+ continue;
+ }
+ trace_one((struct gcobj*)addr, &mark);
}
}
diff --git a/serial-marker.h b/serial-marker.h
index 8f7dec01d..1c2e305a7 100644
--- a/serial-marker.h
+++ b/serial-marker.h
@@ -127,7 +127,7 @@ static void marker_release(struct context *cx) {
struct gcobj;
static inline void marker_visit(void **loc, void *mark_data) ALWAYS_INLINE;
static inline void marker_trace(struct context *cx,
- void (*)(struct context *, struct gcobj *))
+ void (*)(struct gcobj *, void *))
ALWAYS_INLINE;
static inline int mark_object(struct context *cx,
struct gcobj *obj) ALWAYS_INLINE;
@@ -145,10 +145,10 @@ marker_visit_root(void **loc, struct context *cx) {
}
static inline void
marker_trace(struct context *cx,
- void (*process)(struct context *, struct gcobj *)) {
+ void (*trace_one)(struct gcobj *, void *)) {
struct gcobj *obj;
while ((obj = mark_queue_pop(&context_marker(cx)->queue)))
- process(cx, obj);
+ trace_one(obj, cx);
}
#endif // SERIAL_MARK_H
