Benchmarking and Profiling

The previous lesson showed, by running, that a body runs correctly, but measured that this demonstration stays bounded by a limited number of inputs and the decisions of whoever writes the test. This lesson applies the same “guarantee established by running” idea to a completely different question: which of two implementations does less work? The compiler never asks this question, either — both implementations pass type checking, both compile, and the compiler expresses no opinion at all about how many steps either takes to reach a result.

This measurement carries a hard constraint specific to Rust: the compiler’s own distribution has a benchmarking attribute, but this attribute is not available on the stable release — it can only be used on the compiler’s unstable (nightly) branch. Because this lesson runs on the stable compiler, it never uses this attribute; duration is never printed in any lesson of this curriculum anyway — the value a duration takes on this machine does not hold on another machine; the same program, even on the same machine, is affected by another process running in the background, by what the cache happens to hold at that moment, or by the operating system’s scheduling decision. So the question “which implementation’s duration is shorter” is never asked in this lesson; what is asked instead is “which implementation does how many operations.” The Production Go: Testing, Tooling and Performance course measured performance claims in Go with allocations-per-operation instead of duration; this lesson applies the same principle to comparison and copy counts — both come from the same reasoning: a number independent of the environment is a more reliable unit of measurement than a duration dependent on it.

Comparing by Operation Count

Two sorting implementations that do the same job — selection sort and insertion sort — are run on the same array. Both sort the result correctly, but each sorts by making a different number of comparisons and a different number of copies. To make this difference visible, both implementations write an increment to a shared counter on every comparison and every copy.

Selection sort searches the array’s remaining unsorted portion for the smallest element, and once it finds it, moves it right behind the sorted portion, repeating this step to the end of the array — at every step, all remaining elements are examined, but a swap happens only once. Insertion sort instead starts from the beginning of the array and places each new element by shifting it back into the correct position within the already-sorted preceding portion — placing one element may require several shifts, but each shift only compares against neighboring elements. Both implementations arrive at the same result; what is measured is the number of steps they take to get there.

// operation_counter.rs — comparison and copy counter, shared between two sorting implementations
#[derive(Default)]
pub struct OperationCounter {
    pub comparisons: u64,
    pub copies: u64,
}

pub fn selection_sort(array: &mut [i32], counter: &mut OperationCounter) {
    let n = array.len();
    for i in 0..n {
        let mut smallest = i;
        for j in (i + 1)..n {
            counter.comparisons += 1;
            if array[j] < array[smallest] {
                smallest = j;
            }
        }
        if smallest != i {
            array.swap(i, smallest);
            counter.copies += 1;
        }
    }
}

pub fn insertion_sort(array: &mut [i32], counter: &mut OperationCounter) {
    let n = array.len();
    for i in 1..n {
        let value = array[i];
        let mut j = i;
        while j > 0 {
            counter.comparisons += 1;
            if array[j - 1] <= value {
                break;
            }
            array[j] = array[j - 1];
            counter.copies += 1;
            j -= 1;
        }
        array[j] = value;
        counter.copies += 1;
    }
}

PL9. selection_sort searches for the smallest remaining element at every step and, once it finds it, places it with a single swap — so its comparison count is high, but its copy count is low. insertion_sort, instead, places each element by shifting it into the correct position within the already-sorted portion — its comparison count depends on the input’s arrangement, its copy count depends on how many elements get shifted. Both implementations produce the same result, but by a different path.

// measurement.rs — operation count of two sorting implementations on the same array
mod operation_counter;
use operation_counter::{insertion_sort, selection_sort, OperationCounter};

fn main() {
    let input: [i32; 12] = [9, 3, 7, 1, 8, 2, 6, 4, 10, 5, 12, 11];

    let mut array_a = input;
    let mut counter_a = OperationCounter::default();
    selection_sort(&mut array_a, &mut counter_a);

    let mut array_b = input;
    let mut counter_b = OperationCounter::default();
    insertion_sort(&mut array_b, &mut counter_b);

    println!("selection result: {:?}", array_a);
    println!("insertion result: {:?}", array_b);
    println!("both gave the same result: {}", array_a == array_b);
    println!();
    println!("{:<16}{:<14}{}", "implementation", "comparisons", "copies");
    println!("{:<16}{:<14}{}", "selection", counter_a.comparisons, counter_a.copies);
    println!("{:<16}{:<14}{}", "insertion", counter_b.comparisons, counter_b.copies);
}

