Archived

This topic is now archived and is closed to further replies.

Mr_Burns

math in quake

Recommended Posts

Mr_Burns    122
I was browsing the quake 1 and 2 source code, and I noticed that Carmack uses macros for all his vector math. I figure he does everything as optimally as possible, so are macros really any faster than using inline overloaded operators? I would think that in some cases, e.g. if one of the parameters is an expression, macros would be slower because the expression is evaluated more than once when the macro is expanded. I also noticed that whenever he divides a vector by a scalar, he actually multiplies by 1/scaler. On today''s modern processors, is dividing so slow that doing 1 divide and 3 mults is faster than 3 divides? Or does this optimization only apply to the older processors of quake 2''s day? TIA for the input

Share this post


Link to post
Share on other sites
Vlion    151
Intersesting.

I do think that 1 div and 3 muls is faster than 3 divs.

I don''t know about macro/inline speed tradeoffs.




Bugle4d

Share this post


Link to post
Share on other sites
a person    118
1 div and 3 muls are definatly somewhat faster then 3 divs. you see divs are just like muls. repetetive use of subtraction. unfortunatly, it requires doing it many times more then the divsor and a conditional check to see when you are done. also you cant optimize a division well. plus you would always mulitple by the smaller number to reduce the number of additions.

see http://fatphil.org/x86/pentopt/17.html
for some info. the most improtant tidbit is that
quote:

Integer multiplication takes 4 clocks, floating point multiplication 5, and MMX multiplication 3 clocks. Integer and MMX multiplication is pipelined so that it can receive a new instruction every clock cycle. Floating point multiplication is partially pipelined: The execution unit can receive a new FMUL instruction two clocks after the preceding one, so that the maximum throughput is one FMUL per two clock cycles. The holes between the FMUL''s cannot be filled by integer multiplications because they use the same circuitry. XMM additions and multiplications take 3 and 4 clocks respectively, and are fully pipelined. But since each logical XMM register is implemented as two physical 64-bit registers, you need two uops for a packed XMM operation, and the throughput will then be one arithmetic XMM instruction every two clock cycles. XMM add and multiply instructions can execute in parallel because they don''t use the same execution port.

Integer and floating point division takes up to 39 clocks and is not pipelined. This means that the execution unit cannot begin a new division until the previous division is finished. The same applies to squareroot and transcendental functions.




this applies for ppro, p2, and p3 (though naturally mmx is p2/p3 and xmm is for p3).

as for macros, carmack is hoping that the compiler will place the result of the expression in a register. most decent optimizers will do this for many expressions by calculating it then pushing the answer on the stack till needed. again theory, see asm output from your compiler to see what really happens.

Share this post


Link to post
Share on other sites
TerranFury    142
Nowadays inline functions have made macros for math functions relatively useless. Also, remember the well-known macro-killing expression:
f(++x);

Share this post


Link to post
Share on other sites
LilBudyWizer    491
Well, technically you can''t divide a vector by a scalar. It is undefined. I would be inclined to say that is why he does it more than optimization.

A core rule of optimization is that 10% of your code does 90% of your processing. That is in an optimized program. In an unoptimized one it it might be 1% doing 99%. What you do in the other 90% of the code doesn''t much matter. It isn''t 1 divide and 3 multiplies versus 3 divides that matters. Rather it is a billion divides and 3 billion multiplies versus 3 billion divides that matters. Even then that is just a petty issue. You can optimize every individual statement and still end up with performance that sucks. It is like hiring a programmer based on his typing speed. Well, he has to type the program in doesn''t he?

The micro level of optimization will get you like 10 to 20%. The macro level will get you 90, 95, 99% or perhaps even better. There is a time for that 10 to 20%. 10% can double your frame rate if you are just missing your vertical blanking. If you are running like crap on a top of the line machine 10 to 20% isn''t going to cut it. You most likely need 50% just to say it is servicable on the high end. To cover the mass market you are going to have to get a 90% or better improvement. As a general rule if performance is unacceptable then that means I need 10 to 1. There are things at the micro level that will get you that. Generally though 50% is pretty much the top end. Your user will notice an improvement of 50%. It would be foolish to pass up 50% or even 10%. That is unless getting that 50% causes you to miss the 90% you could have gotten. You don''t have an unlimited amount of time. The most highly optimized bubble sort of a million records still sucks and the most optimized sort of a million records that don''t need sorted is still just a waste.

Share this post


Link to post
Share on other sites
ZealousElixir    256
quote:
Original post by LilBudyWizer
Well, technically you can''t divide a vector by a scalar. It is undefined. I would be inclined to say that is why he does it more than optimization.


