How arthkamboj/parallel-mergesort works
1. Repository shape
- This is a small, header-only C++ sorting library centered on src/fast_sort.h.
- src/main.cpp is a usage/demo entry point, and src/main.exe is a generated binary artifact, not a source subsystem.
2. Primary architectural boundary
- The library exposes a template sorter API to application code, likely as ParallelSorter<T>.
- The consuming program provides a container of elements; the sorter owns the orchestration of parallelism, temporary memory, and algorithm selection.
3. Top-level sort pipeline
- The core algorithm is a merge-sort-based pipeline with recursive subdivision, local sorting of small ranges, and merge phases to combine results.
- The sort entry point allocates or initializes shared state once, then drives the recursion tree through parallel or sequential branches depending on size and depth.
4. Parallel execution model
- The parallel subsystem uses a decentralized work-stealing design rather than a single global queue.
- Each worker thread maintains its own deque protected by a CRITICAL_SECTION; workers prefer local work and only steal when idle, which reduces contention on shared synchronization primitives.
5. Task scheduling and load balancing
- Recursive sort work is turned into tasks that can be pushed onto worker-local queues.
- The scheduler limits over-parallelization with two gates: a minimum problem size threshold and a maximum recursion depth based on core count, so the system does not keep spawning tasks after available CPU parallelism is saturated.
6. Worker thread lifecycle
- Idle workers do not block immediately; they first spin using _mm_pause() and then yield with SwitchToThread() if no work appears.
- This design targets low-latency task pickup for short-lived merge/sort jobs while still avoiding a pure busy-wait when the machine is saturated.
7. SIMD acceleration path
- Integer-heavy merge/copy operations use AVX2 intrinsics through __m256i, moving 256 bits at a time.
- The implementation is template-specialized so that arithmetic types like int can take the SIMD fast path, while non-vector-friendly types fall back to the generic implementation.
8. Sequential fallback path
- Small subarrays bypass the parallel scheduler and use an optimized sequential sort.
- This boundary is important to the architecture: the library intentionally trades parallelism for lower overhead below the configured threshold.
9. Memory management model
- The algorithm uses a single auxiliary scratchpad buffer allocated once per top-level sort.
- That buffer is threaded through recursive calls, avoiding repeated heap allocations and reducing cross-thread allocator contention during merge phases.
10. Platform and runtime dependencies
- The implementation is Windows-specific in practice because it relies on Windows threading primitives and scheduling calls.
- AVX2 support is required for the optimized integer path, and the build flags in the README reflect that the architecture depends on compiler support for both optimization and x86 SIMD extensions.
11. How data flows through the system
- Application code calls the sorter with a collection.
- The sorter partitions the input recursively, schedules work onto worker-local queues, performs local sorts or merges, uses the shared scratch buffer for merging, and finally writes the sorted result back to the caller’s container.
12. What is not present
- There is no visible multi-module service boundary, no networking, no persistence layer, and no external runtime dependency beyond the OS and CPU features.
- Architecturally, this is a single-library computational engine with a thin demo application around it.
Main entry points: fast_sort.h Partitioning · main.cpp Demo main
Components 18
Demo app
Usage entry point and example consumer
- Demo main · Usage and demonstration entry point
src/main.cpp
Sort library
Header-only parallel merge-sort engine
- Sorter API · Public sorter interface used by application code
src/fast_sort.h - Sort orchestrator · Top-level sort driver that sets up shared state and launches work
src/fast_sort.h - Partitioning · Splits the input into smaller ranges for recursive processing
src/fast_sort.h - Size gate · Limits parallelization for small subarrays
src/fast_sort.h - Depth gate · Caps recursion depth based on available parallelism
src/fast_sort.h - Seq sort · Optimized local sort for small ranges
src/fast_sort.h - Merge phase · Combines sorted subranges during the merge-sort pipeline
src/fast_sort.h - Scratch buffer · Single shared temporary buffer reused across recursive calls
src/fast_sort.h - Task builder · Turns recursive sort work into schedulable tasks
src/fast_sort.h - Work stealing · Decentralized scheduler that prefers local work and steals when idle
src/fast_sort.h - Local deque · Per-worker task deque protected by a critical section
src/fast_sort.h - Worker loop · Worker lifecycle with spin, pause, and yield behavior
src/fast_sort.h - Spin wait · Short idle phase using processor pause instructions
src/fast_sort.h - Thread yield · Falls back to OS thread yielding when no work is available
src/fast_sort.h - AVX2 path · Vectorized merge and copy operations for arithmetic types
src/fast_sort.h - Generic path · Non-vectorized implementation for other element types
src/fast_sort.h - Windows runtime · Uses Windows threading and scheduling primitives
src/fast_sort.h
Connections 18
- Demo main → Sorter API: calls · Demo program invokes the sorter
- Sorter API → Sort orchestrator: enters · Public API forwards to the top-level sort driver
- Sort orchestrator → Partitioning: subdivides · Driver recursively partitions the input range
- Partitioning → Size gate: checks · Uses problem-size threshold before spawning work
- Partitioning → Depth gate: checks · Uses depth cap to avoid over-parallelization
- Partitioning → Seq sort: fallback · Small ranges are sorted locally
- Partitioning → Task builder: spawns · Parallel branches become schedulable tasks
- Task builder → Work stealing: enqueued by · Tasks are submitted to the work-stealing scheduler
- Work stealing → Local deque: uses · Each worker maintains a local deque
- Work stealing → Worker loop: runs on · Scheduler is executed by worker threads
- Worker loop → Spin wait: idles with · Workers first spin briefly when idle
- Spin wait → Thread yield: then · Idle workers yield if no work appears
- Work stealing → Windows runtime: depends on · Relies on Windows synchronization and scheduling calls
- Sort orchestrator → Scratch buffer: allocates · Top-level sort creates one shared scratch buffer
- Partitioning → Merge phase: merges with · Recursive results flow into merge phases
- Merge phase → Scratch buffer: reuses · Merges read and write through the shared auxiliary buffer
- Merge phase → AVX2 path: specializes to · Arithmetic types use the AVX2 fast path
- Merge phase → Generic path: falls back to · Other types use the generic implementation