|
 |
Skiba <abx### [at] babilon org> wrote:
> I wonder if there could be addition to documentation with some general rules
> of optimizations made by function's parser. For example - is it enough when I
> write just:
Well, the optimizer is subject to constant change and enhancements and the
documentation cannot keep up and optimization is an extremely complex topic
with a lot of research still going on.
1. One thing you can be sure is that it will optimize nearly all constant
expressions (this is called "constant folding". One of the few it doesn't
cover (yet) is i.e. "x/4/5", which it will leave as is, but could turn into
"x/20" which in turn could be turned into "x*0.05". It will, of course
already optimize "40/5/x" and turn it into "8/x". Right now it will also
optimize most math functions. I.e. it will turn "sin(3.14...)" into "0" and
so on. It will also optimize certain simple powers into sequences of
multiplications, i.e. "(x+y*z)^4 will be turned into "temp=(x+y*z)" and then
"temp=temp*temp" and "temp=temp*temp". Calls to functions other than those
with one argument or any user defined function will not be touched (yet).
2. Then it will (with beta 9/10) perform a few "algebraic simplifications",
that is it will turn "x + 0" into "x" and "x * 1" into "x". However, this
is far from complete and much more could be done.
3. Another thing it could do would be "reassociation", that is using
associativity, commutativity and distributivity to simplify a function.
This, together with the optimizations known as "common subexpression
eliminations" could improve speed by another factor of two for many
functions. However, one has to be aware that especially 2 and 3 but also 1
have some serious side effects. A "real" compiler would probably perform
none of these and most likely would not even have the option to perform
these because all these techniques only work really well with integers as
they assume a will specified precision.
To explain the problem, here an example (turned into C code) from S.
Muchnick's book "Advanced Compiler Design and Implementation" (p. 342):
for(eps = 1.0; eps + 1.0 > 1.0; eps = 0.5 * eps)
oldeps = eps;
If you change "eps + 1.0 > 1.0" to "eps > 0.0" you will find that for a
double precision 64-bit IEEE floating-point number the original will return
(according to him, I didn't test it but have no reason to question his
result) oldeps = 2.220446E-16 while the optimized form would return oldeps =
4.940656E-324. Obviously this is a bit different.
However, as POV-Ray supports only a limited accuracy (and the above gives
you a good idea how ""inaccurate"" floating-point math can be) this will
most likely not have any negative effects, but I really don't want to go too
far either. A very careful balance is needed, but would require a lot of
testing on lost of implementations (while all recent processors have a IEEE
mode, by default they usually use slightly different implementations).
> #macro P(F,G)
> function{ x + F*y + z^G }
> #end
>
> or should I write:
>
> #macro P(F,G)
> function{
> x
> #if (F!=0) + #if (F=1) y #else F*y #end #end
> + #if (G=0) 1#else #if( G=1) z #else z^G #end #end
> }
> #end
You are mistaking functions and macros here. F and G are declared
(implicitly) and thus will be substituted by their real value before the
parser even sees them. Thus they will be constants and all the above
applies.
> At this beta time I have unofficial debug stream to check. But what later ?
> Considering time of rendering and designing some general systems for
> isosurfaces it is important to make as big optimization as possible. Not
> everybody know C to verify function equation with source of optimizer.
You should always assume your function can be optimized by hand. The only
thing is guaranteed is that "explicit" subexpressions with all constants
(that is, when you put parenthesis around the constants and they form an
explicit subexpression) will be evaluated.
In particular you should *not* assume calls to any functions will be
optimized in every case. The optimization is a changing implementation
detail and assumptions or optimizations based on any given implementation
may be slower (or faster) in future implementations.
It is just like a sphere that is slightly scaled will be turned into an
ellipsoid by POV-Ray and thus render (marginally) slower.
> Also I wonder if there could be inline type of function (code of function is
> inlined at parsing time instead of calling at render time). So functions could
> be unrolled first, and then optimizations applied.
I have been thinking about this, but it sounds much easier than it is. Time
and other bug priorities permitting I may at least add the ability to detect
things like
foo1(a,b,c,d,e) { a + b * c - d / e}
foo2(a,b,d) { foo1(a,b,3,d,2) }
foo3(x,y,z) { foo2(x,y,z) }
and turn them into
foo3(x,y,z) { foo1(x,y,3,z,2) }
This would allow people to define a kind of "alias" to complex functions and
have something close to default arguments as the time to execute the
optimized form would be less due to to one less function call.
Unfortunately, even this very simple inlining takes time.
> Sorry, I know it is a feature request but I found this thread and this group
> best place to add this, when you feel some other group better, send answer
> there
Well, I understand that people have the desire to know how to make
isosurfaces go faster by changing the function. Unfortunately optimization
is no topic to explain in just a few paragraphs, and not a topic to explain
to people outside the domain of computer scenes with a serious interest in
optimisation.
The general advice for users is that operations which are simple when done
by hand are also simpler for the computer. I.e. most people can (on paper)
do an addition or subtraction faster than a multiplication or division. Let
alone calculating a sine or cosine with the help of a table. The same is
true for the computer.
Ah, one more note: People also have to think about problems in their
functions. I.e. the sin(x)^sin(x) crash is actually a simple (uncaught)
exception when x is zero because 0^0 is undefined. Testing for those
conditions takes some time as well and thus functions which have limited
domain will always be slower than those without limits.
Thorsten
____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
|
|
|
On Tue, 08 Jan 2002 16:55:36 +0100, "Thorsten Froehlich" <tho### [at] trfde>
wrote:
> 1. ...
> 2. ...
> 3. ...
> optimizations known as "common subexpression eliminations"
Thank You for this explanation.
> > #macro P(F,G)
> > function{
> > x
> > #if (F!=0) + #if (F=1) y #else F*y #end #end
> > + #if (G=0) 1#else #if( G=1) z #else z^G #end #end
> > }
> > #end
>
> You are mistaking functions and macros here.
No. I'm not. I play with functions very nice I think. You can check what is the
problem at http://news.povray.org/rlrb3ukjk8omaba2tfs8bjq8l411s5m7lr%404ax.com
> F and G are declared
> (implicitly) and thus will be substituted by their real value before the
> parser even sees them. Thus they will be constants and all the above
> applies.
That is exactly what I asked: "Should I expect this optimisations for ready
floats or not". Now I have comprehensive answer.
> > Also I wonder if there could be inline type of function
>
> I have been thinking about this, but it sounds much easier than it is.
Perhaps it could be enough to extend macros to passing and returning parts of
functions. For example if below code could be possible
#macro Test(a,b,c) 4*a+2*c-b #end
#local F=function{ Test(x,y,z) + Test(z,y,x) }
But it is definitly feature request so do it what you want with it.
I agree with all your other notes and thank You for them.
ABX
Post a reply to this message
|
|
