[Yafray-devel] Little Speed Optimization Patch

[Alex Klein]

Hi guys,
I've just started reading through the code and in order to understand it 
I thought I try to profile and optimize it. Here's a little patch to 
improve the performance a bit, about 7% on a small test scene I used. 
For now I just restricted myself to reorganizing the 
photonLight_t::illuminate(...) method. Here is what I did:

-added some const operators here and there (makes life easier for the 
compiler to optimize the code)
-moved some computations such that they are executed just before they 
are needed (lazy evaluation, better caching/optimization)
-set the vector to K elements at the beginning. This should completely 
avoids reallocations
-reduce number of vector push/pop operations used
-replaced sqrt call by a compile-time constant

In addition, there are a few const operators in other files to make 
optimization easier for the compiler.

The speed gain is not great, but hey, its free as the new version should 
(and does in my test case ... maybe someone should use another scene to 
test it just to be sure) produce the same results as the old one.


By the way, how far along is the refactorization? Does it make sense for 
me to read through the code, suggest some further improvements and start 
writing some doxygen comments in it? By the way, are you planning on 
using doxygen? There is a conf-file in the CVS but there are hardly any 
doxy-comments in the source...
Cheers

AlexK

P.S.: Hope the patch is in the right format, first time I've ever 
submitted a patch to an open source project... :)
Index: src/lights/photonlight.cc
===================================================================
RCS file: /cvsroot/yafray/yafray/src/lights/photonlight.cc,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 photonlight.cc
--- src/lights/photonlight.cc   22 Dec 2004 09:26:21 -0000      1.1.1.1
+++ src/lights/photonlight.cc   9 May 2005 18:40:18 -0000
@@ -246,87 +246,106 @@
        bool operator() (const point3d_t &p,const bound_t &b) {return 
b.includes(p);};
 };
 
