Skip to main content
gamedev.net
🔒 Locked

need to write an efficient C function

Started by Glak 6 replies 1.5k views
Original Post
Glak
Glak
Hi, I'm making my own programming language and I need to implement a function that will run at run time. It will never be invoked by the user, only by the prologue of functions. I decided to write it in C instead of asm to keep it out of the core asm code. I am more of a C++ programmer so my C isn't that good. Basically everytime a function is constructed (functions are first class values) I need to grab a node off of the free list and move it into a tree. Usually when a function's destructor is called the node is pushed back onto the free list. However if a lexically nested function is still in existance I need to retain the node. This is all background information so it doesn't really matter. Anyway when the free list runs out I need to be able to get some more nodes in it quickly. Each node on the free list needs to have three 4-byte members. One should be zero (reference count), one can be filled with garbage, and the third needs to point to the next free node. This does not need to be portable at all. Ok so here is what I am thinking: 

#define node_count 100
#define byte_count node_count*12

int* new_nodes(void)
{
	int* p = malloc(byte_count);
	int* iter=p;
	int* end=p+byte_count;
	while(iter!=end)
	{
		iter[0]=0; //or does malloced memory come zeroed out?
		iter[2]=(int)(iter+3);
		++iter;
	}
	return p;
}
Is there something faster? Thanks (edited out a bug and used node count) [Edited by - Glak on March 27, 2007 5:19:55 PM]
jkleinecke
jkleinecke
I don't think you can get a ton faster than straight pointer manipulation. That being said I think you are over thinking the problem. Go ahead and code it up in C++ using methods and designs that you are familiar with, you'll have an easier time finding and fixing bugs that way. If at somepoint you discover a need for some optimization then rethink your code, you might discover that the time spent optimizing isn't necessary.

Now, if you insist on using the C call, here's a couple of changes I would make. Use a 'char*' to store the data instead of int, incrementing an int pointer will advance 4 bytes instead of just one.
Next, I would create a struct that is the size of the data that you want to create. Then all you have to do to create the memory is malloc( sizeof(STRUCT) ) and if you ever need to add a member to it your code doesn't need to change.
-----------------------------------Indium Studios, Inc.
Iftah
Iftah
your code does not use the node_count, or increase the iter *shrug*

any reason why you don't use structs?

anyway, if you had the refrence count just before the next pointer you could use 64bit instruction to asign both with one cycle (on 64bit machines), at least I think so. But that would probably need to be aligned to 64 bits, so maybe you could add another 4 bytes to the struct?

it would look something like -
typedef unsigned long u32;typedef unsigned long long u64;typedef struct {   u32  garbage;   u32  more_garbage;   union {     struct {        u32  refrence_count;        u32  next_ptr;  // NOT PORTABLE - not sure, maybe next_ptr should come first     } _2x32;     u64  _1x64;   } u;} cell;cell *array = (cell*)malloc(sizeof(cell)*num_of_cells);cell* iter = array;cell* end = &array[num_of_cells];while (iter != end){  iter->garbage = 0xabcdef;  // set both the reference count to zero and the next pointer in one command!  iter->u._1x64   = (u64)(iter+1);  // NOT PORTABLE!!!  ++iter; // next cell}//later - move a cell ptr to next cell and increase its reference countpcell  =  pcell->u._2x32.next_ptr;pcell->u._2x32.reference_count++;kinda clumsy I know... can be written clearer with some static_cast and less union
Glak
Glak
the reason that I didn't use a struct was that I want to be 100% sure of how the memory is laid out. This function will not be called from C, it will be called by assembly code generated by the compiler. Likewise I don't think that I will be able to know if it is fast enough. My program (a compiler) never calls this code; it inserts this code into your program when you use my language. So I don't want it to be slow because then people will think of my language as slow.

Iftah: thanks for catching those. I can't use your 64 bit idea because this compiler is targeting my current computer which is 32 bit. 64 bit compilers for my language are realistictly several years away if ever.

jkleinecke: I intend to increment it by four bytes so that is why I used int

thanks. I guess that I will stick with this code unless someone comes up with something better.
LessBread
LessBread
the reason that I didn't use a struct was that I want to be 100% sure of how the memory is laid out.

A pragma pack of the struct can resolve that by forcing a 1 byte alignment. Check your compiler documentation for pragma pack details.
"I thought what I'd do was, I'd pretend I was one of those deaf-mutes." - the Laughing Man
nagromo
nagromo
At the end of your while loop, you use '++iter;'. This will increment it to point to the next int. You don't want that; you want it to point at the next node. Instead, use 'iter += 3'.
Glak
Glak
LessBread: I'll look into pragma pack when I get a chance. I've just switched to djgpp gcc to get something that will work with nasm so I know nothing yet.
nagromo: Yes you are right, I will fix it, I guess writing code while posting doesn't lead to good code. Maybe I will get around to making it a struct and that will eliminate the bug

ok thanks guys
CadetUmfer
CadetUmfer
calloc gives zerod bytes so that may be faster that doing it yourself in the loop. Test first. Reversing your while loop will also shave a few instructions off.
Anthony Umfer

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.