R Programming / Evaluation, ownership, and reproducible results / Lesson 16

Profiling, allocation, and algorithmic cost

Optimize a measured bottleneck while preserving values, types, and resource bounds.

About 4 min readContent reviewed 2026-10-28

On this page

Lesson goals

Separate algorithmic growth from syntax choices.
Explain preallocation and temporary-object costs.
Design a bounded profiling experiment with honest claims.

A performance question needs a workload contract

Define input dimensions, types, missingness, required output, and the resource that matters before optimizing. A function can be fast on five values and impractical on a million because its algorithm grows quadratically. Conversely, a constant overhead can dominate a tiny benchmark without mattering in the real task. Establish a correct reference and representative bounded inputs. Keep data preparation, computation, and output costs separate unless the user-visible operation includes all three. A shorter expression or a function from a popular package is not evidence of a faster implementation for the relevant workload.

Repeated growth can cause repeated allocation

The first fixture contrasts appending to a numeric vector with allocating its final size before filling it. Both return the same five squares and total, so correctness can be checked independently of timing. Repeated concatenation can require new allocations and copying, while preallocation makes the result size explicit. Actual allocation and copying depend on object state, implementation, and optimization details. Do not convert this teaching example into a universal timing ratio. Before replacing a loop, inspect whether the proposed vectorized expression builds a much larger intermediate result or changes missingness, names, or output type.

r Illustrative base-R script; R runtime not available during review

growing <- function(n) {
  out <- numeric(0)
  for (i in seq_len(n)) out <- c(out, i^2)
  out
}
fixed <- function(n) {
  out <- numeric(n)
  for (i in seq_len(n)) out[i] <- i^2
  out
}
cat("same=", identical(growing(5L), fixed(5L)), "\n", sep = "")
cat("sum=", sum(fixed(5L)), "\n", sep = "")

Expected output

same=TRUE
sum=55

The two bounded implementations have the same declared numeric result; no elapsed-time or allocation measurement is claimed.

Algorithmic counts expose large hidden intermediates

The second fixture counts a hypothetical dense pairwise matrix without allocating it. A thousand observations imply one million cells and an assumed eight million payload bytes for doubles, before object overhead and temporary storage. Only 499500 distinct unordered off-diagonal pairs exist. A task that needs one nearest neighbor or a streamed summary may not need the whole matrix. Changing the algorithm or retaining only required information can matter more than tuning a loop. Any packed representation, blocking scheme, or approximation must preserve or explicitly change the required result contract.

r Illustrative base-R script; R runtime not available during review

n <- 1000
dense_cells <- n*n
unique_pairs <- n*(n-1)/2
payload_bytes <- dense_cells*8
cat(sprintf("dense cells=%.0f; unique pairs=%.0f\n", dense_cells, unique_pairs))
cat(sprintf("assumed double payload bytes=%.0f\n", payload_bytes))

Expected output

dense cells=1000000; unique pairs=499500
assumed double payload bytes=8000000

This is an analytical count for a hypothetical dense double matrix, excluding object overhead and temporary arrays; no million-cell matrix is allocated.

Profiling observations need an execution context

system.time measures an expression under its documented timing categories, while Rprof samples execution information for later summary. Sampling profiles can miss short operations and can attribute time differently under inclusive and self-time views. Warmup, garbage collection, background load, input reuse, and allocation can influence results. Repeat a bounded representative experiment and report the distribution rather than one favorable number. Profiling support and event semantics depend on the platform and build, so read the relevant documentation and record the environment. This course does not execute a profiler or publish any R timing measurements.

Accept an optimization only with equivalent behavior

After a change, compare the result with the reference using justified exact or approximate checks. Include empty input, singleton input, missingness, and relevant ordering or class behavior. A memory optimization that drops identifiers or changes a denominator is a different analysis, even if its elapsed time improves. Record resource limits and avoid uncontrolled benchmark sizes that risk exhausting the session. If the bottleneck is not reproducible, preserve the evidence and measure again under a clearer contract rather than editing unrelated code. The supplied programs provide arithmetic and structural expectations only; no R engine or allocation profiler was available.

Common errors and fixes

A compact expression exhausts memory

Why it happens: It materializes a large intermediate object.
How to fix it: Analyze dimensions and retain only the data the task requires.
Prevent it next time: Set bounded input limits and estimate peak categories before execution.

A benchmark improvement disappears on real inputs

Why it happens: The fixture did not represent types, sizes, or the full relevant operation.
How to fix it: Measure a bounded workload matching the stated contract.
Prevent it next time: Report environment, input shape, repetitions, and timing scope.

An optimized summary changes values

Why it happens: Ordering, missingness, type, or reduction semantics changed.
How to fix it: Compare against a simple correct reference and restore the contract.
Prevent it next time: Keep correctness checks separate from timing assertions.

Check your understanding

1. If observation count doubles, how does the hypothetical dense pairwise cell count change?

Show worked solution

It changes from n squared to (2n) squared, a factor of four. The eight-byte payload assumption then scales by four too. This does not include runtime overhead or prove that the task must allocate that matrix; a different algorithm may avoid it.

2. Why should a performance test not assert a fixed millisecond threshold for this five-value fixture?