Code Runtime

1. Nov 5, 2014

Zondrina

1. The problem statement, all variables and given/known data

Not homework, but I'm wondering why a certain piece of code seems to run faster than another.

2. Relevant equations

3. The attempt at a solution

I'll mention a few relevant structs to be more clear:

Code (Text):

struct intlist {
int  *elems;
int  capacity;  /* Maximum number of elements in the list. */
int  size;       /* Current number of elements in the list */
};

typedef struct intlist IntList;

Here's a piece of code that prints out the heap allocated contents of elems:

Code (Text):

/* Print the list pointed to by parameter list to the console.
* Terminate the program via assert if list is NULL.
*/

void intlist_print(const IntList *list){
assert(list != NULL);

if(list->size == 0)
printf("[]");
else{
clock_t tic = clock();

printf("[");
for(int i=0;i<list->size;i++)
i != list->size-1 ? printf("%d ", list->elems[i]) :  printf("%d]", list->elems[i]);

clock_t toc = clock();
printf("\nElapsed time: %f seconds.\n", (double)(toc - tic) / CLOCKS_PER_SEC);
}
}

This code produces these results:

Code (Text):

Expected output: [1 5 -3 9 1 5 -3 9 1 5]
Actual output:  [1 5 -3 9 1 5 -3 9 1 5]
Elapsed time: 0.000002 seconds.

Now here's another piece of code, which does the same thing, but I originally thought would run faster:

Code (Text):

void intlist_print(const IntList *list){
assert(list != NULL);

if(list->size == 0)
printf("[]");
else{
clock_t tic = clock();

printf("[");
for(int i = 0; i < list->size-1; i++)
printf("%d ", list->elems[i]);
printf("%d]", list->elems[list->size-1]);

clock_t toc = clock();
printf("\nElapsed time: %f seconds.\n", (double)(toc - tic) / CLOCKS_PER_SEC);
}
}

The results are below:

Code (Text):

Expected output: [1 5 -3 9 1 5 -3 9 1 5]
Actual output:  [1 5 -3 9 1 5 -3 9 1 5]
Elapsed time: 0.000003 seconds.

So for large enough $n$, it would appear that the code without the implicit conditional runs slower for some reason. Why is this? I would think checking an extra if statement every loop would cost more time than simply iterating through the list and printing the contents. Is this related to something compiler or cpu specific?

2. Nov 5, 2014

DaveC426913

I am dubious about your conclusion. The time is only measured to one sig dig. What if it were measured to, say, 4 sig digs?

What if the actual values are
.000002999 versus .000003000?

Would you still wonder if one is meaningfully faster than the other?

Easy way to check. Run those sims on a list 1000 times the size.

Last edited: Nov 5, 2014
3. Nov 5, 2014

Zondrina

I ran some more tests for $n = 20 000$. The code without the conditional ran in 0.005440 seconds. The code with the conditional ran in 0.005241 seconds. The code with the conditional was faster for some reason.

To get a better sense I ran it with $n = 1 000 000$. The code without the conditional ran in 0.219394 seconds. The code with the conditional ran in 0.219831 seconds. Now the code without the conditional ran faster.

There appears to be some $n$ such that the efficiency of the conditional code falls below that of the more brute force approach. What's interesting is that for small enough $n$, the code with the conditional runs faster for some reason.

Last edited: Nov 5, 2014
4. Nov 5, 2014

DaveC426913

So, would you consider a 1-in-500 spread on a million record dataset to be of concern? Even if you scaled that up without limit, it's still 1-in-500 (or so). If one took 2 days to finish, would it matter if the other took 2 days and the other took 2 days plus 5 minutes...?

Or is this more of an academic interest?

The magic that happens with things like memory allocation and discrete operations in a processor and a language are pretty arcane. But there is probably some information out there about for loops and conditonals for most popular languages. Couldn't tell you though.

If you wanted to pursue it on your own,. I'd suggest paring the code down to its bare minimum so it's much more intuitive to see what's happening and to eliminate extraneous factors.

Last edited: Nov 5, 2014
5. Nov 5, 2014

Zondrina

This is purely out of academic interest. I've been looking into optimizing code for specific applications.

If you knew the size of the data set you could select the according algorithm.

On topic, I've heard that code can tend to behave differently on different machines. I'm looking around, but it all seems really specific.