1 Background

Speed vs ease of use in programming languages

Python was designed to be easy to use, at the expense of speed; the theory was that often, it's OK if the program runs a couple seconds slower if it took the programmer several hours less to write it. On the other side of this tradeoff is the other language you know, C, which is extremely fast once written, but more difficult to program.

Much of the difference comes from the amount of work each language does for you. For example, in C, you have to allocate and free memory yourself for objects and arrays. In Python, the language does it for you. This is easier on the programmer, but it takes additional overhead to do so, making the program slower.

So this must mean that there's a program which is running your Python program, so that it can figure out what needs to be done for you. And there is! And to minimize overhead, it'd be good if it was fast, and written in C. And it is! This means that every line of Python you write is interpreted, and implemented with equivalent lines of C before those lines are then run.

Review: structs in C

Unlike Python, C is not an object-oriented language, so there are no classes to work with with fields and methods. The best C has to offer is a struct, which is a way of combining multiple pieces of data into one. Think of it as a class with no methods.

For example, here's a very simple C program that declares a struct to store football scores and has a simple function to deal with it. Notice that structs can be allocated and de-allocated with malloc and free (which you should already be familiar with) and you can use the -> operator to access member fields from a pointer to a struct.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <stdio.h>
#include <stdlib.h>
 
// here is the struct declaration.
// The name of the struct is "struct score"
// and the three fields are defined within.
struct score {
  int touchdowns;
  int PATs;
  int fieldgoals;
};
 
// This is a function to add up the points in a score
void print_total(struct score* thescore) {
  int tdpts = thescore->touchdowns * 6;
  int PATpts = thescore->PATs;
  int fgpts = thescore->fieldgoals * 3;
  int total = tdpts + PATpts + fgpts;
  printf("The total score is %d.\n", total);
  printf("The kicker scored %d of them.\n", fgpts + PATpts);
}
 
int main() {
  // allocate a new score struct
  struct score* thescore = malloc(sizeof(struct score));
 
  // assign the fields
  thescore->touchdowns = 7;
  thescore->PATs = 7;
  thescore->fieldgoals = 1;
 
  // call the function
  print_total(thescore);
 
  // de-allocate the memory with free
  free(thescore);
 
  return 0;
}

Make sure you review how this works and ask questions if you don't understand anything!

Pythonic Lists and C Arrays

In SY201, you learned about lists in Python, which can do lots of useful things, including change size when items are added or removed. When you learned about C, you learned about arrays, which can't do any of those things. Surprisingly, Python's lists are just implemented with arrays. So when we do, for example, an append to a Python list, how does that work? How long does it take? And here we get to the point: In order to understand the runtime of list operations, we have to understand what operations are being performed that Python is hiding from us.

Here is a pretty simple Python program. Hopefully you can see what it does.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import sys
import time
 
if __name__ == "__main__":
    # use the first command-line argument as the list size
    n = int(sys.argv[1])
    # the second command-line argument (if present) means to print stuff out
    debug = len(sys.argv) >= 3
 
    lst = []
    start = time.process_time() # start timer
    for i in range(n):
        num = 2*i + 7
        lst.append(num)
        if debug:
            print(lst)
    end = time.process_time() # end timer
 
    elapsed = end - start
    print(elapsed)

If we were to write a program which performs the same task in C, how would we do it?

Approach 1: Well, appending is pretty fast with a Linked List. Could we do that with C? Sure, using structs and pointers, we could do that. But not at first

Approach 2: The other main option is arrays. What if every time we tried to perform an append on an array, we made a new array large enough to contain one more element, and then move everything over? That would work.

Approach 3: For this, let's target what might be bad about Approach 2. In Approach 2, every single append requires making a new array, and re-filling it. Ouch. What if we changed it so that rather than allocating one more element's worth of space, when we ran out of space we added five empty spaces? Now, the next several appends will be fast, because there are empty, already allocated spaces to put that data in.

Approach 4: What if we changed it so that rather than allocating five more elements' amount of space when we run out of room, we made the array twice as big? Like Approach 3, there'd be lots of empty spaces, just an increasing number as \(n\) gets larger.

2 Implementing options 2-4 in C

Take the above python program, and place it in a file called pylist.py. You'll now write three C programs, array1.c, array5.c, and array_double.c.

Increasing size by one every time

array1.c will be an implementation of Approach 2 above. I've started it for you here; you just need to fill in the function append.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
// struct to hold an array and save its length
struct list {
  int* array;
  int length;
};
 
// helper function to print out a list
void print_list(const struct list* lst) {
  int i;
  printf("[");
  if (lst->length >= 1) printf("%d", lst->array[0]);
  for (i = 1; i < lst->length; ++i) printf(", %d", lst->array[i]);
  printf("]\n");
}
 
/* append() takes in a pointer to a list struct and an element to be added 
 * to the array. For array1, you want to increase the array size by 1 every
 * time. This means allocating a new array that is one larger, copying 
 * everything over, adding the new element, and then calling free() to
 * de-allocate the old array. Finally, you want to re-assign the two fields
 * "array" and "length" in the list struct to their new values.
 */
void append(struct list* lst, int num) {
  // delete this comment - you have to write this method!
}
 
