Dynarec Update #4

Posted on 07 Jul 2011

Or fast as ballz memory pool.

The memory pool is now really close to O(1) allocation and deletion. As much as I’d like to take credit for it, I can’t. My friend Marcel Girgis (of Elysian Shadows) figured it out, I just applied it to the memory pool and asked a load of questions about it. I really wish I wasn’t so preoccupied thinking about the block list as recalculated.

So here’s how it goes. you have an array of ints (or chars or whatever) and initialise it to reflect what order you want the blocks to be allocated. Now you have a pivot variable this is initialised to zero on creation of a region (at least in my case). Now here’s where it get’s fun!

int A[12] = {0,1,2,3,4,5,6,7,8,9,10,11};
int pivot = 0; //must be persistent
//allocation
int temp_pivot = pivot;
pivot = A[pivot];
void *ret = (base+(sizeof(whatever)*pivot);
if(A[temp_pivot] != temp_pivot)
	A[temp_pivot] = temp_pivot;
else
	pivot++;
return ret;
//deallocation
int pointer_index = ptr - base / sizeof(whatever);
A[pointer_index] = A[pivot];
A[pivot] = pointer_index;

It’s surprisingly elegant isn’t it. On the surface it works great, except it doesn’t. The idea is sound it’s just the implementation is way off when it comes to reusing deallocated blocks. While it does create the ‘path’ to follow for reusing deallocated blocks, the code for allocation doesn’t actually follow it. Also after the block is allocated pivot is pointing to invalid memory. And since Marcel crashed I couldn’t point that out to him (except for the invalid memory one, I caught that early). But anyway I fixed it.

int A[12] = {0,1,2,3,4,5,6,7,8,9,10,11};
int pivot = 0; //must be persistent
//allocation
int temp_pivot = pivot;
pivot = A[pivot];
void *ret = (base+(sizeof(whatever)*pivot);
if(r->blocks[temp_pivot] == 11) //size-1
	pivot++;
else if(A[temp_pivot] != temp_pivot)
	pivot = A[temp_pivot];
else
	pivot++;
return ret;
//deallocation
int pointer_index = ptr - base / sizeof(whatever);
if(pivot == 12) pivot--; //makes it valid again (when max size it means full)
if(pointer_index == pivot) return; //if this is allowed to continue it'll lock up traversing memory.
A[pointer_index] = A[pivot];
A[pivot] = pointer_index;

So yeah, check that out. It’s extremely simplistic and elegant. This code came about when I asked him for thoughts on making mp_dealloc better than O(n). We threw around all kinds of ideas including making the block list a heap, a stack, a BST (my idea, wasn’t really set on it once I did the math on how much extra memory it would cost) and a bunch of other things. Then he says he’s trying to “find a uber math intensive way to solve it, efficient as fuck…intensive at design time, that is”. And that is the result. I’m kinda mad at myself for not figuring it out, but hey I was glad for the help and I got to fix it.

While he was off figuring that out, I was implementing the beginnings of executable memory block tracking for reuse. Right now the only thing done is the mechanism in which invalidated code lookup entries get removed (but not ‘deallocated’) from the code lookup red-black tree; then passed directly to execution memory’s red-black tree for insertion. Once I have block size tracking in I can make looking for adequate sized blocks easier and hopefully fast.

I’ve also made it so more than one instance of dynarec can be used at a time although you do have to use dynarec_switch for the simple fact I didn’t want to have to pass the struct to everything including the emitter functions. That very fact probably means I need to restructure my code, which I’ll deal with once everything is more or less operational.

The main reason I’m posting the above code is I really liked how simple and fast it was (easy on the memory to ;)). But I’m still playing.

Thanks again Marcel.

Peace. Out.

EDIT: I was wrong

So my fix wasn’t a total fix. It was if you knew you’d never completely deallocate an entire region (so the thing was empty). When you do, it breaks. By this time Marcel had emailed me back with a new 100% guaranteed to work version, which didn’t. So we both went off trying to fix it. We both came back with different solutions. His involved an extra block in the region to track the pivot. Mine involved changing the if statement for when the pivot and pointer index are the same. Here’s the new code, yes it’s a total 100% working version now - there were unit tests and everything (Marcel and I both had our own developed unit test).

//allocation
int temp_pivot = pivot;
pivot = A[pivot];
A[temp_pivot] = temp_pivot;

void *ret = (base+(sizeof(whatever)*pivot);
if(A[pivot] == pivot)
	pivot++;

if(pivot > BANK_SIZE)
{
	//add new region and return first block from that
}

return ret;
//deallocation
//this is pretty much the same, only difference is the if(pointer_index == pivot)
int pointer_index = ptr - base / sizeof(whatever);
if(pivot == 12) pivot--; //makes it valid again (when max size it means full)
if(pointer_index == pivot)
{
	pivot = A[pivot];
	return;
}
A[pointer_index] = A[pivot];
A[pivot] = pointer_index;

The fact that both versions Marcel came up with didn’t work out the box, is because he never actually implemented them. He only did mathematical proofs (proofs can be pretty evil). With proofs it’s easy to make a tiny mistake and have it come up as correct (this is why they’re evil).

When I say “they’re evil” what I’m really saying is “In my opinion, they’re evil”.

Laterz.

comments powered by Disqus