CS 208 s21 — Learning Block #13

Table of Contents

1 Warmup

For each of the following array accesses to the array pictured below, determine if it is a valid access and, if so, what value it returns.1

  1. sea[2][5]
  2. sea[4][-1]
  3. sea[0][19]

array-2d.png

Which of the following statements is FALSE?2

  1. sea[4][-2] is a valid array reference
  2. sea[1][1] makes two memory accesses
  3. sea[2][1] will always be a higher address than sea[1][2]
  4. sea[2] is calculated using only lea

2 Multi-level array exercise

For each of the following array accesses to the array pictured below, determine if it is a valid access and, if so, what value it returns.3

  1. sea[2][3]
  2. sea[1][5]
  3. sea[2][-2]

array-multilevel.png

3 struct exercises

struct-defrag.png

  • why does struct S4 have 3 bytes of padding added after c and after d?4
  • what kinds of fragmentation do struct S4 and struct S5 each have?5

struct-align-exercise.png

  • how would you reorder the fields of struct old in struct new to minimize the overall size of the struct?6

4 Practice

CSPP practice problems 3.41 (p. 268) and 3.45 (p. 275)

Footnotes:

1
  1. valid, 9 (start of row 2, then 5 ints forward)
  2. valid, 5 (start of the non-existent row 4, then 1 int backwards, thereby reference the valid element at the end of row 3)
  3. valid, 5 (start of row 0, then 19 ints forward, referencing the final int in the array)
2

2. is the false statement. The assembly for sea[1][1] will compute the address of that specific element and then make a single memory access to that address.

3
  1. valid, 0
  2. invalid, past the end of row 1 (and rows are not adjacent in memory in this multilevel array)
  3. invalid, past the start of row 2 (and rows are not adjacent in memory in this multilevel array)
4

The int i is 4 bytes, so it must have an address that's a multiple of 4. Hence, the compiler adds 3 bytes of padding after the 1-byte char c to achieve this. The size of the struct as a whole must be a multiple of the size of the largest field. Hence, the compiler adds 3 bytes of padding to the end.

5

S4 has both internal and external fragmentation, while S5 has just external.

6 
struct new {
    int i;
    float f;
    char *c;
    short s[3];
}

This would eliminate the internal fragmentation and leave just 2 bytes of external fragmentation.

  • sizeof(struct old) = 32 bytes (6 bytes of internal fragmentation, 6 bytes external)
  • sizeof(struct new) = 24 bytes (2 bytes external)