[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
gEDA-cvs: pcb.git: branch: master updated (ff33014dc2514203e5c63a055c1e09828d00876a)
The branch, master has been updated
via ff33014dc2514203e5c63a055c1e09828d00876a (commit)
via f9ad8e0026a03091c320612720cb9abab12ad97e (commit)
from 5a4aa55ebebc6d4a30085d655d1b4dfaa320c401 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
=========
Summary
=========
src/global.h | 32 ++++++++++
src/polygon1.c | 185 ++++++++++++++++++++++++++++---------------------------
src/rtree.c | 4 +-
3 files changed, 128 insertions(+), 93 deletions(-)
=================
Commit Messages
=================
commit ff33014dc2514203e5c63a055c1e09828d00876a
Author: Peter Clifton <pcjc2@xxxxxxxxx>
Commit: Peter Clifton <pcjc2@xxxxxxxxx>
Add some annotations to help optimise branch prediction.
Macros G_LIKELY and G_UNLIKELY were taken from GLib (LGPL 2), and
renamed without the G_ prefix.
This hasn't had much discernable effect
:100644 100644 3c383be... e8fc8f1... M src/global.h
:100644 100644 1e2e009... fc01611... M src/polygon1.c
:100644 100644 aa5b41a... f7ffe4d... M src/rtree.c
commit f9ad8e0026a03091c320612720cb9abab12ad97e
Author: Peter Clifton <pcjc2@xxxxxxxxx>
Commit: Peter Clifton <pcjc2@xxxxxxxxx>
Rework iteration over contours in "intersect" to improve performance
We don't need to be using an r_tree search to determine if a contour's
bounding box hits anything in another contour. Just compare the bounding
boxes directly, then continue to the more expensive testing.
Rather than counting the vertices of each POLYAREA then swapping to
ensure we loop over the the small one, wait until we've worked out
which contours we're comparing. Rather than swapping, we just choose
which to loop over. This saves us time in the case where the larger
intersecting contour belongs to the polygon with fewer vertices.
In one case, this change reduced a complex board's load time from
~140 seconds to ~70.
:100644 100644 fdb816d... 1e2e009... M src/polygon1.c
=========
Changes
=========
commit ff33014dc2514203e5c63a055c1e09828d00876a
Author: Peter Clifton <pcjc2@xxxxxxxxx>
Commit: Peter Clifton <pcjc2@xxxxxxxxx>
Add some annotations to help optimise branch prediction.
Macros G_LIKELY and G_UNLIKELY were taken from GLib (LGPL 2), and
renamed without the G_ prefix.
This hasn't had much discernable effect
diff --git a/src/global.h b/src/global.h
index 3c383be..e8fc8f1 100644
--- a/src/global.h
+++ b/src/global.h
@@ -91,6 +91,38 @@ typedef struct
#define __FUNCTION__ __FUNCTION2(__FILE__,__LINE__)
#endif
+
+/* ---------------------------------------------------------------------------
+ * Macros to annotate branch-prediction information.
+ * Taken from GLib 2.16.3 (LGPL 2).G_ / g_ prefixes have
+ * been removed to avoid namespace clashes.
+ */
+
+/* The LIKELY and UNLIKELY macros let the programmer give hints to
+ * the compiler about the expected result of an expression. Some compilers
+ * can use this information for optimizations.
+ *
+ * The _BOOLEAN_EXPR macro is intended to trigger a gcc warning when
+ * putting assignments inside the test.
+ */
+#if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__)
+#define _BOOLEAN_EXPR(expr) \
+ __extension__ ({ \
+ int _boolean_var_; \
+ if (expr) \
+ _boolean_var_ = 1; \
+ else \
+ _boolean_var_ = 0; \
+ _boolean_var_; \
+})
+#define LIKELY(expr) (__builtin_expect (_BOOLEAN_EXPR(expr), 1))
+#define UNLIKELY(expr) (__builtin_expect (_BOOLEAN_EXPR(expr), 0))
+#else
+#define LIKELY(expr) (expr)
+#define UNLIKELY(expr) (expr)
+#endif
+
+
/* ---------------------------------------------------------------------------
* Do not change the following definitions even if they're not very
* nice. It allows us to have functions act on these "base types" and
diff --git a/src/polygon1.c b/src/polygon1.c
index 1e2e009..fc01611 100644
--- a/src/polygon1.c
+++ b/src/polygon1.c
@@ -94,7 +94,7 @@ int vect_inters2 (Vector A, Vector B, Vector C, Vector D, Vector S1,
#define error(code) longjmp(*(e), code)
#define MemGet(ptr, type) \
-if (((ptr) = malloc(sizeof(type))) == NULL) \
+if (UNLIKELY (((ptr) = malloc(sizeof(type))) == NULL)) \
error(err_no_memory);
#undef DEBUG_LABEL
@@ -816,8 +816,8 @@ intersect (jmp_buf * jb, POLYAREA * b, POLYAREA * a, int add)
/* NB: If this actually hits anything, we are teleported back to the beginning */
info.tree = (rtree_t *) rtree_over->tree;
if (info.tree)
- if (r_search (info.tree, &info.s->box,
- seg_in_region, seg_in_seg, &info))
+ if (UNLIKELY (r_search (info.tree, &info.s->box,
+ seg_in_region, seg_in_seg, &info)))
return err_no_memory; /* error */
}
while ((av = av->next) != &looping_over->head);
@@ -849,23 +849,29 @@ M_POLYAREA_intersect (jmp_buf * e, POLYAREA * afst, POLYAREA * bfst, int add)
a->contours->xmin <= b->contours->xmax &&
a->contours->ymin <= b->contours->ymax)
{
- if (intersect (e, a, b, add))
+ if (UNLIKELY (intersect (e, a, b, add)))
error (err_no_memory);
}
}
while (add && (a = a->f) != afst);
for (curcB = b->contours; curcB != NULL; curcB = curcB->next)
if (curcB->Flags.status == ISECTED)
- if (!(the_list = add_descriptors (curcB, 'B', the_list)))
- error (err_no_memory);
+ {
+ the_list = add_descriptors (curcB, 'B', the_list);
+ if (UNLIKELY (the_list == NULL))
+ error (err_no_memory);
+ }
}
while (add && (b = b->f) != bfst);
do
{
for (curcA = a->contours; curcA != NULL; curcA = curcA->next)
if (curcA->Flags.status == ISECTED)
- if (!(the_list = add_descriptors (curcA, 'A', the_list)))
- error (err_no_memory);
+ {
+ the_list = add_descriptors (curcA, 'A', the_list);
+ if (UNLIKELY (the_list == NULL))
+ error (err_no_memory);
+ }
}
while (add && (a = a->f) != afst);
} /* M_POLYAREA_intersect */
diff --git a/src/rtree.c b/src/rtree.c
index aa5b41a..f7ffe4d 100644
--- a/src/rtree.c
+++ b/src/rtree.c
@@ -915,7 +915,7 @@ __r_insert_node (struct rtree_node *node, const BoxType * query,
{
register int i;
- if (manage)
+ if (UNLIKELY (manage))
{
register int flag = 1;
@@ -996,7 +996,7 @@ __r_insert_node (struct rtree_node *node, const BoxType * query,
new_node->u.rects[0].bptr = query;
new_node->u.rects[0].bounds = *query;
new_node->box = *query;
- if (manage)
+ if (UNLIKELY (manage))
new_node->flags.manage = 1;
sort_node (node);
return;
commit f9ad8e0026a03091c320612720cb9abab12ad97e
Author: Peter Clifton <pcjc2@xxxxxxxxx>
Commit: Peter Clifton <pcjc2@xxxxxxxxx>
Rework iteration over contours in "intersect" to improve performance
We don't need to be using an r_tree search to determine if a contour's
bounding box hits anything in another contour. Just compare the bounding
boxes directly, then continue to the more expensive testing.
Rather than counting the vertices of each POLYAREA then swapping to
ensure we loop over the the small one, wait until we've worked out
which contours we're comparing. Rather than swapping, we just choose
which to loop over. This saves us time in the case where the larger
intersecting contour belongs to the polygon with fewer vertices.
In one case, this change reduced a complex board's load time from
~140 seconds to ~70.
diff --git a/src/polygon1.c b/src/polygon1.c
index fdb816d..1e2e009 100644
--- a/src/polygon1.c
+++ b/src/polygon1.c
@@ -660,12 +660,6 @@ seg_in_seg (const BoxType * b, void *cl)
return 0;
}
-static int
-curtail (const BoxType * b, void *cl)
-{
- longjmp (*(jmp_buf *) cl, 1);
-}
-
static void *
make_edge_tree (PLINE * pb)
{
@@ -738,25 +732,12 @@ get_seg (const BoxType * b, void *cl)
static int
intersect (jmp_buf * jb, POLYAREA * b, POLYAREA * a, int add)
{
- POLYAREA *t;
PLINE *pa, *pb; /* pline iterators */
+ PLINE *rtree_over;
+ PLINE *looping_over;
VNODE *av; /* node iterators */
struct info info;
BoxType box;
- int ca = 0, cb = 0;
-
- /* count the vertices in a and b */
- for (pa = a->contours; pa; pa = pa->next)
- ca += pa->Count;
- for (pb = b->contours; pb; pb = pb->next)
- cb += pb->Count;
- /* search the tree with the larger number of verticies */
- if (ca > cb)
- {
- t = b;
- b = a;
- a = t;
- }
if (add)
info.touch = NULL;
@@ -764,71 +745,87 @@ intersect (jmp_buf * jb, POLYAREA * b, POLYAREA * a, int add)
info.touch = jb;
setjmp (info.env); /* we loop back here whenever a vertex is inserted */
{
- for (pa = a->contours; pa; pa = pa->next)
+ pa = a->contours;
+ pb = b->contours;
+ while (pa) /* Loop over the contours of POLYAREA "a" */
{
- jmp_buf env;
- /* skip the whole contour if it's bounding box doesn't intersect */
- if (setjmp (env) == 0)
- {
- /* expand the box to include the max point */
- BoxType sb;
- sb.X1 = pa->xmin;
- sb.X2 = pa->xmax + 1;
- sb.Y1 = pa->ymin;
- sb.Y2 = pa->ymax + 1;
- for (pb = b->contours; pb; pb = pb->next)
- {
- /*
- if (sb.X1 > pb->xmax || sb.X2 < pb->xmin || sb.Y1 > pb->ymax || sb.Y2 < pb->ymin)
- continue;
- */
- info.tree = (rtree_t *) pb->tree;
- if (info.tree)
- r_search (info.tree, &sb, NULL, curtail, &env);
- }
- continue;
- }
- else /* something intersects so check the edges of the contour */
- {
- av = &pa->head;
- do
- {
- /* check this edge for any insertions */
- double dx;
- info.v = av;
- /* compute the slant for region trimming */
- dx = av->next->point[0] - av->point[0];
- if (dx == 0)
- info.m = 0;
- else
- {
- info.m = (av->next->point[1] - av->point[1]) / dx;
- info.b = av->point[1] - info.m * av->point[0];
- }
- box.X2 = (box.X1 = av->point[0]) + 1;
- box.Y2 = (box.Y1 = av->point[1]) + 1;
- /* fill in the segment in info corresponding to this node */
- if (setjmp (info.sego) == 0)
- {
- r_search ((rtree_t *) (pa->tree), &box, NULL, get_seg,
- &info);
- assert (0);
- }
- for (pb = b->contours; pb; pb = pb->next)
- {
- if (pb->xmin > info.s->box.X2 || pb->xmax < info.s->box.X1
- || pb->ymin > info.s->box.Y2
- || pb->ymax < info.s->box.Y1)
- continue;
- info.tree = (rtree_t *) pb->tree;
- if (info.tree && r_search
- (info.tree, &info.s->box, seg_in_region, seg_in_seg,
- &info))
- return err_no_memory; /* error */
- }
- }
- while ((av = av->next) != &pa->head);
- }
+ int found_overlapping_a_b_contour = FALSE;
+
+ while (pb) /* Loop over the contours of POLYAREA "b" */
+ {
+ /* Are there overlapping bounds? */
+ if (pb->xmin <= pa->xmax && pb->xmax >= pa->xmin &&
+ pb->ymin <= pa->ymax && pb->ymax >= pa->ymin)
+ {
+ found_overlapping_a_b_contour = TRUE;
+ break;
+ }
+ pb = pb->next;
+ }
+
+ /* If we didn't find anything intersting, move onto the next "a" contour */
+ if (!found_overlapping_a_b_contour)
+ {
+ pa = pa->next;
+ pb = b->contours;
+ continue;
+ }
+
+ /* something intersects so check the edges of the contour */
+
+ /* Pick which contour has the fewer points, and do the loop
+ * over that. The r_tree makes hit-testing against a contour
+ * faster, so we want to do that on the bigger contour.
+ */
+ if (pa->Count < pb->Count)
+ {
+ rtree_over = pb;
+ looping_over = pa;
+ }
+ else
+ {
+ rtree_over = pa;
+ looping_over = pb;
+ }
+
+ av = &looping_over->head;
+ do /* Loop over the nodes in the smaller contour */
+ {
+ /* check this edge for any insertions */
+ double dx;
+ info.v = av;
+ /* compute the slant for region trimming */
+ dx = av->next->point[0] - av->point[0];
+ if (dx == 0)
+ info.m = 0;
+ else
+ {
+ info.m = (av->next->point[1] - av->point[1]) / dx;
+ info.b = av->point[1] - info.m * av->point[0];
+ }
+ box.X2 = (box.X1 = av->point[0]) + 1;
+ box.Y2 = (box.Y1 = av->point[1]) + 1;
+
+ /* fill in the segment in info corresponding to this node */
+ if (setjmp (info.sego) == 0)
+ {
+ r_search ((rtree_t *) (looping_over->tree), &box, NULL, get_seg, &info);
+ assert (0);
+ }
+
+ /* NB: If this actually hits anything, we are teleported back to the beginning */
+ info.tree = (rtree_t *) rtree_over->tree;
+ if (info.tree)
+ if (r_search (info.tree, &info.s->box,
+ seg_in_region, seg_in_seg, &info))
+ return err_no_memory; /* error */
+ }
+ while ((av = av->next) != &looping_over->head);
+
+ /* Continue the with the _same_ "a" contour,
+ * testing it against the next "b" contour.
+ */
+ pb = pb->next;
}
} /* end of setjmp loop */
return 0;
_______________________________________________
geda-cvs mailing list
geda-cvs@xxxxxxxxxxxxxx
http://www.seul.org/cgi-bin/mailman/listinfo/geda-cvs