selection result: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
insertion result: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
both gave the same result: true

implementation  comparisons   copies
selection       66            9
insertion       32            34

On this twelve-element array, selection sort made sixty-six comparisons and nine copies; insertion sort made thirty-two comparisons and thirty-four copies. PL10. Neither implementation is “fewer” in both columns: selection sort loses on comparisons but wins on copies, insertion sort is exactly the opposite. Producing a single number (“total operations”) would have hidden this difference; keeping two separate counters makes visible, separately, which implementation uses more of which resource.

How merging comparisons and copies into a single total could mislead can be seen in these numbers: once seventy-five (66 + 9) is added up against sixty-six (32 + 34), insertion sort looks like it “did fewer operations.” But this total counts a comparison and a copy as the same unit — when in fact the two are different operations that can carry different costs. The counter deliberately kept these two operations separate; a merged total hides how economical selection sort is with copies (only nine).

These two counters are also a form of profiling. While benchmarking compares two implementations against each other, profiling asks where a single implementation spends its work — which step, which kind of operation makes up how much of the total work. OperationCounter‘s two separate fields do exactly this: almost all of selection sort’s work sits in comparisons (sixty-six comparisons against nine copies), while insertion sort’s work is distributed more evenly between the two kinds (thirty-two comparisons against thirty-four copies). In a real program, a profiling tool usually shows which function consumes how much of the total duration; this lesson uses operation kind instead of duration, but the question is the same: where does the work go?

Distinguishing this from a related idea: the Production Go: Testing, Tooling and Performance course’s Benchmarking lesson measured how many allocations a body made per operation — what was counted there was whether new memory was allocated on the heap, and how many times that repeated within a function call. This lesson has no memory allocation at all; both sorts sort the input array in place (&mut [i32]), building no new array or structure. What is counted are the algorithm’s direct steps, like comparisons and copies. Both use a number instead of a duration, but what the number represents differs: one counts resource consumption (how many times space was requested from the heap), this lesson counts the algorithm’s own work steps (how many times two values were compared, how many times a value was moved).

The guarantee this number gives comes from running, not from the compiler — and nobody watches this number continuously. The compiler checked both implementations’ types, confirmed both carry the same signature, but never asked which one makes fewer comparisons; only the run above answered that question, and the answer is valid only for that run — if the array changes, if either one’s source code changes, there is no way to say the numbers still hold without rerunning the same measurement. The class measured in this lesson is nobody checks it: the two implementations’ relative cost is not continuously watched by any tool, it can only be learned with a one-off run whenever requested.

This is a separate place from the handed-to-the-writer class measured in the previous lesson. There, a property test existed, and that test answered the same question again whenever it was rerun — the responsibility had been handed to the writer, but it could be made continuous in the form of a test. In this lesson there is no such test; the run above is a one-off observation, and turning it into a test that reruns automatically whenever the source changes lies outside this lesson’s scope. Even if such a test had been written, the writer would still be the one deciding what counts as “good” (which number needs to stay below which limit) — but checking would at least become continuous then. As things stand today, checking is limited to just this lesson’s run.

A Bounding Measurement

The numbers above belong to a single input, a shuffled twelve-element array. How do the numbers change when the same two implementations run on a different input? The run below applies the same two functions to an already-sorted array.

// bounding_measurement.rs — same implementations, how operation count changes on an ordered array
mod operation_counter;
use operation_counter::{insertion_sort, selection_sort, OperationCounter};

fn main() {
    let ordered: Vec<i32> = (1..=12).collect();

    let mut a = ordered.clone();
    let mut counter_a = OperationCounter::default();
    selection_sort(&mut a, &mut counter_a);

    let mut b = ordered.clone();
    let mut counter_b = OperationCounter::default();
    insertion_sort(&mut b, &mut counter_b);

    println!(
        "selection comparisons={} copies={}",
        counter_a.comparisons, counter_a.copies
    );
    println!(
        "insertion comparisons={} copies={}",
        counter_b.comparisons, counter_b.copies
    );
}

selection comparisons=66 copies=0
insertion comparisons=11 copies=11

