commit b727febcd1f3cfdf423d4e9d684298381e2a5b34
parent 434046e459c3944170c94904bf740175fa250299
Author: Christophe Coustet <christophe.coustet@meso-star.com>
Date: Sun, 28 Apr 2019 13:55:06 +0200
Merge branch 'release_0.3.1'
Diffstat:
6 files changed, 105 insertions(+), 14 deletions(-)
diff --git a/README.md b/README.md
@@ -35,6 +35,12 @@ variable the install directories of its dependencies.
Release notes
-------------
+### Version 0.3.1
+
+- Performance Fix: when a connex component was canceled by a thread the
+ complexity was O(n^2). New algorithm is O(n).
+- Output execution time for analysis steps in the log.
+
### Version 0.3
- Add API calls to access to geometry frontiers.
@@ -61,7 +67,7 @@ Release notes
License
-------
-StarEnclosures 2D is Copyright (C) \\\|Meso\\\|Star> 2018
+StarEnclosures 2D is Copyright (C) |Méso|Star> 2018
(<a href="mailto:contact@meso-star.com" class="email">contact@meso-star.com</a>).
It is free software released under the GPLv3+ license. You are welcome
to redistribute it under certain conditions; refer to the COPYING files
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -47,7 +47,7 @@ endif()
################################################################################
set(VERSION_MAJOR 0)
set(VERSION_MINOR 3)
-set(VERSION_PATCH 0)
+set(VERSION_PATCH 1)
set(VERSION ${VERSION_MAJOR}.${VERSION_MINOR}.${VERSION_PATCH})
set(SENC2D_FILES_SRC
diff --git a/src/senc2d_device.c b/src/senc2d_device.c
@@ -73,6 +73,17 @@ log_warn(struct senc2d_device* dev, const char* msg, ...)
va_end(vargs_list);
}
+void
+log_info(struct senc2d_device* dev, const char* msg, ...)
+{
+ va_list vargs_list;
+ ASSERT(dev && msg);
+
+ va_start(vargs_list, msg);
+ log_msg(dev, LOG_OUTPUT, msg, vargs_list);
+ va_end(vargs_list);
+}
+
/*******************************************************************************
* Exported functions
******************************************************************************/
diff --git a/src/senc2d_device_c.h b/src/senc2d_device_c.h
@@ -56,4 +56,16 @@ log_warn
#endif
;
+/* Conditionally log a message on the LOG_OUTPUT stream of the device logger,
+ * with respect to the device verbose flag */
+extern LOCAL_SYM void
+log_info
+ (struct senc2d_device* dev,
+ const char* msg,
+ ...)
+#ifdef COMPILER_GCC
+ __attribute((format(printf, 2, 3)))
+#endif
+ ;
+
#endif /* SENC2D_DEVICE_C_H */
diff --git a/src/senc2d_internal_types.h b/src/senc2d_internal_types.h
@@ -123,6 +123,11 @@ SEGSIDE_2_SIDEFLAG(side_id_t s) {
return (s & 1) ? FLAG_BACK : FLAG_FRONT;
}
+static FINLINE enum side_flag
+SIDE_CANCELED_FLAG(enum side_flag f) {
+ return ((unsigned char)f) << 4;
+}
+
static FINLINE side_id_t
SEGIDxSIDE_2_SEGSIDE(seg_id_t s, enum side_id i) {
ASSERT((((size_t)s << 1) | (i == SIDE_BACK)) < SIDE_MAX__);
diff --git a/src/senc2d_scene_analyze.c b/src/senc2d_scene_analyze.c
@@ -26,6 +26,7 @@
#include <rsys/hash_table.h>
#include <rsys/dynamic_array.h>
#include <rsys/dynamic_array_uchar.h>
+#include <rsys/clock_time.h>
#include <star/s2d.h>
@@ -227,6 +228,7 @@ extract_connex_components
vrtx_id_t max_y_vrtx_id = VRTX_NULL__;
struct cc_descriptor *cc;
double max_y = -DBL_MAX;
+ component_canceled = 0;
ASSERT(start_side_id == SIDE_NULL__ || start_side_id < 2 * scn->nusegs);
darray_side_id_clear(¤t_component);
@@ -314,15 +316,21 @@ extract_connex_components
enum side_flag nbour_side_id = SEGSIDE_2_SIDEFLAG(neighbour_id);
unsigned char* nbour_used = processed + nbour_seg_id;
const struct segside* neighbour = segsides + neighbour_id;
- if(*nbour_used & nbour_side_id) continue; /* Already processed */
- if(neighbour->medium < m) {
- /* Not the same medium.
+ if(neighbour->medium < m
+ || (*nbour_used & (unsigned char)SIDE_CANCELED_FLAG(nbour_side_id)))
+ {
+ /* 1) Not the same medium.
* Neighbour's medium id is less than current medium: the whole
* component is to be processed by another thread (possibly the one
- * associated with neighbour's medium). */
+ * associated with neighbour's medium).
+ * 2) Neighbour was canceled: no need to replay the component
+ * again as it will eventually rediscover the side with low medium
+ * id and recancel all the work in progress. */
component_canceled = 1;
darray_side_id_clear(&stack);
- /* Reverse the used flag for sides in cancelled component */
+ /* Don't cancel used flags as all these sides will get us back to
+ * (at least) the neighbour side we have just discovered, that will
+ * cancel them again and again */
sz = darray_side_id_size_get(¤t_component);
FOR_EACH(ii, 0, sz) {
side_id_t used_side
@@ -332,11 +340,14 @@ extract_connex_components
= SEGSIDE_2_SIDEFLAG(used_side);
unsigned char* used = processed + used_trg_id;
ASSERT(*used & (unsigned char)used_side_flag);
- *used &= 0xFF ^ (unsigned char)used_side_flag;
+ /* Set the used flag for sides in cancelled component as leading
+ * to further cancellations */
+ *used |= (unsigned char)SIDE_CANCELED_FLAG(used_side_flag);
}
goto canceled;
}
+ if(*nbour_used & nbour_side_id) continue; /* Already processed */
/* Mark neighbour as processed and stack it */
*nbour_used |= (unsigned char)nbour_side_id;
OK2(darray_side_id_push_back(&stack, &neighbour_id));
@@ -375,15 +386,17 @@ canceled:
current_media = NULL;
/* Write component membership in the global structure
- * No need for sync here as an unique thread write a given side */
+ * No need for sync here as an unique thread writes a given side */
{STATIC_ASSERT(sizeof(cc->cc_id) >= 4, Cannot_write_IDs_sync_free);}
ASSERT(IS_ALIGNED(segments_comp->component, sizeof(cc->cc_id)));
FOR_EACH(ii, 0, sz) {
const side_id_t s = darray_side_id_cdata_get(¤t_component)[ii];
- ASSERT(segments_comp[SEGSIDE_2_SEG(s)].component[SEGSIDE_2_SIDE(s)]
- == COMPONENT_NULL__);
- segments_comp[SEGSIDE_2_SEG(s)].component[SEGSIDE_2_SIDE(s)]
- = cc->cc_id;
+ seg_id_t segid = SEGSIDE_2_SEG(s);
+ enum side_id sid = SEGSIDE_2_SIDE(s);
+ component_id_t* cmp = segments_comp[segid].component;
+ ASSERT(cmp[sid] == COMPONENT_NULL__);
+ ASSERT(segsides[s].medium >= m);
+ cmp[sid] = cc->cc_id;
}
/* Compute the normal at the max_y vertex. */
@@ -402,7 +415,7 @@ canceled:
darray_position_cdata_get(&scn->vertices);
double edge[2], normal[2], norm;
- /* To garanty that segments with 2 sides in the component total to 0
+ /* To ensure that segments with 2 sides in the component total to 0
* regardless of numeric accuracy, we need to prevent them to
* contribute (remember than x + y - y == x can be false). */
ASSERT(seg_comp->component[s] == cc->cc_id); (void)s;
@@ -1123,6 +1136,8 @@ senc2d_scene_analyze
/* Atomic counters to share beetwen threads */
ATOMIC component_count = 0;
ATOMIC next_enclosure_id = 1;
+ char dump[64];
+ struct time t0, t1;
res_T res = RES_OK;
res_T res2 = RES_OK;
@@ -1137,6 +1152,11 @@ senc2d_scene_analyze
if(!scn->nusegs) goto exit;
+ #pragma omp single nowait
+ if(scn->dev->verbose) {
+ time_current(&t0);
+ }
+
darray_segment_tmp_init(scn->dev->allocator, &segments_tmp);
segments_tmp_initialized = 1;
darray_vrtx_id_init(scn->dev->allocator, &frontiers);
@@ -1218,6 +1238,15 @@ senc2d_scene_analyze
neighbourhood_by_vertex_initialized = 0;
} /* No barrier here */
+ #pragma omp single nowait
+ if(scn->dev->verbose) {
+ time_sub(&t1, time_current(&t1), &t0);
+ time_current(&t0);
+ time_dump(&t1, TIME_MSEC | TIME_SEC | TIME_MIN, NULL, dump, sizeof(dump));
+ log_info(scn->dev,
+ "senc2d_scene_analyze: collect_and_link_neighbours step in %s\n", dump);
+ }
+
/* Step 2: extract segment connex components */
extract_connex_components(desc, segsides, &connex_components,
&segments_tmp, &segments_comp, &s2d_view, &component_count, &res);
@@ -1245,6 +1274,15 @@ senc2d_scene_analyze
segments_tmp_initialized = 0;
} /* No barrier here */
+ #pragma omp single nowait
+ if(scn->dev->verbose) {
+ time_sub(&t1, time_current(&t1), &t0);
+ time_current(&t0);
+ time_dump(&t1, TIME_MSEC | TIME_SEC | TIME_MIN, NULL, dump, sizeof(dump));
+ log_info(scn->dev,
+ "senc2d_scene_analyze: extract_connex_components step in %s\n", dump);
+ }
+
/* Step 3: group components */
group_connex_components(desc, segsides, &segments_comp, &connex_components,
s2d_view, &next_enclosure_id, &res);
@@ -1268,6 +1306,15 @@ senc2d_scene_analyze
s2d_view = NULL;
} /* No barrier here */
+ #pragma omp single nowait
+ if(scn->dev->verbose) {
+ time_sub(&t1, time_current(&t1), &t0);
+ time_current(&t0);
+ time_dump(&t1, TIME_MSEC | TIME_SEC | TIME_MIN, NULL, dump, sizeof(dump));
+ log_info(scn->dev,
+ "senc2d_scene_analyze: group_connex_components step in %s\n", dump);
+ }
+
/* Step 4: Build result */
build_result(desc, &connex_components, &segments_comp, &frontiers,
&res);
@@ -1300,6 +1347,16 @@ senc2d_scene_analyze
segments_comp_initialized = 0;
}
} /* No barrier here */
+
+ #pragma omp single nowait
+ if(scn->dev->verbose) {
+ time_sub(&t1, time_current(&t1), &t0);
+ time_current(&t0);
+ time_dump(&t1, TIME_MSEC | TIME_SEC | TIME_MIN, NULL, dump, sizeof(dump));
+ log_info(scn->dev,
+ "senc2d_scene_analyze: build_result step in %s\n", dump);
+ }
+
error_:
;
} /* Implicit barrier here */
