   interpolator optimization
  I have a template class, which handles interpolation based on time-value pairs. It is primarily used by particles to evaluate speed, size, color, etc... over particle life.Class data is being edited via a GUI editor ("curve editor") and then saved. At "build" time it is also checked if all points fall within some threshold, and if true, ConstVal is calculated and marked via Attr (bitmask flag). Maxpoints is commonly 16 with count being atleast 4. Class is generally used with floats and vectors.template <class T, int maxpoints> class TGraphInterpolator {public:   //   enum EAttr { // Mode aLinear = MBit( 0 ), aSmooth = MBit( 1 ), aStep   = MBit( 2 ), // State aAllowNegative    = MBit( 5 ), aConstant    = MBit( 6 ),   };   public:   int   aTime[maxpoints];   TaValue[maxpoints];   TConstVal;   //   char  hermitetension;   char  hermitebias;   TAttribute8Attr;   byte  count;};template <class T, int maxpoints> xinline T TestEvaluate(int timeus, const TGraphInterpolator<T,maxpoints> &eval){   if( eval.Attr.is( TGraphInterpolator<T,maxpoints>::aConstant ) ) return eval.ConstVal;   //   if( timeus < eval.aTime[0] ) return eval.aValue[0];   if( timeus > eval.aTime[eval.count - 1] ) return eval.aValue[eval.count - 1];   //   int i1 = 0;   for(int a = 0; a < eval.count; a++)   { if( eval.aTime[a] > timeus )    break; i1 = a;   }   //   float tl = (float)( timeus - eval.aTime[i1] ) / (float)( eval.aTime[i1 + 1] - eval.aTime[i1] );   T value = 0;   //   if( eval.Attr.is( TGraphInterpolator<T,maxpoints>::aSmooth ) )   { int i0 = max( i1 - 1, 0 ); int i2 = i1 + 1; int i3 = min( i1 + 2, eval.count - 1 ); // const float oo127 = 1.0f / 127.0f; // float tension  = (float)eval.hermitetension * oo127; float bias= (float)eval.hermitebias    * oo127; // value = HermiteInterpolate( eval.aValue[i0], eval.aValue[i1], eval.aValue[i2], eval.aValue[i3], tl, tension, bias );   }   else   { if( eval.Attr.is( TGraphInterpolator<T,maxpoints>::aStep ) ) {    value = eval.aValue[i1];  } else {    T v1  = eval.aValue[i1];T v2  = eval.aValue[i1 + 1];    value = v1 + (v2 - v1) * tl; }   }   //   if( !eval.Attr.is( TGraphInterpolator<T,maxpoints>::aAllowNegative ) ) value = clamp( value, (T)0, value );   //   return value;}basic runtime flow is:- early outs:-- return if constant-- return if under/over range, return min, max value- find between which points we fit- branch based on type-- perform interpolation (smooth, linear, step)- clamp if neededHermiteInterpolation is not a problem at this stage, since it is barely used, linear is the most common usage.Before going to platform specifics (targets are Win/x86, PS3, Xbox360) are there any obvious algorithmic fubars i missed? Any other tips (intrinsic, branches)?   
  1. you could make the interpolation method a template argument. Would allow you to pass in step / hermite / linear as an argument instead of if statements. 2. use intrinsics.inline __m128 lerp4(__m128 a, __m128 b, __m128 t){  return _mm_add_ps(_mm_mul_ps(t, _mm_sub_ps(b,a)), a);}3. get rid of the templates completely. interpolation doesn't work too well with integers, so everything is likely to be cast to a float before being computed anyway. You might as well accept that fact and just provide optmisied versions for float/double and be done with it. In fact, if you were to provide a method for float array / double array, then you'd cover all bases for Vector3 / Colour etc (without the need to generate pointless template specialisations)   ;  Can Attr change during run-time?Quote:Maxpoints is commonly 16Can it be more?   ;Quote:Original post by AntheusCan Attr change during run-time?Quote:Maxpoints is commonly 16Can it be more?nope, Attr will not change during rt, while maxpoints can be more, but it will probably stay at 16, seems to be enough for current particles.   ;Quote:Original post by RobTheBloke1. you could make the interpolation method a template argument. Would allow you to pass in step / hermite / linear as an argument instead of if statements. 2. use intrinsics.*** Source Snippet Removed ***3. get rid of the templates completely. interpolation doesn't work too well with integers, so everything is likely to be cast to a float before being computed anyway. You might as well accept that fact and just provide optmisied versions for float/double and be done with it. In fact, if you were to provide a method for float array / double array, then you'd cover all bases for Vector3 / Colour etc (without the need to generate pointless template specialisations)1. good point2. yep, next step3. initial idea was to skip float compares as much as possible. you are probably right, it would be best to just use optimized code for floats, since template arguments are float1 and float3.   ;  Optimizing single function call is pointless, so the following assumes there is an array of lots of particles.First, pre-sort the array based on Attr. Have two arrays:Particle p[...];int types[6];Types contains subranges for individual values of Attr. If aLinear are the first 7, then types[0] = 7.Next, rather than returning a value, have second array which stores the results.To process, one ends up with 7 different for loops, each of which can be ran in parallel.for (int i = 0; i < types[0]; i++) { if( timeus < eval.aTime[0] ) { results = eval.aValue[0]; continue; } if( timeus > eval.aTime[eval.count - 1] ) results = eval.aValue[eval.count - 1]; ...  T v1  = eval.aValue[i1];   T v2  = eval.aValue[i1 + 1];  result = v1 + (v2 - v1) * tl;}And so on, for each type, the aConstant doesn't need to be processed.Similar approach can be applied to other if statements, meaning that the core of such system becomes just one big branchless for loop. Which makes it ideal for SIMD.;Quote:Original post by AntheusOptimizing single function call is pointless, so the following assumes there is an array of lots of particles....well, there is. particleeffect class has a pool of particles (max 512), and a pool of emitters (max 16). each emitter then keeps an array of indices (max 128) to particles. effectupdate calls emitterupdate which in turn calls particleupdate, which first calculates new particle life, and then performs all evaluation (size, speed, spin, force1, force2, alpha, color). after that all particle calculations are performed.   ;  If you're moving forward in time, i1 will never decrease between calls to TestEvaluate. Add int i1 to your TGraphInterpolator, initialized to 0. Change your loop which calculates it to while(eval.aTime[i1] > timeus) i1++;.   ;Quote:Original post by SneftelIf you're moving forward in time, i1 will never decrease between calls to TestEvaluate. Add int i1 to your TGraphInterpolator, initialized to 0. Change your loop which calculates it to while(eval.aTime[i1] > timeus) i1++;.i like the idea, but i'm not sure i can make it, since TGraphInterpolator objects are stored in particledata objects (one TGraphInterpolator is used for multiple particle instances) and are hence const. I could add the index on particle instance object, but i would have to do this for each evaluator, which would add up to at least 8-10 bytes :O   ;Quote:Original post by marc0reparticleeffect class has a pool of particles (max 512), and a pool of emitters (max 16). each emitter then keeps an array of indices (max 128) to particlesIt sounds like you could get hammered by cache misses here because those indices could jump all over the particle pool. Since memory reading is often a bottleneck, I'd optimize for that first.For example, unless the emitters have a very variable number of live particles you should be able to allocate a fixed size block of particles for each one. That will also make SIMD processing easier.   