Add a hash table to make the garbage collection faster

1 files changed, 33 insertions, 18 deletions

diff --git a/garbage.c b/garbage.c
index ce5bc17..714520c 100644
--- 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 @@ struct Allocation
 	Allocation *prev;
 };
 
+static int hash(void *);
 static void mark(void *);
 static void freealloc(Allocation *);
 static void markmodules(void);
@@ -25,7 +28,7 @@ static void markclauses(Clause *);
 static void markterm(Term *);
 static void markbindings(Binding *);
 
-static Allocation *allocations;
+static Allocation *allocationtab[TableSize];
 
 void *
 gmalloc(ulong size)
@@ -35,10 +38,11 @@ gmalloc(ulong size)
 	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 @@ collectgarbage(void)
 	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 @@ collectgarbage(void)
 	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 @@ mark(void *ptr)
 		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 @@ freealloc(Allocation *a)
 	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;