Common Lisp (SBCL) Report — CSC 482 HW3 (Language Comparison)

Language / toolchain

• Common Lisp, implementation SBCL 2.4.9 (Steel Bank Common Lisp), official binary release from sbcl.org, installed inside WSL2 Ubuntu and wrapped at /usr/local/bin/sbcl (sets SBCL_HOME and execs the real runtime binary; the distribution's own run-sbcl.sh script is broken in this environment and was not used).
• Run non-interactively with sbcl --script quicksort.lisp (loads and evaluates the file top-to-bottom, then exits cleanly — no REPL).
• (declaim (optimize (speed 3) (safety 0) (debug 0) (compilation-speed 0))) at the top of the source requests maximum-speed native-code compilation; SBCL compiles all top-level defuns to native machine code by default (it is not an interpreter), so this declaration mainly removes bounds/type-check overhead and encourages inlining rather than switching compilation modes.
• Heap raised from the 1024 MB default to 16 GB via --dynamic-space-size 16384 (the default was insufficient — a first run hit a HEAP-EXHAUSTED-ERROR around n = 32,768,000..65,536,000, since a 65.5M-element simple-array of fixnum is ~512 MB by itself and momentarily two generations' worth can be live around a GC).
• Exact command used:

  wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/lisp' && sbcl --dynamic-space-size 16384 --script quicksort.lisp"
  

• Machine: AMD Ryzen 7 5800H (8 cores / 16 threads, ~3.2 GHz base), 32 GB RAM, Windows 11 Pro host, benchmark executed inside WSL2 Ubuntu (single-threaded workload).

Algorithm / RNG

Implements CLRS's RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION (Ch. 5) directly on a simple-array of fixnum, accessed via aref:

• randomized-partition (Lomuto scheme) picks a pivot index uniformly at random from the inclusive subarray range [p, r] via (+ p (random (1+ (- r p)))), swaps it into the last position r with rotatef, then runs a standard Lomuto partition (single forward scan swapping elements <= pivot to the front) using a[r] as the pivot value.
• randomized-quicksort drives this with an explicit stack of (lo . hi) bounds (rather than recursive function calls), pushing the two resulting subranges after each partition — behaviorally identical to the recursive CLRS pseudocode, but avoids any risk of Lisp call-stack overflow at the largest n values in this experiment.
• RNG: the standard random function (Common Lisp's built-in pseudo-random number generator, using SBCL's default global *random-state*), used both for pivot selection in randomized-partition and for generating each iteration's fresh input array ((random 1000000) per element in make-random-vector), per DESIGN.md.
• No built-in sort/stable-sort is called anywhere; sorting is done entirely by the hand-written randomized-quicksort/randomized-partition functions.
• Data generation (make-random-vector) happens before (get-internal-real-time) is called and is excluded from the timed interval; only the call to randomized-quicksort is timed, using get-internal-real-time / internal-time-units-per-second (which SBCL reports as 1,000,000 — i.e. the API claims microsecond resolution, see anomaly note below).

External code used

No external code used — original implementation based on CLRS RANDOMIZED-QUICKSORT/RANDOMIZED-PARTITION pseudocode (Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Ch. 5). Standard library only, no Quicklisp packages.

Results

Full results (also in HW3/results/lisp.csv), 17 iterations, stopped when iteration 17 (n = 65,536,000) took 8.800s, exceeding the 4.0s cutoff:

Max n reached: 65,536,000, time 8.800s (this is the iteration that triggered the stop, per the >4.0s rule). Total wall-clock time for the whole run (SBCL process start to exit, per time around the sbcl --script invocation): ~17.2s real.

Growth analysis

For O(n log n) behavior, doubling n should roughly double the runtime times a slowly growing log factor — the ratio T(2n)/T(n) should sit a bit above 2 and should trend toward 2 from above as n grows. From n = 128,000 upward (past the noise floor discussed below), the observed per-doubling ratios are 128,000→256,000: 2.00x, 256,000→512,000: 2.33x, 512,000→1,024,000: 2.21x, 1,024,000→2,048,000: 2.00x, 2,048,000→4,096,000: 2.15x, 4,096,000→8,192,000: 1.82x, 8,192,000→16,384,000: 1.66x, 16,384,000→32,768,000: 2.35x, 32,768,000→65,536,000: 2.33x. These cluster in the ~1.7–2.35x range, consistent with O(n log n) (a pure O(n) algorithm would show ratios flat at ~2.0x; O(n^2) would show ratios near 4.0x) — the data is clearly not quadratic and sits in the expected linearithmic neighborhood, though the ratios are noisier than the smoother per-doubling curves seen in the round-1 compiled languages (C/C++/Rust/Go).

Anomalies. Two are worth flagging. First, internal-time-units-per-second reports 1,000,000 (nominally microsecond resolution), but the smallest nonzero measured values are all exact multiples of 0.004 seconds (4 ms), and several early iterations (n = 1,000–4,000, and oddly n = 16,000) read exactly 0.0. This indicates the actual clock backing get-internal-real-time in this WSL2/SBCL combination has ~4 ms real granularity regardless of what units it reports in — a coarser effective resolution than the microsecond/nanosecond timers available to e.g. C's clock_gettime, Rust's Instant, or Java's System.nanoTime() in the earlier round-1 runs on this same machine. This makes the small-n rows unreliable for growth-rate analysis (hence excluding them above) but does not affect the large-n rows, where real elapsed time is many multiples of the 4 ms quantum. Second, SBCL compiles to native machine code ahead of time (there is no JIT warm-up or GC pause comparable to the JVM/.NET, and this is a single-generation-friendly workload with few large long-lived allocations), so per-iteration timings otherwise show the smooth, low-noise behavior typical of natively-compiled languages once past the clock-floor region — comparable in shape to the C/Rust/Go curves and clearly faster per element than the interpreted/managed-runtime languages, matching the expectation that a natively-compiled Lisp should perform in the same tier as C/C++/Rust/Go rather than Python, and at least as well as Java/C#.