commit 4ebc559661477726f3d58366b7e3395ccd41812c
parent 1f0bb151f24016699eb94a95847c107e11132fea
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Tue, 28 Apr 2026 14:49:28 +0200
Rework the draft of the parallel tree-building function
Adds a helper function that partitions lines according to a breadth-first
tree traversal strategy. A maximum number of leaves in the tree is
provided as an input to the function as a new termination criterion for
the partitioning (in addition to the maximum number of lines per leaf).
In the tree-building function designed for parallelization, the
partitioning of lines by this function uses the number of available
threads as the maximum number of leaves. After this partitioning, the
leaves of the tree are then treated as the roots of independent subtree,
which can thus be built in parallel.
This is, in fact, exactly the same algorithm as before. This commit
consists mainly of a rewrite and restructuring of the source code aimed
at improving its readability and making it more robust.
Diffstat:
| M | src/sln_tree_build.c | | | 233 | +++++++++++++++++++++++++++++++++++++++++++++++++++++-------------------------- |
1 file changed, 158 insertions(+), 75 deletions(-)
diff --git a/src/sln_tree_build.c b/src/sln_tree_build.c
@@ -67,6 +67,14 @@ collapse_child_polylines
* well above the actual ka value. */
#define KA_ADJUSTEMENT 1.01
+/* Maximum queue size used for the breadth-first tree traversal. For a perfectly
+ * balanced tree, this corresponds to the maximum number of leaves a tree can
+ * have. Note that this value does not need to be too high, since the
+ * breadth-first traversal is only used to partition the first few levels of the
+ * tree until a sufficient number of subtrees have been identified so that they
+ * can then be constructed in parallel using a depth-first algorithm */
+ #define QUEUE_SIZE_MAX 256
+
/*******************************************************************************
* Helper functions
******************************************************************************/
@@ -758,7 +766,7 @@ build_polylines
#ifndef NDEBUG
/* Check that all children have their polylines created */
FOR_EACH(i, 1, nchildren) {
- const size_t ichild = inode + NODE(inode)->offset + i;
+ const size_t ichild = ichild0 + i;
ASSERT(NODE(ichild)->nvertices != 0);
}
#endif
@@ -775,12 +783,12 @@ build_polylines
/* Child nodes have NOT their polyline created */
} else {
- ASSERT(istack < STACK_SIZE - (nchildren - 1/*ichild0*/ + 1/*inode*/));
+ ASSERT(istack + (nchildren - 1/*ichild0*/ + 1/*inode*/) <= STACK_SIZE);
stack[istack++] = inode; /* Push the current node */
/* Push the children except the 1st one */
FOR_EACH_REVERSE(i, nchildren-1, 0) {
- const size_t ichild = inode + NODE(inode)->offset + i;
+ const size_t ichild = ichild0 + i;
ASSERT(NODE(ichild)->nvertices == 0);
stack[istack++] = ichild;
}
@@ -820,7 +828,9 @@ error:
}
static res_T
-partition_lines(struct sln_tree* tree, const size_t root_index)
+partition_lines_depth_first
+ (struct sln_tree* tree,
+ const size_t root_index)
{
/* Stack */
#define STACK_SIZE (SLN_TREE_DEPTH_MAX*(SLN_TREE_ARITY_MAX-1))
@@ -928,10 +938,9 @@ partition_lines(struct sln_tree* tree, const size_t root_index)
inode = ichildren; /* Make the first child the current node */
- ASSERT(istack < STACK_SIZE - 1/*1st child*/);
- FOR_EACH_REVERSE(i, nchildren-1, 0) {
- stack[istack++] = ichildren + i; /* Push the other children */
- }
+ /* Push the other children */
+ ASSERT(istack + (nchildren-1/*1st child*/) <= STACK_SIZE);
+ FOR_EACH_REVERSE(i, nchildren-1, 0) stack[istack++] = ichildren + i;
}
}
ASSERT(nlines_processed == nlines_total);
@@ -939,39 +948,6 @@ partition_lines(struct sln_tree* tree, const size_t root_index)
#undef NODE
#undef CREATE_NODE
#undef STACK_SIZE
-exit:
- return res;
-error:
- darray_node_clear(&tree->nodes);
- goto exit;
-}
-
-/*******************************************************************************
- * Local functions
- ******************************************************************************/
-res_T
-tree_build(struct sln_tree* tree)
-{
- struct sln_node node = SLN_NODE_NULL;
- size_t nlines = 0;
- size_t nnodes = 0;
- size_t iroot = 0;
- res_T res = RES_OK;
-
- SHTR(line_list_get_size(tree->args.lines, &nlines));
-
- iroot = darray_node_size_get(&tree->nodes);
- ASSERT(iroot == 0); /* assume that the tree contains no data */
-
- /* Setup the root node */
- node.range[0] = 0;
- node.range[1] = nlines - 1/* inclusive bound */;
- if((res = darray_node_push_back(&tree->nodes, &node)) != RES_OK) goto error;
-
- if((res = partition_lines(tree, iroot)) != RES_OK) goto error;
-
- nnodes = darray_node_size_get(&tree->nodes);
- if((res = build_polylines(tree, iroot, nnodes)) != RES_OK) goto error;
exit:
return res;
@@ -979,32 +955,33 @@ error:
goto exit;
}
-res_T
-tree_build2(struct sln_tree* tree)
+static res_T
+partition_lines_breadth_first
+ (struct sln_tree* tree,
+ const size_t root_index,
+ const unsigned nleaves_max_hint) /* Advice on the maxium of leafs to create */
{
/* Static memory space of the queue */
- #define QUEUE_SIZE_MAX 256
struct item {
struct list_node link;
size_t inode;
} items[QUEUE_SIZE_MAX];
- size_t sub_trees[QUEUE_SIZE_MAX]; /* List of sub-tree root indices */
- #undef QUEUE_SIZE_MAX
-
/* Linked lists for managing queue data */
struct list_node free_items;
struct list_node queue;
- struct list_node* it;
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 nnodes_upper_tree = 0; /* #nodes from the root to the subtrees */
+ size_t nleaves = 0;
size_t i = 0;
res_T res = RES_OK;
+ /* Pre-conditions */
ASSERT(tree);
+ ASSERT(root_index < darray_node_size_get(&tree->nodes));
/* Macros to help in managing nodes */
#define NODE(Id) (darray_node_data_get(&tree->nodes) + (Id))
@@ -1039,14 +1016,13 @@ tree_build2(struct sln_tree* tree)
SHTR(line_list_get_size(tree->args.lines, &nlines_total));
/* Setup the root node */
- CREATE_NODE; /* Alloc the root node */
- NODE(0)->range[0] = 0;
- NODE(0)->range[1] = nlines_total - 1;
+ NODE(root_index)->range[0] = 0;
+ NODE(root_index)->range[1] = nlines_total - 1;
/* Register the root node in the queue */
- ENQUEUE(0);
+ ENQUEUE(root_index);
- /* Breadth-first tree building */
+ /* Breadth-first partitionning */
while(!is_list_empty(&queue)) {
size_t node_range[2] = {0,0};
size_t nlines_node = 0; /* #lines in the node */
@@ -1065,19 +1041,23 @@ tree_build2(struct sln_tree* tree)
nlines_node = node_range[1] - node_range[0] + 1/*inclusive bound*/;
ASSERT(nlines_node > tree->args.leaf_nlines);
- /* Compute how the number of children that node has */
+ if(nlines_node <= tree->args.leaf_nlines) {
+ /* Make a leaf */
+ ++nleaves;
+ continue;
+ }
+
+ /* Compute the number of children that node has */
nchildren = node_child_count(NODE(inode), tree->args.arity);
ASSERT(nchildren <= tree->args.arity);
- /* Check whether, once the child nodes have been queued, the total number of
- * queued nodes would exceed the number of threads - or, in other words,
- * whether the number of subtree to be constructed would exceed the number
- * of threads available to construct them in parallel. If so, terminate this
- * breadth first traversal and proceed to the parallel construction of the
- * subtrees already queued so that there is at least one thread available
- * per subtree to be built */
- if(nnodes + nchildren > tree->args.nthreads_hint) {
- ENQUEUE(inode); /* Do not forget to enqueue the current node */
+ /* 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) {
+ nleaves += nnodes + 1/*Do not forget the the current node*/;
break;
}
@@ -1117,29 +1097,132 @@ tree_build2(struct sln_tree* tree)
}
}
- ASSERT(!is_list_empty(&queue));
+ #undef NODE
+ #undef CREATE_NODE
+ #undef ENQUEUE
+ #undef DEQUEUE
+
+exit:
+ return res;
+error:
+ goto exit;
+}
+
+/*******************************************************************************
+ * Local functions
+ ******************************************************************************/
+res_T
+tree_build(struct sln_tree* tree)
+{
+ struct sln_node node = SLN_NODE_NULL;
+ size_t nlines = 0;
+ size_t nnodes = 0;
+ size_t iroot = 0;
+ res_T res = RES_OK;
+
+ SHTR(line_list_get_size(tree->args.lines, &nlines));
+
+ iroot = darray_node_size_get(&tree->nodes);
+ ASSERT(iroot == 0); /* assume that the tree contains no data */
+
+ /* Setup the root node */
+ node.range[0] = 0;
+ node.range[1] = nlines - 1/* inclusive bound */;
+ if((res = darray_node_push_back(&tree->nodes, &node)) != RES_OK) goto error;
+
+ if((res = partition_lines_depth_first(tree, iroot)) != RES_OK) goto error;
+
+ nnodes = darray_node_size_get(&tree->nodes);
+ if((res = build_polylines(tree, iroot, nnodes)) != RES_OK) goto error;
+
+exit:
+ return res;
+error:
+ goto exit;
+}
+
+res_T
+tree_build2(struct sln_tree* tree)
+{
+ /* Stack data structure */
+ #define STACK_SIZE (SLN_TREE_DEPTH_MAX*(SLN_TREE_ARITY_MAX-1))
+ size_t stack[STACK_SIZE];
+ size_t istack = 0;
+
+ /* Subtrees */
+ size_t subtrees[QUEUE_SIZE_MAX]; /* List of sub-tree root indices */
+ size_t nsubtrees = 0;
+
+ /* Miscellaneous */
+ struct sln_node root = SLN_NODE_NULL;
+ size_t nlines = 0;
+ size_t nnodes_upper_tree = 0; /* #nodes from the root to the subtrees */
+ size_t iroot = 0;
+ size_t inode = 0;
+ size_t i = 0;
+ res_T res = RES_OK;
+
+ ASSERT(tree);
+
+ iroot = darray_node_size_get(&tree->nodes);
+ ASSERT(iroot == 0); /* assume that the tree contains no data */
+
+ SHTR(line_list_get_size(tree->args.lines, &nlines));
+
+ /* Setup the root node */
+ root.range[0] = 0;
+ root.range[1] = nlines;
+ res = darray_node_push_back(&tree->nodes, &root);
+ if(res != RES_OK) goto error;
+
+ /* Partition the lines in bread-first fixing the maximum number of leafs to
+ * the available number of threads */
+ res = partition_lines_breadth_first(tree, iroot, tree->args.nthreads_hint);
+ if(res != RES_OK) goto error;
+
+ /* Push back SIZE_MAX which, once pop up, will mark the end of recursion */
+ stack[istack++] = SIZE_MAX;
+
+ /* Retrieve the leaf indices generated by bread-first partitioning. These
+ * correspond to the roots of the subtree to be built */
+ inode = iroot; /* Root node */
+ while(inode != SIZE_MAX) {
+ const struct sln_node* node = darray_node_cdata_get(&tree->nodes) + inode;
+ ASSERT(inode < darray_node_size_get(&tree->nodes));
+
+ if(sln_node_is_leaf(node)) {
+ ASSERT(nsubtrees < QUEUE_SIZE_MAX);
+ subtrees[nsubtrees++] = inode;
+ inode = stack[--istack]; /* Pop the next node */
+
+ } else {
+ const size_t ichild0 = inode + node->offset;
+ const unsigned nchildren = node_child_count(node, tree->args.arity);
+
+ /* Push the children except the 1st one */
+ ASSERT(istack + (nchildren-1/*ichild0*/) <= STACK_SIZE);
+ FOR_EACH_REVERSE(i, nchildren-1, 0) stack[istack++] = ichild0 + i;
+
+ /* Recursively traverse the 1st child */
+ inode = ichild0;
+ }
+ }
/* Retrieves the number of registered nodes. This is the number of nodes from
* the root to the subtrees, excluding the roots of those subtrees */
nnodes_upper_tree = darray_node_size_get(&tree->nodes);
- nnodes_upper_tree -= nnodes; /* Exclude the root node of the subtrees */
-
- /* Configure the list of subtree structures to be built in parallel */
- i = 0;
- LIST_FOR_EACH(it, &queue) {
- sub_trees[i++] = CONTAINER_OF(it, struct item, link)->inode;
- }
+ nnodes_upper_tree -= nsubtrees; /* Exclude the root node of the subtrees */
/* This will the loop to parallelize, with a chunk size of 1 */
- for(i=0; i < nnodes; ++i) {
+ for(i=0; i < nsubtrees; ++i) {
size_t nnodes_subtree = darray_node_size_get(&tree->nodes);
- res = partition_lines(tree, sub_trees[i]);
+ res = partition_lines_depth_first(tree, subtrees[i]);
if(res != RES_OK) goto error;
nnodes_subtree = darray_node_size_get(&tree->nodes) - nnodes_subtree;
nnodes_subtree += 1; /* Do not forget the root node */
- res = build_polylines(tree, sub_trees[i], nnodes_subtree);
+ res = build_polylines(tree, subtrees[i], nnodes_subtree);
if(res != RES_OK) goto error;
}
