multithreading-optimization-inverted-tree

this is a way to handle multi threading so that you get more efficiency out of it and faster compute times

👉 CLICK HERE TO RUN THE LIVE BENCHMARK

Co-authored by sighthough and Googles Gemini.

feel free to rip the index file (its the tech demo) and also a guide provided for how you can make it work for your own use !

Architectural Logic of the Top-Down Task Tree

Top-down tree parallelism—often called Fork-Join Task Parallelism or Divide-and-Conquer Parallelism—decouples parallel work from fixed hardware threads. Instead of assigning static iteration ranges to threads, the algorithm dynamically decomposes a problem domain into a hierarchical task tree.

                             [0 ... N)                     <-- (1) Root Task
                            /         \
                 FORK      /           \      FORK
                          v             v
                     [0 ... N/2)     [N/2 ... N)           <-- (5)(6) Sub-Problem Bisection
                     /        \       /        \
                    v          v     v          v
                  [T1]        [T2]  [T3]       [T4]        <-- (3) Leaves (Sequential Cutoff)
                    \          /     \          /
                     \        /       \        /
                      v      v         v      v
                     [Res 0..N/2)     [Res N/2..N)         <-- (7)(8) JOIN & Reduce
                            \             /
                             \           /
                              v         v
                             [Final Result]

The model operates in three distinct logical phases across the call stack:

Phase 1: The Top-Down Splitting (FORK Phase)

1. The root process takes the full range $[0, N)$ and splits it into two equal ranges: $[0, \frac{N}{2})$ and $[\frac{N}{2}, N)$.
2. The left half is forked as an independent, asynchronous task context and placed into a thread-local queue or task scheduler.
3. The right half continues down the current execution path on the same thread, preventing redundant stack allocations.
4. This bisection recurses downwards, creating an implicit binary tree of depth $D = \log_2\left(\frac{N}{\text{CUTOFF}}\right)$.

Phase 2: Base-Case Execution (LEAF Phase)

1. Recursion halts when the problem size reaches a pre-defined Sequential Cutoff Threshold ($\le \text{CUTOFF}$).
2. The leaf node executes a tight, sequential loop over its range.
3. Operating sequentially at the leaves ensures that the computational work outweighs the overhead of task creation, stack pushing, and queue management.

Phase 3: The Bottom-Up Merging (JOIN Phase)

1. As leaf functions complete, execution unwinds up the call tree.
2. The parent node hits a synchronization barrier (join or taskwait), blocking until its left child task completes.
3. The parent combines the results of the left child and right child using an associative operator (e.g., addition, bitwise operations, or bounds merging).
4. The merged value returns up the stack to the root node.

---

Universal Barebones Implementation Template

Below is language-agnostic, imperative pseudo-code representing the minimal implementation of a parallel top-down tree reduction. It uses standard scalar primitives and pointer/slice indexing, making it easily translatable to C, C++, Rust, Go, Java, C#, or Python.

// Top-Down Parallel Tree Reduction Kernel
// Computes associative reduction over array slice [start, end)
int64_t parallel_tree_reduce(const int32_t* array, size_t start, size_t end, size_t cutoff) {  // (1)
    size_t length = end - start;                                                                // (2)

    // --- LEAF BASE CASE ---
    if (length <= cutoff) {                                                                     // (3)
        int64_t local_accumulator = 0;
        for (size_t i = start; i < end; ++i) {
            local_accumulator += (int64_t)array[i];
        }
        return local_accumulator;
    }

    // --- TOP-DOWN FORK ---
    size_t mid = start + (length / 2);                                                         // (4)

    TaskHandle left_task = SPAWN_ASYNC_TASK(parallel_tree_reduce, array, start, mid, cutoff);   // (5)

    int64_t right_result = parallel_tree_reduce(array, mid, end, cutoff);                       // (6)

    // --- BOTTOM-UP JOIN ---
    int64_t left_result = AWAIT_TASK_RESULT(left_task);                                        // (7)

    return left_result + right_result;                                                          // (8)
}

---

Technical Component Breakdown

(1) Function Signature & Range Parameters

int64_t parallel_tree_reduce(const int32_t* array, size_t start, size_t end, size_t cutoff)

• Logic: Accepts a pointer/reference to contiguous memory (array), an explicit sub-range half-open interval $[start, end)$, and the performance-tuning parameter cutoff.
• State Scope: Half-open intervals $[start, end)$ guarantee that $start + (end - start) = end$, eliminating off-by-one errors during bisection.
• Return Value: Returns a 64-bit integer (int64_t) to prevent numerical overflow during the reduction of smaller 32-bit types (int32_t).

