HW3 Report — Pascal (Free Pascal)

Language / toolchain

• Language: Object Pascal ({$mode objfpc})
• Compiler: Free Pascal Compiler version 3.2.2 [2021/05/16] for x86_64, Target OS: Linux for x86-64, confirmed with fpc -iV inside WSL2 Ubuntu.
• Build flags: -O3
• Build/run command:

  fpc -O3 quicksort.pas
  ./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 call on subarray [lo, hi], an index r is drawn uniformly from [lo, hi] via r := lo + Random(hi - lo + 1) (FPC's standard Random(N) returns a value uniformly distributed over [0, N-1]), arr[r] is swapped with arr[hi], and then a standard Lomuto partition runs using arr[hi] as the pivot. RandomizedQuicksort then recurses on the two resulting subarrays, mirroring RANDOMIZED-QUICKSORT.

RNG used: the standard Pascal RTL Random/Randomize procedures (unit System, always available, no uses clause needed). Randomize is called exactly once at program start to seed the generator from the system clock; Random (used both for pivot selection and for generating each array of test data) draws from that single seeded stream for the whole run. This is acceptable per the assignment's allowance of each language's standard RNG facility — the only requirement here is a plausible uniformly-random pivot to avoid worst-case O(n^2) behavior on adversarial/sorted inputs, not cryptographic-grade randomness.

Timer used

FPC 3.2.2's SysUtils unit does not provide TStopwatch for this Linux/x86-64 target — confirmed directly by a failed compile attempt (Error: Identifier not found "TStopwatch") before falling back. The other commonly-suggested low-effort option, SysUtils.GetTickCount64, is only millisecond resolution, which would be too coarse to distinguish early iterations (n = 1000 sorts in ~60 microseconds — sub-millisecond).

Instead, the harness uses fpgettimeofday from the standard FPC RTL units BaseUnix and Unix — a thin wrapper around the POSIX gettimeofday() call, giving microsecond resolution (TTimeVal.tv_usec). Elapsed time per iteration is computed as (tvEnd.tv_sec - tvStart.tv_sec) + (tvEnd.tv_usec - tvStart.tv_usec) / 1.0e6. Both BaseUnix and Unix ship as part of the standard FPC RTL (no external packages), satisfying the "RTL only" constraint. gettimeofday()-based timing is wall-clock rather than a dedicated monotonic clock, but since each measured interval is a single short, uninterrupted in-process call with no system clock adjustments occurring during the run, this has no practical effect on the results.

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).

Results

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

Run stopped after 17 iterations because the elapsed time for n = 65,536,000 (9.287187 s) exceeded the 4.0 s cutoff. (25-iteration and 200,000,000-n caps were not reached.) Total wall-clock time for the executable's run (build excluded; build itself took ~0.3 s per fpc's own report) was approximately 17.4 s.

Growth analysis

The observed timings are broadly consistent with the expected O(n log n) average-case running time of randomized quicksort. Doubling n should roughly double the time with a small extra factor from the growing log n term (T(2n)/T(n) ≈ 2·(1 + 1/log2 n)), which for this run's range (log2 n from ~10 to ~26) predicts a per-doubling ratio tapering from around 2.2 down toward roughly 2.05–2.1. The measured ratios track this well in the middle of the range — e.g. 128,000→256,000 is 2.05x, 512,000→1,024,000 is 2.13x, 4,096,000→8,192,000 is 2.08x — and drift somewhat higher at the largest sizes (16,384,000→32,768,000 is 2.24x, 32,768,000→65,536,000 is 2.41x), which is a plausible sign of growing cache/TLB-miss pressure once the working set (hundreds of megabytes for a 65-million-element Integer array plus recursion overhead) exceeds the CPU's cache hierarchy, on top of the expected log n growth. At small n (1,000–16,000) the ratios are noisier (as low as 1.59x at 8,000, as high as 2.79x at 4,000) because absolute times are only tens to a few hundred microseconds there, where timer granularity, dynamic-array allocation overhead, and one-off process/cache warmup are a comparatively large fraction of the measurement — expected measurement noise, not an algorithmic anomaly.

Comparing against results/c.csv: both C and Pascal reached the same maximum n (65,536,000) in 17 iterations before crossing the 4.0 s cutoff, confirming FPC compiles to genuinely competitive native code. Pascal was consistently slower than C by roughly 1.5–1.7x at comparable n (e.g. at n = 65,536,000, C: 5.586515 s vs Pascal: 9.287187 s), which is a reasonable gap given FPC's optimizer is less aggressive than GCC's -O2/ -O3 (notably around inlining and register allocation for recursive calls), while both remain in the same broad "compiled native code" performance class rather than differing by an order of magnitude the way an interpreted language would. No other anomalies (no GC pauses or JIT warmup apply to natively-compiled Pascal) were observed; recursion depth from randomized pivoting stayed well within stack limits for all tested n.