Selection Operator Benchmark Performance Comparison——Truncation vs Tournament vs Roulette Measured

This article is based on actual measured data from Apple M3 Max, providing a comprehensive performance comparison of the three major selection operators in the ARES GA framework. It covers ns/op, memory allocation, complexity scaling with population size, 3-run variance analysis, and practical guidance on choosing the optimal operator based on the scenario. All data comes from real go test -bench output and 3-run multi-round tests.

1. Test Environment and Methodology

1.1 Hardware Platform

1.2 Data Sources

This article analyzes two independently run benchmark results:

• evolution_bench.txt: Single run (-count=1), covering the full evolution system + selection operators
• genome_bench.txt: 3 runs (-count=3), providing variance information, genome package only
• benchmark_results.json: Summary of 47 benchmarks with performance ratings (excellent/good/acceptable)

1.3 Subjects Under Test

All tests use b.ReportAllocs() to report memory allocation, with controlled RNG seeds for reproducibility.

2. Detailed Benchmark Data

2.1 TruncationSelection

Selection strategy: sort by score descending → take top N% (top 30% in the test). Total cost is almost entirely dominated by sorting.

Single run results:

3-run variance analysis:

Key finding: Run 1 of pop_500 at 96,348 ns is clearly abnormal (about 2× the latter two runs). This is likely due to GC triggering + memory allocation from the sort operation causing first-run latency. Excluding run 1, the pop_500 mean is 47,295 ns, consistent with the scaling trend.

2.2 TournamentSelection

Randomly draw k individuals from the population and select the best among them. The test selects half the population (25 out of 50 for pop=50, 100 out of 200 for pop=200).

pop=50 (select 25):

pop=200 (select 100):

k-value cost analysis (pop=200, 3-run mean):

② Cost per Select = total time / number of selections. pop=200 with selectN=100, 100 selections total.

Key finding: Increasing k from 2 to 10 (5×) only results in approximately 11% performance degradation. This is because the pickUniqueIndices() implementation is O(poolSize) rather than O(k)——it randomly picks across the entire population, so the cost is largely independent of k.

2.3 RouletteWheelSelection

Fitness-proportional selection: individuals with higher scores have a greater probability of being selected. Each selection traverses the entire population to compute cumulative probabilities.

Single run results:

3-run variance analysis:

Key finding: Roulette results are very stable, with the coefficient of variation consistently around 1%. This is because its computation path is highly predictable——each time it traverses the entire population to compute cumulative probabilities, with no branch prediction issues like sorting.

2.4 SortByScore

Not an independent selection operator, but a foundational operation used by most selectors (truncation, rank, lineage rank, etc.).

Single run results:

3-run mean:

Key finding: SortByScore has extremely low 3-run variance (<1%), making it the most predictable operation. The test includes 20% unevaluated strategies (Score=-1), which are placed at the end during sorting, not affecting the stable sorting property.

3. Complexity Analysis and Scaling Comparison

3.1 Algorithmic Complexity vs Measured

Complexity comparison (time unit: ns/op):
                pop=10    pop=100   pop=500   pop=1000
Truncation:       183      5,490    46,136    129,687    O(n log n)
SortByScore:      229      5,765    44,288    116,356    O(n log n)  
Roulette:         205      2,760    41,703    151,649    O(n²) ③
Tournament(k=2):  -         -       2,822④    29,651⑤   O(k·n)

③ Roulette selects n/2 individuals = executes n/2 traversals, each O(n), total complexity O(n²)
④ pop=50, selectN=25
⑤ pop=200, selectN=100

Key insights:

• Truncation and Roulette cross over around pop=500: Roulette is faster when pop<500, but Truncation overtakes it when pop>500. This is because the O(n log n) cost of sorting is not significant for small n, while the O(n²) cost of roulette accelerates as n grows.
• Tournament's memory consumption is the biggest challenge: At pop=200, it uses up to 180KB/op, 22× that of truncation. This is because each Select creates a result slice.

3.2 Partition Analysis by Population Size

