commit fd528771c888a8fc1ba4053eb9edc9de7eaf387d
parent 5988c0e10871220ec62d94324d42c66b564caeaa
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Wed, 29 Apr 2026 12:46:26 +0200
Update to tree construction progress tracking
This change aims to accurately reflect progress, whether the tree is
constructed with or without the use of subtrees. Previously, the
construction of each [sub]tree was logged and displayed individually,
which made the log messages confusing when subtrees were used. Now, the
progress of line partitioning and the construction of the tree node mesh
are tracked at the level of the construction function itself, so that
overall progress is shared across all [sub]trees.
The progress update is protected by mutual exclusion (actually an OpenMP
critical section), so it should work correctly even when multithreading
will be enabled.
Diffstat:
| M | src/sln_tree_build.c | | | 154 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++---------------------- |
1 file changed, 112 insertions(+), 42 deletions(-)
diff --git a/src/sln_tree_build.c b/src/sln_tree_build.c
@@ -26,6 +26,21 @@
#include <rsys/cstr.h>
#include <rsys/math.h>
+/* Structure used to track the progress of a construction phase */
+struct progress {
+ /* Absolute progression */
+ size_t total; /* Total number of items to process */
+ size_t processed; /* Number of items already processed */
+
+ /* Relative progression */
+ int pcent; /* Currently displayed percentage */
+ int pcent_step; /* Increment between displayed percentages */
+
+ const char* msg; /* Message to add before the displayed percentage */
+};
+#define PROGRESS_DEFAULT__ {0,0,0,10,NULL}
+static const struct progress PROGRESS_DEFAULT = PROGRESS_DEFAULT__;
+
/* Structure containing temporary variables used to create polyline on a leaf
* These variables are not declared locally within the function responsible for
* constructing this polyline in order to avoid having to allocate and
@@ -73,7 +88,7 @@ collapse_child_polylines
* 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
+#define QUEUE_SIZE_MAX 256
/*******************************************************************************
* Helper functions
@@ -94,6 +109,43 @@ size_t_to_unsigned(const size_t sz)
return (unsigned)sz;
}
+static void
+progress_print(struct sln_device* dev, const struct progress* progress)
+{
+ ASSERT(dev && progress);
+ if(progress->msg) {
+ INFO(dev, "%s%3d%%\n", progress->msg, progress->pcent);
+ } else {
+ INFO(dev, "%3d%%\n", progress->pcent);
+ }
+}
+
+static void
+progress_update
+ (struct sln_device* dev,
+ struct progress* progress,
+ const size_t count)
+{
+ int pcent = 0;
+ ASSERT(dev && progress);
+
+ #pragma omp critical
+ {
+ progress->processed += count;
+ ASSERT(progress->processed <= progress->total);
+
+ pcent = (int)
+ ( (double)progress->processed*100.0
+ / (double)progress->total
+ + 0.5 /* round */);
+
+ if(pcent/progress->pcent_step > progress->pcent/progress->pcent_step) {
+ progress->pcent = pcent;
+ progress_print(dev, progress);
+ }
+ }
+}
+
static INLINE void
build_leaf_polyline_scratch_init
(struct mem_allocator* allocator,
@@ -722,7 +774,8 @@ build_polylines
(struct sln_tree* tree,
const size_t root_index,
const size_t nodes_count, /* Total number of nodes in the tree (for debug) */
- struct darray_vertex* vertices)
+ struct darray_vertex* vertices,
+ struct progress* progress)
{
/* Stack */
#define STACK_SIZE (SLN_TREE_DEPTH_MAX*SLN_TREE_ARITY_MAX)
@@ -731,7 +784,6 @@ build_polylines
/* Progress */
size_t nnodes_processed = 0;
- int progress = 0;
/* Miscellaneous */
struct build_leaf_polyline_scratch scratch;
@@ -740,16 +792,13 @@ build_polylines
ASSERT(tree && nodes_count != 0);
ASSERT(root_index < darray_node_size_get(&tree->nodes));
+ (void)nodes_count; /* Avoid "Unused variable" warning */
build_leaf_polyline_scratch_init(tree->sln->allocator, &scratch);
- #define LOG_MSG "Meshing: %3d%%\n"
#define NODE(Id) (darray_node_data_get(&tree->nodes) + (Id))
#define IS_LEAF(Id) (NODE(Id)->offset == 0)
- /* Print that nothing has been done yet */
- INFO(tree->sln, LOG_MSG, progress);
-
/* Push back SIZE_MAX which, once pop up, will mark the end of recursion */
stack[istack++] = SIZE_MAX;
@@ -817,17 +866,10 @@ build_polylines
/* Handle progression bar */
if(istack < istack_saved) {
- int pcent = 0;
+ size_t nnodes = istack_saved - istack;
- nnodes_processed += istack_saved - istack;
- ASSERT(nnodes_processed <= nodes_count);
-
- /* Print progress update */
- pcent = (int)((double)nnodes_processed*100.0/(double)nodes_count+0.5);
- if(pcent/10 > progress/10) {
- progress = pcent;
- INFO(tree->sln, LOG_MSG, progress);
- }
+ nnodes_processed += nnodes;
+ progress_update(tree->sln, progress, nnodes);
}
}
ASSERT(nnodes_processed == nodes_count);
@@ -848,7 +890,8 @@ static res_T
partition_lines_depth_first
(struct sln_tree* tree,
const size_t root_index,
- struct darray_node* nodes)
+ struct darray_node* nodes,
+ struct progress* progress)
{
/* Stack */
#define STACK_SIZE (SLN_TREE_DEPTH_MAX*(SLN_TREE_ARITY_MAX-1))
@@ -858,17 +901,16 @@ partition_lines_depth_first
/* Progress */
size_t nlines_total = 0;
size_t nlines_processed = 0;
- int progress = 0;
/* Miscellaneous */
size_t inode = 0;
res_T res = RES_OK;
/* Pre-condition */
- ASSERT(tree && nodes);
+ ASSERT(tree && nodes && progress);
ASSERT(root_index < darray_node_size_get(nodes));
+ (void)nlines_total; /* Avoid "Unused variable" warning */
- #define LOG_MSG "Partitioning: %3d%%\n"
#define NODE(Id) (darray_node_data_get(nodes) + (Id))
#define CREATE_NODE { \
res = darray_node_push_back(nodes, &SLN_NODE_NULL); \
@@ -881,10 +923,6 @@ partition_lines_depth_first
/* Push back SIZE_MAX which, once pop up, will mark the end of recursion */
stack[istack++] = SIZE_MAX;
- /* Print that although nothing has been done yet,
- * the calculation is nevertheless in progress */
- INFO(tree->sln, LOG_MSG, progress);
-
inode = root_index; /* Root node */
while(inode != SIZE_MAX) {
/* #lines into the node */
@@ -892,20 +930,13 @@ partition_lines_depth_first
/* Make a leaf */
if(nlines_node <= tree->args.leaf_nlines) {
- int pcent = 0;
NODE(inode)->offset = 0;
inode = stack[--istack]; /* Pop the next node */
- ASSERT(nlines_processed + nlines_node <= nlines_total);
- nlines_processed += nlines_node;
+ nlines_processed += nlines_node; /* For debug */
- /* Print progress update */
- pcent = (int)((double)nlines_processed*100.0/(double)nlines_total+0.5);
- if(pcent/10 > progress/10) {
- progress = pcent;
- INFO(tree->sln, LOG_MSG, progress);
- }
+ progress_update(tree->sln, progress, nlines_node);
/* Split the node */
} else {
@@ -1041,7 +1072,7 @@ partition_lines_breadth_first
/* Register the root node in the queue */
ENQUEUE(root_index);
- /* Breadth-first partitionning */
+ /* Breadth-first partitioning */
while(!is_list_empty(&queue)) {
size_t node_range[2] = {0,0};
size_t nlines_node = 0; /* #lines in the node */
@@ -1128,7 +1159,11 @@ error:
}
static res_T
-build_subtrees(struct sln_tree* tree, const size_t subtrees[], size_t nsubtrees)
+build_subtrees
+ (struct sln_tree* tree,
+ const size_t subtrees[],
+ size_t nsubtrees,
+ struct progress* meshing)
{
/* Subtree temporary data */
struct scratch {
@@ -1138,7 +1173,9 @@ build_subtrees(struct sln_tree* tree, const size_t subtrees[], size_t nsubtrees)
}* scratches;
/* Miscellaneous */
+ struct progress partitioning = PROGRESS_DEFAULT;
struct mem_allocator* allocator = NULL;
+ size_t nlines = 0;
size_t i = 0;
ATOMIC res = RES_OK;
@@ -1157,6 +1194,14 @@ build_subtrees(struct sln_tree* tree, const size_t subtrees[], size_t nsubtrees)
darray_vertex_init(allocator, &scratches[i].vertices);
}
+
+ /* Setup the progress bar and print that although nothing has been done yet,
+ * the calculation is nevertheless in progress */
+ SHTR(line_list_get_size(tree->args.lines, &nlines));
+ partitioning.total = nlines;
+ partitioning.msg = "Partitioning: ";
+ progress_print(tree->sln, &partitioning);
+
/* This loop should be parallelized, with a block size of 1 */
for(i=0; i < nsubtrees; ++i) {
struct sln_node root = SLN_NODE_NULL;
@@ -1177,7 +1222,8 @@ build_subtrees(struct sln_tree* tree, const size_t subtrees[], size_t nsubtrees)
if(res2 != RES_OK) { ATOMIC_SET(&res, res2); continue; }
/* Partition the line */
- res2 = partition_lines_depth_first(tree, 0/*root*/, &scratch->nodes);
+ res2 = partition_lines_depth_first
+ (tree, 0/*root*/, &scratch->nodes, &partitioning);
if(res2 != RES_OK) { ATOMIC_SET(&res, res2); continue; }
#pragma omp critical
@@ -1207,6 +1253,13 @@ build_subtrees(struct sln_tree* tree, const size_t subtrees[], size_t nsubtrees)
scratch->nnodes = nnodes_s;
}
+ /* Setup the progress bar and print that although nothing has been done yet,
+ * the calculation is nevertheless in progress */
+ *meshing = PROGRESS_DEFAULT;
+ meshing->total = darray_node_size_get(&tree->nodes);
+ meshing->msg = "Meshing: ";
+ progress_print(tree->sln, meshing);
+
/* This loop should be parallelized, with a block size of 1 */
for(i=0; i < nsubtrees; ++i) {
struct scratch* scratch = scratches + i;
@@ -1219,7 +1272,8 @@ build_subtrees(struct sln_tree* tree, const size_t subtrees[], size_t nsubtrees)
/* Skip the remaining subtrees in case of an error */
if(ATOMIC_GET(&res) != RES_OK) continue;
- res2 = build_polylines(tree, inode, scratch->nnodes, &scratch->vertices);
+ res2 = build_polylines
+ (tree, inode, scratch->nnodes, &scratch->vertices, meshing);
if(res2 != RES_OK) { ATOMIC_SET(&res, res2); continue; }
#pragma omp critical
@@ -1272,6 +1326,10 @@ error:
res_T
tree_build(struct sln_tree* tree)
{
+ /* Progress statuses */
+ struct progress partitioning = PROGRESS_DEFAULT;
+ struct progress meshing = PROGRESS_DEFAULT;
+
struct sln_node node = SLN_NODE_NULL;
size_t nlines = 0;
size_t nnodes = 0;
@@ -1289,11 +1347,19 @@ tree_build(struct sln_tree* tree)
res = darray_node_push_back(&tree->nodes, &node);
if(res != RES_OK) goto error;
- res = partition_lines_depth_first(tree, iroot, &tree->nodes);
+ /* Partition lines */
+ partitioning.total = nlines;
+ partitioning.msg = "Partitioning: ";
+ progress_print(tree->sln, &partitioning);
+ res = partition_lines_depth_first(tree, iroot, &tree->nodes, &partitioning);
if(res != RES_OK) goto error;
+ /* Create polylines */
nnodes = darray_node_size_get(&tree->nodes);
- res = build_polylines(tree, iroot, nnodes, &tree->vertices);
+ meshing.total = nnodes;
+ meshing.msg = "Meshing: ";
+ progress_print(tree->sln, &meshing);
+ res = build_polylines(tree, iroot, nnodes, &tree->vertices, &meshing);
if(res != RES_OK) goto error;
exit:
@@ -1314,6 +1380,9 @@ tree_build2(struct sln_tree* tree)
size_t subtrees[QUEUE_SIZE_MAX]; /* List of sub-tree root indices */
size_t nsubtrees = 0;
+ /* Progress message of the meshing step */
+ struct progress meshing = PROGRESS_DEFAULT;
+
/* Miscellaneous */
struct sln_node root = SLN_NODE_NULL;
size_t nlines = 0;
@@ -1374,12 +1443,13 @@ tree_build2(struct sln_tree* tree)
nnodes_upper_tree = darray_node_size_get(&tree->nodes);
nnodes_upper_tree -= nsubtrees; /* Exclude the root node of the subtrees */
- res = build_subtrees(tree, subtrees, nsubtrees);
+ res = build_subtrees(tree, subtrees, nsubtrees, &meshing);
if(res != RES_OK) goto error;
/* Build the polylines of the upper level if necessary */
if(nnodes_upper_tree != 0) {
- res = build_polylines(tree, 0/*root*/, nnodes_upper_tree, &tree->vertices);
+ res = build_polylines
+ (tree, 0/*root*/, nnodes_upper_tree, &tree->vertices, &meshing);
if(res != RES_OK) goto error;
}