---

(2) Range Length Calculation

size_t length = end - start;

• Logic: Determines the exact element count contained within the current subtree node.
• Role: Drives both the base-case decision check (3) and the midpoint calculation (4).

---

(3) Sequential Cutoff Threshold (Base Case)

if (length <= cutoff) { ... }

• Logic: Checks if the node's payload is small enough to run sequentially on the current thread.
• Why it Matters: Thread scheduling, queue allocation, and task creation impose a fixed time overhead $\Delta t_{\text{overhead}}$. If a task executes fewer operations than $\Delta t_{\text{overhead}}$, parallelism degrades total throughput.
• Hardware Alignment: Ideal cutoff values balance task creation cost against cache utilization. Setting cutoff so that $N_{\text{bytes}} = \text{cutoff} \times \text{sizeof(element)}$ fits within the processor's L1 data cache (32 KB - 128 KB) or L2 cache (512 KB - 1 MB) maximizes memory throughput.

---

(4) Safe Midpoint Bisection

size_t mid = start + (length / 2);

• Logic: Computes the array index where the current range splits into two child subtrees.
• Numerical Safety: Formulated as start + (length / 2) rather than (start + end) / 2. The latter expression risks integer overflow when operating on large memory-mapped arrays where $start + end > \text{SIZE_MAX}$.

---

(5) Asynchronous Task Spawning (Left Subtree FORK)

TaskHandle left_task = SPAWN_ASYNC_TASK(parallel_tree_reduce, array, start, mid, cutoff);

• Logic: Instantiates a new execution node representing the left child range $[start, mid)$ and yields control of that node to the runtime's task scheduler.
• Under the Hood:
• The scheduler encapsulates the function pointer and arguments into a task closure or frame.
• The task frame is pushed onto the thread-local work queue (deque) of the invoking CPU core.
• If another worker thread in the system is idle, it can steal this task from the tail of the queue (Work-Stealing Algorithm), achieving dynamic load balancing across variable CPU frequencies.

---

(6) Direct Subtree Execution (Right Subtree Optimization)

int64_t right_result = parallel_tree_reduce(array, mid, end, cutoff);

• Logic: Recursively executes the right sub-range $[mid, end)$ immediately on the current thread, bypassing the task queue.
• Why it Matters: Spawning tasks for both children (left and right) doubles queue pushes, memory allocations, and runtime overhead. By executing one child directly on the current call stack, stack allocations scale with the tree depth $O(\log N)$ rather than node count $O(N)$.

---

(7) Task Synchronization (JOIN Phase)

int64_t left_result = AWAIT_TASK_RESULT(left_task);

• Logic: Blocks the parent execution context until the asynchronously spawned left_task has completed and returned its reduced scalar value.
• Work-Stealing Synergy: In modern job systems (such as Intel TBB, Cilk, or Rust Rayon), calling AWAIT_TASK_RESULT does not stall or sleep the physical OS thread. If left_task is still processing, the current thread executes other tasks from its queue while waiting, keeping CPU utilization high.

---

(8) Bottom-Up Combination / Reduction

return left_result + right_result;

• Logic: Merges the evaluations of the left and right subtrees into a single scalar result, completing the node's lifecycle and passing the result up to its parent.
• Generalization: To adapt this template to other algorithms, replace the addition operator + with any binary associative operator:
• Min/Max Search: $\min(a, b)$ or $\max(a, b)$
• Bitwise Parity: $a \oplus b$ (XOR)
• Image / Spatial Bounding: Merge bounding boxes $\text{AABB}_a \cup \text{AABB}_b$
• Prefix Scans: Two-pass tree scans for parallel prefix sums.

---

Language Implementation Mapping

Language / Framework	Spawn Primitive (5)	Join Primitive (7)
C / C++ (OpenMP)	#pragma omp task shared(left_res)	#pragma omp taskwait
C++20 (std::async)	std::async(std::launch::async, ...)	future.get()
Rust (Rayon)	`rayon::join(
Go (Goroutines)	go func() { ... }()	<-ch (Channel read) or sync.WaitGroup
Java (ForkJoin Framework)	leftTask.fork()	leftTask.join()
C# (.NET TPL)	Task.Run(() => ...)	task.Result / await task