CODEWITHSUNDEEP
coptimization
sl0815
sl0815

Reputation: 567

function pointers in loops

for my bachelor thesis I have written a program (in C) to sort large tables and now everything works as it should. For some of my test files, however, the program is a little slow. To be able to store temporary data more efficently, the user may specify a data type for each column of the table. Then the input data is first parsed into some binary format, then sorted and finally transformed back into its textual form.

For each data type one has to implement four functions (encode, decode, getlength and compare) and pointers to these are stored in an array for each column. So, to do anything with a row of the table, I have to call the correct function for each row in a loop, which has a fair overhead if the columns are rather short.

As an example, here is the code of my row compare function (called from qsort):

int line_cmp(const void *p1,const void *p2)
{
    int i,o1=0,o2=0,r;

    for(i=0;i<opt.nocols;i++)
        if((r=(*opt.cols[i].cmp)(*(char* const*)p1,&o1,
                                 *(char* const*)p2,&o2)))
            return r;

    return 0;
}

This function loops through all columns and if the called function returns a value other than 0 (meaning not equal) the value is returned (just like qsort demands).

Now my question is, how can this (or similar) function be optimized (if possible at all), especially when all the pointers are only setup once and then never changed during the whole program?

EDIT: I use function pointers so that it is possible for a third person to develop arbitrary data types. These would then be loaded through (dlopen, etc.). Thus, I can not think of a common binary format to compare columns and the binary data is just a black box for my program.

Upvotes: 2

Views: 1470

Answers (4)

Peter G.
Peter G.

Reputation: 15134

Is it possible to switch to C++?

I'm asking because the C++ STL's template sort algorithm usually leads to an inlined comparison and a nice performance boost. The difference ist most pronounced when comparing simple types like int.

If you have to stay with C you could try to get your hands at quicksort source code and embed a direct call of the comparison. This will manually achieve what STL and templates automatically do for you.

Having read your EDIT, I think you cannot really speed up the sort without some radical change like parallel sorting or requiring the user to supply the data in a better suited format.

One more idea: Perhaps you can speed up the sort by sorting successively according to the single columns. This could profit a fair amount from cache locality.

Upvotes: 0

Jonathan Wood
Jonathan Wood

Reputation: 67223

I don't see room for much optimization within the function you've posted. It is simply a for loop that calls a function each time through.

Calling a function pointer is efficient. Even if you had a common binary format that could be used to compare all item types, I doubt that would be much faster than calling a compare function specific for the current type.

One possible idea is to have your user-defined function compare all columns. That could eliminate the for loop in the function you posted. Although a similar loop may be required in the specialized function, reducing a number of calls may shave a little time. However, if a single row can have multiple types, that wouldn't work.

Beyond that, I suspect any further optimizations that could be made would be part of your code not posted here. I don't have enough information to know what, if any, could be made there.

Upvotes: 2

Jens Gustedt
Jens Gustedt

Reputation: 78923

You should check the assembler that your code produces, but you might have a problem of too many indirections, here, and also that the compiler has to reload the contents of opt.

Also depends a little bit on how your global opt is defined (const or not) how much the compiler is able to optimize. Since you have function calls between the iterative usage of opt the compiler wouldn't know if the value has changed.

Try to do something like

size_t nocols = opt.nocols
columnType const*const myFunc = opt.cols;

and use nocols and myFunc[i].comp for the loop.

Upvotes: 3

Steven Feldman
Steven Feldman

Reputation: 841

Make it Concurrent, upgrade your design to a Lock-Free Concurrent Sort. Maybe lock-free is more of a master leve project, if you can't think of a Lock-Free, go for a lock-based one.

Upvotes: 1

Related Questions