<!-- Abstract: CS 211 Computer Architecture Lecture 07: Structions and Recursion --> # CS 211 - Lecture 08 - Structs, Recursion, & Memory Bernhard Firner 2025-09-24 --- ## Review? * Everyone seemed okay with stacks * There are other common data structures * Linked lists, trees, heaps --- ## Why Stacks? * We spent a bunch of time on stacks * Stacks are constantly visible as we program assembly * Also useful to model several parts of the architecture * Also simple enough to understand --- ## Trees ```python typedef struct TreeNode TreeNode; struct TreeNode { TreeNode* left; TreeNode* right; char* data; ... } ``` * Trees are often used in memory management * By in filesystems and in devices * Not quite as interesting for us --- ## Topics * Today we'll go over a few useful tidbits * Recursion and stacks * Time measurements * struct features * unions * bit fields * Memory management --- ## Why? * Why cover these topics? * Knowing architecture informs your programming decisions * Usually, the bridge between your code and the hardware is your compiler * So let's begin learning how the compiler treats your code * Later, you'll be the ones talking with the CPU --- ## Recursion * Recursion is often the most elegant way to express an idea * Searching, sorting, etc * How does that translate to hardware? * We saw before that functions can cause a `stack overflow` if the call stack is deep enough * Let's revisit this --- ## No Recursion ```python #include <stdio.h> #include <stdlib.h> // Calculate the nth fibonocci number and return it. unsigned long long fibonocci(unsigned long long n) { if (n == 0 || n == 1) { return n; } return fibonocci(n-1) + fibonocci(n-2); } int main(int argc, char** argv) { if (argc < 2) { printf("Give me the nth fibonocci number that you want to see."); return 0; } int n = atoi(argv[1]); unsigned long long nth = fibonocci(n); printf("The %i fibonocci number is %llu\n", n, nth); return 0; } ``` --- ## Calculating the fibonocci * Calculating fibonocci numbers takes about $1.6^n$ steps * Plenty of calls, and we only avoid a stack overflow because it takes nearly no memory * However, this kind of call is what causes stack overflows * Compile with `gcc -S fib.c -o fib.s` --- ## Assembly View ```asm[|22,25] .file "example25.c" .text .globl fibonocci .type fibonocci, @function fibonocci: .LFB39: .cfi_startproc endbr64 movq %rdi, %rax cmpq $1, %rdi jbe .L5 pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 pushq %rbx .cfi_def_cfa_offset 24 .cfi_offset 3, -24 subq $8, %rsp .cfi_def_cfa_offset 32 movq %rdi, %rbx leaq -1(%rdi), %rdi call fibonocci movq %rax, %rbp leaq -2(%rbx), %rdi call fibonocci addq %rbp, %rax addq $8, %rsp .cfi_def_cfa_offset 24 popq %rbx .cfi_def_cfa_offset 16 popq %rbp .cfi_def_cfa_offset 8 ret .L5: .cfi_restore 3 .cfi_restore 6 ret .cfi_endproc .LFE39: .size fibonocci, .-fibonocci .section .rodata.str1.8,"aMS",@progbits,1 .align 8 .LC0: .string "Give me the nth fibonocci number that you want to see." .align 8 .LC1: .string "The %i fibonocci number is %llu\n" .text .globl main .type main, @function main: .LFB40: .cfi_startproc endbr64 pushq %rbx .cfi_def_cfa_offset 16 .cfi_offset 3, -16 cmpl $1, %edi jle .L12 movq 8(%rsi), %rdi movl $10, %edx movl $0, %esi call strtol@PLT movl %eax, %ebx movslq %eax, %rdi call fibonocci movq %rax, %rcx movl %ebx, %edx leaq .LC1(%rip), %rsi movl $2, %edi movl $0, %eax call __printf_chk@PLT .L10: movl $0, %eax popq %rbx .cfi_remember_state .cfi_def_cfa_offset 8 ret .L12: .cfi_restore_state leaq .LC0(%rip), %rsi movl $2, %edi movl $0, %eax call __printf_chk@PLT jmp .L10 .cfi_endproc .LFE40: .size main, .-main .ident "GCC: (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0" .section .note.GNU-stack,"",@progbits .section .note.gnu.property,"a" .align 8 .long 1f - 0f .long 4f - 1f .long 5 0: .string "GNU" 1: .align 8 .long 0xc0000002 .long 3f - 2f 2: .long 0x3 3: .align 8 4: ``` --- ## CALL * The call instructions are assembly's way of calling a function * Each call means more memory on the stack * What if we want to avoid this? --- ## Changing Calls into Loops * Recursive functions can be converted into loops * Use a stack to manually store the temporary variables --- ## Recursion to Loop Example ```C #include <stdio.h> #include <stdlib.h> #include "llu_stack.h" int main(int argc, char** argv) { if (argc < 2) { printf("Give me the nth fibonocci number that you want to see."); return 0; } int n = atoi(argv[1]); Stack s = newStack(10); push(&s, n); unsigned long long sum = 0; while (len(s) > 0) { unsigned long long next = pop(&s); if (next == 0 || next == 1) { sum += next; } else { push(&s, next - 1); push(&s, next - 2); } } freeStack(s); printf("The %i fibonocci number is %llu\n", n, sum); return 0; } ``` --- ## Is One Superior? * Yes; the compiler knows how to optimize the recursive call better * First, recompile with `-O3` to enable optimizations * We can time it with the `time` command <pre> $ time ./example25 50 The 50 fibonocci number is 12586269025 real 0m17.635s user 0m17.630s sys 0m0.003s $ time ./example26 50 The 50 fibonocci number is 12586269025 real 3m0.281s user 3m0.260s sys 0m0.005s </pre> --- ## Compiler Tricks * The compiler knows tricks for your hardware and OS * And it will execute them better than you will * So we are not going to be doing assembly for speed (usually) * A combination of C and assembly will allow us to access the hardware in ways other languages cannot --- ## Tail Recursion * There are times where there is a faster version of a recursive function * `Tail recursion` occurs when the value being returned is only the recursive call * That means that nothing else in the function will be used again * So memory can be freed, even before the next call completes * Also means that actually calling the function is unnecessary * Must tell gcc to use some optimization level, (usually -O2 or -O3) --- ## Tail Recursion Example ```C #include <stdio.h> #include <stdlib.h> // Calculate the sum n + (n - 1) + (n - 2) ... + 1 unsigned long long sequence(unsigned long long n, unsigned long long current) { if (n < 2) { return 1 + current; } // This is now tail recursive return sequence(n-1, current+n); } int main(int argc, char** argv) { if (argc < 2) { printf("Give me the number that you want to see."); return 0; } int n = atoi(argv[1]); printf("The %i sequence number is %llu\n", n, sequence(n, 0)); return 0; } ``` --- ## Assembly ```asm[|14,21-25] .file "example25_c.c" .text .p2align 4 .globl sequence .type sequence, @function sequence: .LFB39: .cfi_startproc endbr64 cmpq $1, %rdi jbe .L3 leaq -1(%rdi), %rax testb $1, %dil jne .L2 addq %rdi, %rsi movq %rax, %rdi cmpq $1, %rax je .L3 .p2align 4,,10 .p2align 3 .L2: leaq -1(%rsi,%rdi,2), %rsi subq $2, %rdi cmpq $1, %rdi jne .L2 .L3: leaq 1(%rsi), %rax ret .cfi_endproc .LFE39: .size sequence, .-sequence .section .rodata.str1.8,"aMS",@progbits,1 .align 8 .LC0: .string "Give me the nth fibonocci number that you want to see." .align 8 .LC1: .string "The %i sequence number is %llu\n" .section .text.startup,"ax",@progbits .p2align 4 .globl main .type main, @function main: .LFB40: .cfi_startproc endbr64 subq $8, %rsp .cfi_def_cfa_offset 16 cmpl $1, %edi jle .L35 movq 8(%rsi), %rdi movl $10, %edx xorl %esi, %esi call strtol@PLT xorl %ecx, %ecx movl %eax, %edx cltq cmpq $1, %rax jbe .L21 leaq -1(%rax), %rsi testb $1, %al jne .L20 movq %rax, %rcx movq %rsi, %rax cmpq $1, %rsi je .L21 .p2align 4,,10 .p2align 3 .L20: leaq -1(%rcx,%rax,2), %rcx subq $2, %rax cmpq $1, %rax jne .L20 .L21: addq $1, %rcx leaq .LC1(%rip), %rsi movl $2, %edi xorl %eax, %eax call __printf_chk@PLT .L19: xorl %eax, %eax addq $8, %rsp .cfi_remember_state .cfi_def_cfa_offset 8 ret .L35: .cfi_restore_state leaq .LC0(%rip), %rsi movl $2, %edi xorl %eax, %eax call __printf_chk@PLT jmp .L19 .cfi_endproc .LFE40: .size main, .-main .ident "GCC: (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0" .section .note.GNU-stack,"",@progbits .section .note.gnu.property,"a" .align 8 .long 1f - 0f .long 4f - 1f .long 5 0: .string "GNU" 1: .align 8 .long 0xc0000002 .long 3f - 2f 2: .long 0x3 3: .align 8 4: ``` --- ## Assembly and Architecture * Programming C requires a bit of hardware knowledge * Programming in assembly requires more * So we will doing more assembly * Also using "Computer Systems: A Programmer's Perspective" as reference * If you find the idea daunting, preemptively find a resource that you like * Try searching for "intro to x86 assembly programming" --- ## Memory Handling * Setting up structs in assembly wouldn't be fun * Stick with C for those tasks * There are a few C features that we haven't covered that will prove useful --- ## Bit Fields * We can specify the length of a struct field, in bits ```C struct Bits { int a : 5; }; ``` * Bits.a is a 5 bit type --- ## Why? * The compiler automatically packs `bool` into 1 bit * But not other types ```C typedef struct Bits Bits; struct Bits { bool a : 1; bool b : 1; bool c : 1; bool d : 1; bool e : 1; bool f : 1; bool g : 1; bool h : 1; }; ``` * `sizeof(Bits)` will be 8 --- ## Bit packing ```C typedef struct Numbers Numbers; struct Numbers { int a : 10; int b : 10; int c : 10; }; ``` * `sizeof(Numbers)` will be 4 * 30 bits fits into 4 bytes * Size will always be a whole number of bytes --- ## Memory Alignment ```C typedef struct Aligned Aligned; struct Aligned { int a : 10; int b : 10; int c : 10; long long int d : 64; }; ``` * `sizeof(Aligned)` will have a size of 16 * On this architecture at least * Why? Should be 4 + 8 = 12, right? --- ## Words * Recall our discussion of bits, nibbles, bytes, words, dwords, and qwords? * 1 bit, 4 bits, 8 bits, 16 bits, 32 bits, and 64 bits? * Memory is fetched at particular byte boundaries * Aligning to those boundaries make a program faster * But less space efficient * The compiler aligns the "Aligned" struct members to qword boundaries * So there is empty space between Aligned.c and Aligned.d --- ## Packing * We can tell the compiler to pack things together to save space ``` #pragma pack(push, 4) typedef struct Unaligned Unaligned; struct Unaligned { int a : 10; int b : 10; int c : 10; long long int d : 64; }; #pragma pack(pop) ``` * This tells the compiler to align to 4 byte (double word) boundaries * Now the size is 12 --- ## Code ```C #include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct Bits Bits; struct Bits { bool a : 1; bool b : 1; bool c : 1; bool d : 1; bool e : 1; bool f : 1; bool g : 1; bool h : 1; }; typedef struct Numbers Numbers; struct Numbers { int a : 10; int b : 10; int c : 10; }; typedef struct Aligned Aligned; struct Aligned { int a : 10; int b : 10; int c : 10; long long int d : 64; }; #pragma pack(push, 4) typedef struct Unaligned Unaligned; struct Unaligned { int a : 10; int b : 10; int c : 10; long long int d : 64; }; #pragma pack(pop) int main(int argc, char** argv) { printf("The size of Bits is %lu\n", sizeof(Bits)); printf("The size of numbers is %lu\n", sizeof(Numbers)); printf("The size of aligned is %lu\n", sizeof(Aligned)); printf("The size of unaligned is %lu\n", sizeof(Unaligned)); return 0; } ``` --- ## Interpreting Memory * One more trick * The way data at a memory location is treated is arbitrary * Normally we have to get a pointer and recast to change it ```C int a = 10; char* b = (char*)(&a); ``` --- ## Unions * In assembly, data is loaded into a register before use * The type of register changes the way the data is treated * Not the source of the data! * All data is just data, only the registers have types! * So we could treat memory any way we want, or in multiple ways * C calls this a Union --- ## Union Syntax * Declaring a union looks like declaring a struct * But every member is treated as having overlapping memory --- ## Union Example ```C union together { int number; char chars[4]; }; ``` * Equivalent to having an int and a char* to it. --- ## Useful Union ```C #include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct Bits Bits; struct Bits { bool a : 1; bool b : 1; bool c : 1; bool d : 1; bool e : 1; bool f : 1; bool g : 1; bool h : 1; }; typedef union LLUBits LLUBits; union LLUBits { // 8 bytes to a long long Bits bits[8]; long long number; }; int main(int argc, char** argv) { if (argc < 2) { printf("Give me a number!"); return 1; } char* endptr = argv[1]; LLUBits value; value.number = strtoll(argv[1], &endptr, 10); for (int i = sizeof(LLUBits)-1; i >= 0; --i) { printf("%i", value.bits[i].h); printf("%i", value.bits[i].g); printf("%i", value.bits[i].f); printf("%i", value.bits[i].e); printf("%i", value.bits[i].d); printf("%i", value.bits[i].c); printf("%i", value.bits[i].b); printf("%i", value.bits[i].a); printf(" "); } printf("\n"); return 0; } ``` --- ## Outputs <pre> $ ./example29 1 $ ./example29 9223372036854775807 01111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 $ ./example29 -9223372036854775807 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001 $ ./example29 -9223372036854775808 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 </pre> --- ## Float Union ```C #include <stdio.h> #include <stdlib.h> typedef struct FloatBits FloatBits; struct FloatBits { unsigned int significand : 23; unsigned int exponent : 8; unsigned int sign : 1; }; typedef union FloatIntBits FloatIntBits; union FloatIntBits { float the_float; int the_int; FloatBits the_bits; }; int main(int argc, char** argv) { if (argc < 2) { printf("Give me a float!"); return 0; } FloatIntBits fib = {.the_float = atof(argv[1])}; printf("The size of fib is %lu\n", sizeof(fib)); printf("The size of FloatBits is %lu\n", sizeof(FloatBits)); printf("The sign is %u, the exponent is %u, and the significand is %u\n", fib.the_bits.sign, fib.the_bits.exponent, fib.the_bits.significand); printf("%f as an int is %i\n", fib.the_float, fib.the_int); return 0; } ``` --- ## Review * We'll have one more lecture before the quiz * On data representation and arithmetic before the quiz * Won't be on the quiz though * Material will cover through today's lecture * Let's review with a few example questions --- ## Q1 <div style="text-align: left;"> What is the output of the following code snippet? printf("6 / 4 = %i\n", 6/4); a. 1 b. 1.5 c. 1.0 d. This code is not syntactically correct and will not compile. </div> --- ## Q2 <div style="text-align: left;"> The exit status of a program is NOT: a. Always an integer. b. Generally nonzero to indicate failure. c. The value of the last variable cleaned up from the stack. d. The value returned from the main function. </div> --- ## Q3 <div style="text-align: left;"> After the following line of code, what is the value of a? int a = 2.7; a. 2.7 b. 2 c. The value will be architecture specific. d. This code is not syntactically correct and will not compile. </div> --- ## Q4 <div style="text-align: left;"> On a 64-bit machine, the maximum value of a signed long long int will be a. $2^{32}$ b. INT_MAX as defined in limits.h c. $2^{63}$ - 1 d. $2^{64}$ - 1 </div> --- ## Q5 <div style="text-align: left;"> Which of the following statements about argc and argv are false? a. The values of argc and argv are only known at run time. b. C requires both argc and argv when declaring the main function. c. argv is a pointer that ponits to other pointers. d. argc[0] is the program name itself. </div> --- ## Q6 <div style="text-align: left;"> ``` #include <stdio.h> int main(int argc, char** argv) { printf("%lu\n", sizeof(int*)); return 0; } ``` The above code will: a. Print the size of a pointer on the current architecture. b. Print the size of an int on the current architecture. c. It will not compile because sizeof cannot be used with int*. d. It will not compile for other reasons. </div> --- ## Q7 <div style="text-align: left;"> <pre> int a = 6; int *b = &a; b[0] = 2; *b += 10; </pre> After the above, code, what is the value of a? a. 6 b. 12 c. 16 d. None of those. </div> --- ## Q8 <div style="text-align: left;"> In a little endian system, the first byte of an integer is a. Loaded into a register first during qword instructions b. Where the sign bit is stored c. The least significant d. The most significant </div> --- ## Q9 <div style="text-align: left;"> The type signature for the calloc function is as follows: void *calloc(size_t nmemb, size_t size); Write a single line of code that declares an int* and sets it equal to dynamically allocated memory with space for 35 integers. <br> \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ </div>