Thread: dynamic function execution

I am working on a scientific project. Currently I am in the process of optimizing the program performance. The program consists of many functions/sets of functions that produce a large amount of data. The user can choose via commandline parameters which results he/she needs. Sadly, all functions that are not needed to produce the requested results are executed too - this is not efficient. Of course, I have implemented some simple if(...) statements to reduce the amount of function call overhead, but most of the functions are highly interdependent. Simply setting sets of flags according to the requested results is much too complex.
I have attached a file that shows a simplified example of the kind of function interdependencies in my program. If you happen to know of an easy and/or proven solution, please tell me!

But at first here is my solution I am currently trying to implement ... there are some problems left though:

I hardcode the interdependencies of the functions in a tree-like structure (just look at the picture I've attached). A node represents a single function (except the root node):

Code:

typedef enum calc	{ROOT, FUNC1, FUNC2, FUNC3, FUNC4, FUNC5
					}CALC;

typedef struct node NODE;

struct node {
	NODE *prev;
	NODE *next;
	size_t size_prev;
	size_t size_next;
	CALC func;
};

Each node consists of a pointer to the previous node(s) - functions the current function depends on - and a pointer to the next node(s) - function(s) that depend(s)on the data produced by the current function. Furthermore, to avoid unnecessary string comparisons I choose an enum type variable to identify the function each node represents.
When the user executes the program, the tree-like structure is being built up. The commandline parameters are then used to search in the tree for the necessary functions and the order in which the functions must be executed.
As the program usually gets more than one data set as a source, I want to avoid traversing the tree again and again for each set. I thought about building up a "list" of the minimal function set in the order of execution in a continuous memory space - maybe an array of structures:

Code:

typedef union fnptrs FNPTRS;

union fnptrs {
	void (func1*) (struct foo1 *, const int);
	double (func2*) (struct foo2 *, const int, const int);
	double (func3*) (struct foo3 *, const int);
	int * (func4*) (struct foo3 *, const int);
	float (func5*) (struct foo4 *, const int);
};

struct funclist {
	CALC func; //from previous source code example
	FNPTRS f;
};

The structure consists of an union - which holds all function pointers - and an enum type variable you already know from the first source code example (appropriate function pointer in the union is initialized to point to the desired function).
Although, I still need to check each time I want to call a function, which function pointer in the union I have to execute. And that surely means a lot of branch prediction overhead ... just imagine 40 function pointers and 20000 data sets!
I do not know a better performing solution yet. I hope, you understood this long posting. Please, tell me if you need more information or if something is not making sense.

Thank you for your help.

damn, I forgot the attachment ...

This works if your tree has no shared subroutines (which your diagram does seem to imply)

Code:

struct node {
	NODE *prev;
	NODE *next;
	NODE *exec;  // added
	size_t size_prev;
	size_t size_next;
	CALC func;
};

I would try adding an 'exec' pointer, which forms a simple linked list through the tree. When you want to create a program, you walk the tree and append to the exec list those nodes which you want to execute.
Running the program is simply
while ( e ) { e->func(); e = e->exec; }

If you do have common subroutines, the alternative is to build the same list as a separate linked list, containing 'exec' pointers to appropriate nodes in your tree. Since the list is separate, nodes in your tree can be referenced multiple times.

> And that surely means a lot of branch prediction overhead
You lost (some) of the branch prediction when you went to a function pointer - the fact that you have a union of them doesn't really matter. If there is any prediction to be done, it will be when the register is finally loaded with an address (and not when the instruction is seen in the case of a normal function call).

> I am not quite sure, if I understand exactly what you mean.
Label all your boxes on your diagram, then I can tell you what I mean

Basically, func6 can be called from func3 and func4. If it has only one 'exec' pointer, and needs to be called from both places, then the 2nd attempt to use func6 will overwrite the 1st call to func6

Eg
3->6->10->4->6->10->7->11

Specifically in this case, updating 10->7 loses the 10->4 link

But if your dependencies are strictly a TREE (and not a more generalised DAG), then you should be OK.