shithub: pprolog

Info  •  Files  •  Log  •  Branches

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;

-- 

⑨