Thread: Code review

  1. #1
    Registered User
    Join Date
    Oct 2009
    Posts
    8

    Code review

    Guys,
    I'm pretty new at C programming, nevertheless I am currently interviewing for an embedded sw position. As part of the interview I was given a coding exercise in C.
    I would appreciate if you guys could give some constructive feedback on coding and style. I'm open to any and all suggestions on style, good coding practices and code optimization (both for memory and performance).

    Thanks a lot!

    The Problem Statement:

    Implement a function in C to perform the computation described below. Then implement a program to test the function. The input data for the test program shall be provided in the file TEST.PRN, and consists of an array of floating point numbers, one per line. The output of the test program shall consist of the matrix II displayed to standard output, with one row of II being displayed per line. The test program shall provide for command line options to specify the input data file to be processed, and for the value of c and N.

    My Solution:

    If you look at the equation for the summation (in the file header comment), you will see that the solution matrix is actually symmetric, and mirrored about the array diagonal (from top left to bottom right). So, I decided to only allocate memory for a triangular array and compute only what is necessary. That's pretty much the only optimization that I can see. Any ideas are welcome. As for parallelizing, I was thinking to maybe use pthreads, but somehow I feel that may be a bit of overkill. On the other hand, it's for a job... so any ideas on that are also welcome!
    Code:
    /***************************************************************
     *
     * Dependencies: 
     *    - gcc version 4.3.3 (Ubuntu 4.3.3-5ubuntu4).
     *    - stdio.h
     *    - stdlib.h
     *    - math.h
     *
     * Purpose:
     * This program provides a command line interface to compute the
     * following function:
     * 
     *      II = SUM( I[i-col]*I[i-row] ) from i = c to i = N-1
     *      
     *      where   I is the input array (file name given by user)
     *              c is array dim given by user
     *              N is summation sentinel
     *      
     * the above three parameters are expected when invoking this 
     * program:
     *      <prog name> <input file name> <c> <N>
     *      
     ***************************************************************/
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <time.h> 
    
    
    /* defines for verification */
    #undef VERIFY
    #ifdef VERIFY
    #define VALIDATION_FILE "test.txt_299_300"
    #define VER_VALUE 1000000
    #endif
    
    
    /* Function declarations. 
     * explanations given in respective function header
     */
    void fnc(int c, int N, float *src, float **res);
    void printMatrix(int c, float **res);
    float * alloc1D(int N);
    float ** alloc2D(int c, int N);
    int initArray(int N, float *ar, char *fname);
    int checkArgs( int argc, char *argv[], int *c, int *N);
    int cleanup(float *src, float **res, int *c, int *N);
    
    #ifdef VERIFY
    int checkRes(int c, char fname[], float **res);
    #endif
      
    int main( int argc, char *argv[] ) {
      /* Variable declarations:.*/
      int *c;
      int *N;
      float *src;
      float **res;
      
      c = malloc(sizeof(*c));
      N = malloc(sizeof(*N));
    
      /* check arguments, allocate source and result array 
       * and initialize source array with data from file 
       */
      if (checkArgs(argc, argv, c, N)) return EXIT_FAILURE;
      if ((src = alloc1D(*N)) == NULL) return EXIT_FAILURE;
      if ((res = alloc2D(*c, *N)) == NULL) return EXIT_FAILURE;
      if ((*N = initArray(*N, src, argv[1])) == -1) return EXIT_FAILURE;
      
      /* start the timer and compute the function */
      clock_t start = clock();
      fnc(*c, *N, src, res);
    
      /* print out stats and result */
      fprintf(stdout, "\nCalculating II from file data: %s, with N = %d, c = %d\n", argv[1], *N, *c-1);
      printMatrix(*c, res);
      
    #ifdef VERIFY
      if (checkRes(*c, VALIDATION_FILE, res))
        fprintf(stdout, "\nValidation did not succeed!\nResult may be incorrect!\n");
      else
        fprintf(stdout, "\nResult validated (correct to within %f)!\n\n", (float)1/VER_VALUE);
    #endif
      printf("Execution time in seconds: %.15lf\n", ((double)clock()-start)/CLOCKS_PER_SEC);
      
      /* Finally, free allocated memory and return*/
      return cleanup(src, res, c, N);
    }
    
    
    /* fnc(): This is the actual computation of the sum.
     * 
     * args: c - specifies array size
     *       N - specifies sum sentinel
     *       *src - the source data
     *       **res - result data array
     * 
     * return: Nothing
     */
    void fnc(int c, int N, float *src, float **res) {
      int row, col, i;
      /* since the array is mirrored about the diagonal, 
      * we only compute part of the array.
      * this significantly reduces the computation time
      * and memory requirements
      * The inner-most for-loop computes the summation
      * SUM(I[i-col]*I[i-row]) from i = c to N-1 for
      * the bottom left triangle.
      */
      for (row = 0; row < c; row++) {
        for (col = 0; col < row+1; col++) {
          res[row][col] = 0;
          for (i = c-1; i < N; i++)
            res[row][col] += src[i-col]*src[i-row];
        } 
      }
    }
    
    /* checkArgs(): this function checks the command line
     * arguments for valid input. We also assign *c and *N
     * here.
     * 
     * args: argc - the # of args passed into main
     *       argv[] - the actual arguments
     *       *c - pointer to where c should be stored
     *       *N - pointer to where N should be stored
     *       
     * return: EXIT_FAILURE or EXIT_SUCCESS
     */
    int checkArgs(int argc, char *argv[], int *c, int *N) {
      /* the number of command line arguments must be not less and
      * not more than 4. <prog name> <input file> <N> <c>.
      * print out usage instructions and return.
      */
      if ( (argc < 4) | (argc > 4)) {
        fprintf(stderr, "Usage: %s <input file> <N> <c>\n", argv[0]);
        return EXIT_FAILURE;
      }
      /* we check here to make sure a valid file is provided
      * before doing anything else. 
      */
      if (!(fopen(argv[1], "r"))) {
        fprintf(stderr, "Cannot open file %s\n", argv[1]);
        return EXIT_FAILURE;
      }
      /* assign c and N, and make sure c < N
      * Note, it is assumed that these are ints
      * The program's behavior is undefined if these are not ints,
      * but does seem to handle invalid inputs gracefully.
      */
      if ((*c = atoi(argv[2])) > (*N = atoi(argv[3]))-1) {
        fprintf(stderr, "c must be strictly smaller than N!\n");
        return EXIT_FAILURE;
      }
      *c += 1;
      return EXIT_SUCCESS;
    }
    
    /* initArray(): loads the source data array with data from
     * the given file.
     * if N is specified to be larger than the number of data
     * elements found in the file, N will be capped to the
     * number of data elements.
     * returns *N, possibly modified, in case N is capped.
     * 
     * args: *N - the size of the array to be init'ed
     *       *ar - the pointer to the array to be filled
     *       fname[] - the filename to read data from
     *       
     * return: *N.  If the user specifies N greater than
     *              data available in fname, N is capped
     *              to reflect the nbr of data elements
     *                              NOTE: If fopen fails, -1 is returned.
     */
    int initArray(int N, float *ar, char fname[]) {
      int i = 0;
      FILE *fp = fopen( fname, "r");
    
      /* check if fopen succeeded, then read the file until the 
      * end-of-file (EOF) is reached or we have reached N
      */
      if (fp == NULL) {
        fprintf(stderr, "Cannot open file %s\n", fname);
        /* return -1 because we need to be able to check for failure 
         * (vs valid N) in checkRes if VERIFY is defined.
         */
        return -1;
      }
      while((fscanf( fp, "%f", &ar[i++]) != EOF) & ((i-1) < N)){}
      fclose(fp);
      /* if N is actually larger than the size of the data array, 
       * we return i so that N can be set to the actual number of 
       * data elements 
       * The reason for i-1 is that i is actually incremented once 
       * for EOF, so we need to sub 1 from i
       */
      if ((i-1) < N) {
        fprintf(stderr, "WARNING:\nWill only use the N=%d data elements found in %s\n", (i-1), fname);
        return i-1;
      }
      return N;
    }
    
    /* alloc1D(): allocates memory and error-check for the 1-d source
     * data array.
     * 
     * args: size - the size of the array to be allocated
     * 
     * return: pointer to the array initialized. May be NULL
     *         if malloc fails.
     */
    float * alloc1D(int size) {
      float *ar;
      /* try and allocate float array of size 'size', 
      * return pointer to start of array, return null if unsuccessful
      */
      if ((ar = malloc(sizeof(*ar)*(size+1))) == NULL){
        fprintf(stderr, "Could not allocate memory for 1D array!\n");
        return NULL;
      }
      return ar;
    }
    
    /* alloc2D(): allocates memory and error-check for the 2-D triangular 
     * array to hold the result data
     */
    float ** alloc2D(int c, int N) {
      int i = 0;
      float **ar = NULL;
    
      /* try and allocate memory for the row pointers of the
      * triangular array that stores the result 
      */
      if ((ar = (float **)alloc1D(c)) == NULL ) return ar;
      /* now we allocate memory for the columns.
      * since the result is actually mirrored about the top left to bottom right 
      * diagnoal, we only allocate memory for the bottome left triangle.
      * this saves memory and allows for faster computation.
      */
      for (i = 0; i < c; i++) {
        ar[i] = malloc(sizeof(**ar)*(i+1));
        if (ar[i] == NULL){
          fprintf(stderr, "Could not allocate 2-D memory for result data!\n");
          return NULL;
        }
      }
      return ar;
    }
    
    /* printMatrix(): prints out the triangular array as a full
     * square array.
     */
    void printMatrix(int c, float **res) {
      int row, col;
      printf("\n");
      for (row = 0; row < c; row++) {
        fprintf(stdout, "%s", (row==c/2)?"II =  |  ":"      |  ");
        for (col = 0; col < c; col++) {
          /* since we only computed part of the array, and the matrix has the 
          * property such that res[i][j] == res[j][i], we need to print
          * selectively depending on the relative values of row and col
          */
          fprintf(stdout, "%f  ", (row>col)?res[row][col]:res[col][row]);
        }
        fprintf(stdout, "|\n");
      }
      printf("\n");
    }
    
    /* cleanup(): deallocates all the allocated memory */
    int cleanup(float *src, float **res, int *c, int *N) {
      int i;
      
      if (src) free(src);
      if (N) free(N);
      if (res)
        for (i = 0; i < *c; i++)
          free(res[i]);
      free(res);
      if (c) free(c);
      return ((res == NULL) & (src == NULL) & (c == NULL) & (N == NULL));
    }
    
    /* checkRes(): given golden result in a file, this function
     * validates the computed result.
     * expects data from file in colum order. i.e.
     * 0
     * 1 3
     * 2 4 5
     */
    #ifdef VERIFY
    int checkRes(int c, char fname[], float **res) {
      float *gres;
      int row, col, k;
      int *n = malloc(sizeof(*n));
    
      fprintf(stdout, "Validating result against %s.\n", VALIDATION_FILE);
      /* triangular array size is c + (c-1) + ... + 1 */
      *n = 0;
      for (k = c; k > 0; k--)
            *n += k;
      /* try to allocate and initialize array for golden result */
      if ((gres = alloc1D(*n)) == NULL) {
        fprintf(stderr, "Could not allocate memory for golden result data!\n");
        return EXIT_FAILURE;
      }
      if ((initArray(*n, gres, fname)) == -1) return EXIT_FAILURE;
    
      /* compare computed result to golden result */
      k=0;
      for (col = 0; col < c; col++) 
        for (row = col; row < c; row++) {
          if ((fabs((double)res[row][col]-(double)gres[k]))*VER_VALUE > 1){
            return EXIT_FAILURE;
          }
          k++;
        }
        cleanup(gres, NULL, n, NULL);
        return EXIT_SUCCESS;
    }
    #endif
    Last edited by bennywhere; 10-18-2009 at 03:11 PM. Reason: modified code to reflect suggestions

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Why are you assuming the data is mirrored? Nothing in the description says anything about the data being mirrored.
    Code:
    void fnc(int c, int N, float *src, float **res) {
      int row, col, i;
      /* since the array is mirrored about the diagonal, 
      * we only compute part of the array.
      * this significantly reduces the computation time
      * and memory requirements
      * The inner-most for-loop computes the summation
      * SUM(I[i-col]*I[i-row]) from i = c to N-1 for
      * the bottom left triangle.
      */
      for (col = 0; col <= c; col++)
        for (row = col; row <= c; row++) {
        res[row][col] = 0;
        for (i = c; i < N; i++)
          res[row][col] += src[i-col]*src[i-row];
        } 
    }
    Why are you counting <=? If c = 5, you're going to actually be trying to screw with six values. That doesn't seem correct to me. Also, I would prefer you indent that second for loop's body one more level:
    Code:
    for...
        for...
            stuff...
            for...
                stuff...
    Because otherwise it just doesn't look right.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Oct 2009
    Posts
    8
    Hey there, thanks for the feedback!
    Yeah, I agree, I will fix the indentation.

    As for the mirroring, the problem doesn't say anything about it, but if you analyze the equation, you will see that the solution is actually mirrored.
    As for the c value, there is probably a clarification necessary. c is basically the starting value of the summation, and its solution is an array of c+1 by c+1.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I'm still not convinced on the array size / mirror issue, but if you are, that's good enough for me. (Edit: You also seem to just be adding 1 to everything, and doing a lot of <= ... so why not just increment C at the start and not have to do all of that?)

    You have a function to set up a 1D array, why not use it in your loop for you 2D array maker? You could argue either way, but I'm curious as to your decision on that one. (Think of me as your boss, asking why.)


    Quzah.
    Last edited by quzah; 10-17-2009 at 07:10 PM.
    Hope is the first step on the road to disappointment.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    How about some consistency on performing allocations?:
    Code:
    if (!(ar = malloc(sizeof(*ar)*(size+1)))){
    Code:
    if ((ar = malloc(sizeof(*ar)*(c+1))) == NULL ){
    Code:
    ar[i] = malloc(sizeof(**ar)*(i+1));
    if (ar[i] == NULL){
    Personally I think the last one, split over two lines, is best.

    You don't need to check a pointer for NULL before calling free.

    You may be over-commenting a little. Much of your commenting is of good quality, but I feel there is just a little too much. Or maybe it's just because there is no colouring to separate the comments from the code.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    I, too, believe you're over-commenting. And the variable names aren't too great. Pick better variable names and you'll only need one small comment every code block.

    I never comment variable declarations in functions, I always make sure it's clear what they do. In classes I do always comment it though, even if it's obvious.


    I think it's really hard to read:
    Code:
      /* First check command line arguments */
      if (checkArgs(argc, argv, c, N)) return EXIT_FAILURE;
      /* Args OK, so setup source data array */
      if ((src = setup1D(*N)) == NULL) return EXIT_FAILURE;
      /* Setup triangular result data array */
      if ((res = setup2D(*c, *N)) == NULL) return EXIT_FAILURE;
      /* Memory has been allocated, so load data from file into src */
      if ((*N = initArray(*N, src, argv[1])) == -1) return EXIT_FAILURE;
    And a lot clearer to read:
    Code:
      if (checkArgs(argc, argv, c, N)) return EXIT_FAILURE;
      if ((src = setup1D(*N)) == NULL) return EXIT_FAILURE;
      if ((res = setup2D(*c, *N)) == NULL) return EXIT_FAILURE;
      if ((*N = initArray(*N, src, argv[1])) == -1) return EXIT_FAILURE;
    The function names describe what you're doing (well, setup1D/setup2D might have a better possibity as a name, or you might add a comment above the whole block for that). But to me, this provides consistency. It's obviously initialisations where you exit with a failure if it goes wrong. Those comments just clutter it.

    Also, I personally make sure I always have a blank line above any comment that spans an entire line. The only exception is comments like:
    Code:
      int test;                       //!< A test variable
    Last edited by EVOEx; 10-18-2009 at 04:21 AM.

  7. #7
    Registered User
    Join Date
    Oct 2009
    Posts
    8
    Thanks a lot for all your suggestions.

    As for the commenting:
    I usually tend to comment sparingly, and was told by a friend to comment more... So, I guess I just gotta find a good middle grounds.

    As for the mirrored matrix:
    The equation is:
    Code:
    II = SUM( I[i-col]*I[i-row] ) from i = c to i = N-1
    so, for c = 4, this results in the solution matrix:
    Code:
    0 0  0 1  0 2  0 3  0 4
    1 0  1 1  1 2  1 3  1 4
    2 0  2 1  2 2  2 3  2 4
    3 0  3 1  3 2  3 3  3 4
    4 0  4 1  4 2  4 3  4 4
    And since I[0]*I[4] == I[4]*I[0], and both of these locations go from c to N-1, both location 4 0 and 0 4 are the same.

    This is a (correct) output when c = 4 and N = 300:
    Code:
           |  0.279525  0.276682  0.268098  0.254212  0.235722  |
           |  0.276682  0.280218  0.277855  0.269717  0.256231  |
    II =  |  0.268098  0.277855  0.281863  0.279912  0.272113  |
           |  0.254212  0.269717  0.279912  0.284270  0.282571  |
           |  0.235722  0.256231  0.272113  0.282571  0.287076  |
    And the first few lines of input (as given in the file):
    0.0532925166190
    0.0516683794558
    0.0476902537048
    0.0413647554815
    0.0329319946468
    0.0228458903730
    0.0117255663499
    0.0002848691074

    Now, mostly I have gotten style/coding practices feedback. Are there any performance optimizations that you guys notice?
    One thing in particular: If N gets large, each inner most for loop in fnc() accesses the large source array, which potentially could lead to thrashing the cache. Would it make sense to first compute the result for c to N-1/2 and then from (N-1/2)+1 to N-1? Or something along those lines?
    Any feedback is highly appreciated!

    Thanks!
    Last edited by bennywhere; 10-20-2009 at 09:32 AM. Reason: Added clarification

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I would have liked to see sample input and output, because the description they've given is that from the file you're going to be given an array of floating point numbers, one per line:

    1.1 2.2 3.3 4.4
    3.4 5.2 6.7 9.8

    But no where does it say you're going to end up with mirrored data.

    Edit: You could always just use a single dimension array, and use a bit of row/col math on it. You'd only need a single loop that way.


    Quzah.
    Last edited by quzah; 10-19-2009 at 02:34 PM.
    Hope is the first step on the road to disappointment.

  9. #9
    Registered User
    Join Date
    Oct 2009
    Posts
    8
    quzah: I agree, it does not say that the result is mirrored... but usually problems don't scream at you where they leave room for potential optimization.
    Anyway, could you elaborate on the single loop approach? Thanks a lot!

    Oh, and another question. Since I have that alloc1D() function that returns a pointer to a float array, is it ok to do the following:
    Code:
     
    int *someInt = (int *)alloc1D( someArg );
    So, obviously this works, but what do I actually get? A float pointer or int pointer that has room for float??
    Thanks for clarification
    Last edited by bennywhere; 10-20-2009 at 07:35 PM.

  10. #10
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by bennywhere View Post
    q
    So, obviously this works, but what do I actually get? A float pointer or int pointer that has room for float??
    Thanks for clarification
    This is wrong.

    It works because usually an int is the same size as a pointer, but you did not get either thing. You got an int, not any kind of pointer:
    Code:
    int someInt = (int *)alloc1D( someArg );
    The cast is irrelevant -- you cannot change a datatype that way. Eg:
    Code:
    float X = (char*)whatever;
    Should throw a warning (at least). Regardless, "X" remains a float. You could (try and) use it like a char pointer later but you will always have to cast it:
    Code:
    (char*)X;
    Basically it is a pointless and awkward thing to do.

    Ie. all you are doing is putting an address into an int, since all addresses are integer values.
    Last edited by MK27; 10-20-2009 at 10:03 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by bennywhere View Post
    Anyway, could you elaborate on the single loop approach? Thanks a lot!
    Say you have an array of ROW by COL. Instead of allocating a 2D array, with both ROW and COL dimensions, you can just allocate a 1D array that is ROW*COL in length. Then, to run through the whole thing, you do:
    Code:
    for( counter = 0; counter < ROW*COL; counter++ )
        printf( "array[ %d ][ %d ] is %d\n", (counter / COL), (counter % COL), array[ counter ] );

    Quzah.
    Hope is the first step on the road to disappointment.

  12. #12
    Registered User
    Join Date
    Oct 2009
    Posts
    8
    MK27: Of course it should have read int *someptr = (int *)alloc1D(1);
    is that still wrong? I mean all that malloc really does is allocate memory for 1 float (in the alloc1D()), and return a pointer to it. Since ints and floats are usually(??) 4 bytes, there's no real difference... or is there?

    Thanks so much for the help!

  13. #13
    Registered User
    Join Date
    Oct 2009
    Posts
    8
    Quote Originally Posted by quzah View Post
    Say you have an array of ROW by COL. Instead of allocating a 2D array, with both ROW and COL dimensions, you can just allocate a 1D array that is ROW*COL in length. Then, to run through the whole thing, you do:
    Code:
    for( counter = 0; counter < ROW*COL; counter++ )
        printf( "array[ %d ][ %d ] is %d\n", (counter / COL), (counter % COL), array[ counter ] );

    Quzah.
    Would you say that provides any significant optimization? In the meanwhile I have parallelized this code with pthreads. So, with my mirroring (yes, it is indeed mirrored ;-) ), I can cut execution time into a bit more than half of the original full array computation. With pthreads I can get another almost 50% reduction in time.

    Thanks for the feedback

  14. #14
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You were worried about the cache with the looping involved.
    One thing in particular: If N gets large, each inner most for loop in fnc() accesses the large source array, which potentially could lead to thrashing the cache
    I was only suggesting using a single array in case it would help with that.

    You mention this is for embedded programming. Is the speed you get by using pthreads worth the additional overhead required to use multiple threads instead of just one?


    Quzah.
    Hope is the first step on the road to disappointment.

  15. #15
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Why do you list "gcc version 4.3.3" as a dependency? Are you trying to say that your code is non-portable?

    Why do you list the specific header files as dependencies? Is the fact that the source module includes these files not enough evidence? Anybody who updates your source module to include some new header has to make the update in two places -- the actual #include list, and the comment header at the front.

    The sense I get as an imaginary interviewer, is that you're trying too hard.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Code Review for upcoming contest
    By Darryl in forum Contests Board
    Replies: 2
    Last Post: 02-28-2006, 02:39 PM
  2. Problem : Threads WILL NOT DIE!!
    By hanhao in forum C++ Programming
    Replies: 2
    Last Post: 04-16-2004, 01:37 PM
  3. True ASM vs. Fake ASM ????
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 04-02-2003, 04:28 AM
  4. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 05:06 PM
  5. Replies: 0
    Last Post: 02-21-2002, 06:05 PM