Dynarec Update #3

Posted on 05 Jul 2011

Or how to reduce worst case (O(N)) showing up.

So I’ve managed to free up some memory and make mp_alloc super fast. Freeing up memory is in regard to mp_block (it used to be a node for a linked list type deal), but since I was already bulk allocating the entire linked list I figured why not get rid of the next pointer and make it a regular array; so I did.

Making it so the worst case doesn’t show up with mp_alloc had to do with reordering the array. I made it so available blocks are always at the start of the array (whether it’s 1 or 100 blocks doesn’t matter). It implemented by just swapping two blocks around by keeping track of the number of available blocks in a region.

//from mp_alloc
current->blocks_available--;
b = swap_blocks(&current->blocks[current->blocks_available], b);
return b->ptr;
//from mp_dealloc
b->used = 0;
swap_blocks(&r->blocks[r->blocks_available], b);
r->blocks_available++;

By doing this we limit the O(N) to mp_dealloc. This isn’t really a big problem cause the red-black tree that’s used for code lookup doesn’t allow duplicate keys, so instead of removing the node from the tree when that section of code is invalidated; just update it. I’ll have to add some stuff to make that possible for when exec memory blocks are being tracked.

I do have an idea to reduce mp_dealloc to O(log n) by, you guessed it - using a red-black tree. It would actually be a bastardisation of the array method I’m using now and a red-black tree. The one downside is it’d probably cost all the memory I just freed up and then some. It wouldn’t be a complete red-black tree implementation either since we know the number of nodes beforehand. The nodes would be ordered in memory with unused nodes appearing first (and it’ll be kept that way). This will keep mp_alloc fast and when mp_dealloc is called it’ll treat that block of memory as a red-black tree.

If I did decide to go in that direction, I’d need to rework handling of the red-black trees to work without having a parent pointer in the nodes to free up some more memory (I’m really trying to keep operational memory to a minimum).

Currently all the new improved code is sitting in the experimental branch on github mainly cause I’m not done playing. I’ll definately be trying out that whole array/tree amalgamation mainly cause I want to see how it’ll perform.

Peace. Out.

comments powered by Disqus