Undefined? By what line of reasoning?



//email me.//zealouselixir software.//msdn.//n00biez.//
miscellaneous links

[if you have a link proposal, email me.]

Share this post


Link to post
Share on other sites
LilBudyWizer    491
I could be wrong, but in the sense that your scalar could be a vector, i.e. a vector of vectors. You could not take a reciprocal of your scalar then because division by a vector is undefined. As far as I know scalars are not limited to real and complex numbers. Rather it is whatever is considered one element of your vector. It could be a vector, a matrix, a function, or anything for which the properties concerning scalars still hold. So division is only defined if it is defined for whatever you defined as your scalar.

Share this post


Link to post
Share on other sites
ZealousElixir    256
The primary definition of a scalar is that of a value, something with neither magnitude or direction. If you define scalar as the Game Dictionary does, it is a single element, which could conceivably be of any number of dimensions. However, in the above statement, I assumed the writer was referring to a vector as a 3D vector, in which case a scalar would be a single value, a single number. So division by such a number would not be undefined.

Later,
ZE.

//email me.//zealouselixir software.//msdn.//n00biez.//
miscellaneous links

[if you have a link proposal, email me.]

Share this post


Link to post
Share on other sites
LilBudyWizer    491
Yes, true, but still most mathematics and physics textbooks will use (1/c)*u instead of u/c. That is the convention. I personally wouldn''t override the / operator for a vector. I would want to get a compile error if I tried to divide a vector by a scalar since the main reason I would attempt that is mistyping a formula. Oh yeah, that was suppose to be the magnitude of u, not u.

Share this post


Link to post
Share on other sites
a person    118
lets see. optimization of division for mulitplication is for the vector macros.
instead of:
Normalize: vector/magnitde_of_vector
mag = sqrt(x*x+y*y+z*z);
x/=mag;
y/=mag;
z/=mag;

you could do
mag = 1.0/sqrt(x*x+y*y+z*z);
x*=mag;
y*=mag;
z*=mag;

which is generally faster.

division by a scalar MUST be a valid operation to be done to a vector, otherwise you could not normalize a vector.

also explain how:
vector*0.5;
differs from:
vector/2.0;

if you can prove they are different operation and result in a different answer, then you are correct and prove many mathmaticans wrong.

btw, a vector of ANY valid dimension can be used in any operation. there is no difference to the algorithm of what is done. a scalar is a single value, by defination. not an element of a matrix, not a subset of a vector. a single mathmatical number. 4.5 is a scalar. (2.3, 4.5, 7.8) is not.

you are confusing the STL vector class, with an actual vector. this is the MATH discussion. as such we are using mathmatical definations of things. dont confuse two different things.