Small populations (pop < 50):
  Operator       ns/op    Recommendation
  Truncation      183     ★★★★★  (Best)
  Roulette        205     ★★★★☆  (Close)
  Tournament      2,822   ★★★☆☆  (at pop=50)

Medium populations (pop 100-500):
  Operator       ns/op    Recommendation  
  Roulette(p=100) 2,760  ★★★★★  (Best, 4.1μs/select)
  Truncation(p=100)5,490  ★★★★☆  (≈ 2× roulette)
  Tournament(p=200)29,651 ★★★☆☆  (7× roulette)

Large populations (pop 1000+):
  Operator       ns/op    Recommendation
  Truncation    129,687   ★★★★★  (Best)
  Roulette      151,649   ★★★★☆  (17% slower than truncation)
  Tournament     ~33,662⑥ ★★★★★  (Selects half of all, but higher precision)

⑥ Tournament(pop=200) conversion: selecting all 1000 individuals would require approximately 10× time ≈ 336,620 ns

4. In-depth Memory Allocation Analysis

4.1 Allocation Pattern Comparison

Key observations:

1. Truncation has the most stable allocation: Always 3 allocations, only copies the population slice. alloc count does not vary with scale.
2. Tournament allocation grows linearly with population: 201 allocations (pop=200)——approximately 1 map operation for deduplication per select. This is the biggest optimization opportunity.
3. Roulette allocation grows slowly: From 4 (pop=10) to 10 (pop=1000), primarily from the cumulative probability array.

4.2 Average Cost per Select

Calculating the marginal cost of "selecting one individual" by dividing total time by the number of selected individuals:

pop=500, selectN=250:

  Truncation:  46,136 ns / 250 = 184.5 ns/select
  Roulette:    41,703 ns / 250 = 166.8 ns/select
  Tournament⑦: 46,136 / (500×0.5) / 50 ≈ difficult to compare

⑦ Tournament's Select() returns n individuals, but the internal cost per select
   is primarily determined by k (pickUniqueIndices → sort → pick best).

Key insight: At medium scale (pop=500), Roulette's marginal cost per select (166.8 ns) is actually lower than Truncation's (184.5 ns). This is because truncation requires sorting all 500 individuals at once, while roulette's batch selection amortizes the cost of building the cumulative probability array.

5. Overall Evolution System Performance Data

5.1 Full Evolution Cycle Benchmarks

End-to-end evolution system performance extracted from benchmark_results.json:

5.2 Selection Operator Share of Total Evolution Time

Using idle evolution for 10 generations at pop=20 (420μs) as an example:

Total time: 420,000 ns

Of which per generation:
  Selection operation (tournament, select 50%): ~6,000 ns × 10 = 60,000 ns
  Mutation operation: ~10,000 ns × 10 = 100,000 ns
  Evaluation: ~30,000 ns × 10 = 300,000 ns
  Other overhead (snapshots, lineage records, etc.): ~60,000 ns

Selection operations account for approximately 14% of total time.

Note: In actual LLM-driven evolution, LLM call cost accounts for 99%+. The computational overhead of selection operations (microseconds) is negligible compared to a single LLM API call's latency (seconds). Therefore, in real-world scenarios, the algorithmic effectiveness (solution quality) of the selection operator is far more important than its computational efficiency.

6. Application Scenario Guide for Each Operator

┌─────────────────────────────────────────────────────────┐
│                  Selection Operator Matrix                │
├────────────┬──────────┬──────────┬──────────┬───────────┤
│  Scenario   │Truncation│Tournament│ Roulette │ Best Pick │
├────────────┼──────────┼──────────┼──────────┼───────────┤
│  Rapid proto│    ✓     │          │    ✓✓    │ Roulette  │
│  LLM-driven │    ✓     │    ✓✓    │    ✓     │ Tournament│
│  pop<50     │    ✓✓    │          │    ✓✓    │ Truncation│
│  pop 100-500│    ✓✓    │    ✓     │    ✓✓    │ Roulette  │
│  pop>1000   │    ✓     │    ✓✓    │          │ Tournament│
│  Sorted output│   ✓✓   │          │          │ Truncation│
│  Selection   │          │    ✓✓    │          │ Tournament│
│  pressure ctl│          │          │          │           │
│  Low memory  │    ✓✓    │          │    ✓✓    │ Truncation│
│  Lineage     │          │    ✓✓    │          │ LineageRank│
│  diversity   │          │          │          │           │
└────────────┴──────────┴──────────┴──────────┴───────────┘