PL11. Selection sort’s comparison count did not change: still sixty-six — even though the input is already ordered, selection sort still scans every remaining element one by one, because the only way to find the smallest is to look at all of them. Insertion sort’s comparison count, however, dropped from thirty-two to eleven, and its copy count dropped from thirty-four to eleven: in an already-ordered array, every element is larger than the one before it, so it keeps its place with a single comparison, and no shifting is needed at all.

An input in the opposite direction gives an exactly opposite result. Had the array been sorted from largest to smallest, insertion sort would have had to shift every element all the way to the start of the sorted portion — its copy count would climb even above the shuffled array’s thirty-four, while selection sort’s would again stay fixed at sixty-six. The same two implementations, across three different input arrangements (shuffled, ordered, reverse-ordered), stand in three different positions relative to each other: sometimes one does less work, sometimes the other, sometimes both do the same fixed amount. Selection sort’s comparison count staying the same every time is not a flaw, it is the direct result of the algorithm’s structure — wherever an element sits, every remaining element still gets scanned.

This almost reverses the first run’s result, though not entirely: selection sort’s comparison count is still larger than insertion sort’s, but the ratio between them changed considerably. In the first array, insertion sort made fewer comparisons; the same holds in this array, but the gap grew much wider — from thirty-two against sixty-six, to eleven against sixty-six. The same two implementations, on a different input of the same length, stand at a very different ratio relative to each other. PL12. This shows that operation count is dependent on the input, and that a measurement taken on a single input says nothing about another input — selection sort’s comparison count is independent of the input, while insertion sort’s is entirely dependent on it.

Operation count itself does not mean duration, either. A comparison and a copy may not carry the same cost — if the copied value is a large structure, a copy can be far more expensive than an integer comparison; here, since an i32 is copied, this difference is small, but the counter knows nothing about this difference at all, it only counts how many times each ran. It is also possible for an implementation that does fewer operations to actually have a longer duration: the kind of operations, the memory access pattern, and the hardware itself all affect the outcome.

Memory access pattern is a concrete example of this. While scanning the remaining elements, selection sort reads through the array from start to end continually; insertion sort, instead, only concerns itself with nearby neighbors. These two access patterns can use the hardware’s cache differently, and this difference never shows up in the operation count at all — even if two implementations make the same number of comparisons, one may access memory in an order more cache-friendly than the other’s more scattered order. This lesson does not measure such a difference, because measuring it would bring in real hardware and real duration; here, only the question “how many times” is answered, not “in what duration.” So the table above should not be read as “insertion sort is better” — it should only be read as “on this input, insertion sort made fewer comparisons and fewer copies,” and even that is no guarantee it will repeat on the next input.

Summary

• Two sorting implementations (selection_sort, insertion_sort) were compared by separately counting comparisons and copies with a shared counter; duration was never measured, printed, or compared anywhere.
• On a shuffled twelve-element array, selection sort made sixty-six comparisons and nine copies, insertion sort made thirty-two comparisons and thirty-four copies.
• The guarantee’s class is nobody checks it: how many operations each implementation makes is not continuously watched by any tool, it can only be learned with a one-off run whenever requested.
• On an already-ordered array, selection sort’s comparison count did not change (sixty-six), insertion sort’s dropped to eleven — operation count depends on the input.
• Operation count does not mean duration: a comparison and a copy do not carry the same cost, and an implementation that does fewer operations can actually have a longer duration.
• A measurement taken on a single input says nothing about another input; a “fewer operations” claim cannot be written without being tied to which input it was measured on.

Next Step

This lesson showed that the relative cost of two implementations can only be learned by running, that this learning stays bounded to a single input, and that the compiler expresses no opinion on this at all — all three lessons (the closed flag in Dependencies and Feature Flags, the guarantee established by running in Testing and Property-Based Testing, the operation count in this lesson) are different faces of the same underlying fact: where the compiler stops, the remaining responsibility either falls to nobody, or is handed to a running process. The next lesson — this topic’s final one — applies the same “where the compiler never looks” question to an entirely different source: the explanation written next to a code block. The Documentation lesson shows that no tool checks whether a documentation sentence is correct, but that a runnable example embedded inside that same documentation can genuinely be tested — that two different guarantee classes can stand side by side in the same source.