Revision: 56825
http://sourceforge.net/p/brlcad/code/56825
Author: brlcad
Date: 2013-08-14 04:38:37 +0000 (Wed, 14 Aug 2013)
Log Message:
-----------
revert r56812 after doing a little bit of performance testing. it's looking
like my change that got things working on 32-bit definitely did slow TIE down
(was expected), but r56812 slows it down another 5-15% (tested on models up to
200k). interesting to see how touchy the performance is, but this is to be
expected when one deals with data coherency, branch prediction, and memory
alignment optimizations.
Revision Links:
--------------
http://sourceforge.net/p/brlcad/code/56812
http://sourceforge.net/p/brlcad/code/56812
Modified Paths:
--------------
brlcad/trunk/include/tie.h
brlcad/trunk/src/librt/primitives/bot/tie.c
brlcad/trunk/src/librt/primitives/bot/tie_kdtree.c
brlcad/trunk/src/librt/primitives/bot/tieprivate.h
Modified: brlcad/trunk/include/tie.h
===================================================================
--- brlcad/trunk/include/tie.h 2013-08-14 03:33:34 UTC (rev 56824)
+++ brlcad/trunk/include/tie.h 2013-08-14 04:38:37 UTC (rev 56825)
@@ -107,16 +107,13 @@
*/
tfloat *v; /* 4-bytes or 8-bytes */
void *ptr; /* 4-bytes or 8-bytes */
- int8_t b;
+ uint32_t b; /* 4-bytes (way more than we need, but helps
keep alignment) */
};
struct tie_kdtree_s {
- struct tie_kdtree_s *left;
- struct tie_kdtree_s *right;
- fastf_t axis;
- int8_t split;
- int8_t has_children;
- struct tie_geom_s *data;
+ float axis; /* 4-bytes, intentionally float */
+ uint32_t b; /* 4-bytes, bit array to store data about the kdtree node */
+ void *data; /* 4-bytes or 8-bytes */
};
Modified: brlcad/trunk/src/librt/primitives/bot/tie.c
===================================================================
--- brlcad/trunk/src/librt/primitives/bot/tie.c 2013-08-14 03:33:34 UTC (rev
56824)
+++ brlcad/trunk/src/librt/primitives/bot/tie.c 2013-08-14 04:38:37 UTC (rev
56825)
@@ -86,15 +86,12 @@
if (u.v[2] > u.v[1] && u.v[2] > u.v[0]) {
i1 = 0;
i2 = 1;
- tri->b = 2;
} else if (u.v[1] > u.v[2] && u.v[1] > u.v[0]) {
i1 = 0;
i2 = 2;
- tri->b = 1;
} else {
i1 = 1;
i2 = 2;
- tri->b = 0;
}
/* compute u1, v2, u2, v2 */
@@ -103,6 +100,12 @@
tri->v[0] = v1.v[i2] - tri->data[0].v[i2];
tri->v[1] = v2.v[i2] - tri->data[0].v[i2];
+ /* !!! what? no entiendo. */
+ if (i1 == 0 && i2 == 1)
+ tri->b = tri->b + 2;
+ else if (i1 == 0)
+ tri->b = tri->b + 1;
+
/* Compute DotVN */
VSCALE(v1.v, tri->data[0].v, -1.0);
tri->data[2].v[0] = VDOT( v1.v, tri->data[1].v);
@@ -233,7 +236,7 @@
}
/* Extracting value of splitting plane from the kdtree */
- split = tie->kdtree->split;
+ split = tie->kdtree->b & (uint32_t)0x3L;
/* Initialize ray segment */
if (ray->dir[split] < 0.0)
@@ -268,22 +271,17 @@
*
* Gordon Stoll's Mantra - Rays are Measured in Millions :-)
*/
- while (node->has_children) {
+ while (node && node->data && TIE_HAS_CHILDREN(node->b)) {
ray->kdtree_depth++;
/* Retrieve the splitting plane */
- split = node->split;
+ split = node->b & (uint32_t)0x3L;
/* Calculate the projected 1d distance to splitting axis */
dist = (node->axis - ray->pos[split]) * dirinv[split];
- if (!ab[split]) {
- temp[0] = node->left;
- temp[1] = node->right;
- } else {
- temp[0] = node->right;
- temp[1] = node->left;
- }
+ temp[0] = &((struct tie_kdtree_s *)(node->data))[ab[split]];
+ temp[1] = &((struct tie_kdtree_s *)(node->data))[1-ab[split]];
i = near >= dist; /* Node B Only? */
node = temp[i];
@@ -340,8 +338,8 @@
/* Extract i1 and i2 indices from the 'b' field */
v = tri->v;
- i1 = TIE_TAB1[tri->b];
- i2 = TIE_TAB1[3 + tri->b];
+ i1 = TIE_TAB1[tri->b & (uint32_t)0x7L];
+ i2 = TIE_TAB1[3 + (tri->b & (uint32_t)0x7L)];
/* Compute U and V */
u0 = t.pos[i1] - tri->data[0].v[i1];
@@ -427,9 +425,9 @@
unsigned int i;
/* expand the tri buffer if needed */
- if (tie->tri_num + tnum > tie->tri_num_alloc) {
- tie->tri_num_alloc = tie->tri_num + tnum;
- tie->tri_list = (struct tie_tri_s *)bu_realloc(tie->tri_list,
tie->tri_num_alloc * sizeof(struct tie_tri_s), "tri_list during tie_push");
+ if (tnum + tie->tri_num > tie->tri_num_alloc) {
+ tie->tri_list = (struct tie_tri_s *)bu_realloc( tie->tri_list,
sizeof(struct tie_tri_s) * (tie->tri_num + tnum), "tri_list during tie_push");
+ tie->tri_num_alloc += tnum;
}
for (i = 0; i < tnum; i++) {
Modified: brlcad/trunk/src/librt/primitives/bot/tie_kdtree.c
===================================================================
--- brlcad/trunk/src/librt/primitives/bot/tie_kdtree.c 2013-08-14 03:33:34 UTC
(rev 56824)
+++ brlcad/trunk/src/librt/primitives/bot/tie_kdtree.c 2013-08-14 04:38:37 UTC
(rev 56825)
@@ -116,24 +116,20 @@
static void
tie_kdtree_free_node(struct tie_kdtree_s *node)
{
- if (node->has_children) {
+ if (node && TIE_HAS_CHILDREN(node->b)) {
/* Node Data is KDTREE Children, Recurse */
- tie_kdtree_free_node(node->left);
- tie_kdtree_free_node(node->right);
+ tie_kdtree_free_node(&((struct tie_kdtree_s *)(node->data))[0]);
+ tie_kdtree_free_node(&((struct tie_kdtree_s *)(node->data))[1]);
} else {
/* This node points to a geometry node, free it */
- if (node->left) {
- bu_free(node->left, "node left");
+ struct tie_geom_s *tmp;
+ tmp = (struct tie_geom_s *)node->data;
+ if (tmp) {
+ if (tmp->tri_num > 0) {
+ bu_free(tmp->tri_list, "tri_list");
+ }
+ bu_free(tmp, "data");
}
- if (node->right) {
- bu_free(node->right, "node right");
- }
- if (node->data && node->data->tri_num > 0) {
- bu_free(node->data->tri_list, "tri_list");
- }
- if (node->data) {
- bu_free(node->data, "data");
- }
}
}
@@ -588,7 +584,6 @@
/* Terminating criteria for KDTREE subdivision */
if (node_gd->tri_num <= TIE_KDTREE_NODE_MAX || depth > tie->max_depth) {
tie->stat += node_gd->tri_num;
- node->has_children = 0;
return;
}
@@ -600,14 +595,15 @@
bu_bomb("Illegal tie kdtree method\n");
/* Allocate 2 children nodes for the parent node */
- node->left = (struct tie_kdtree_s *)bu_calloc(1, sizeof(struct
tie_kdtree_s), "tie node left");
- node->left->data = (struct tie_geom_s *)bu_calloc(1, sizeof(struct
tie_geom_s), "tie node left tie_geom_s");
- node->right = (struct tie_kdtree_s *)bu_calloc(1, sizeof(struct
tie_kdtree_s), "tie node right");
- node->right->data = (struct tie_geom_s *)bu_calloc(1, sizeof(struct
tie_geom_s), "tie node right tie_geom_s");
+ node->data = bu_calloc(2, sizeof(struct tie_kdtree_s), __FUNCTION__);
+ node->b = 0;
+ BU_ALLOC(((struct tie_kdtree_s *)(node->data))[0].data, struct tie_geom_s);
+ BU_ALLOC(((struct tie_kdtree_s *)(node->data))[1].data, struct tie_geom_s);
+
/* Initialize Triangle List */
- child[0] = node->left->data;
- child[1] = node->right->data;
+ child[0] = ((struct tie_geom_s *)(((struct tie_kdtree_s
*)(node->data))[0].data));
+ child[1] = ((struct tie_geom_s *)(((struct tie_kdtree_s
*)(node->data))[1].data));
child[0]->tri_list = (struct tie_tri_s **)bu_calloc(node_gd->tri_num,
sizeof(struct tie_tri_s *), "child[0]->tri_list");
child[0]->tri_num = 0;
@@ -681,14 +677,13 @@
VMOVE(lmin[1], cmin[1].v);
VMOVE(lmax[0], cmax[0].v);
VMOVE(lmax[1], cmax[1].v);
- tie_kdtree_build(tie, node->left, depth+1, lmin[0], lmax[0]);
- tie_kdtree_build(tie, node->right, depth+1, lmin[1], lmax[1]);
+ tie_kdtree_build(tie, &((struct tie_kdtree_s *)(node->data))[0], depth+1,
lmin[0], lmax[0]);
+ tie_kdtree_build(tie, &((struct tie_kdtree_s *)(node->data))[1], depth+1,
lmin[1], lmax[1]);
}
/* Assign the splitting dimension to the node */
/* If we've come this far then YES, this node DOES have child nodes, MARK
it as so. */
- node->split = split;
- node->has_children = 1;
+ node->b = TIE_SET_HAS_CHILDREN(node->b) + split;
}
/*************************************************************
Modified: brlcad/trunk/src/librt/primitives/bot/tieprivate.h
===================================================================
--- brlcad/trunk/src/librt/primitives/bot/tieprivate.h 2013-08-14 03:33:34 UTC
(rev 56824)
+++ brlcad/trunk/src/librt/primitives/bot/tieprivate.h 2013-08-14 04:38:37 UTC
(rev 56825)
@@ -30,6 +30,14 @@
extern "C" {
#endif
+/* The last three bits of the 'b' field in the kdtree are used to
+ * store data about the object. 0x4L marks if the node has children
+ * (is set to 0 for a leaf), the last two are the encoding for the
+ * splitting plane.
+ */
+#define TIE_HAS_CHILDREN(bits) (bits & (uint32_t)0x4L)
+#define TIE_SET_HAS_CHILDREN(bits) (bits | (uint32_t)0x4L)
+
struct tie_geom_s {
struct tie_tri_s **tri_list; /* 4-bytes or 8-bytes */
uint32_t tri_num; /* 4-bytes */
This was sent by the SourceForge.net collaborative development platform, the
world's largest Open Source development site.
------------------------------------------------------------------------------
Get 100% visibility into Java/.NET code with AppDynamics Lite!
It's a free troubleshooting tool designed for production.
Get down to code-level detail for bottlenecks, with <2% overhead.
Download for free and get started troubleshooting in minutes.
http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
_______________________________________________
BRL-CAD Source Commits mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/brlcad-commits
