Mercurial > repos > rhope

changeset 41:1b86a1ee500a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added faster allocator for small objects
author Mike Pavone <pavone@retrodev.com>
date Sat, 10 Oct 2009 16:40:50 -0400
parents 789a146a48e1
children aabda74c7a88 b218af069da7
files runtime/block_alloc.h runtime/fixed_alloc.c runtime/fixed_alloc.h runtime/object.c runtime/object.h
diffstat 5 files changed, 242 insertions(+), 23 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/runtime/block_alloc.h	Sat Oct 10 16:40:50 2009 -0400
@@ -0,0 +1,13 @@
+#ifndef BLOCK_ALLOC_H_
+#define BLOCK_ALLOC_H_
+
+#ifdef _WIN32
+#define BLOCK_SIZE 1024*16
+#include <windows.h>
+
+#define block_alloc(size)      VirtualAlloc(NULL, size, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
+#define block_free(block,size) VirtualFree(block, size, MEM_RELEASE)
+
+#endif
+
+#endif //BLOCK_ALLOC_H_
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/runtime/fixed_alloc.c	Sat Oct 10 16:40:50 2009 -0400
@@ -0,0 +1,153 @@
+#include "fixed_alloc.h"
+#include <stdlib.h>
+
+uint16_t max_free[(MAX_SIZE-MIN_SIZE)/STRIDE];
+
+void fixed_alloc_init()
+{
+	int i;
+	for(i = 0; i < (MAX_SIZE-MIN_SIZE)/STRIDE; ++i)
+		max_free[i] = (BLOCK_SIZE - sizeof(mem_block)+1)*8/((i*STRIDE+MIN_SIZE)*8+1);
+}
+
+mem_manager * new_mem_manager()
+{
+	int i;
+	mem_manager * ret = malloc(sizeof(mem_manager));
+	memset(ret, 0, sizeof(mem_manager));
+	return ret;
+}
+
+void * falloc(size_t size, mem_manager * manager)
+{
+	uint16_t i,bit;
+	uint16_t bucket;
+	mem_block * block,*temp;
+	if(size > MAX_SIZE)
+		return malloc(size);
+	//puts("falloc");
+	size = ADJUST_SIZE(size);
+	bucket = (size-MIN_SIZE)/STRIDE;
+	block = manager->inuse[bucket];
+	if(!block)
+	{
+		block = manager->freelist;
+		if(block)
+		{
+			--manager->freecount;
+			manager->freelist = block->next;
+		}
+		else
+		{
+			block = block_alloc(BLOCK_SIZE);
+		}
+		manager->inuse[bucket] = block;
+		block->next = NULL;
+		block->last = NULL;
+		block->numfree = max_free[bucket];
+		block->firstfree = 0;
+		memset(block->bitmap, 0xFF, max_free[bucket]/8+1);
+	}
+	//printf("block: %X,numfree: %d, firstfree: %d, maxfree: %d\n", block, block->numfree, block->firstfree, max_free[bucket]);
+	/*if(block->numfree > max_free[bucket])
+	{
+		puts("uh oh!");
+		exit(1);
+	}*/
+	//find first free 
+	i = block->firstfree;
+	while(!block->bitmap[i])
+		++i;
+	//printf("i:%d,bitmap:%X\n", i, block->bitmap[i]);
+	bit = 0;
+	while(!((1 << bit) & block->bitmap[i]))
+		++bit;
+	//update free bitmask
+	block->bitmap[i] ^= 1 << bit;
+	//If current bitmap has no more free elements, set firstfree to the next bitmap
+	if(!block->bitmap[i])
+		block->firstfree = i+1;
+	else
+		block->firstfree = i;
+	--block->numfree;
+	if(!block->numfree)
+	{
+		//Remove from linked list if there are no more free elements
+		manager->inuse[bucket] = block->next;
+		if(block->next)
+			block->next->last = block->last;
+	}
+	i = i*8+bit;
+	//printf("%X\n", ((char *)block)+BLOCK_SIZE-((i+1)*size));
+	return (void *)(((char *)block)+BLOCK_SIZE-((i+1)*size));
+}
+
+void ffree(void * ptr, size_t size, mem_manager * manager)
+{
+	mem_block * block,*temp;
+	uint16_t i,bit,bucket;
+	if(size > MAX_SIZE)
+	{
+		free(ptr);
+		return;
+	}
+	//puts("ffree");
+	size = ADJUST_SIZE(size);
+	block = GET_BLOCK(ptr);
+	i = (((((char *)block) + BLOCK_SIZE) - ((char *)ptr))/size)-1;
+	bit = i & 0x7;
+	i = (i&0xFFFFFFF8) >> 3;
+	//printf("ptr:%X,block:%X,i:%d,bit:%d\n", ptr,block,bit,i);
+	block->bitmap[i] |= 1 << bit;
+	if(i < block->firstfree)
+		block->firstfree = i;
+	++block->numfree;
+	bucket = (size-MIN_SIZE)/STRIDE;
+	//printf("numfree:%d,max_free:%d,last:%X,next:%X\n", block->numfree, max_free[bucket], block->last, block->next);
+	/*if(block->numfree > max_free[bucket])
+	{
+		puts("uh oh!");
+		exit(1);
+	}*/
+	if(block->numfree == max_free[bucket])
+	{
+		//Block is now unused, remove it from the inuse list
+		if(block->last)
+			block->last->next = block->next;
+		else
+			manager->inuse[bucket] = block->next;
+		if(block->next)
+			block->next->last = block->last;
+		if(manager->freecount == MAX_FREE)
+			block_free(block, BLOCK_SIZE);
+		else
+		{
+			block->next = manager->freelist;
+			manager->freelist = block;
+			++manager->freecount;
+		}
+	} else if(block->numfree == 1) {
+		//Block was previously full, add it to the inuse list
+		block->next = manager->inuse[bucket];
+		block->last = NULL;
+		manager->inuse[bucket] = block;
+		if(block->next)
+			block->next->last = block;
+	} else if(block->next && block->next->numfree < block->numfree) {
+		//We want to use more filled blockes before less filled ones
+		//so we can return empty ones to the OS more often
+		//so if we now have more free nodes in this block than the 
+		//next one swap them
+		temp = block->next;
+		block->next = temp->next;
+		temp->last = block->last;
+		block->last = temp;
+		temp->next = block;
+		if(block->next)
+			block->next->last = block;
+		if(temp->last)
+			temp->last->next = temp;
+		else
+			manager->inuse[bucket] = temp;
+	}
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/runtime/fixed_alloc.h	Sat Oct 10 16:40:50 2009 -0400
@@ -0,0 +1,40 @@
+#ifndef FIXED_ALLOC_H_
+#define FIXED_ALLOC_H_
+
+#include <stddef.h>
+#include "plat_types.h"
+#include "block_alloc.h"
+
+#define GET_BLOCK(ptr) ((void*)(((uint32_t)(ptr))&(~(BLOCK_SIZE-1))))
+
+#define MAX_SIZE   (BLOCK_SIZE/32)
+#define STRIDE     (BLOCK_SIZE/1024)
+#define MIN_SIZE   (BLOCK_SIZE/1024)
+#define MAX_FREE   16
+
+#define ADJUST_SIZE(requested) (((requested)+(STRIDE-1)) & (~(STRIDE-1)))
+
+
+#pragma pack(push,1)
+typedef struct mem_block {
+	struct mem_block *next;
+	struct mem_block *last;
+	uint16_t         numfree;
+	uint16_t          firstfree;
+	uint8_t          bitmap[1];
+} mem_block;
+#pragma pack(pop)
+
+//num_elements = (BLOCK_SIZE - sizeof(mem_block)+1)*8/(sizeof(element)*8+1)
+typedef struct {
+	mem_block *freelist;
+	mem_block *inuse[(MAX_SIZE-MIN_SIZE)/STRIDE];
+	uint32_t freecount;
+} mem_manager;
+
+void fixed_alloc_init();
+mem_manager * new_mem_manager();
+void * falloc(size_t size, mem_manager * manager);
+void ffree(void * ptr, size_t size, mem_manager * manager);
+
+#endif //FIXED_ALLOC_H_
--- a/runtime/object.c	Fri Oct 09 01:01:26 2009 -0400
+++ b/runtime/object.c	Sat Oct 10 16:40:50 2009 -0400
@@ -3,11 +3,14 @@
 #include <stdlib.h>
 #include <string.h>
 #include <stdio.h>
+#include "fixed_alloc.h"
 
 blueprint ** registered_types = NULL;
 uint32_t max_registered_type = 0;
 uint32_t type_storage = 0;
 
+mem_manager * manager = NULL;
+
 returntype call_method(uint32_t methodid, calldata * params)
 {
 	int i;
@@ -125,19 +128,13 @@
 
 object * alloc_object(blueprint * bp)
 {
-	//TODO: Replace with something more performant
-	return malloc(bp->boxed_size);
-}
-
-void * alloc_variable(uint32_t size)
-{
-	return malloc(size);
+	return falloc(bp->boxed_size, manager);
+	//return malloc(bp->boxed_size);
 }
 
 void dealloc_object(blueprint * bp, object * obj)
 {
-	//TODO: Replace with something more performant
-	free(obj);
+	ffree(obj, bp->boxed_size, manager);
 }
 
 object * new_object(uint32_t type)
@@ -172,7 +169,7 @@
 	multisize * ret;
 	if(type >= max_registered_type || !registered_types[type])
 		return NULL;
-	ret = alloc_variable(sizeof(multisize) + type);
+	ret = falloc(sizeof(multisize) + size, manager);
 	if(ret)
 	{
 		bp = registered_types[type];
@@ -195,7 +192,7 @@
 	bp = get_blueprint(tocopy);
 	if(bp->size < 0) {
 		mtocopy = (multisize *)tocopy;
-		mcopy = alloc_variable(sizeof(multisize) + mtocopy->size);
+		mcopy = falloc(sizeof(multisize) + mtocopy->size, manager);
 		mcopy->size = mtocopy->size;
 		memcpy(((char *)mcopy)+sizeof(multisize), ((char *)mtocopy)+sizeof(multisize), mtocopy->size);
 		copy = (object *)mcopy;
@@ -214,7 +211,7 @@
 {
 	object * dest;
 	blueprint * bp = get_blueprint_byid(type);
-	if(!bp->size)
+	if(!bp->boxed_size)
 		return NULL; //We don't know how big a naked multi-size object is so we can't do anything with it
 	dest = alloc_object(bp);
 	memcpy(((char *)dest) + sizeof(object), rawdata, bp->size);
@@ -227,24 +224,16 @@
 void boxed_to_naked(object * src, void * dest)
 {
 	blueprint * bp = get_blueprint(src);
-	if(!bp->size)
+	if(!bp->boxed_size)
 		return; //We don't know how big a naked multi-size object is so we can't do anything with it
 	memcpy(dest, ((char *)src) + sizeof(object), bp->size);
 	bp->copy(src);
 }
 
-void free_object(object * obj)
-{
-	blueprint * bp = get_blueprint(obj);
-	if(bp->cleanup)
-		bp->cleanup(obj);
-	dealloc_object(bp, obj);
-}
-
 void release_ref(object * obj)
 {
 	if(rh_atomic_sub_testzero(obj, refcount, 1))
-		free_object(obj);
+		get_blueprint(obj)->free(obj);
 }
 
 void check_type_storage(type)
@@ -290,17 +279,40 @@
 {
 }
 
+void normal_free(object * obj)
+{
+	blueprint * bp = get_blueprint(obj);
+	if(bp->cleanup)
+		bp->cleanup(obj);
+	ffree(obj, bp->boxed_size, manager);
+}
+
+void multi_free(object * obj)
+{
+	multisize * multi = (multisize *)obj;
+	blueprint * bp = get_blueprint(obj);
+	if(bp->cleanup)
+		bp->cleanup(obj);
+	ffree(multi, sizeof(multi) + multi->size, manager);
+}
+
 blueprint * new_blueprint(uint32_t type, uint32_t size, special_func init, special_func copy, special_func cleanup)
 {
 	blueprint * bp = malloc(sizeof(blueprint));
+	//dirty hack!, move elsewhere
+	if (!manager) {
+		fixed_alloc_init();
+		manager = new_mem_manager();
+	}
 	if(bp)
 	{
 		bp->size = size;
-		bp->boxed_size = size >= 0 ? size + sizeof(object) : size;
+		bp->boxed_size = size >= 0 ? size + sizeof(object) : 0;
 		bp->method_lookup = bp->getter_lookup = bp->setter_lookup = bp->convert_to = bp->convert_from = NULL;
 		bp->init = init ? init : default_action;
 		bp->copy = copy ? copy : default_action;
 		bp->cleanup = cleanup ? cleanup : default_action;
+		bp->free = size >= 0 ? normal_free : multi_free;
 		bp->first_methodid = bp->last_methodid = bp->first_getfieldid = bp->last_getfieldid = bp->first_setfieldid = bp->last_setfieldid = bp->first_convertto = bp->last_convertto = bp->first_convertfrom = bp->last_convertfrom = 0;
 		//TODO: Handle names
 		bp->name = NULL;
--- a/runtime/object.h	Fri Oct 09 01:01:26 2009 -0400
+++ b/runtime/object.h	Sat Oct 10 16:40:50 2009 -0400
@@ -14,6 +14,7 @@
 	special_func   init;
 	special_func   copy;
 	special_func   cleanup;
+	special_func   free;
 	struct object  *name;
 	uint32_t       first_methodid;
 	uint32_t       last_methodid;