wingo pushed a commit to branch wip-whippet
in repository guile.
commit 30b5c8a6c8835cb580d257331ad4e5c768b6b40d
Author: Andy Wingo <wi...@igalia.com>
AuthorDate: Mon Feb 28 21:35:28 2022 +0100
Use handle API, add semispace collector
---
GCBench.c | 169 +++++++++++++++++++++++++++++++++++-------------------
Makefile | 5 +-
bdw.h | 46 +++++++++------
semi.h | 193 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 336 insertions(+), 77 deletions(-)
diff --git a/GCBench.c b/GCBench.c
index 8331e82be..a16eb6eb1 100644
--- a/GCBench.c
+++ b/GCBench.c
@@ -42,17 +42,65 @@
#include <stdlib.h>
#include <sys/time.h>
+#ifdef GC_BDW
+#include "bdw.h"
+#elif defined(GC_SEMI)
+#include "semi.h"
+#else
+#error unknown gc
+#endif
+
+static const int kStretchTreeDepth = 18; // about 16Mb
+static const int kLongLivedTreeDepth = 16; // about 4Mb
+static const int kArraySize = 500000; // about 4Mb
+static const int kMinTreeDepth = 4;
+static const int kMaxTreeDepth = 16;
+
typedef struct Node {
+ GC_HEADER;
struct Node * left;
struct Node * right;
int i, j;
} Node;
-#ifdef GC_BDW
-#include "bdw.h"
-#else
-#error unknown gc
-#endif
+typedef struct DoubleArray {
+ GC_HEADER;
+ size_t length;
+ double values[0];
+} DoubleArray;
+
+static inline size_t node_size(void *obj) {
+ return sizeof(Node);
+}
+static inline size_t double_array_size(void *obj) {
+ DoubleArray *array = obj;
+ return sizeof(*array) + array->length * sizeof(double);
+}
+static inline void visit_node_fields(struct context *cx, void *obj,
+ field_visitor visit) {
+ Node *node = obj;
+ visit(cx, (void**)&node->left);
+ visit(cx, (void**)&node->right);
+}
+static inline void visit_double_array_fields(struct context *cx, void *obj,
+ field_visitor visit) {
+}
+
+typedef HANDLE_TO(Node) NodeHandle;
+typedef HANDLE_TO(DoubleArray) DoubleArrayHandle;
+
+static Node* allocate_node(struct context *cx) {
+ // memset to 0 by the collector.
+ return allocate(cx, NODE, sizeof (Node));
+}
+
+static struct DoubleArray* allocate_double_array(struct context *cx,
+ size_t size) {
+ // note, not memset to 0 by the collector.
+ DoubleArray *ret = allocate(cx, DOUBLE_ARRAY, sizeof (double) * size);
+ ret->length = size;
+ return ret;
+}
/* Get the current time in milliseconds */
static unsigned currentTime(void)
@@ -65,12 +113,6 @@ static unsigned currentTime(void)
return (t.tv_sec * 1000 + t.tv_usec / 1000);
}
-static const int kStretchTreeDepth = 18; // about 16Mb
-static const int kLongLivedTreeDepth = 16; // about 4Mb
-static const int kArraySize = 500000; // about 4Mb
-static const int kMinTreeDepth = 4;
-static const int kMaxTreeDepth = 16;
-
void init_Node(Node *me, Node *l, Node *r) {
init_field((void**)&me->left, l);
init_field((void**)&me->right, r);
@@ -87,57 +129,57 @@ static int NumIters(int i) {
}
// Build tree top down, assigning to older objects.
-static void Populate(int iDepth, Node *node) {
+static void Populate(struct context *cx, int iDepth, Node *node) {
if (iDepth<=0) {
return;
} else {
iDepth--;
NodeHandle self = { node };
- PUSH_HANDLE(self);
- NodeHandle l = { allocate_node() };
- PUSH_HANDLE(l);
- NodeHandle r = { allocate_node() };
- PUSH_HANDLE(r);
+ PUSH_HANDLE(cx, self);
+ NodeHandle l = { allocate_node(cx) };
+ PUSH_HANDLE(cx, l);
+ NodeHandle r = { allocate_node(cx) };
+ PUSH_HANDLE(cx, r);
set_field((void**)&HANDLE_REF(self)->left, HANDLE_REF(l));
set_field((void**)&HANDLE_REF(self)->right, HANDLE_REF(r));
- Populate (iDepth, HANDLE_REF(self)->left);
- Populate (iDepth, HANDLE_REF(self)->right);
- POP_HANDLE(r);
- POP_HANDLE(l);
- POP_HANDLE(self);
+ Populate (cx, iDepth, HANDLE_REF(self)->left);
+ Populate (cx, iDepth, HANDLE_REF(self)->right);
+ POP_HANDLE(cx, r);
+ POP_HANDLE(cx, l);
+ POP_HANDLE(cx, self);
}
}
// Build tree bottom-up
-static Node* MakeTree(int iDepth) {
+static Node* MakeTree(struct context *cx, int iDepth) {
if (iDepth<=0) {
- return allocate_node();
+ return allocate_node(cx);
} else {
- NodeHandle left = { MakeTree(iDepth-1) };
- PUSH_HANDLE(left);
- NodeHandle right = { MakeTree(iDepth-1) };
- PUSH_HANDLE(right);
- Node *result = allocate_node();
+ NodeHandle left = { MakeTree(cx, iDepth-1) };
+ PUSH_HANDLE(cx, left);
+ NodeHandle right = { MakeTree(cx, iDepth-1) };
+ PUSH_HANDLE(cx, right);
+ Node *result = allocate_node(cx);
init_Node(result, HANDLE_REF(left), HANDLE_REF(right));
- POP_HANDLE(left);
- POP_HANDLE(right);
+ POP_HANDLE(cx, right);
+ POP_HANDLE(cx, left);
return result;
}
}
-static void TimeConstruction(int depth) {
+static void TimeConstruction(struct context *cx, int depth) {
int iNumIters = NumIters(depth);
NodeHandle tempTree = { NULL };
- PUSH_HANDLE(tempTree);
+ PUSH_HANDLE(cx, tempTree);
printf("Creating %d trees of depth %d\n", iNumIters, depth);
{
long tStart = currentTime();
for (int i = 0; i < iNumIters; ++i) {
- HANDLE_SET(tempTree, allocate_node());
- Populate(depth, HANDLE_REF(tempTree));
+ HANDLE_SET(tempTree, allocate_node(cx));
+ Populate(cx, depth, HANDLE_REF(tempTree));
HANDLE_SET(tempTree, NULL);
}
long tFinish = currentTime();
@@ -148,7 +190,7 @@ static void TimeConstruction(int depth) {
{
long tStart = currentTime();
for (int i = 0; i < iNumIters; ++i) {
- HANDLE_SET(tempTree, MakeTree(depth));
+ HANDLE_SET(tempTree, MakeTree(cx, depth));
HANDLE_SET(tempTree, NULL);
}
long tFinish = currentTime();
@@ -156,54 +198,61 @@ static void TimeConstruction(int depth) {
tFinish - tStart);
}
- POP_HANDLE(tempTree);
+ POP_HANDLE(cx, tempTree);
}
int main() {
+ size_t kHeapMaxLive =
+ 2 * sizeof(struct Node) * TreeSize(kLongLivedTreeDepth) +
+ sizeof(double) * kArraySize;
+ double kHeapMultiplier = 3;
+ size_t kHeapSize = kHeapMaxLive * kHeapMultiplier;
+
+ struct context _cx;
+ struct context *cx = &_cx;
+ initialize_gc(cx, kHeapSize);
+
NodeHandle root = { NULL };
NodeHandle longLivedTree = { NULL };
NodeHandle tempTree = { NULL };
- HANDLE_TO(double) array = { NULL };
-
- PUSH_HANDLE(root);
- PUSH_HANDLE(longLivedTree);
- PUSH_HANDLE(tempTree);
- PUSH_HANDLE(array);
+ DoubleArrayHandle array = { NULL };
- initialize_gc();
+ PUSH_HANDLE(cx, root);
+ PUSH_HANDLE(cx, longLivedTree);
+ PUSH_HANDLE(cx, tempTree);
+ PUSH_HANDLE(cx, array);
printf("Garbage Collector Test\n");
- printf(" Live storage will peak at %zd bytes.\n\n",
- 2 * sizeof(struct Node) * TreeSize(kLongLivedTreeDepth) +
- sizeof(double) * kArraySize);
+ printf(" Live storage will peak at %zd bytes.\n\n", kHeapMaxLive);
printf(" Stretching memory with a binary tree of depth %d\n",
kStretchTreeDepth);
- print_start_gc_stats();
+ print_start_gc_stats(cx);
long tStart = currentTime();
// Stretch the memory space quickly
- HANDLE_SET(tempTree, MakeTree(kStretchTreeDepth));
+ HANDLE_SET(tempTree, MakeTree(cx, kStretchTreeDepth));
HANDLE_SET(tempTree, NULL);
// Create a long lived object
printf(" Creating a long-lived binary tree of depth %d\n",
kLongLivedTreeDepth);
- HANDLE_SET(longLivedTree, allocate_node());
- Populate(kLongLivedTreeDepth, HANDLE_REF(longLivedTree));
+ HANDLE_SET(longLivedTree, allocate_node(cx));
+ Populate(cx, kLongLivedTreeDepth, HANDLE_REF(longLivedTree));
// Create long-lived array, filling half of it
printf(" Creating a long-lived array of %d doubles\n", kArraySize);
- HANDLE_SET(array, allocate_double_array(kArraySize));
+ HANDLE_SET(array, allocate_double_array(cx, kArraySize));
for (int i = 0; i < kArraySize/2; ++i) {
- HANDLE_REF(array)[i] = 1.0/i;
+ HANDLE_REF(array)->values[i] = 1.0/i;
}
for (int d = kMinTreeDepth; d <= kMaxTreeDepth; d += 2) {
- TimeConstruction(d);
+ TimeConstruction(cx, d);
}
- if (HANDLE_REF(longLivedTree) == 0 || HANDLE_REF(array)[1000] != 1.0/1000)
+ if (HANDLE_REF(longLivedTree) == 0
+ || HANDLE_REF(array)->values[1000] != 1.0/1000)
fprintf(stderr, "Failed\n");
// fake reference to LongLivedTree
// and array
@@ -212,11 +261,11 @@ int main() {
long tFinish = currentTime();
long tElapsed = tFinish - tStart;
printf("Completed in %ld msec\n", tElapsed);
- print_end_gc_stats();
+ print_end_gc_stats(cx);
- POP_HANDLE(array);
- POP_HANDLE(tempTree);
- POP_HANDLE(longLivedTree);
- POP_HANDLE(root);
+ POP_HANDLE(cx, array);
+ POP_HANDLE(cx, tempTree);
+ POP_HANDLE(cx, longLivedTree);
+ POP_HANDLE(cx, root);
}
diff --git a/Makefile b/Makefile
index 819cf3f5d..c5573977c 100644
--- a/Makefile
+++ b/Makefile
@@ -1,5 +1,5 @@
TESTS=GCBench MT_GCBench MT_GCBench2
-COLLECTORS=bdw
+COLLECTORS=bdw semi
CC=gcc
CFLAGS=-Wall -O2 -g
@@ -11,6 +11,9 @@ all: $(ALL_TESTS)
bdw-%: bdw.h %.c
$(CC) $(CFLAGS) -lpthread `pkg-config --libs --cflags bdw-gc` -I.
-DGC_BDW -o $@ $*.c
+semi-%: semi.h %.c
+ $(CC) $(CFLAGS) -I. -DGC_SEMI -o $@ $*.c
+
check: $(addprefix test-$(TARGET),$(TARGETS))
test-%: $(ALL_TESTS)
diff --git a/bdw.h b/bdw.h
index aea294ac6..571f67639 100644
--- a/bdw.h
+++ b/bdw.h
@@ -12,14 +12,24 @@
#include <gc/gc.h>
-static Node* allocate_node(void) {
- // memset to 0 by the collector.
- return GC_malloc (sizeof (Node));
-}
+struct context {};
+
+enum alloc_kind { NODE, DOUBLE_ARRAY };
+
+typedef void (*field_visitor)(struct context *, void **ref);
-static double* allocate_double_array(size_t size) {
- // note, not memset to 0 by the collector.
- return GC_malloc_atomic (sizeof (double) * size);
+#define GC_HEADER /**/
+
+static inline void* allocate(struct context *cx, enum alloc_kind kind,
+ size_t size) {
+ // memset to 0 by the collector.
+ switch (kind) {
+ case NODE:
+ return GC_malloc(size);
+ case DOUBLE_ARRAY:
+ return GC_malloc_atomic(size);
+ }
+ abort();
}
struct handle {
@@ -29,15 +39,13 @@ struct handle {
#define HANDLE_TO(T) union { T* v; struct handle handle; }
#define HANDLE_REF(h) h.v
#define HANDLE_SET(h,val) do { h.v = val; } while (0)
-#define PUSH_HANDLE(h) push_handle(&h.handle)
-#define POP_HANDLE(h) pop_handle(&h.handle)
-
-typedef HANDLE_TO(Node) NodeHandle;
+#define PUSH_HANDLE(cx, h) push_handle(cx, &h.handle)
+#define POP_HANDLE(cx, h) pop_handle(cx, &h.handle)
-static inline void push_handle(struct handle *handle) {
+static inline void push_handle(struct context *cx, struct handle *handle) {
}
-static inline void pop_handle(struct handle *handle) {
+static inline void pop_handle(struct context *cx, struct handle *handle) {
}
static inline void init_field(void **addr, void *val) {
@@ -50,16 +58,22 @@ static inline void* get_field(void **addr) {
return *addr;
}
-static inline void initialize_gc(void) {
+static inline void initialize_gc(struct context* cx, size_t heap_size) {
// GC_full_freq = 30;
// GC_free_space_divisor = 16;
// GC_enable_incremental();
+ GC_INIT();
+ size_t current_heap_size = GC_get_heap_size();
+ if (heap_size > current_heap_size) {
+ GC_set_max_heap_size (heap_size);
+ GC_expand_hp(heap_size - current_heap_size);
+ }
}
-static inline void print_start_gc_stats(void) {
+static inline void print_start_gc_stats(struct context *cx) {
}
-static inline void print_end_gc_stats(void) {
+static inline void print_end_gc_stats(struct context *cx) {
printf("Completed %ld collections\n", (long)GC_get_gc_no());
printf("Heap size is %ld\n", (long)GC_get_heap_size());
}
diff --git a/semi.h b/semi.h
new file mode 100644
index 000000000..16bb8566c
--- /dev/null
+++ b/semi.h
@@ -0,0 +1,193 @@
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+#include <sys/mman.h>
+#include <unistd.h>
+
+struct handle {
+ void *v;
+ struct handle *next;
+};
+
+struct context {
+ uintptr_t hp;
+ uintptr_t limit;
+ uintptr_t base;
+ size_t size;
+ struct handle *roots;
+ long count;
+};
+
+static const uintptr_t ALIGNMENT = 8;
+
+static uintptr_t align_up(uintptr_t addr, size_t align) {
+ return (addr + align - 1) & ~(align-1);
+}
+
+#define GC_HEADER uintptr_t _gc_header
+
+enum alloc_kind { NODE, DOUBLE_ARRAY };
+
+typedef void (*field_visitor)(struct context *, void **ref);
+
+static inline size_t node_size(void *obj) __attribute__((always_inline));
+static inline size_t double_array_size(void *obj)
__attribute__((always_inline));
+static inline void visit_node_fields(struct context *cx, void *obj,
field_visitor visit) __attribute__((always_inline));
+static inline void visit_double_array_fields(struct context *cx, void *obj,
field_visitor visit) __attribute__((always_inline));
+
+static inline void clear_memory(uintptr_t addr, size_t size) {
+ memset((char*)addr, 0, size);
+}
+
+static void collect(struct context *cx, size_t bytes)
__attribute__((noinline));
+
+static void process(struct context *cx, void **loc);
+
+static void flip(struct context *cx) {
+ uintptr_t split = cx->base + (cx->size >> 1);
+ if (cx->hp <= split) {
+ cx->hp = split;
+ cx->limit = cx->base + cx->size;
+ } else {
+ cx->hp = cx->base;
+ cx->limit = split;
+ }
+ cx->count++;
+}
+
+static void* copy(struct context *cx, uintptr_t kind, void *obj) {
+ size_t size;
+ switch (kind) {
+ case NODE:
+ size = node_size(obj);
+ break;
+ case DOUBLE_ARRAY:
+ size = double_array_size(obj);
+ break;
+ default:
+ abort ();
+ }
+ void *new_obj = (void*)cx->hp;
+ memcpy(new_obj, obj, size);
+ *(uintptr_t*) obj = cx->hp;
+ cx->hp += align_up (size, ALIGNMENT);
+ return new_obj;
+}
+
+static uintptr_t scan(struct context *cx, uintptr_t grey) {
+ void *obj = (void*)grey;
+ uintptr_t kind = *(uintptr_t*) obj;
+ switch (kind) {
+ case NODE:
+ visit_node_fields(cx, obj, process);
+ return grey + align_up (node_size(obj), ALIGNMENT);
+ break;
+ case DOUBLE_ARRAY:
+ visit_double_array_fields(cx, obj, process);
+ return grey + align_up (double_array_size(obj), ALIGNMENT);
+ break;
+ default:
+ abort ();
+ }
+}
+
+static void* forward(struct context *cx, void *obj) {
+ uintptr_t header_word = *(uintptr_t*)obj;
+ switch (header_word) {
+ case NODE:
+ case DOUBLE_ARRAY:
+ return copy(cx, header_word, obj);
+ default:
+ return (void*)header_word;
+ }
+}
+
+static void process(struct context *cx, void **loc) {
+ void *obj = *loc;
+ if (obj != NULL)
+ *loc = forward(cx, obj);
+}
+static void collect(struct context *cx, size_t bytes) {
+ // fprintf(stderr, "start collect #%ld:\n", cx->count);
+ flip(cx);
+ uintptr_t grey = cx->hp;
+ for (struct handle *h = cx->roots; h; h = h->next)
+ process(cx, &h->v);
+ // fprintf(stderr, "pushed %zd bytes in roots\n", cx->hp - grey);
+ while(grey < cx->hp)
+ grey = scan(cx, grey);
+ // fprintf(stderr, "%zd bytes copied\n", (cx->size>>1)-(cx->limit-cx->hp));
+
+ if (cx->limit - cx->hp < bytes) {
+ fprintf(stderr, "ran out of space, heap size %zu\n", cx->size);
+ abort();
+ }
+}
+
+static inline void* allocate(struct context *cx, enum alloc_kind kind,
+ size_t size) {
+ while (1) {
+ uintptr_t addr = cx->hp;
+ uintptr_t new_hp = align_up (addr + size, ALIGNMENT);
+ if (cx->limit < new_hp) {
+ collect(cx, size);
+ continue;
+ }
+ cx->hp = new_hp;
+ void *ret = (void *)addr;
+ uintptr_t *header_word = ret;
+ *header_word = kind;
+ if (kind == NODE)
+ clear_memory(addr + sizeof(uintptr_t), size - sizeof(uintptr_t));
+ return ret;
+ }
+}
+
+#define HANDLE_TO(T) union { T* v; struct handle handle; }
+#define HANDLE_REF(h) h.v
+#define HANDLE_SET(h,val) do { h.v = val; } while (0)
+#define PUSH_HANDLE(cx, h) push_handle(cx, &h.handle)
+#define POP_HANDLE(cx, h) pop_handle(cx, &h.handle)
+
+static inline void push_handle(struct context *cx, struct handle *handle) {
+ handle->next = cx->roots;
+ cx->roots = handle;
+}
+
+static inline void pop_handle(struct context *cx, struct handle *handle) {
+ cx->roots = handle->next;
+}
+
+static inline void init_field(void **addr, void *val) {
+ *addr = val;
+}
+static inline void set_field(void **addr, void *val) {
+ *addr = val;
+}
+static inline void* get_field(void **addr) {
+ return *addr;
+}
+
+static inline void initialize_gc(struct context *cx, size_t size) {
+ size = align_up(size, getpagesize());
+
+ void *mem = mmap(NULL, size, PROT_READ|PROT_WRITE,
+ MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
+ if (mem == MAP_FAILED) {
+ perror("mmap failed");
+ abort();
+ }
+ cx->hp = cx->base = (uintptr_t) mem;
+ cx->size = size;
+ cx->count = -1;
+ flip(cx);
+ cx->roots = NULL;
+}
+
+static inline void print_start_gc_stats(struct context *cx) {
+}
+
+static inline void print_end_gc_stats(struct context *cx) {
+ printf("Completed %ld collections\n", cx->count);
+ printf("Heap size is %zd\n", cx->size);
+}
