Optimization by hand.

[Steven T. Hatton]

In the following code I have attempted to perform all calculations that are
repeated in the mathematical expression for the rotation being evaluated.
IOW, I calculate cos(_angle) only once, and put it in a variable. Perhaps
a compiler is smart enough to do this for me. I don't know. When I get a
chance I plan on trying to look at the compiler output to determine what is
happening with gcc.

I'm wondering what others think about this kind of hand optimization.

Matrix3<T> setRotation(const Vector3<T>& axis, const T& angle)
{
axis.normal(_axis); // puts unit-length vector parallel to axis in _axis
_angle = angle;

// need to specialize these for float
T c = cos(_angle);
T s = sin(_angle);
T t = T(1) - c;

// references should vanish at compile time
const T& x = axis[0];
const T& y = axis[1];
const T& z = axis[2];

T txy = t * x * y;
T& tyx(txy);

T txz = t * x * z;
T& tzx(txz);

T tyz = t * y * z;
T& tzy(tyz);

T sx = s * x;
T sy = s * y;
T sz = s * z;

// The following is based on the articel found here
// http://www.gamedev.net/reference/articles/article1199.asp
// I have not yet tested the operations to verify my correction to
// the formula in the article are valid.
_data[0][0] = t*x*x+c; _data[0][1] = tyx + sz; _data[0][2] = tzx-sy;
_data[1][0] = txy-sz; _data[1][1] = t*y*y+c; _data[1][2] = tzy+sx;
_data[2][0] = txz+sy; _data[2][1] = tyz-sx; _data[2][2] = tzz+c;

/* my original form
_data[0][0]=t*x*x+c; _data[0][1]=t*y*x+s*z; _data[0][2]=t*z*x-s*y;
_data[1][0]=t*x*y-s*z; _data[1][1]=t*y*y+c; _data[1][2]=t*z*y+s*x;
_data[2][0]=t*x*z+s*y; _data[2][1]=t*y*z-s*x; _data[2][2]=t*z*z+c;
*/

}

/***************************************************************************
 *   Copyright (C) 2004 by Steven T. Hatton                                *
 *   (e-mail address removed)                                            *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
* Gunax lbh sbe gur Qbanyq Xahgu dhbgr. Yvxrjvfr ba vg'f vzcyrzragngvba *
* qrcraqrag. *
 ***************************************************************************/

 

[Mike Wahler]

In the following code I have attempted to perform all calculations that are
repeated in the mathematical expression for the rotation being evaluated.
IOW, I calculate cos(_angle) only once, and put it in a variable. Perhaps
a compiler is smart enough to do this for me. I don't know. When I get a
chance I plan on trying to look at the compiler output to determine what is
happening with gcc.

I'm wondering what others think about this kind of hand optimization.

I think one should give the compiler first crack at it,
then only 'hand optimize' if necessary. But even before
doing that, I'd first try a different compiler(s).

-Mike

 

[Steven T. Hatton]

I think one should give the compiler first crack at it,
then only 'hand optimize' if necessary. But even before
doing that, I'd first try a different compiler(s).

-Mike

The real question is whether I have removed operations from the object code,
and/or replaced them with more efficient operations. Sure, I can and will
experiment with this. I know from experience that when I start performing
multiple nested operations on nodes in a tree the cost can get very high in
a hurry. O(log(n)) IIRC.

I'm not trying to solve one problem. I'm trying to address an entire class
of problems. If there are formal discussions of these issues available in
articels or books, I am interested to know where.
--
"If our hypothesis is about anything and not about some one or more
particular things, then our deductions constitute mathematics. Thus
mathematics may be defined as the subject in which we never know what we
are talking about, nor whether what we are saying is true." - Bertrand
Russell

 

[David Lindauer]

The real question is whether I have removed operations from the object code,
and/or replaced them with more efficient operations. Sure, I can and will
experiment with this. I know from experience that when I start performing
multiple nested operations on nodes in a tree the cost can get very high in
a hurry. O(log(n)) IIRC.

I'm not trying to solve one problem. I'm trying to address an entire class
of problems. If there are formal discussions of these issues available in
articels or books, I am interested to know where.
--
"If our hypothesis is about anything and not about some one or more
particular things, then our deductions constitute mathematics. Thus
mathematics may be defined as the subject in which we never know what we
are talking about, nor whether what we are saying is true." - Bertrand
Russell

the problem is dependent both on the processor you are using and the compiler
you are using. Most modern compilers will be able to cache often used integer
values in registers, and on some processors this will happen for often used
floating values as well. But it is really up to the compilers judgement as to
what constitutes 'often used' and how much trouble the compiler author went to.
Most modern day compilers will do a good job of this if the processor lets them
(for example on intel processors it would be somewhat difficult but not
impossible to cache floating values because of the floating point stack
architecture, but depending on usage and scope integers are easily cacheable).
But there was a time in the not too distant past where compilers were *so*
dismal that if you wanted this kind of optimization you *had* to do it by hand
the way you are doing it here.

David

 

[Mike Wahler]

The real question is whether I have removed operations from the object code,
and/or replaced them with more efficient operations.

That depends entirely upon the implementation (and upon the
platform where the program is executed). The question cannot
be answered from a language perspective.

Sure, I can and will
experiment with this. I know from experience that when I start performing
multiple nested operations on nodes in a tree the cost can get very high in
a hurry. O(log(n)) IIRC.

Yes it can, at the algorithmic level. How various compiler implement
the algorithm can vary widely, resulting in widely differing performance.

I'm not trying to solve one problem. I'm trying to address an entire class
of problems. If there are formal discussions of these issues available in
articels or books, I am interested to know where.

For discussion of algorithmic solutions, try an algorithms group.
And there are also always the famous Knuth books.

For discussion of the efficiency of implementation of particular
compilers, ask in groups about those compilers.

I can't at the moment think of any particular books or articles
about these issues, but google's always a good place to start.

-Mike

 

[Victor Bazarov]

[...]
I can't at the moment think of any particular books or articles
about these issues, but google's always a good place to start.

Efficient C++, maybe...