*From*: Jon Trowbridge <trow emccta com>*To*: Gustavo Joćo Alves Marques Carneiro <ee96090 fe up pt>*Cc*: gnome-devel-list gnome org*Subject*: Re: GnomeCanvasLine*Date*: Wed, 3 May 2000 15:22:09 -0500

On Wed, May 03, 2000 at 09:24:34PM +0100, Gustavo Joćo Alves Marques Carneiro wrote: <snip> > ...which calls the item's point virtual > function. This function calculates the distance between the point and > each of the item's edges, using formulas like > dist = sqrt (dx * dx + dy * dy) - width / 2.0; > > This is very slow; my teacher says we should use something like > dist = dx; if the line's inclination is < 1.0, or > dist = dy; otherwise. IMHO, your teacher is wrong. I would guess that, unless you are on some very brain-damaged hardware, the biggest bottleneck here is the virtual function call overhead. (Your sqrt() call doesn't generate a function call: the compiler should inline it for you). Of course, if you *really* want to avoid transcendental functions, there is always the approximation: if (-epsilon < dx < epsilon) /* epsilon = 1e-8 is always a good choice... */ dist = dy; else { /* based on taylor expansion of sqrt(1+t^2), which is 1 + 1/2 t^2 - 1/8 t^4 + ... */ if (dx > dy) { quot = dy/dx; mult = dx; else { quot = dx/dy; mult = dy; } quot *= quot; dist = 1 + 0.5 * quot; quot *= quot; /* optional */ dist -= 0.125 * quot; /* optional */ dist *= mult; } dist -= width / 2.0; (You can omit the steps marked "optional" and still get pretty good accuracy. Your error will be O(min(x/y,y/x)^3) rather than O(min(x/y,y/x)^6). And beware, I just typed this code it: I didn't try to compile it or check it...) but these sorts of machinations shouldn't be necessary on modern hardware for anything but the most intense numerical computing problems. Of course, these things used to be *very* necessary. I used to use tricks like this all the time... back before CPUs had build in FPUs. (I still remember the explosive performance boost I got after installing an 8087 in my old PC.) Your teacher is probably a relic of this era. Nowadays, code locality is key: actual computation tends to be very inexpensive relative to memory access. > This is also very slow. Amazingly, I don't notice it being slow. If you can't notice it, great --- one less thing to optimize. Sometimes it is very hard to predict what will be slow and what won't be. -JT -- GNU/Linux: Free your mind and your OS will follow.

**References**:**GnomeCanvasLine***From:*Gustavo Joćo Alves Marques Carneiro

[Date Prev][Date Next] [Thread Prev][Thread Next] [Thread Index] [Date Index] [Author Index]