Study Guide 6

Code Jams are open book. 40 minutes in lab.

Topics:

Everything from Study Guide 5, plus

  • Memory hierarchy, primary and secondary storage, caches, temporal and spatial locality

  • Advanced pointers, pointer arithmetic, void*, function pointers, pass by pointer

  • Implementations of malloc and free. sbrk()

  • Code optimization best practices

Practice questions

Advanced pointers

1) Draw a stack diagram for the following program. Show all intermediate values.

#include <stdio.h>

int main() {
  int vals[4] = {1,2,3,4};

  printf("-------\n");
  for (int* ptr = vals; ptr < vals+4; ptr++) {
    printf("%p %d\n", ptr, *ptr);
  }

  return 0;
}

2) Fix the error in the following program. Then draw the function stack and heap for the working program.

#include <stdio.h>

int main() {
  void *gen_ptr;
  int x = 3;
  char ch = 'a';

  gen_ptr = &x;  // gen_ptr can be assigned the address of an int
  gen_ptr = &ch; // or the address of a char (or the address of any type)

  int* int_ptr;
  int_ptr = &x;

  printf("The int value is %d\n", *int_ptr);
  printf("The char value is %c\n", *gen_ptr);
  return 0;
}

3) Fix the error in the following program. Then draw the function stack and heap for the working program.

#include <stdio.h>

int main() {
  int* value = NULL;
  printf("value is %d\n", *value);

  int a = 4;
  value = &a;
  printf("value is %d\n", *value);
}

4) Draw the stack and heap diagram for the following program.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct headerT {
  int a;
  int b;
};

struct studentT {
  char name[64];
  int age;
  float gpa;
};

int main() {

  void* data = malloc(sizeof(struct headerT) + 2 * sizeof(struct studentT));
  struct headerT* header = (struct headerT*) data;
  header->a = 5;
  header->b = 7;

  struct studentT* student = (struct studentT*) (header + 1);
  strncpy(student->name, "Bill", 4);
  student->age = 18;
  student->gpa = 3.3;

  student++;
  strncpy(student->name, "Carol", 5);
  student->age = 22;
  student->gpa = 3.6;

  free(data);
  // draw the stack and heap here
  return 0;
}

Memory

1) Short answers

  • What is the memory hierarchy?

  • What are some examples of primary storage?

  • What are some examples of secondary storage?

  • What is locality and what impact does it have on performance?

  • What is sbrk()? Why do we use functions such as malloc and free, rather than call sbrk() directly from our programs?

2) In the following code, which variables have temporal locality? spatial locality?

#include <stdio.h>

int main() {
    int i, size = 0;

    // declare array of 10 ints
    int my_arr[10];

    // set the value of each array element
    for (i = 0; i < 10; i++) {
        my_arr[i] = i;
        size++;
    }

    // set value at position 3 to 100
    my_arr[3] = 100;

    // print the number of array elements
    printf("array of %d items:\n", size);

    // print each element of the array
    for (i = 0; i < 10; i++) {
        printf("%d\n", my_arr[i]);
    }

    return 0;
}

3) Is the following program guaranteed to have good spatial locality? Why or why not?

#include <stdio.h>
#include <stdlib.h>

void init_matrix(int** m, int rows, int cols) {
  int i, j;
  for (i = 0; i < rows; i++) {  // for each row i
    for (j = 0; j < cols; j++) { // iterate over each column in row i
        m[i][j] = 0;
    }
  }
}

int main() {
  int nrows = 50;
  int ncols = 100;

  int** matrix = malloc(sizeof(int*) * nrows);
  for (int i = 0; i < nrows; i++) {
    matrix[i] = malloc(sizeof(int) * ncols);
  }

  init_matrix(matrix, nrows, ncols);

  for (int i = 0; i < nrows; i++) {
    free(matrix[i]);
  }
  free(matrix);
  matrix = NULL;
  return 0;
}

4) Does the following code efficiently access memory? Why or why not?

int array[N][N];
...
int sum = 0;
for (int i = 0; i < N; i++) {
  for (int j = 0; j < N; j++) {
    sum += array[j][i];
  }
}

Code optimization

Short answers

  • Give examples of the types of code that the compiler can optimize

  • Give an example of code that cannot be optimized by the compiler?

1) Ann-marie has the following errors when she tried to build. What type of error is it (compile, link, runtime, or logical)? How can she fix it?

/usr/bin/ld: /tmp/ccH1QHw0.o: in function `main':
thread-argv.c:(.text+0x1c4): undefined reference to `pthread_attr_setstacksize'
/usr/bin/ld: thread-argv.c:(.text+0x2e4): undefined reference to `pthread_create'
/usr/bin/ld: thread-argv.c:(.text+0x38d): undefined reference to `pthread_join'
collect2: error: ld returned 1 exit status

2) Can the compiler optimize the following code? If no, how can we make the following code more efficient?

char text[64];
scanf(" %s", text);
int sum = 0;
for (int i = 0; i < strlen(text); i++) {
  sum += text[i];
}