6.1 Recommended Usage Conditions for Each Operator

TruncationSelection:

• When to use: Small to medium populations (pop ≤ 500), need deterministic output, memory-sensitive
• When not to use: When exploration is needed (truncation's elitism accelerates convergence), or when sorting cost is non-negligible at very large pop sizes

TournamentSelection:

• When to use: Need fine-grained control over selection pressure (via k value), very large populations (cost independent of size)
• When not to use: Sensitive to per-run memory allocation (201 allocs/op for pop=200), need deterministic scenarios (non-seeded non-deterministic)

RouletteWheelSelection:

• When to use: Medium populations (100 ≤ pop ≤ 500), want score differences to drive selection probability
• When not to use: Score differences are very small (all individuals have similar scores, making selection nearly random), O(n²) cost is significant at very large pop sizes

7. Benchmark Code Analysis

7.1 Benchmark Test Design Quality

Design considerations for the three selection operator benchmarks:

// Truncation: sort + slice, excluding selector object creation
// Only measures the core operations of sorting and taking top-N
b.ResetTimer()
for i := 0; i < b.N; i++ {
    sorted := make([]*mutation.Strategy, len(population))
    copy(sorted, population)
    SortByScore(sorted)
    _ = sorted[:selectN]
}

// Tournament: includes selector creation, because NewTournamentSelection has parameter configuration
// Selector creation is outside ResetTimer, does not affect timing
sel, _ := NewTournamentSelection(WithTournamentSize(k), WithTournamentSeed(42))
b.ResetTimer()
for i := 0; i < b.N; i++ {
    _, _ = sel.Select(ctx, population, selectN)
}

// Roulette: similarly starts timing only after selector creation
sel, _ := NewRouletteWheelSelection(WithRouletteSeed(42))
b.ResetTimer()
for i := 0; i < b.N; i++ {
    _, _ = sel.Select(ctx, population, selectN)
}

Design differences:

• Truncation uses an inline implementation (not through the Select method) to reduce function call overhead, providing a purer measurement of sorting + truncation cost
• Tournament and Roulette both measure the full operator call path via the sel.Select() method
• All benchmarks complete RNG seeding and data generation before ResetTimer()

7.2 3-Run Variance Analysis Summary

Truncation's large variance stems from GC interference in the first run. Excluding the first run, pop=500's CV drops to 0.5%, comparable to SortByScore——which also confirms that Truncation's cost comes almost entirely from the sorting operation.

8. Summary

1. Small populations (pop ≤ 50): Truncation is the fastest selector (183ns), but Roulette is also close (205ns). The differences among the three are at the microsecond level, essentially negligible.

2. Medium populations (100 ≤ pop ≤ 500): Roulette is the optimal choice——below 3μs (pop=100) to 42μs (pop=500), with extremely low variance (<1.2%). Truncation requires about 2× the time at pop=100.

3. Large populations (pop ≥ 1000): Truncation overtakes Roulette (129μs vs 152μs, 17% faster). Tournament becomes the best choice for very large populations due to its O(k) cost and selection pressure control that is independent of population size.

4. Tournament's k value has minimal impact: Increasing k from 2 to 10 (5× growth) produces only about an 11% performance difference. Larger k values can be safely used to increase selection pressure.

5. In modern evolution systems, computational efficiency is no longer the primary constraint: In LLM-driven evolution, a single API call takes seconds, while selection operations take only microseconds. Therefore, the algorithmic effectiveness (population diversity, convergence speed, solution quality) of the selection operator is far more important than its performance numbers.

6. Memory allocation is the most easily overlooked cost: Tournament allocates 180KB per operation (201 allocs) at pop=200, while Truncation allocates only 8KB (3 allocs). In high-frequency call scenarios, this will significantly increase GC pressure.