Skip to content

v1.0.3

Choose a tag to compare

View all tags
@ysemenenko ysemenenko released this 08 Apr 16:37
v1.0.3
6e72ed2

Highlights

Performance optimization series — three independent wins, each measured with BenchmarkDotNet:

  • MinHeap.ReplaceMin fast path in the merge inner loop: 30% faster at K=8, 34% at K=16. Replaces ExtractMin + Insert (two heap ops) with Peek + ReplaceMin (one heap op) when the source still has more data.
  • Pipelined parallel chunk creation: SortOptions.DegreeOfParallelism is no longer a dead option. One reader thread feeds N sort+write workers via a bounded BlockingCollection. ~1.12× speedup at P=4 on a 4-physical-core box for in-memory workloads (wider for disk-bound).
  • Knuth's Replacement Selection algorithm (SortOptions.UseReplacementSelection): produces runs that average 2× the heap size for random input. On a 50K-record dataset with 32 KB heap: 74 chunks → 38 chunks (49% fewer), 3 → 2 merge passes, 32% less memory allocated.

Test count grew from 35 → 51 covering RS correctness, parallel determinism stress, race conditions, cancellation safety. New tests/ExternalSorting.Benchmarks/ project with three BenchmarkDotNet suites (MergeBenchmarks, ChunkStrategyBenchmarks, SortBenchmarks).

Backward compatible: every new feature is opt-in via SortOptions, defaults preserve previous behavior except DegreeOfParallelism which now actually does something (was declared but unused before).

Changes since v1.0.2

  • release v1.0.3 — perf benchmarks, README, version bump
  • test(parallel): correctness + race + cancellation coverage for parallel chunk creation
  • feat(chunk): Replacement Selection algorithm for ~2x larger runs
  • test(bench): BenchmarkDotNet project for end-to-end sort
  • perf(chunk): pipelined parallel chunk creation honoring DegreeOfParallelism
  • perf(merge): use ReplaceMin in MergeBatch hot loop
Assets 2
Loading