The goal of this pre-assignment is to practice basics of C programming that go beyond other languages. This is also an opportunity to train the use of the terminal environment and make.
Memory can be allocated on the stack and on the heap. In these assignments you get to know common simple programming patterns that give you access to both.
Most relevant videos: Basic C Programming, Memory Handling in C.
Allocation describes the reserving of memory for a program. Stack allocation is the fastest variant. While the C standard makes no assumption on what memory is allocated on the stack, it is reasonable to assume that arrays of static size are allocated on the stack.
Write a program employing the following allocation pattern
int size = 10;
int as[size];
for ( size_t ix = 0; ix < size; ++ix )
as[ix] = 0;
printf("%d\n", as[0]);
Make sure that you place the declaration of the array in the main function (as opposed to global scope).
Compile and run the program. Then increase the size of the array, recompile and run, until the program fails with a segmentation fault. Explain this behavior assuming that that allocation was performed on the stack.
Heap allocation is the alternative to stack allocation. It is generally slower, but more flexible. In particular, it has less restrictions on the size of allocated memory.
Write a program with the following allocation pattern
int size = 10;
int * as = (int*) malloc(sizeof(int) * size);
for ( size_t ix = 0; ix < size; ++ix )
as[ix] = 0;
printf("%d\n", as[0]);
free(as);
Compile and run as above, and verify that the program does not fail for sizes that triggered a segmentation fault before.
When allocating memory on the heap, there is no guarantee about where it is positioned. A common strategy to avoid this is to allocate memory in large blocks (contiguous memory). Implement a program based on the next two code snippets. Explain the meaning of all variables, and exhibit the possible layout of allocated memory in both cases.
Using contiguous memory and thus avoiding memory fragmentation:
int size = 10;
int * asentries = (int*) malloc(sizeof(int) * size*size);
int ** as = (int**) malloc(sizeof(int*) * size);
for ( size_t ix = 0, jx = 0; ix < size; ++ix, jx+=size )
as[ix] = asentries + jx;
for ( size_t ix = 0; ix < size; ++ix )
for ( size_t jx = 0; jx < size; ++jx )
as[ix][jx] = 0;
printf("%d\n", as[0][0]);
free(as);
free(asentries);
Not avoiding memory fragmentation:
int size = 10;
int ** as = (int**) malloc(sizeof(int*) * size);
for ( size_t ix = 0; ix < size; ++ix )
as[ix] = (int*) malloc(sizeof(int) * size);
for ( size_t ix = 0; ix < size; ++ix )
for ( size_t jx = 0; jx < size; ++jx )
as[ix][jx] = 0;
printf("%d\n", as[0][0]);
for ( size_t ix = 0; ix < size; ++ix )
free(as[ix]);
free(as);
Most relevant videos: Basic C Programming, Memory Handling in C.
Implement two programs. One that
The other one
How does your choice of memory allocation (contiguous vs. noncontiguous) impact the possibilties to write the matrix in text and binary format?
Most relevant videos: Memory Handling in C, Files in C and Binary Data.
Programs can be called with command line arguments. For example, a program printargs might be called as
./printargs -a2 -b4
These arguments are passed to the main function
int
main(
int argc,
char *argv[]
)
as an array of null-terminated strings argv (argument vector), the number of which is argc (argument count). In the above example the argument count is 3 and the argument vector accordingly contains 3 strings "./printargs", "-a2", and "-b4".
Implement a program that
For example calling
printargs -a2 -b4
or
printargs -b4 -a2
should output
A is 2 and B is 4
As a final remark observe that standard programs would equally accept "-a2" and "-a 2". When using standard solutions like POSIX getopt, this is automatically taken care of.
Most relevant videos: Pointer Arithmetic, String Encoding and Handling.
Implement a program that
Compile and run the program with all possible optimization levels (add the flags -O0, -O1, -O2, -O3, -Os, and -Og to the compiler).
Discuss the timing results and speculate about the possible cause.
Most relevant videos: Basic C Programming. In particular, you are not expected to watch the video on naive benchmarking from week 3.
This assignment is a preparation towards your working on Assignments 2 through 5. In particular, you will need the following:
From the part on stack and heap allocation, it is helpful to remember that stack memory can be much faster, but its size is limited. Once you can argue that an array fits on the stack, it is preferable to allocate it there.
From the part on reducing memory fragmentation, it is helpful to remember both memory allocation patterns. Contiguous memory allocation is typically faster, but it is also less flexible. That is, using contiguous memory allocation you are forced to allocated the required memory at once. As for non-contiguous memory allocation you can allocate and free each row whenever it is optimal in your code.
From the part on writing to files, it is helpful to record that fprintf is potentially much slower than fwrite. In particular, when writing the same string repeatedly in a program, it can be helpful to prepare a string in memory (i.e. an array of char) via, for example, sprintf and then write it to file employing fwrite.
From the part on parsing command line arguments, it is helpful to remember the programming pattern. Most programs need to parse command line arguments. You can reuse the code that you have written in other assignments.
From the part on naive benchmarking, it is helpful to remember that reasonable benchmarking of small pieces of code can be achieved by running it sufficiently often and taking the average. Running code a single time, on the other hand, incurs so many random effects that the resulting performance mearsurement is invalid. It is also important to watch for simplifications made by the compiler.