Profiling in Practice: Naive vs FFT Convolution (imgconv_fft)

We will learn profiling by investigating a real C++ program that applies convolution filters to an image. The program supports two convolution methods:

naive (direct spatial convolution) (Explanation)
fft (FFT-based convolution) (Explanation)

The goal is not to “make the code faster today.”
The goal is to answer, with evidence:

Where does the runtime go?
Why does performance differ between naive and FFT?
When is FFT slower, and when can it win?

Project repo: https://github.com/Kenyon-CS/imgconv_fft

What profiling is (and what it is not)

Profiling answers: where does the runtime go? It helps you find hot spots (functions/loops that dominate total time), and it helps you verify that your optimization efforts are aimed at the right place.

Profiling is not debugging. Your program can be correct and still slow.
Profiling is not guessing. We do not optimize by vibe. We measure, change one thing, then measure again.

Two useful ideas:

Wall-clock timing: “How long did the whole thing take?”
Sampling profilers: “Which functions/lines are we spending time in?”

In this lab, chrono timing is already built into the program. Your job is to use:

perf (Linux) for sampling-based hotspot profiling
Instruments Time Profiler (macOS) for visual call trees and phase timelines

Critical idea: FFT is NOT always faster

Do not assume “FFT beats naive.” That is a myth without context.

For small kernels (3×3 sharpen/edge/emboss), naive typically wins because FFT has heavy setup overhead.
FFT becomes competitive only when the kernel is large enough (like large blur), and when the FFT implementation is efficient.

So your job is to measure, not assume.

Part 0 — Build and confirm the program works

Build

make clean
make

Sanity run (any output is fine)

./imgconv \
  --in oldkenyon.ppm \
  --filter emboss \
  --method naive \
  --repeat 10 \
  --out /tmp/emboss_naive.pgm

./imgconv \
  --in oldkenyon.ppm \
  --filter emboss \
  --method fft \
  --repeat 10 \
  --out /tmp/emboss_fft.pgm

If the images look similar, correctness is “good enough” for profiling.

Part 1 — Chrono timing experiments (already built in)

Chrono gives you a fast answer to:
which algorithm is faster for this input?

Experiment A: Small-kernel filter (FFT usually loses)

Try emboss (3×3 kernel): (See examples above?

Expected pattern:

naive is often faster
FFT overhead dominates

Experiment B: Large blur (FFT has a chance to win)

Try a large blur kernel:

./imgconv \
  --in oldkenyon.ppm \
  --filter blur \
  --kernel-size 51 \
  --method naive \
  --repeat 3 \
  --out /tmp/blur_naive.pgm

./imgconv \
  --in oldkenyon.ppm \
  --filter blur \
  --kernel-size 51 \
  --method fft \
  --repeat 3 \
  --out /tmp/blur_fft.pgm

Expected pattern:

naive slows dramatically as kernel grows
FFT may win or at least become more competitive

What to record

For each experiment, record:

method (naive/fft)
filter
kernel size
repeat count
average runtime reported by program

Part 2 — Linux profiling with perf (step-by-step)

Perf is a sampling profiler. It periodically interrupts your program and records where the CPU is executing. After the run, it reports which functions used the most CPU time.

Step 2.1 — Build with symbols (required)

You need -g so perf can display function names. Use:

make clean
make CXXFLAGS="-O3 -g -march=native -Wall -Wextra -pedantic"

Step 2.2 — Run perf record

Use a workload that runs long enough to profile well (repeat helps).

Start with FFT emboss:

perf record -g ./imgconv --filter emboss --method fft --repeat 30 --out /tmp/o.pgm

Then generate a report:

perf report

Step 2.3 — How to interpret perf report

In perf report, focus on:

The top 1–3 entries
- These are the hotspots.
- If your “optimization target” is not in the top few lines, it won’t matter.
Self vs Children
- Self: time spent in that function itself
- Children: time spent in functions it called
- High “Children” means the function is a wrapper around the real work.
Call graph (-g)
- Expand a hotspot and look at what it calls.
- This helps answer: “Which phase dominates?”

What you should expect to see

For FFT method, you should see hotspots in:

fft1d_inplace and/or fft2d_inplace
complex math / vector loops
maybe copying rows/columns

For naive method, you should see hotspots in:

convolve_naive
tight inner loops over kernel elements

Step 2.4 — Compare naive vs fft in perf

Profile naive emboss:

perf record -g ./imgconv --filter emboss --method naive --repeat 30 --out /tmp/o.pgm
perf report

Now compare:

Does the hotspot move?
Are the hotspots “one big loop” (naive) vs “multi-phase FFT” (fft)?
Which functions dominate each method?

Part 3 — macOS Instruments Time Profiler (step-by-step)

Instruments is a GUI profiler. It’s excellent for seeing:

call trees
percent time per function
time over the course of the run (“phases”)

Step 3.1 — Build with debug symbols

make clean
make CXXFLAGS="-O3 -g -Wall -Wextra -pedantic"

Step 3.2 — Launch Instruments

Open:

Xcode → Open Developer Tool → Instruments
(or search “Instruments” in Spotlight)

Choose the template:

Time Profiler

Step 3.3 — Set the target executable

In the Instruments window:

Choose your executable: imgconv

Set arguments (example FFT emboss):

--filter emboss --method fft --repeat 30 --out /tmp/o.pgm

Click Record, let it run, then stop.

Step 3.4 — What to look at in Instruments

Go to the Call Tree and focus on:

Heaviest stack / highest percent
- That’s where your CPU time is going.
Turn on:
- “Hide System Libraries” (so you see your functions)
- “Invert Call Tree” (often easier to interpret)
- “Separate by Thread” (optional)
Identify the top 1–3 functions
- Note their percent time

Expected patterns

FFT method:

time concentrated in FFT routines and support loops
visible “phases”: forward FFT → multiply → inverse FFT

Naive method:

time concentrated in convolve_naive
fewer distinct phases

Part 4 — What you report back to the class (group deliverable)

Your group will present a short summary:

1) What you measured

which filter(s)
which method(s)
kernel sizes
repeat count
chrono times

2) What you profiled

perf or Instruments
top 2–3 hotspots for each method

3) Your explanation (the point of the lab)

Answer these questions:

Why is FFT slower for emboss/sharpen/edge?
What overhead dominates FFT runs?
For large blur, does FFT become competitive? Why?
Is the bottleneck compute (FFT math) or memory movement (copies, cache misses)?

You are not expected to provide a formal proof.
You are expected to provide measurement-backed reasoning.

Pitfalls to avoid (read this carefully)

Do not compare runs with different inputs or different repeat counts.
Do not draw conclusions from a single timing run.
If the program finishes too quickly, perf/Instruments won’t collect useful samples.
Increase --repeat until the run lasts at least ~1 second.
If you cannot see function names in perf/Instruments, you built without -g.

Optional extension (if time allows)

Try to find the “crossover point” where FFT becomes faster than naive for blur:

kernel sizes: 3, 7, 15, 31, 51, 101
plot or tabulate runtime vs kernel size
identify where the winner changes (if it changes at all)

That crossover point is hardware- and implementation-dependent — which is exactly why we measure.