int main(int argc, char *argv[]) {
  int n;
  sscanf(argv[1], "%d", &n); //store the first argument as n
 
  // if there is a second argument (no matter what it is), make "debug" equal 1
  int debug = (argc >= 3);
 
  struct list* lst = malloc(sizeof(struct list)); // allocate space for the list struct
  lst->length = 0; // array starts off size 0
  lst->array = malloc(lst->length * sizeof(int)); //allocate that much space
 
  // start a timer
  clock_t start = clock();
 
  int i;
  for(i = 0; i < n; ++i) {
    int num = 2*i + 7;
    // call append() to add num to the array
    append(lst, num);
 
    // if we had a second argument, print out the current contents of the array
    if (debug) print_list(lst);
  }
 
  // end the timer
  clock_t end = clock();
  double elapsed = difftime(end, start) / CLOCKS_PER_SEC;
  printf("%lf\n", elapsed);
 
  free(lst->array); // we're done with the array, so de-allocate it
  free(lst); // now free the struct itself
 
  return 0;
}

Notice that when it runs, it uses the int argc and the string array argv to deal with command-line arguments. The first argument tells how many times to append something, and the existence of a second argument causes it to print the elements of the array after each step. If I run my solution, with a second argument, I get this:

$ ./array1 5 anything
[7]
[7, 9]
[7, 9, 11]
[7, 9, 11, 13]
[7, 9, 11, 13, 15]
0.000022

The number on the very last line is the time it took (in seconds). If you run it without the second argument (./array1 5 for example) it does exactly the same amount of work, it just doesn't print anything out except for the time.

Compile with the following command:

gcc -Wall -Wextra -g -O2 -o array1 array1.c

(The -Wall and -Wextra flags print out extra warning messages that can be really useful to find bugs in your code. The -g flag will help if you need to do debugging/backtraces, and -O2 tells the compiler to do some optimizations to make your program faster.)

As a reminder, malloc allocates space, and free deallocates it. Everything which is allocated should be deallocated.

If you want, you can use the valgrind program to help you find any memory errors or leaks. For example, with my sample solution, I get:

$ valgrind --leak-check=full ./array1 100
==12762== Memcheck, a memory error detector
==12762== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==12762== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==12762== Command: ./array1 100
==12762==
0.003101
==12762==
==12762== HEAP SUMMARY:
==12762==     in use at exit: 0 bytes in 0 blocks
==12762==   total heap usage: 102 allocs, 102 frees, 20,216 bytes allocated
==12762==
==12762== All heap blocks were freed -- no leaks are possible
==12762==
==12762== For counts of detected and suppressed errors, rerun with: -v
==12762== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

If my program had memory leaks, they would show up with additional information about what was causing the memory error or leak.

Five at a time

array5.c will be an implementation of Approach 3. Alter your array1.c program so that it performs append() in that way, only building a new array when the old one is already full. You'll have to add another field to the struct list definition, as the size of the array and the number of items which have been stored in the array are now not always the same. You'll also need to modify the part in main to initialize this new field.

Compile with the following command:

gcc -Wall -Wextra -g -O2 -o array5 array5.c

Doubling the size

array_double.c will be an implementation of Approach 4. A correct implementation of array5.c should make this modification fairly straightforward.

Compile with the following command:

gcc -Wall -Wextra -g -O2 -o array_double array_double.c

3 Run-time analysis

Once you're confident they are working correctly for small values of \(n\), we need to think about the running times of these three approaches. The bash script timer.sh will run one of your three programs (depending on which line is uncommented), for increasing values of \(n\), and print out a table, in TSV (tab-separated values) format. When saved to a file, such a file is openable either by a text editor or a spreadsheet program like Excel. You can simultaneously see the program running and save its output to a file by doing:

$ ./timer.sh | tee savedfile.tsv

You should run this (editing the script each time accordingly) to create the files pylist.tsv, array1.tsv, array5.tsv, and array_double.tsv, and include all these in your submission for the lab.

After running this script for all four programs, have a look at (or graph) the values within and answer the following questions in a file called README.txt.

1. What is the total runtime of calling append \(n\) times in array1? Explain your answer.
2. Do the same for array5.
3. Do the same for array_double.
4. Which approach do you think is most similar to the implementation of append in Python? Why?
5. The timing script runs your programs with up to 1 million insertions. Even 1 million is small potatoes in large-scale data collection and analysis these days.
   Without actually running anything, estimate (for all four programs) how long they would take with 1 billion insertions (which would be 4GB of data - still pretty small really!).

4 Going farther

The rest of this lab is optional for your enrichment and enjoyment. Be sure to work on this only after getting everything else perfect. You should still submit this work, but make sure it doesn't break any of the parts you already had working correctly!

Linked lists in C

We skipped approach 1 (linked lists) above, mostly because you already did that in last week's lab. Well, it's a whole different challenge to do linked lists in C!

Create a new program linked.c which is similar to array1.c and the others, except that it uses linked lists instead of arrays.

Note, to implement linked lists you will want an additional struct for a linked list node. Your node and list structures definitions might look something like this:

1
2
3
4
5
6
7
8
9

struct node {
  int data;
  struct node* next;
};
 
struct list {
  struct node* head;
  struct node* tail;
};

Note, everything is done with pointers! So every time you want to create a node, you will have to call malloc(sizeof(struct node)), and you'll call free to de-allocate each node in the list at the end of your program.

Once you get linked.c working, add it to the analysis parts (do the timing and say what the runtime is for append), comparing to the various array versions you already completed.

Inserting at the beginning

Everything so far has been assuming we are inserting at the end of the list. What if we wanted to add something to the front (index 0) of a list? What would change about the running times? After copying everything to a new directory so as not to overwrite the work you've already done, try modifying all the programs to insert at the beginning rather than the end of the list. Then run the timing script again. Add a paragraph to your README.txt explaining what you found in this experiment, and what you think it means about the running time for adding to the front rather than the end of a list.