# HG changeset patch # User Mike Pavone # Date 1255207250 14400 # Node ID 1b86a1ee500a09664a45227157b43c809366a3d9 # Parent 789a146a48e12b78c3704c9f42b43724058eb7b8 Added faster allocator for small objects diff -r 789a146a48e1 -r 1b86a1ee500a runtime/block_alloc.h --- /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 + +#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_ diff -r 789a146a48e1 -r 1b86a1ee500a runtime/fixed_alloc.c --- /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 + +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; + } +} diff -r 789a146a48e1 -r 1b86a1ee500a runtime/fixed_alloc.h --- /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 +#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_ diff -r 789a146a48e1 -r 1b86a1ee500a runtime/object.c --- 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 #include #include +#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; diff -r 789a146a48e1 -r 1b86a1ee500a runtime/object.h --- 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;