HW3 Report — x86-64 Assembly (NASM)

Language / toolchain

• Language: x86-64 assembly, NASM syntax.
• Assembler: NASM version 2.16.03 (compiled Aug 31 2026), confirmed with nasm -v.
• Linker: gcc (Ubuntu 15.2.0-16ubuntu1) 15.2.0 used as the linker driver (gcc quicksort.o -o quicksort -no-pie), so the standard C runtime startup and libc are linked correctly and the assembly's main: label runs as the C main entry point. No optimization flags apply (hand-written machine code, not compiled).
• Build/run commands:

  nasm -f elf64 quicksort.asm -o quicksort.o
  gcc quicksort.o -o quicksort -no-pie
  ./quicksort
  

• Environment: WSL2 Ubuntu, AMD Ryzen 7 5800H (8 cores / 16 threads, ~3.2 GHz base), 32 GB RAM, Windows 11 Pro host.

Randomized pivot / RNG

Pivot selection follows CLRS's RANDOMIZED-PARTITION: at every partition step on subarray [lo, hi], a random offset is computed as rand() % (hi - lo + 1) (32-bit unsigned div instruction, remainder in edx), added to lo to get index r, and arr[r] is swapped with arr[hi] before running a standard Lomuto partition using arr[hi] as the pivot. RANDOMIZED-QUICKSORT then recurses on the two resulting subarrays — implemented here iteratively (see "Implementation notes" below) rather than via native call/ret recursion, but performing the exact same sequence of partition operations as the recursive pseudocode.

RNG used: libc's rand(), seeded once at program start via srand(time(NULL)) (using extern time / extern srand / extern rand declared directly and called with the SysV AMD64 calling convention). Same RNG quality caveats as any C rand()-based entry in this comparison apply (glibc rand() is not cryptographically strong and has known statistical limitations) but is entirely adequate here, since the only requirement is a plausible uniformly-random pivot to avoid worst-case O(n^2) behavior on adversarial/sorted inputs.

External code

No external code used — original implementation based on CLRS RANDOMIZED-QUICKSORT/RANDOMIZED-PARTITION pseudocode (Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Ch. 5). The only external dependency is the C standard library, extern-declared and called directly per the SysV AMD64 ABI (as directed for this language's toolchain — writing this program against raw syscalls only, including hand-rolled float formatting and buffered file I/O, would be needlessly obscure and was explicitly not required): printf, fprintf, fopen, fclose, malloc, free, rand, srand, time, clock_gettime, exit.

Implementation notes

RANDOMIZED-QUICKSORT is naturally recursive, but this implementation uses an explicit work stack of (lo, hi) index pairs held in a small fixed-size buffer on the native stack, rather than native call/ret recursion, to avoid deep call-frame bookkeeping in hand-written assembly (a reasonable and common simplification, noted up front as acceptable for this assignment). To keep the explicit stack small and bounded, the well-known "recurse into the smaller partition, push the larger one" technique is used: after each partition, the loop continues in place on whichever of the two resulting subarrays is smaller, and only pushes the larger one onto the work stack. This bounds the maximum simultaneous stack depth to O(log n) (≈28 for the largest n reached here), so a 128-slot (2048-byte) buffer is always more than sufficient — it never grows anywhere near that even though worst-case Lomuto partitioning without this trick could require O(n) frames. This changes only the bookkeeping strategy, not the algorithm: the exact same partition/pivot operations run as CLRS's recursive pseudocode.

Array elements are 32-bit integers (range fits comfortably; values are drawn from [0, 1000000)). SysV AMD64 calling convention register/stack-alignment discipline (args in rdi/rsi/rdx/rcx/r8/r9, return in rax, callee-saved rbx/rbp/r12–r15, 16-byte rsp alignment before every call) is followed throughout; values that must survive a libc call (e.g. lo/hi across call rand, or n/the FILE*/the array pointer across the many calls in the harness loop) are kept in callee-saved registers for the life of each function, so no manual spill/reload bookkeeping was needed beyond the initial register-saving prologue/epilogue in quicksort and main. See the comments at the top of asm/quicksort.asm for the full register map.

A sanity check (check_sorted) verifies the array is fully sorted ascending after each of the first two (small-n) iterations and prints the result; both came back sorted=1, confirming correctness before trusting the timed runs at larger n.

Results

Full results (also in results/asm.csv):

Run stopped after 17 iterations because the elapsed time for n = 65,536,000 (5.949566 s) exceeded the 4.0 s cutoff (the 25-iteration and 200,000,000-n caps were not reached). Total wall-clock time for the whole program run (time ./quicksort, build excluded) was 12.09 s.

Growth analysis

The observed timings track the expected O(n log n) average-case running time well. The per-doubling ratio (T(2n)/T(n)) stays in a tight band of roughly 2.05–2.22 across the whole run (e.g. 1,000→2,000 is 2.05x, 128,000→256,000 is 2.08x, 1,024,000→2,048,000 is 2.09x, 32,768,000→65,536,000 is 2.21x), consistent with the theoretical prediction that T(2n)/T(n) ≈ 2·(1 + 1/log2 n), which for log2 n ranging from ~10 to ~26 over this run predicts ratios tapering from about 2.2 down toward about 2.08 — matching the measured values closely, with the usual extra noise at the smallest n (timer-resolution and cache/allocation effects are a larger fraction of a ~40 microsecond measurement). No anomalies specific to assembly were observed (no runtime/JIT/GC involved at all — every measured sample is pure hand-written machine code executing directly), and no recursion-depth issues occurred since the explicit work-stack design bounds depth to O(log n) by construction.

Comparison to C: with zero language-runtime overhead, hand-written assembly is generally expected to be at or near the top of a language comparison like this. That expectation held relative to any interpreted or managed-runtime language, but it is worth stating plainly that this implementation did not consistently beat gcc -O2-compiled C (results/c.csv) — the two tracked each other very closely, with assembly sometimes marginally ahead at small n (1,000: 0.000041s asm vs 0.000043s C) and marginally behind at large n (65,536,000: 5.949566s asm vs 5.586515s C, about 6.5% slower). This makes sense: for a straightforward, branch-heavy, non-vectorizable algorithm like Lomuto-partition quicksort over int32s, an optimizing compiler at -O2 produces machine code that is already close to what a careful hand-written implementation produces — this implementation used no manual loop unrolling, no SIMD, and no branch-elimination tricks (e.g. a branchless swap-on-compare) beyond a direct translation of the CLRS pseudocode, so there was no headroom left for hand-written assembly to exploit over gcc's own code generation for this particular workload. Assembly's real advantage in this comparison is against languages with meaningful runtime overhead (interpreters, JIT warmup, GC pauses, managed array bounds-checking), not against another compiled, unmanaged language solving the same simple integer-array problem.