Selection Operator Performance — Truncation vs Tournament vs Roulette

This article compares the three major selection operators in internal/runtime/ares_evolution/genome/selection.go using real go test -bench output — their asymptotic complexity, memory behavior, and the right situation for each. Every number below is a single -count=1 measured run, not an invented figure.

⚠️ Note: Go benchmark ns/op depends on the machine, the compiler, and load. The numbers below were measured on go1.27.1 / darwin / arm64 (Apple Silicon) with -benchtime=200ms -count=1 and are meant to convey order-of-magnitude only. Treat the earlier draft's certainty about a specific "Apple M3 Max single run" as non-reproducible.

1. What we benchmark, and where it lives

All benchmarks live in internal/runtime/ares_evolution/genome/benchmark_test.go.

The same file also holds whole-cycle / whole-system benches: BenchmarkEvolve_OneGeneration, BenchmarkEvolveOnIdle_OneGeneration, BenchmarkEvolve_MultipleGenerations, BenchmarkRealWorldEvolution (pop 20, 100 generations of EvolveOnIdle), BenchmarkApplyFitnessSharing, and crossover benchmarks.

2. Measured data (go1.27.1 darwin/arm64, -count=1)

2.1 TruncationSelection

pop_10    161.2 ns/op
pop_100   5669  ns/op
pop_500   52825 ns/op
pop_1000  156384 ns/op

Cost is almost entirely the sort plus a slice copy.

2.2 SortByScore (sort baseline)

pop_10    208.7 ns/op
pop_100   6098  ns/op
pop_500   51463 ns/op
pop_1000  144377 ns/op

Truncation and SortByScore are the same order of magnitude (truncation's pop_500 is a touch under the bare sort because the benchmark also builds a result slice; within measurement noise).

2.3 TournamentSelection

pop_50  k=2   3875 ns/op   k=3  4013   k=5  4299   k=10  5514
pop_200 k=2  31903 ns/op   k=3 34263   k=5 34876   k=10 38656

Observation: going k from 2 to 10 (a 5× change) moves pop200 only from ~32µs to ~39µs (≈ +21%) — far from linear. The reason is in the code: pickUniqueIndices uses a Fisher–Yates partial shuffle whose cost is dominated by poolSize, and pool copying plus slice construction dominate. So raising k to raise selection pressure costs almost nothing computationally — but it also means tournament's dominant cost is a fixed constant (copy, slice building), not the number of comparisons.

2.4 RouletteWheelSelection

pop_10    202.1 ns/op
pop_100   2902  ns/op
pop_500   43097 ns/op
pop_1000  160606 ns/op

Each spin walks the full cumulative-weight array (O(n)); selecting n/2 individuals is O(n²). So by pop=1000, roulette (160.6µs) has tipped past truncation (156.4µs).

3. The crossover point

flowchart LR
    subgraph small["pop ≈ 10-100"]
        t1[Truncation ~161-5669 ns]
        r1[Roulette ~202-2902 ns]
        NOTE1[roulette slightly faster / comparable]
    end
    subgraph large["pop ≥ 1000"]
        t3[Truncation ~156 µs]
        r3[Roulette ~161 µs]
        NOTE3[truncation wins; roulette is O(n²)]
    end

• Small populations: effectively a wash (microseconds); which is "fastest" is drowned in noise.
• Around pop≈500 they cross: truncation's O(n log n) meets roulette's O(n²).
• Tournament: the absolute time is the highest of the three (already ~32µs at pop200), driven by result construction and shuffling — but it's flat as k grows.

4. Memory allocation

Following the logic of the same benchmarks: all three copy the population and build a result slice (allocations grow linearly with population). Tournament is the heaviest per Select because of the shuffle scratch array plus the result slice. For exact B/op and allocs/op, run:

go test -bench=BenchmarkTournamentSelection -benchmem ./internal/runtime/ares_evolution/genome/

(The qualitative statement is safe: sort/truncation allocators don't grow with size — the bench copies the population slice once; roulette/tournament allocate fresh slices per select, so allocs grow linearly. Exact numbers must be measured.)

5. Complexity at a glance (from code and comments, not invented)

SUS deserves a special mention: versus roulette it takes one random start and then evenly spaced picks, guaranteeing a more even sampling distribution and less genetic drift — exactly what the comment states: "guarantees that an individual with above-average fitness is selected at least floor(fitness/avg_fitness) times."

6. How to choose: an engineering judgment

The code comments already point the way:

The most important reality: in LLM-driven evolution a single scoring call takes seconds, while any selection operator's whole batch takes microseconds. The operator's algorithmic effect — diversity, convergence quality — matters far more than tens of microseconds. Don't sweat 5% of ns/op; choose the operator that is less likely to converge prematurely on your task distribution.

7. Appendix: reproducing

go test -run=^$ \
  -bench='Benchmark(Truncation|Tournament|RouletteWheel|SortByScore)Selection?$' \
  -benchtime=200ms -count=1 -benchmem \
  ./internal/runtime/ares_evolution/genome/

Baseline reproduced: go1.27.1 darwin/arm64, single -count=1 run. Add -count=3 for variance and discount the first run's GC disturbance.