+
 color_t photonLight_t::illuminate(renderState_t &state,const scene_t &s,const 
surfacePoint_t sp,
                                                                                
                                        const vector3d_t &eye)const
 {
-       color_t total(0.0);
-       if(!sp.getObject()->reciveRadiosity()) return total;
-       //photonQueue_t found;
-       vector<foundPhoton_t> found;
-       compareFound_f cfound;
-       foundPhoton_t temp;
-       vector3d_t N = FACE_FORWARD(sp.Ng(), sp.N(), eye),VX,VY;
-       if(mode==DIFFUSE) createCS(N,VX,VY);
+       if(!sp.getObject()->reciveRadiosity()) return color_t(0,0,0);
+
+       // Allocate an vector that will be used as a heap with
+       // space for K photons. We are looking for the closest K
+       // photons, so the exact size is known.
+       vector<foundPhoton_t> found(0);
+       found.reserve(K);
+       vector3d_t N = FACE_FORWARD(sp.Ng(), sp.N(), eye);
        gObjectIterator_t<photonMark_t *,point3d_t,pointCross_f> 
ite(tree,sp.P());
        for(;!ite;++ite)
        {
-               temp.dis=(sp.P()-(*ite)->position()).length();
-               if((temp.dis<=fixedRadius) && (((*ite)->direction()*N)>0.0))
+               // First check if the direction of the photon is appropriate
+               // for the current surface position. This is quite cheap, so
+               // do it before testing if the photon is in the search radius.
+               // However, this test is not only for early rejection but 
+               // also a required property for a gathered photon.
+               if (((*ite)->direction()*N)<=0.0)
+               {
+                       continue;
+               }
+               // Now check if the photon is so close that it should be put
+               // in the heap.
+               const PFLOAT dis = (sp.P()-(*ite)->position()).length();        
        
+               if (dis<=fixedRadius)
                {
-                       temp.p=*ite;
-
                        if(found.size()==K)
                        {
-                               //if(temp.dis<found.top().dis)
-                               if(temp.dis<found.front().dis)
+                               if(dis<found.front().dis)
                                {
-                                       found.push_back(temp);
-                                       
push_heap(found.begin(),found.end(),cfound);
-                                       
pop_heap(found.begin(),found.end(),cfound);
-                                       found.pop_back();
-                                               //found.push(temp);
-                                               //found.pop();
+                                       // Swap the most distant photon at the 
end.
+                                       pop_heap(found.begin(),found.end(), 
cfound);
+                                       // Override it with the current photon.
+                                       found.back().p = *ite;
+                                       found.back().dis = dis;
+                                       // Heap the new photon into the heap.
+                                       push_heap(found.begin(),found.end(), 
cfound);
                                }
                        }
                        else
                        {
+                               // Put the photon in the vector and heap it.
+                               foundPhoton_t temp;
+                               temp.p = *ite;
+                               temp.dis = dis;
                                found.push_back(temp);
-                               push_heap(found.begin(),found.end(),cfound);
-                               //found.push(temp);
+                               push_heap(found.begin(),found.end(), cfound);
                        }
                }
        }
-
        if(found.size()<2) return color_t(0,0,0);
-       PFLOAT area;
-       PFLOAT radius=found.front().dis;
-       //PFLOAT radius=found.top().dis;
-       PFLOAT minarea=4*M_PI/(PFLOAT)Np;
-       CFLOAT filter;
+
+       const PFLOAT radius=found.front().dis;
+       color_t total(0.0);
        const shader_t *sha= sp.getShader();
        vector<sample_t> samples(0);
-       if(mode==DIFFUSE) samples.reserve(found.size());
-       //while(!found.empty())
+       vector3d_t VX,VY;
+       if(mode==DIFFUSE)
+       {
+               createCS(N,VX,VY);
+               samples.reserve(found.size());
+       }
+
        for(vector<foundPhoton_t>::iterator i=found.begin();i!=found.end();++i)
        {
-               //const photonMark_t *p=found.top().p;
                const photonMark_t *p=i->p;
-               //PFLOAT dis=found.top().dis;
-               PFLOAT dis=i->dis;
-               filter=filterCone(dis,radius);
-               energy_t ene(p->direction(),p->color()*filter);
-               total=total+sha->fromLight(state,sp,ene,eye);
+               const PFLOAT dis=i->dis;
+               const CFLOAT filter=filterCone(dis,radius);
+               const energy_t ene(p->direction(),p->color()*filter);
+               total += sha->fromLight(state,sp,ene,eye);
                if(mode==DIFFUSE)
                {
-                       sample_t sample;
                        vector3d_t sub=p->position()-sp.P();
                        sub/=radius;
+                       sample_t sample;
                        sample.x=sub*VX;
                        sample.y=sub*VY;
                        sample.weight=(p->direction()*N)*filter*0.5;
                        samples.push_back(sample);
                }
-               //found.pop();
        }
-       area=M_PI*radius*radius;
-       const PFLOAT SQRT2=sqrt(2.0);
-       if(mode==DIFFUSE) area*=fillArea(samples,SQRT2);
-       
-       if(area<minarea) area=minarea;
-       CFLOAT factor=4*M_PI/((CFLOAT)Np*area);
-       total=total*factor;
+       PFLOAT area = M_PI*radius*radius;
+       if(mode==DIFFUSE)
+       {
+               const PFLOAT SQRT2=1.414213562373095;
+               area*=fillArea(samples,SQRT2);
+       }       
+       const PFLOAT minarea=4.0*M_PI/(PFLOAT)Np;
+       if(area<minarea)
+       {
+               area=minarea;
+       }
+       const CFLOAT factor=4.0*M_PI/((CFLOAT)Np*area);
+       total *= factor;
        return total;
 }
