Optimized custom math library for Pentium under Watcom C
Vesa Karvonen
Copyright (C) 1996 by Vesa Karvonen. All rights reserved.
All information is subject to future changes or improvements
_without_ notice.
-------------------------------------------------------------
I'm propably releasing an optimized math library in two months or so.
The library contains functions for complex numbers, 2D & 3D vectors,
quaternions, 3x3 and 4x4 matrices and some miscellaneous real number
functions. The library uses double precision floating point numbers and
is specificly optimized for Pentium under Watcom C (#pragma rulez!).
I would like to know if there are people interested in my library.
I will now ask myself some questions I would expect to hear...
What sort of licensing you use for the library?
-----------------------------------------------
The library will be 100% free and it comes with full source code. (I am
a young student and any donations will be greatly appreciated. However
such donations are not required. All donators will get their name on the
library documentations and will receive updates to the library
automatically, as long as the library is under development.) However
there are certain important restrictions on the use of the library:
1. Original library may be spread, but only if the library is spread
in the original unmodified form.
2. If you make changes to the library and wish to publish it, you
are not allowed to use the original title of the library (which
hasn't been determined yet).
3. All products that use the original library must clearly state the
original developer of the library (namely me). This also means
that if you publish the library under a new title, then you must
state the developer of original library.
4. Naturally all of these restrictions are inhereted to third parties.
I'm sure that some fancy lawyer could find loopholes in my licensing
terms (they will be more thoroughly explained in the documentations of
the library). The point is that if I ever see anyone abuse the library
I _will_ immediately stop supporting it publicly.
What comes with the library?
----------------------------
The library comes with full source code (assembler and C). I will not
provide precompiled .OBJs, .LIBs or .DLLs with the library. (If I would
the size of the library would be more than what I can conveniently send
through E-mail.) Don't ask me to compile the library for you. I won't.
How fast are the functions in the library?
------------------------------------------
All routines are optimized specificly for Pentium (Pentium, Pentium
Pro, Pentium with MMX and Pentium Pro with MMX). Optimizations include
code that hurts performance on 486(487?) and 387 processors, however
such code is kept to a minimum (compared to some FPU code I have seen).
Most functions in the library are very close to optimal. Short
operations, such as a vector dot product, suffer a lot of stalls due
to the fact that there generally aren't many parallel operations in such
short operations. However longer operations like matrix multiplies
(equivalent to 3 or more parallel dot products) usually only have a few
stalls of 1 or 2 cycles.
Because all classes (not C++) are implemented with double precision
floats, memory bandwidth is an issue that may hurt performance. However
some of the functions include code that avoids certain caching problems
without increasing clock counts.
I am using inline code for math functions. Your library can not be any
faster?
------------------------------------------------------------------------------
Special inline assembly versions of basic functions are implemented
for the Watcom C compiler. Even a simple vector dot product is usually
slower with inline C code. The Watcom C compiler isn't particularly
clever in FPU code optimization. Inline assembly versions aren't
supported for other compilers, because they don't have such clever
#pragma directives.
What functions are implemented in the library?
----------------------------------------------
The library contains functions for complex numbers, 2D & 3D vectors,
quaternions, 3x3 and 4x4 matrices and some miscellaneous real number
functions.
Vectors and matrices are best supported in the library. Only the basic
quaternion operations are implemented (so far). The library literally
contains hundreds of functions.
The library is continuously under development. I will add new functions
to the library, and perhaps even allow interested parties to include
their code in the official library (their names will be included in the
library and added to the licensing agreement - unless someone plays a
trick on me I will not change my licensing policy). Optimization
suggestions can also be sent.
How would I benefit from using the library?
-------------------------------------------
It is upto you do determine if a vast optimized math library is what
you need. If this is the case, then I would assume that my library is
one of the best to begin with. As the library is completely free and
comes with a very simple licensing policy, I would say that it can not
hurt to try it.
When will the library be available?
-----------------------------------
The library will be available (if I don't have problems with my
schedule) before '97. As this is not a commercial product (I have both
studying and commercial projects undergoing) so this library isn't the
highest priority project. However as I need the library for certain
future projects of mine, I am pretty sure that I will find the
necessary time to finish it.
How difficult it is to adopt your library?
------------------------------------------
The library has been designed in a way that allows programmer to use a
vast number of distinct functions without the need to know each of the
functions specificly. This has been carried out by using special naming
and parameter passing conventions for fuctions. For example all
multiplication functions use a operation keyword and object
identifiers:
Vector3 *MulV3M3x3( Vector3 *result, Vector3 *left, Matrix3x3 *right);
Matrix3x3 *MulM3x3M3x3( Matrix3x3 *result, Matrix3x3 *left, Matrix3x3
*right);
Complex *MulCC( Complex *result, Complex *left, Complex *rigth);
...
You must have also noticed that the parameters were given in the same
logical order on all of the above functions. Member functions (familiar
to C++ programmers) are also implemented:
Vector3 *v3MulM3x3( Vector3 *this_left, Matrix3x3 *right);
Matrix3x3 *m3x3MulM3x3( Matrix3x3 *this_left, Matrix3x3 *right);
Complex *cMulC( Complex *this_left, Complex *rigth);
...
Most non-member functions allow overwriting the arguments. However it
is recommended to use the member functions for such operations. There
are also reverse operations where appropriate.
IMO this library is nearly as easy to use in C and assembly language as
a
class library in C++.
-------------------------------------------------------------------------
I would be interested to hear your comments and questions about the
library.
If you are interested in licensing or writing code for the library then
E-mail me privately. Note that at the moment the development of the
library is suspended. It will continue in two maybe tree weeks. Thus I
can not and will not send you pre-release versions of the library.
I will send the library source code to all licensees as a .ARJ
file attached to a message. The size of the first release file
could be over 100kb (current size 85kb).
E-mail is the easiest method for me because I only have to setup a
mailing list. There are (theoretically) possible alternatives to
this (home page/ftp), but they would generally require extra time
on my side. It is likely that at some point this will change,
because I may have to setup such things anyway, but until then
E-mail is the easiest method.
The library should be ready for first release before the end of the
year. It only takes about a week of coding to reach the first release
stage but I really am very busy.
---------------------------------------------------------------------
Information that may have been somewhat unclear:
Article Unavailable
TheCrow
In article <327F70...@raita.oulu.fi>, vkar...@raita.oulu.fi says...
>
>Copyright (C) 1996 by Vesa Karvonen. All rights reserved.
>
>All information is subject to future changes or improvements
>_without_ notice.
>
>-------------------------------------------------------------
>
>I'm propably releasing an optimized math library in two months or so.
>The library contains functions for complex numbers, 2D & 3D vectors,
>quaternions, 3x3 and 4x4 matrices and some miscellaneous real number
>functions. The library uses double precision floating point numbers and
>is specificly optimized for Pentium under Watcom C (#pragma rulez!).
>I would like to know if there are people interested in my library.
Hi,
My name is Jack Mott and over the last 3 days I have been building a
3-D engine. I have a working engine now that can read 3-D objects in from a
file and display them as wireframes. Idividual objects can be translated, and
rotated around all axes, and you can fly around the world like in DOOM.
Anyway I just sorted hacked the code out through intuition so it is very slow.
And not everything works just right. I don't fully understand how to use
matrices to the best advantage, and would be very interested in your library.
Thanks for any info.
Tim Sweeney
> All routines are optimized specificly for Pentium (Pentium, Pentium
> Pro, Pentium with MMX and Pentium Pro with MMX). Optimizations include
> code that hurts performance on 486(487?) and 387 processors, however
> such code is kept to a minimum (compared to some FPU code I have seen).
>
> Most functions in the library are very close to optimal. Short
> operations, such as a vector dot product, suffer a lot of stalls due
> to the fact that there generally aren't many parallel operations in such
> short operations. However longer operations like matrix multiplies
> (equivalent to 3 or more parallel dot products) usually only have a few
> stalls of 1 or 2 cycles.
You should check out Visual C++'s optimizer. It generates stall-free code
for vector
and matrix operations floating point ops. I used VC++ to create a
3-component vector
class and defined all of the operators - add, subtract, scalar multiply,
dot product, matrix
transform, etc. This makes 3D math really easy -- "trade ease of
implementation for
speed", I thought.
To my utter surprise, I checked the assembly code output by VC++ and its
floating point
was perfectly pipelined for the Pentium.
-Tim
Chris Hargrove
>How difficult it is to adopt your library?
>------------------------------------------
>The library has been designed in a way that allows programmer to use a
>vast number of distinct functions without the need to know each of the
>functions specificly. This has been carried out by using special naming
>and parameter passing conventions for fuctions. For example all
>multiplication functions use a operation keyword and object
>identifiers:
>Vector3 *MulV3M3x3( Vector3 *result, Vector3 *left, Matrix3x3 *right);
>Matrix3x3 *MulM3x3M3x3( Matrix3x3 *result, Matrix3x3 *left, Matrix3x3
>*right);
>Complex *MulCC( Complex *result, Complex *left, Complex *rigth);
>...
>You must have also noticed that the parameters were given in the same
>logical order on all of the above functions. Member functions (familiar
>to C++ programmers) are also implemented:
If you are targetting this library to C++ programmers (as it appears
you are), then why aren't you using operator overloading? I think
vector = vector * matrix3;
is considerably more intuitive than
vector = MulV3M3x3(vector, vector, matrix3);
Operator overloading represents tensor math at its most natural level,
as it fits the equations you're trying to represent. So why the crude
function convention?
Also in another note, this was a very long post for the type of
library that many people can write up effectively in a day or two.
--
Chris Hargrove
Technology Programmer, Raven Software Corp.
char...@mail.ravensoft.com
http://www.ravensoft.com/
--
Vesa Karvonen
Vesa Karvonen wrote:
> The second compile (AFAIK) should have produced the absolutely
> best results that the compiler can provide. After _quickly_
> examining the results (the disassembled code) I found that only
> AddV3V3(), secondAddV3V3(), DotV3V3(), secondDotV3V3() had
> compiled into optimal code.
Sorry as I said I examined the code very quickly. Only DotV3V3() and
secondDotV3V3() compiled into optimal code. Both AddV3V3() and
secondAddV3V3() had an unnecessary AGI...
==> Vesa Karvonen
Vesa Karvonen
Tim Sweeney wrote:
>
> > All routines are optimized specificly for Pentium (Pentium, Pentium
> > Pro, Pentium with MMX and Pentium Pro with MMX). Optimizations include
> > code that hurts performance on 486(487?) and 387 processors, however
> > such code is kept to a minimum (compared to some FPU code I have seen).
> >
> > Most functions in the library are very close to optimal. Short
> > operations, such as a vector dot product, suffer a lot of stalls due
> > to the fact that there generally aren't many parallel operations in such
> > short operations. However longer operations like matrix multiplies
> > (equivalent to 3 or more parallel dot products) usually only have a few
> > stalls of 1 or 2 cycles.
>
> for vector
> and matrix operations floating point ops. I used VC++ to create a
> 3-component vector
> class and defined all of the operators - add, subtract, scalar multiply,
> dot product, matrix
> transform, etc. This makes 3D math really easy -- "trade ease of
> implementation for
> speed", I thought.
>
> To my utter surprise, I checked the assembly code output by VC++ and its
> floating point
> was perfectly pipelined for the Pentium.
>
> -Tim
Immediately after reading this reply I created a test source to see if
VC++ does indeed optimally pipeline vector/matrix floating point
operations. The test source is included in this message.
After compiling the source with the two command lines
CL.EXE -Ox -G5 -Zp1 -Gr -c -WX test.c
CL.EXE -Ox -Oa -G5 -Zp1 -Gr -c -WX test.c
The compiler's version was 10.00.5270 for 80x86.
I then disassembled the resulting object file with WDISASM.
The first compile was without the -Oa which assumes no aliasing.
After _quickly_ examining the first results I found that only
DotV3V3() and secondDotV3V3() had compiled into optimal code. Other
routines had either redundant FXCH's or stalls, most had both.
The second compile (AFAIK) should have produced the absolutely
best results that the compiler can provide. After _quickly_
examining the results (the disassembled code) I found that only
AddV3V3(), secondAddV3V3(), DotV3V3(), secondDotV3V3() had
compiled into optimal code.
However this was not all that I found out. Cross examining (from
short time memory mostly) I found out that the second compile
actually produced _slower_ code for many of the other functions!!!
Another factor here is that the Watcom C register calling
conventions are in fact faster and that the Watcom C's pragma's
provide a way to describe more efficiently how a function uses
memory and registers. Under Watcom C none of the following
functions need to change the contents of any general purpose
(EAX,EBX,ECX,EDX,EPB,ESI,EDI) integer registers. Under VC++
fastcall conventions only two registers are used to pass
arguments and a function that returns a value must always
copy it to EAX.
However Watcom C 10.? seems to produce less efficient FPU
code which is a real shame.
<<< test.c >>>
typedef struct Vector3 {
double x, y, z;
} V3;
typedef struct Matrix3x3 {
V3 u, v, w;
} M3x3;
V3 *AddV3V3( V3 *d, V3 *l, V3 *r)
//*************************************
{
d->x = l->x + r->x;
d->y = l->y + r->y;
d->z = l->z + r->z;
return ( d);
}
V3 *secondAddV3V3( V3 *d, V3 *l, V3 *r)
//*************************************
{
register double x, y, z;
x = l->x + r->x;
y = l->y + r->y;
z = l->z + r->z;
d->x = x;
d->y = y;
d->z = z;
return ( d);
}
double DotV3V3( V3 *l, V3 *r)
//***************************
{
return ( l->x * r->x + l->y * r->y + l->z * r->z);
}
double secondDotV3V3( V3 *l, V3 *r)
//*********************************
{
register double x, y, z;
x = l->x * r->x;
y = l->y * r->y;
z = l->z * r->z;
return ( x + y + z);
}
V3 *CrossV3V3( V3 *d, V3 *l, V3 *r)
//*********************************
{
d->x = l->y * r->z - l->z * r->y;
d->y = l->z * r->x - l->x * r->z;
d->z = l->x * r->y - l->y * r->x;
return ( d);
}
Article Unavailable
Tim
>>I'm propably releasing an optimized math library in two months or so.
Is the code in C or asm? I would be very interested in the asm code,
but I am forced to use MSoft VC++ (I use it at work and can't afford
to buy my own compiler.) I would however, be somewhat interested in
trying to "port" to MSoft.
Vesa Karvonen
Chris Hargrove wrote:
> If you are targetting this library to C++ programmers (as it appears
> you are), then why aren't you using operator overloading? I think
> vector = vector * matrix3;
> is considerably more intuitive than
> vector = MulV3M3x3(vector, vector, matrix3);
No, I am not targeting this to C++ programmers. If you read through my
message
you should have been able to determine that. The library can be useful
for C++
programmers as well, but they aren't my primary target group.
> Operator overloading represents tensor math at its most natural level,
> as it fits the equations you're trying to represent. So why the crude
> function convention?
C and assembler do not provide operator overloading.
> Also in another note, this was a very long post for the type of
> library that many people can write up effectively in a day or two.
_Hundreds_ of assembly language optimized functions in two days? You
really do know a set of good and _fast_ assembly language programmers
programmers!
==> Vesa Karvonen
Federico Mena
> Is the code in C or asm? I would be very interested in the asm code,
> but I am forced to use MSoft VC++ (I use it at work and can't afford
> to buy my own compiler.) I would however, be somewhat interested in
> trying to "port" to MSoft.
So why not use GCC? It's free and *VERY* good. Let's not start a
flame war, though.
Quartic
Vesa Karvonen
Tim wrote:
>
> >>I'm propably releasing an optimized math library in two months or so.
>
> but I am forced to use MSoft VC++ (I use it at work and can't afford
> to buy my own compiler.) I would however, be somewhat interested in
> trying to "port" to MSoft.
Most of the code is in assembly language. Certain complex
(not complex number functions) are written in C, because I
haven't had the time or enthusiasm to optimize them in
assembly language. ANSI C alternatives are provided for
most (maybe all - there is still some work to do before
the first release version is finished) functions, thus you
can compile the library under most environments.
Most assembly language functions use Watcom C register
calling conventions. As an extension to this I also use
FPU registers to pass floating point values to the small
number of functions that take them as arguments. This is
made transparent to C users by using Watcom C's auxialiry
pragmas and ANSI C alternatives for other compilers.
Currently it wouldn't be easy to use the assembly language
optimized functions under VC++, because (AFAIK) you can not
specify the way arguments are passed (except the few fixed
choices). However as I still need to make modifications to
many of the functions I will investigate if there is a way
to use clever assembly language macros to easily port between
a number of distinct calling conventions. If this is indeed
possible I will try to make DJGPP/GCC (I have no info on it's
calling conventions at the moment, but I will investigate)
and VC++ __fastcall ports for the first release. Note that
under VC++ __fastcall conventions many functions will be a
cycle or two slower. Reasons:
1. Most functions take more than 2 pointers as arguments
2. Most functions return a pointer to the destination
for convenience
Naturally 2. could be avoided, but it doesn't usually help,
because the following code can be used to load the third
argument (most functions have 3 parameters: destination,
left, right)) to a register and return the first argument
in EAX under the __fastcall conventions.
mov eax,ecx
mov ecx,[esp+4]
As you can see the instructions can pair and removing the
usually redundant return by loading the third argument to
EAX would not increase performance considerably.
==> Vesa Karvonen
Dann Corbit
Vesa Karvonen <vkar...@raita.oulu.fi> wrote in article
<3281C8...@raita.oulu.fi>...
> Chris Hargrove wrote:
> > If you are targetting this library to C++ programmers (as it appears
> > you are), then why aren't you using operator overloading? I think
> > vector = vector * matrix3;
> > is considerably more intuitive than
> > vector = MulV3M3x3(vector, vector, matrix3);
>
> No, I am not targeting this to C++ programmers. If you read through my
> message
> you should have been able to determine that. The library can be useful
> for C++
> programmers as well, but they aren't my primary target group.
>
> > Operator overloading represents tensor math at its most natural level,
> > as it fits the equations you're trying to represent. So why the crude
> > function convention?
If you want to create your own operator overloads,
it's absolutely trivial to accomplish, since you have
the functions written to accomplish the task. So
you can have the lovely C++ notation. On the other
hand, the way that Vesa has designed his library,
it is universally useful in Assembler, C, C++, and
many other languages. Also, especially for a graphics
solution, you will find that many (not all) compilers will
generate a temporary when you use operator overloading
and are hence much less efficient than using the function
call. Where speed is of the utmost, notational
simplification can be an expensive trade-off.
YMMV
[snip]
arj brussee
Tim Sweeney wrote:
> To my utter surprise, I checked the assembly code output by VC++ and its
> floating point was perfectly pipelined for the Pentium.
we've been playing around with PROTON (Intel reference C compiler) which
totally rocks on this. It takes some time to compile (dont do this
during debug phase ;-) but the code it generates is along the best that
I know.
-arjan/DD
Chris
In article <55rkcf$q...@unix.midplains.net>, char...@mail.ravensoft.com wrote:
>
>If you are targetting this library to C++ programmers (as it appears
>you are), then why aren't you using operator overloading? I think
>vector = vector * matrix3;
>is considerably more intuitive than
>vector = MulV3M3x3(vector, vector, matrix3);
>
>as it fits the equations you're trying to represent. So why the crude
>function convention?
Overloading operators is SO nice - cleans up the code no end - but is there a
price to pay? Being a relative newcomer to C++, I have yet to hear any
discussion of overhead associated with things like operator overloading.
>Also in another note, this was a very long post for the type of
>library that many people can write up effectively in a day or two.
Maybe for you - but some of us do not yet have the experience to write such a
library for ourselves. Having someone do it for us is a time saving way to
learn. If you yourself have such a library I'd be very interested in it.
Chris Maunder (ch...@cbr.dwr.csiro.au)
CSIRO Canberra, Australia
#include <disclaimer.h>