Re: gEDA-user: PCB Polygon code (with r-tree speedups) triggers GCC bug...

[Peter Clifton <pcjc2@xxxxxxxxx>]

On Tue, 2009-02-24 at 19:35 -0500, der Mouse wrote:
> > I guess I'll have to look out for any stack variables used in the
> > routines which use setjmp / longjmp, and make sure they are not going
> > to cause trouble.
> 
> > Since PCB works, I'll assume that the likelihood of that case is low.
> 
> On *most* current systems, *most* objects retain their values, even if
> they're auto and non-volatile.  The usual case that causes trouble is
> when the object happens to be kept in a register across the call which
> ends up longjmping; when longjmp unwinds the stack and restores
> registers, it restores the object's value as well.  But the C people
> wisely decided not to try to cast the current problematic cases in
> stone as the only allowed-to-be-problematic cases, to allow more
> latitude in the implementation of setjmp and longjmp (and, quite
> probably, to avoid making it impossible to implement without ruinous
> efficency penalties on some of the more arcane architectures).  Making
> such objects "indeterminate" rather than "changes may be rolled back"
> allows things like part of an object being in memory (and thus not
> rolled back) and part in a register (and thus rolled back).  And, of
> course, there's no guarantee that longjmp is implemented that way....
> 
> So don't assume that the code is correct just because it currently
> doesn't break.  The chances of being bitten by this issue at the
> moment are low, even for buggy code, but the next compiler release may
> include a more aggressive optimizer, or just a different
> code-generation module, and render such bugs blatant instead of latent.

In the polygon code, I found two examples which are likely to be buggy.
They are of the error trap pattern:

func (...)
{
  PLINE p;
  PLINE *holes = NULL;
  jmp_buf e;

  if ((code = setjmp (e)) == 0)
    {
      /* Do a series of things, accumulating a list of holes,
       * the head of which is pointed to by "holes". There
       * are multiple operations, many passed &e to allow
       * errors inside those long, perhaps recursive operations
       * to short-cut back and bypass further processing.
       */
    }

  while ((p = holes) != NULL)
    {
      holes = p->next;
      poly_DelContour (&p);
    }
  /* .... */
}

Since "holes" might be wound back, or just generally undefined, we at
least leak memory, and at worst do something strange and undefined.

Having looked at all this, I think I need to fix up my error clean-up
for the sped-up polygon routines anyway, so I'll see if I can fix this
at the same time.

As it currently stands though, I can't merge the sped-up polygon
routines anyway, as they actually impact negatively on the dicer
performance. (Even with the GL GUI, the dicer is used for PNG, PS and
gerber export etc..)

I had a lead on what I thought to be a possible reason for the slowness
(aside from the obvious extra work of keeping an r-tree of contours for
each POLYAREA), however my attempt to fix it resulted in further
slowdown!

The r-tree search for intersecting contours between a given polygon and
the clipping polygon (used in each dicing step to split a polygon about
the centre of some hole), must fire for every contour in the polygon
which is enclosed in, or intersects the large clipping polygon.

Most of those returns from r_search are not actually going to be
intersections, and we do work for no reason checking in more detail. The
obvious attempt to fix this looks out for the single contour, four sided
cliping polygon, and if it finds that case, it searches for
intersections of the main polygon contours and the boxes bounding each
individual edge on the clipping polygon.

IE.. test for |, _, - and | boxes separately, rather than a larger area
box. |_|

I think I need to start adding some performance counters manually to the
code.. with generic time-consuming routines such as r_search (which may
do work on behalf of other calls), it is sometimes difficult to
disambiguate between the cost of various r_tree searches within the same
routine.

(And compiler optimisation of statically declared functions often
results in harder to diagnose costs).

-- 
Peter Clifton

Electrical Engineering Division,
Engineering Department,
University of Cambridge,
9, JJ Thomson Avenue,
Cambridge
CB3 0FA

Tel: +44 (0)7729 980173 - (No signal in the lab!)



_______________________________________________
geda-user mailing list
geda-user@xxxxxxxxxxxxxx
http://www.seul.org/cgi-bin/mailman/listinfo/geda-user