C / Advanced: Language Boundaries and Systems / Lesson 18

Performance, Measurement, and Correctness

Optimize a defined program against a representative workload, and separate algorithmic improvement from unsupported timing claims.

About 5 min readContent reviewed 2026-10-23

On this page

Lesson goals

Choose a workload and correctness oracle before timing.
Compare algorithmic work and data locality.
Recognize optimization, restrict, and measurement pitfalls.

Ask a measurable question

Performance work begins with a target: latency, throughput, peak memory, or another concrete resource under a specified workload. Record data size, distribution, compiler, flags, hardware, and operating-system conditions. A faster result for a toy input does not establish a useful improvement for the real workload. First make outputs demonstrably correct.

Use profiling to locate expensive work rather than guessing from source appearance. Time complete relevant operations, include repeated trials, and report variation. Separate setup and I/O only when the product question excludes them. A benchmark whose work differs between candidates does not make a fair comparison even if its timer is precise.

Reduce repeated work with a proof

An algorithmic change often matters more than a clever expression. For repeated prefix-sum queries on unchanged data, precomputing prefixes costs linear work once and answers each query with direct indexing. The extra array costs memory and becomes stale when source values change, so the tradeoff depends on the query-to-update ratio.

The first example computes prefixes of four fixed small values and verifies a known query result. Every intermediate sum fits int. For arbitrary large or signed inputs, use an explicit overflow policy. The example proves the calculation’s result without claiming any elapsed-time improvement on every compiler or machine.

c Precompute a reusable prefix result

#include <stddef.h>
#include <stdio.h>

int main(void)
{
    const int data[] = {2, 4, 1, 3};
    int prefix[5] = {0};
    for (size_t i = 0; i < 4; ++i) prefix[i + 1] = prefix[i] + data[i];
    int first_three = prefix[3];
    if (first_three != 7) return 1;
    printf("first-three=%d all=%d\n", first_three, prefix[4]);
    return 0;
}

Expected output

first-three=7 all=10

prefix[k] stores the sum of the first k values; the fixed outputs are seven and ten.

Check a candidate against a simple oracle

A simple implementation can serve as a correctness oracle for a more elaborate candidate on bounded test data. Compare normal, empty, boundary, and irregular inputs. Preserve a checksum or otherwise consume the computed result in benchmarks so the compiler can see an observable purpose; do not add volatile everywhere as a universal optimization-control technique.

The second example checks that a direct sum and a prefix calculation agree on the same fixed data. It deliberately prints a correctness statement rather than a fabricated timing number. For a real benchmark, choose a supported timer whose resolution and meaning match the question; standard clock reports processor time, not a universal monotonic wall clock.

c Verify equivalence before benchmarking

#include <stddef.h>
#include <stdio.h>

int main(void)
{
    const int data[] = {2, 4, 1, 3};
    int direct = 0;
    int prefix[5] = {0};
    for (size_t i = 0; i < 4; ++i) direct += data[i];
    for (size_t i = 0; i < 4; ++i) prefix[i + 1] = prefix[i] + data[i];
    if (direct != prefix[4]) return 1;
    printf("equivalent sum=%d\n", direct);
    return 0;
}

Expected output

equivalent sum=10

Both algorithms compute ten for the same inputs, establishing this bounded correctness check.

Optimization needs true promises

Compiler optimization levels enable different transformations and have target-dependent effects. Select and record them explicitly; inspect optimized behavior only after the program is defined. GCC -O2 is a tool setting, not a language guarantee of speed. Options such as fast-math can change floating assumptions and must be judged against the application’s numerical contract.

restrict is a C pointer qualifier that creates access-based aliasing obligations for an execution of its block. It is not a casual “probably different pointers” hint, and violating its contract can cause undefined behavior. Do not add it until the permitted accesses are understood and callers can satisfy them; start with simpler nonaliasing interfaces where possible.

Keep the measured improvement maintainable

Contiguous data, fewer allocations, and less repeated traversal can improve locality and reduce overhead, but the actual benefit depends on element size and access patterns. Avoid changing a clear algorithm into opaque pointer tricks for an unmeasured gain. Include memory consumption and failure complexity in the comparison, not just successful-path runtime.

After a justified optimization, retain correctness tests, the representative workload, measurement conditions, and the reason the tradeoff was accepted. Recheck performance when workload or toolchain changes materially. An optimization that invalidates ownership or numerical guarantees is a correctness regression, regardless of how attractive its timing looks.

Common errors and fixes

A benchmark reports no work or implausibly tiny time.

Why it happens: The compiler removed unused computations or the timer resolution is insufficient.
How to fix it: Consume a validated result and choose an appropriate workload and timer.
Prevent it next time: Inspect benchmark structure before trusting a number.

A faster build changes numerical results beyond tolerance.

Why it happens: Optimization flags relaxed assumptions required by the application.
How to fix it: Restore compatible flags or revise the numerical model explicitly.
Prevent it next time: Include accuracy checks in every performance comparison.

Adding restrict breaks overlapping callers.

Why it happens: A contractual aliasing promise was introduced without proof.
How to fix it: Remove the qualifier or redesign and enforce nonaliasing access.
Prevent it next time: Review all callers before strengthening access preconditions.

Check your understanding

1. A program makes one prefix query after every update to a large array. Explain why precomputation may be a poor optimization.

Show worked solution

Recomputing the entire prefix array after each update costs linear work and extra storage, while a single direct query may already cost linear work with less maintenance. The query-to-update ratio does not amortize the setup. Measure the actual query ranges and consider a different structure only if requirements justify its complexity and ownership rules. The example’s repeated-query advantage does not transfer automatically.

2. Design a fair comparison of two parsers without inventing timing results.