star-line

commit b696d0f7b6d4564489bce772d451351101bddcfa
parent 206585bccb3a3b1f95ca53bdb869d89a87f5adf6
Author: Vincent Forest <vincent.forest@meso-star.com>
Date:   Mon,  4 May 2026 14:21:03 +0200

Improving Parallelism in tree construction

Until now, the parallelization policy treated a node's children as
eligible for parallel construction if, once added to the list of nodes
already identified as eligible for parallel construction, the size of
that list did not exceed the total number of threads.

Thus, with 4 threads and a tree arity of 8, the aforementioned policy
resulted in sequential tree construction because, starting from the root
node, the number of its children already exceeded the number of threads.

This commit modifies this policy by adding the node's children to the
list of nodes to be built in parallel, as long as the number of nodes
_already_ registered does not exceed the number of threads.
Consequently, there are not fewer, but more nodes to be built in
parallel than there are available threads. In the worst-case scenario,
there will therefore be less work than available threads. However, the
tree construction will still be parallelized and thus accelerated. For
instance, in the previous example, each thread will have to process 2
nodes.

Diffstat:
M
src/sln_tree_build.c
 | 
20
+++++++++++++++-----

1 file changed, 15 insertions(+), 5 deletions(-)
diff --git a/src/sln_tree_build.c b/src/sln_tree_build.c
@@ -1028,7 +1028,6 @@ partition_lines_breadth_first
   size_t nnodes = 0; /* Number of enqueud nodes */
 
   /* Miscellaneous */
-  const size_t nleaves_max = MMIN(nleaves_max_hint, QUEUE_SIZE_MAX);
   size_t nlines_total = 0;
   size_t nleaves = 0;
   size_t i = 0;
@@ -1088,6 +1087,17 @@ partition_lines_breadth_first
     size_t iline = 0;
     size_t inode = 0;
 
+
+    /* Check whether the number of registered leaves and currently processed
+     * nodes is greater than or equal to the recommended maximum number of
+     * leaves. If so, stop breadth-first partitioning and treat all registered
+     * nodes as leaves. The policy is therefore to accept more leaves than
+     * expected */
+    if(nnodes + nleaves >= nleaves_max_hint) {
+      nleaves += nnodes;
+      break;
+    }
+
     inode = DEQUEUE; /* Get the current node */
 
     /* Retrieve the range of lines contained within the node */
@@ -1108,10 +1118,10 @@ partition_lines_breadth_first
 
     /* Check whether, after adding the child nodes to the queue, the total
      * number of nodes in the queue, plus the number of leaves already created,
-     * does not exceed the maximum allowed number of leaves. If so, the
-     * breadth-first partitioning is complete and the nodes currently in the
-     * queue are all leaves */
-    if(nnodes + nchildren + nleaves > nleaves_max) {
+     * does not exceed the max size of the queue. If so, the breadth-first
+     * partitioning is complete and the nodes currently in the queue are all
+     * leaves */
+    if(nnodes + nchildren + nleaves > QUEUE_SIZE_MAX) {
       nleaves += nnodes + 1/*Do not forget the the current node*/;
       break;
     }