commit 7a7232f676612edadc921a163796c4ef865a694d
parent 9f95af9e3a415345edea3232410a4875beca94ef
Author: Christophe Coustet <christophe.coustet@meso-star.com>
Date: Fri, 26 Apr 2019 16:48:14 +0200
Performance Fix: some special case was in O(n^2)
Diffstat:
6 files changed, 109 insertions(+), 21 deletions(-)
diff --git a/src/senc_descriptor.c b/src/senc_descriptor.c
@@ -282,7 +282,7 @@ senc_descriptor_get_frontier_segments_count
unsigned* count)
{
size_t tmp;
- if (!desc || !count)
+ if(!desc || !count)
return RES_BAD_ARG;
tmp = darray_frontier_edge_size_get(&desc->frontiers);
ASSERT(tmp < UINT_MAX);
@@ -297,7 +297,7 @@ senc_descriptor_get_frontier_segment
unsigned vrtx_id[2])
{
const struct trg_edge* edge;
- if (!vrtx_id || !desc
+ if(!vrtx_id || !desc
|| iseg >= darray_frontier_edge_size_get(&desc->frontiers))
return RES_BAD_ARG;
edge = darray_frontier_edge_cdata_get(&desc->frontiers) + iseg;
diff --git a/src/senc_descriptor_c.h b/src/senc_descriptor_c.h
@@ -106,12 +106,11 @@ set_edge
{
ASSERT(edge && reversed && vrtx0 != vrtx1);
ASSERT(*reversed == UCHAR_MAX); /* Should not be already set. */
- if (vrtx0 < vrtx1) {
+ if(vrtx0 < vrtx1) {
edge->vrtx0 = vrtx0;
edge->vrtx1 = vrtx1;
*reversed = 0; /* Non reversed edge */
- }
- else {
+ } else {
edge->vrtx0 = vrtx1;
edge->vrtx1 = vrtx0;
*reversed = 1; /* Reversed edge */
diff --git a/src/senc_device.c b/src/senc_device.c
@@ -73,6 +73,17 @@ log_warn(struct senc_device* dev, const char* msg, ...)
va_end(vargs_list);
}
+void
+log_info(struct senc_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/senc_device_c.h b/src/senc_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 senc_device* dev,
+ const char* msg,
+ ...)
+#ifdef COMPILER_GCC
+ __attribute((format(printf, 2, 3)))
+#endif
+ ;
+
#endif /* SENC_DEVICE_C_H */
diff --git a/src/senc_internal_types.h b/src/senc_internal_types.h
@@ -123,6 +123,11 @@ TRGSIDE_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
TRGIDxSIDE_2_TRGSIDE(trg_id_t t, enum side_id i) {
ASSERT((((size_t)t << 1) | (i == SIDE_BACK)) < SIDE_MAX__);
diff --git a/src/senc_scene_analyze.c b/src/senc_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/s3d.h>
@@ -228,7 +229,7 @@ extract_connex_components
vrtx_id_t max_z_vrtx_id = VRTX_NULL__;
struct cc_descriptor *cc;
double max_z = -DBL_MAX;
-
+ component_canceled = 0;
ASSERT(start_side_id == SIDE_NULL__ || start_side_id < 2 * scn->nutris);
darray_side_id_clear(¤t_component);
@@ -310,35 +311,45 @@ extract_connex_components
*trg_used |= (unsigned char)crt_side_flag;
}
- /* Store neighbour' sides in a waiting stack */
+ /* Store neighbour's sides in a waiting stack */
FOR_EACH(i, 0, 3) {
side_id_t neighbour_id = crt_side->facing_side_id[i];
trg_id_t nbour_trg_id = TRGSIDE_2_TRG(neighbour_id);
enum side_flag nbour_side_id = TRGSIDE_2_SIDEFLAG(neighbour_id);
unsigned char* nbour_used = processed + nbour_trg_id;
const struct trgside* neighbour = trgsides + 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
+ enum side_id_t used_side
= darray_side_id_cdata_get(¤t_component)[ii];
trg_id_t used_trg_id = TRGSIDE_2_TRG(used_side);
enum side_flag used_side_flag
= TRGSIDE_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));
@@ -377,15 +388,17 @@ extract_connex_components
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(triangles_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(triangles_comp[TRGSIDE_2_TRG(s)].component[TRGSIDE_2_SIDE(s)]
- == COMPONENT_NULL__);
- triangles_comp[TRGSIDE_2_TRG(s)].component[TRGSIDE_2_SIDE(s)]
- = cc->cc_id;
+ trg_id_t tid = TRGSIDE_2_TRG(s);
+ enum side_id sid = TRGSIDE_2_SIDE(s);
+ component_id_t* cmp = triangles_comp[tid].component;
+ ASSERT(cmp[sid] == COMPONENT_NULL__);
+ ASSERT(trgsides[s].medium >= m);
+ cmp[sid] = cc->cc_id;
}
/* Compute the normal at the max_z vertex. */
@@ -404,7 +417,7 @@ extract_connex_components
darray_position_cdata_get(&scn->vertices);
double edge0[3], edge1[3], normal[3], norm;
- /* To garanty that triangles with 2 sides in the component total to 0
+ /* To ensure that triangles 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(trg_comp->component[s] == cc->cc_id); (void)s;
@@ -1157,9 +1170,11 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc)
/* Atomic counters to share beetwen threads */
ATOMIC component_count = 0;
ATOMIC next_enclosure_id = 1;
+ char msg[128], dump[64];
+ struct time t0, t1;
res_T res = RES_OK;
res_T res2 = RES_OK;
-
+
if(!scn || !out_desc) return RES_BAD_ARG;
desc = descriptor_create(scn);
@@ -1170,6 +1185,11 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc)
if(!scn->nutris) goto exit;
+#pragma omp single nowait
+ if(scn->dev->verbose) {
+ time_current(&t0);
+ }
+
darray_triangle_tmp_init(scn->dev->allocator, &triangles_tmp);
triangles_tmp_initialized = 1;
darray_frontier_edge_init(scn->dev->allocator, &frontiers);
@@ -1234,6 +1254,16 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc)
goto error_;
}
+ #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));
+ sprintf(msg,
+ "senc_scene_analyze: collect_and_link_neighbours step in %s\n", dump);
+ log_info(scn->dev, msg);
+ }
+
/* Step 2: extract triangle connex components */
extract_connex_components(desc, trgsides, &connex_components,
&triangles_tmp, &triangles_comp, &s3d_view, &component_count, &res);
@@ -1261,6 +1291,16 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc)
triangles_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));
+ sprintf(msg,
+ "senc_scene_analyze: extract_connex_components step in %s\n", dump);
+ log_info(scn->dev, msg);
+ }
+
/* Step 3: group components */
group_connex_components(desc, trgsides, &triangles_comp,
&connex_components, s3d_view, &next_enclosure_id, &res);
@@ -1284,6 +1324,16 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc)
s3d_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));
+ sprintf(msg,
+ "senc_scene_analyze: group_connex_components step in %s\n", dump);
+ log_info(scn->dev, msg);
+ }
+
/* Step 4: Build result */
build_result(desc, &connex_components, &triangles_comp, &frontiers, &res);
/* No barrier at the end of step 4: data used in step 4 cannot be
@@ -1315,6 +1365,17 @@ senc_scene_analyze(struct senc_scene* scn, struct senc_descriptor** out_desc)
triangles_comp_initialized = 0;
}
} /* No barrier here */
+
+ #pragma omp single nowait
+ {
+ time_sub(&t1, time_current(&t1), &t0);
+ time_current(&t0);
+ time_dump(&t1, TIME_MSEC | TIME_SEC | TIME_MIN, NULL, dump, sizeof(dump));
+ sprintf(msg,
+ "senc_scene_analyze: build_result step in %s\n", dump);
+ log_info(scn->dev, msg);
+ }
+
error_:
;
} /* Implicit barrier here */