also no matter what multiplication of a vector by a scalar value is defined as:
for(i=0; i element*=scalar;
division ironically is:
for(i=0; i element[i]/=scalar;

LilBudyWizer, please go learn some math before continuing game programming. it will really help you.

Share this post


Link to post
Share on other sites
ZealousElixir    256
a person: Please watch it with the cutting remarks. Analyze why you do it: does it really help the person see their mistake? If not, then perhaps you''re doing it to gratify yourself, which doesn''t do anyone any good.

Peace,
ZE.

//email me.//zealouselixir software.//msdn.//n00biez.//
miscellaneous links

[if you have a link proposal, email me.]

Share this post


Link to post
Share on other sites
LilBudyWizer    491
There is no need to be insulting here. The definition of a vector is an element of a vector space. Now admittedly I don''t know what restrictions there are on what you call a scalar. It could be the field axioms in which case you are arguably right. The problem is that all of those axioms don''t hold for vector spaces that I''m quite certain are valid. It could be that both of my linear algebra books were wrong to use the example of a vector space composed of vectors whose elements are n x n matrices. The commutative property for multiplication doesn''t hold and the zero matrix is not the only matrix that is singular. They are left commutative and right commutative, but not generally commutative. So perhaps you are right, but I don''t see much of a convincing arguement from you that you are right.

If you had of said no, a scalar must meet these conditions then I would be more convinced. The entire part of about a single number just baffles me. A scalar is a single number, but an element of a vector is what? The logic mystifies me. You are both arguing that it is not a single number and that it is a single number. Which is it? At least don''t contridict yourself. Is an element of a vector a scalar or not? Does a scalar have to be a real number or not? If a scalar must be a real number then what is a complex number? If it is not a scalar then does that mean you can''t have a vector composed of complex numbers? If you can does that mean you can only multiply that vector by real numbers? If you can also multiply be complex numbers and a complex number is not a scalar then what is that called? It can''t be scalar multiplication if it isn''t a scalar. If both a real number and complex number can be scalars then what determines what is a scalar? Does that definition exclude 2 x 2 matrices? Let''s at least be consistant here.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
You should get some rest, LilBudyWizer...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
vector spaces exist over fields.

reference:
http://mathworld.wolfram.com/AbstractVectorSpace.html

Remember what got this started was someone tried to multiply by a multiplicative inverse. You harped on division as undefined against a vector. but its clearly defined.


First lets be blunt division is a defined operation: it must be translated to equation to have meaning. notice there is no reference to division in the field axioms. its not there because you need field axioms to define linear equations then having that you can define division. if you referenced division in field axioms you would have serious conceptual issues.

b/a is _defined_ as the unique solution of the equation aX = b. defined. not proven. just defined. where the equilvalence of b*1/a to b/a is easy to show. since we know that a*"inverse of a" = 1 and we say that 1/a must equal "inverse of a by" invoking uniqueness. they cant be different becuase they both solve the same equation.

Moving on again then is how does this relate to the original assertion you said:
" technically dividing a vector by a scalar is undefined"

citing field axioms that define a field. but what about the axioms that define a vector space ?
here:
http://mathworld.wolfram.com/VectorSpace.html

though i must say the wolfram.com definitions lack completeness. The concept is that to be a vector space over a field there must both exist a vector v element of V (of stuff you decide) AND AND!!!! there must exist "a" an element of a field with the following properties:

(STOP!!! intrinsic to understanding this is there has to exist a "a" an element of a field to have a vector! Also notice how the mathematica page defined it with a complete loss of generality skipping to an "a" of the field of reals where thats not required at all. it could be an "a" of field foofield. but moving on)

one requirement to be a vector space as per the above and every intro abstract linear algebra book in the world is that this be true and defined:

(ab)U = a(bU) where U is an element of the potential vector space and a,b are elements of a field space.

AHHH!!!
note that a,b have to abide by the field space axioms because they are in a field space. so "a" can take on the value 1. becuase 1 has to be defined in the field space. leaving 1*bU.
now note that b can take on the value you f^(-1) becuase f^(-1) has to be defined in that same field space where f is arbitrary.
so we have a vector U being multiplied by a mutliplicative inverse being not only DEFINED but REQUIRED for the vector space to exist as a vector space.

since division is defined as multiplication by a multiplicative inverse as above then we can safely say that division of a scalar (field) against a vector of scalars is not only defined but required to exist.

your original statement that it is technically undefined is quite wrong. i could be only slightly be more thorough in showing you why by writing a first chapter on abstract linear algebra.



Share this post


Link to post
Share on other sites
davepermen    1047
and now we come down onto the floor realising that our vector in a 3dgame is simply an array of 3 floats, and to get it to length 1 you have to divide each component through the length of the whole..

result:

float div = 1.f/sqrtf(x*x+y*y+z*z);
x *= div;
y *= div;
z *= div;

or even faster you get some fast rsq function and have no div left:

float div = rsq(x*x+y*y+z*z);
x *= div;
y *= div;
z *= div;

rsq is reverse square root..
rsq x = x^-.5

the optimized funcion for this can be found on flipcode if you search for a thread called "arcus cosinus"


but don''t use macros anymore..

carmack wrote/writes good engines. but his code is not the best designed.. but thats live.. it has to work no mather if ugly or not

"take a look around" - limp bizkit
www.google.com

Share this post


Link to post
Share on other sites
TheMuuj    122
Okay, I did not see anyone mention WHY Carmack would choose macros over overloaded inline operators. Of course, the answer is quite simple: He codes in C, not C++. I suppose he could hvae used inline functions (I am not sure if inline was part of ANSI C), but there is nothing really wrong with using macros in C, since you have to use them for constants anyway. But in C++, you should try to avoid using macros.

--TheMuuj

Share this post


Link to post
Share on other sites
LilBudyWizer    491
Well, that seems to prove one can refute a statement without being insulting and impart some knowledge in the process. I stand corrected. Whatever you use for a scalar must have a multiplicative inverse except for zero. My mistake was thinking that whatever your vector was made out of was your scalar. Looking in my linear algebra book they still used reals when the vector was composed of 2 x 2 matrices. I was correct that you have a choice in what you use as a scalar, but I was wrong that the requirements don''t include the existance of a multiplicative inverse.

I find it somewhat funny that the original supposition was just that he did it as a matter of style rather than performance. I was wrong to say that you may not be able to do anything equivalent to division, but it is a property of the scalar that a multiplicative inverse exists. Seperating that makes it clearer. You will catch more errors at compile time if you do not define the division operator for your vector than if you do.

Share this post


Link to post
Share on other sites