Code Optimization

Due Date: Monday, Nov 25th (in class)
Hardcopy only (no electronic submissions)

Late Penalty: 10% per day

This assignment involves code optimization and measurements. You will need to make some measurements (using gprof) and determine the effect of various changes to some provided C functions. The general idea is that you should think about some of the code optimization issues we discussed (and mentioned in Chapter 5) as well as patterns of memory access (and the resulting cache performance).

For each of the 3 functions listed below you are provided with C source code as a starting point. You should make measurements with gprof to establish a starting point for your comparisons. Next you should apply whatever changes you think make sense and make measurements of your new code. You should make one change at a time, then run some experiments (make some measurements) so that you can determine what changes actually make a difference. If you make a bunch of changes at once it will be impossible to determine which changes helped.

You need create a writeup that describes each of your experiments, including the following:

• The source code for the function being tested

• A description of how the function was invoked (matrix size, string lengths, etc).

• A summary of the results reported by gprof, including:

  • The number of times the function was called.
  • The average time/call.

• A brief description of why your modifications did (or did not) make any difference in the average time/call. This is the most important part of this assignment - you need to prove that you understand why the change did or did not make a difference.

IMPORTANT: Your job is to make changes to the code provided. You should NOT switch to a completely different algorithm. The code provided for each function is based on very simple, straightforward algorithms, you should try to speed up these algorithms by making a few small changes (one at a time). Do not simply replace them with more efficient algorithms.

For example: there are plenty of great substring detection algorithms that will outperform the function provided (no matter how well you optimize it). However, this is not an algorithm design assignment, this is a code optimization assignment!

Make sure that any changes you make to each function does not change what the function computes!

The three C functions you should start with are included below.

#include <string.h> /* needed for strlen */
/* Is p a substring of s? 
      returns 1 if p is a substring of s, 
      otherwise returns 0
*/
int substr(char s[], char p[]) {
  int i;
  int flag=0; /* assume we don't find p in s */

  /* look for the substring at each possible starting point. */
  for (i=0;i<strlen(s);i++) {
    if (strncmp(&s[i],p,strlen(p))==0) {
      // we found a match, set flag to 1
      flag=1;
    }
  }
  return(flag==1);
}

/* use whatever size you want, but don't use something too small
   or your measurements will probably not be reliable */
 
#define SIZE 100
typedef int mtx[SIZE][SIZE];

/* put the transpose of matrix a in b */

void transpose(mtx a, mtx b ) {
  int i,j,k;

  for (i=0;i<SIZE;i++) {
    for (j=0;j<SIZE;j++) {
      b[j][i] = a[i][j];
    }
  }
}

/* use whatever size you want, but don't use something too small
   or your measurements will probably not be reliable */
 
#define SIZE 100
typedef int mtx[SIZE][SIZE];

/* matrix multiplication. c=ab
   assumes that all of the matrices are the same
   size (and square).
*/
void matrix_mult(mtx a, mtx b, mtx c ) {
  int i,j,k;

  /* initialize c to all zeros */
  for (i=0;i<SIZE;i++) 
    for (j=0;j<SIZE;j++) 
      c[i][j]=0;

  /* do the multiplication */
  for (i=0;i<SIZE;i++) {
    for (j=0;j<SIZE;j++) {
      for (k=0;k<SIZE;k++) {
        c[i][j]+=a[i][k]*b[k][j];
      }
    }
  }
}

gcc -pg -o hw6substr hw6substr.c

gprof hw6substr

gprof -b hw6substr

/* assigns random integer values to
   the elements of a matrix.
   Use srandom() first if you want 
   to establish the seed used by the
   random number generator!
*/

#include <stdlib.h> /* for random, srandom */

void random_matrix(mtx x, int max) {
  int i,j;

  for (i=0;i<SIZE;i++)
    for (j=0;j<SIZE;j++) 
      x[i][j] = random()%(max+1);

}  

Your grade is based primarily on your understanding of why various optimizations made a difference (or why not). You should do all you can to optimize the code you have been given as a starting point, but keep in mind that your grade does not solely depend on how fast you can make the code run.

Each of the three functions count equally in the grading. To get full credit you must run experiments that produce meaningful results. This means you should not run each function a few times, think thousands (or more). Try to make sure that the total run time is at least 10 seconds for each experiment. You must describe your experiments in enough detail so that we can see what was measured, and can verify that your conclusions about the results are valid.