ref: 6dd50f970be88637fd2799ae8e2868c01002898e
parent: 28e7dd47d568908702264977d70860c25467fb6e
author: Peter Mikkelsen <peter@pmikkelsen.com>
date: Thu Jul 8 16:29:09 EDT 2021
Add a hash table to make the garbage collection faster
--- a/garbage.c
+++ b/garbage.c
@@ -5,6 +5,8 @@
#include "dat.h"
#include "fns.h"
+#define TableSize (1<<16)
+
typedef struct Allocation Allocation;
struct Allocation
{
@@ -15,6 +17,7 @@
Allocation *prev;
};
+static int hash(void *);
static void mark(void *);
static void freealloc(Allocation *);
static void markmodules(void);
@@ -25,7 +28,7 @@
static void markterm(Term *);
static void markbindings(Binding *);
-static Allocation *allocations;
+static Allocation *allocationtab[TableSize];
void *
gmalloc(ulong size)
@@ -35,11 +38,12 @@
a->reachable = 1;
a->data = malloc(size);
a->prev = nil;
- a->next = allocations;
- if(allocations)
- allocations->prev = a;
- allocations = a;
+ a->next = allocationtab[hash(a->data)];
+ if(a->next)
+ a->next->prev = a;
+ allocationtab[hash(a->data)] = a;
+
return a->data;
}
@@ -50,8 +54,11 @@
Allocation *a;
/* Start by marking all allocations as unreachable */
- for(a = allocations; a != nil; a = a->next)
- a->reachable = 0;
+ int i;
+ for(i = 0; i < TableSize; i++){
+ for(a = allocationtab[i]; a != nil; a = a->next)
+ a->reachable = 0;
+ }
/* Go through root pointers and mark all allocations found as reachable.
The root pointers are:
@@ -64,20 +71,28 @@
markchoicestack();
/* Free the allocations that were not marked as reachable */
- a = allocations;
- while(a != nil){
- if(a->reachable)
- a = a->next;
- else{
- Allocation *tmp = a;
- collected += a->size;
- a = a->next;
- freealloc(tmp);
+ for(i = 0; i < TableSize; i++){
+ a = allocationtab[i];
+ while(a != nil){
+ if(a->reachable)
+ a = a->next;
+ else{
+ Allocation *tmp = a;
+ collected += a->size;
+ a = a->next;
+ freealloc(tmp);
+ }
}
}
return collected;
}
+static int
+hash(void *i)
+{
+ return (uintptr)i % TableSize;
+}
+
static void
mark(void *ptr)
{
@@ -85,7 +100,7 @@
return;
Allocation *a;
- for(a = allocations; a != nil; a = a->next){
+ for(a = allocationtab[hash(ptr)]; a != nil; a = a->next){
if(a->data == ptr)
a->reachable = 1;
}
@@ -97,7 +112,7 @@
if(a->prev)
a->prev->next = a->next;
else
- allocations = a->next;
+ allocationtab[hash(a->data)] = a->next;
if(a->next)
a->next->prev = a->prev;