dynamic function execution

This is a discussion on dynamic function execution within the C Programming forums, part of the General Programming Boards category; I am working on a scientific project. Currently I am in the process of optimizing the program performance. The program ...

  1. #1
    Registered User Sargnagel's Avatar
    Join Date
    Aug 2002
    Posts
    166

    Question 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.
    Last edited by Sargnagel; 05-07-2003 at 03:33 AM.

  2. #2
    Registered User Sargnagel's Avatar
    Join Date
    Aug 2002
    Posts
    166
    damn, I forgot the attachment ...
    Attached Images Attached Images  
    Last edited by Sargnagel; 05-07-2003 at 04:55 AM.

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,434
    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).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User Sargnagel's Avatar
    Join Date
    Aug 2002
    Posts
    166
    Hey, that sounds like it will work.
    The 'exec' pointer is an elegant solution. I think it is better than building up a separate list.
    Thank you very much for your help, Salem!

    @shared subroutines:
    I am not quite sure, if I understand exactly what you mean. Do you mean a function that all other functions call?

    @branch prediction:
    I was referring to the switch ... case statements necessary to find out which function pointer to use, but I am sure you were aware of that:
    Code:
    switch(funclist.func)
    {
    	case FUNC1: funclist.f.func1(...); break;
    	case FUNC2: funclist.f.func2(...); break;
    	...
    }

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,434
    > 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
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Registered User Sargnagel's Avatar
    Join Date
    Aug 2002
    Posts
    166
    OK, I've uploaded an updated diagram.

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,434
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  8. #8
    Registered User Sargnagel's Avatar
    Join Date
    Aug 2002
    Posts
    166
    I think my explanations were not good enough.
    func6 depends on the results from func3 && func4. The 'exec' pointer concept will still work. The exec pointer from func3 will point to func4 and func4->exec will point to func6. The order in which functions, that are on the same level, are executed is not important.
    So, I guess your concept will still work.

    Thank you very much for your help, Salem.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Beginner Needs help in Dev-C++
    By Korrupt Lawz in forum C++ Programming
    Replies: 20
    Last Post: 09-28-2010, 01:17 AM
  2. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Replies: 3
    Last Post: 03-04-2005, 01:46 PM
  5. dynamic memory deletion via function
    By starkhorn in forum C++ Programming
    Replies: 4
    Last Post: 08-25-2004, 09:11 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21