1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Code Runtime

  1. Nov 5, 2014 #1

    Zondrina

    User Avatar
    Homework Helper

    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. jcsd
  3. Nov 5, 2014 #2

    DaveC426913

    User Avatar
    Gold Member

    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
  4. Nov 5, 2014 #3

    Zondrina

    User Avatar
    Homework Helper

    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
  5. Nov 5, 2014 #4

    DaveC426913

    User Avatar
    Gold Member

    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
  6. Nov 5, 2014 #5

    Zondrina

    User Avatar
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Code Runtime
  1. Hamming Code (Replies: 1)

  2. Matlab code (Replies: 14)

  3. Fortran code (Replies: 1)

  4. Function / coding (Replies: 5)

Loading...