+
 
 void photonLight_t::preGathering()
 {
Index: src/lights/photonlight.h
===================================================================
RCS file: /cvsroot/yafray/yafray/src/lights/photonlight.h,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 photonlight.h
--- src/lights/photonlight.h    22 Dec 2004 09:26:21 -0000      1.1.1.1
+++ src/lights/photonlight.h    9 May 2005 18:40:18 -0000
@@ -117,7 +117,7 @@
        {
                return a.dis<b.dis;
        }
-};
+} cfound;
 
 
 /*
@@ -195,21 +195,21 @@
                renderState_t nullstate;
 };
 
-inline CFLOAT filterGauss(PFLOAT x,PFLOAT limit)
+inline CFLOAT filterGauss(const PFLOAT &x, const PFLOAT &limit)
 {
                if(limit==0) return 1.0;
-               PFLOAT filter=1.0-(x*x)/(limit*limit);
+               const PFLOAT filter=1.0-(x*x)/(limit*limit);
                return filter*filter*2.0;// 15/8
 }
 
-inline CFLOAT filterCone(PFLOAT x,PFLOAT limit)
+inline CFLOAT filterCone(const PFLOAT &x, const PFLOAT &limit)
 {
                if(limit==0) return 1.0;
-               PFLOAT filter=1.0-x/limit;
+               const PFLOAT filter=1.0-x/limit;
                return filter*2.0;
 }
 
-inline CFLOAT filterPara(PFLOAT x,PFLOAT limit)
+inline CFLOAT filterPara(const PFLOAT &x, const PFLOAT &limit)
 {
                if(limit==0) return 1.0;
                PFLOAT filter=x/limit;
Index: src/shaders/blendershader.cc
===================================================================
RCS file: /cvsroot/yafray/yafray/src/shaders/blendershader.cc,v
retrieving revision 1.3
diff -u -r1.3 blendershader.cc
--- src/shaders/blendershader.cc        20 Jan 2005 06:29:25 -0000      1.3
+++ src/shaders/blendershader.cc        9 May 2005 18:40:20 -0000
@@ -824,7 +824,7 @@
        vector3d_t edir=eye;
        edir.normalize();
        vector3d_t N = FACE_FORWARD(sp.Ng(),sp.N(), edir);
-       CFLOAT inte = N*energy.dir;
+       const CFLOAT inte = N*energy.dir;
        if (inte<0) return color_t(0.0);
 
        colorA_t col=scolor, spcol=speccol, refc(0.0), cm=mircol;
Index: src/yafraycore/triangle.h
===================================================================
RCS file: /cvsroot/yafray/yafray/src/yafraycore/triangle.h,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 triangle.h
--- src/yafraycore/triangle.h   22 Dec 2004 09:26:47 -0000      1.1.1.1
+++ src/yafraycore/triangle.h   9 May 2005 18:40:20 -0000
@@ -47,7 +47,8 @@
                bool Z_hit();
                bool hit(const point3d_t &from,const vector3d_t &ray)
                {
-                       vector3d_t va=(*a)-from,vb=(*b)-from,vc=(*c)-from,r;
+                       const vector3d_t va=(*a)-from,vb=(*b)-from,vc=(*c)-from;
+                       vector3d_t r;
                        if((ray*normal)<0) r=-ray;
                        else r=ray;
                        if( ((va^vb)*r)<0 ) return false;
Index: src/yafraycore/vector3d.h
===================================================================
RCS file: /cvsroot/yafray/yafray/src/yafraycore/vector3d.h,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 vector3d.h
--- src/yafraycore/vector3d.h   22 Dec 2004 09:26:49 -0000      1.1.1.1
+++ src/yafraycore/vector3d.h   9 May 2005 18:40:21 -0000
@@ -47,7 +47,7 @@
                        PFLOAT vl = x*x + y*y + z*z;
                        if (vl!=0.0) {
                                vl = sqrt(vl);
-                               PFLOAT d = 1.0/vl;
+                               const PFLOAT d = 1.0/vl;
                                x*=d; y*=d; z*=d;
                        }
                        return vl;
@@ -57,7 +57,7 @@
                {
                        PFLOAT vl = x*x + y*y + z*z;
                        if (vl!=0.0) {
-                               PFLOAT d = 1.0/sqrt(vl);
+                               const PFLOAT d = 1.0/sqrt(vl);
                                x*=d; y*=d; z*=d;
                        }
                        return vl;
@@ -212,7 +212,7 @@
 
 inline vector3d_t reflect(const vector3d_t &n,const vector3d_t &v)
 {
-       PFLOAT vn = v*n;
+       const PFLOAT vn = v*n;
        if (vn<0) return -v;
        return 2*vn*n - v;
 }
@@ -241,8 +241,9 @@
        }
        else
        {
-               PFLOAT d = N.y*N.y + N.x*N.x;
-               if (d!=0.0) d=1.0/sqrt(d);
+               // Note: The root cannot become zero if
+               // N.x==0 && N.y==0.
+               const PFLOAT d = 1.0/sqrt(N.y*N.y + N.x*N.x);
                u.set(N.y*d, -N.x*d, 0);
                v = N^u;
        }