Lookup Tables as a Code Optimization

First and foremost, you should generally push off optimizing code until the end and instead be thinking about a coherent and simple design during most of your coding. This approach will often allow you to avoid duplicating (or triplicating, quadrupling…) effort or allow you to bypass certain computations entirely. However, if at the end of the day you find you’ve done all this and you would still like to accelerate your program lookup tables are one thing to try. They boil down to, it can be faster to retrieve a value stored in memory than it is to compute the value. So if you need to compute a given function 10^5 times on the range [0-1] you might be able to compute the function at intervals of 1/10^3 and then use the nearest value stored in the table instead of computing every time. Of course you’re losing accuracy, but you gain speed, and if you are willing to tolerate this tiny bit of error you might do a lot better. You could also think about doing some sort of linear interpolation between values in the lookup table which will decrease your error significantly, but again at the cost of speed.

Here’s a little program that allows you to change the operation in only one place. You can also change the size of the lookup table and the number of computations (if you’re doing fewer than the number of entries in the table you’re always better computing directly).

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <vector>

using namespace::std;

double my_rand();
double my_operation(double input);
void init_sqrt_table(vector <int> & sqrt_table, double & step);

#ifdef FAST
  double my_sqrt(double input, vector <int> & sqrt_table, int & num_steps);
#else
  double my_sqrt(double input);
#endif

int main()
{
  time_t start,end;
  double execution_time, tmp, maxval;
  vector  sqrt_table(1000);
  double step = 0;
  int num_steps;
  time (&start);

#ifdef FAST
  init_sqrt_table(sqrt_table, step);
#endif

  srand (1);
  maxval = 0;
  num_steps = sqrt_table.size();
  for(int i = 0; i < num_steps*100000; i++)
  {
    tmp = my_rand();
#ifdef FAST
    tmp = my_sqrt(tmp, sqrt_table, num_steps); // gets it from a lookup table
#else
    tmp = my_sqrt(tmp); // just calls c sqrt
#endif

    if(maxval < tmp)
    {
      maxval = tmp;
    }
  }

  cout << maxval << endl;
  time (&end);
  execution_time = difftime (end,start);
  cout << "Program execution time: " << execution_time << endl;
  return 0;
}

double my_rand()
{
  return rand()*1.0/(RAND_MAX + 0.0);
}

void init_sqrt_table(vector <int> & sqrt_table, double & step)
{
  cout << "filling sqrt table" << endl;
  step = 1.0 / sqrt_table.size();
  for(int i = 0; i < sqrt_table.size(); ++i)
  {
    sqrt_table[i] = my_operation(i * step);
  }
}

#ifdef FAST
double my_sqrt(double input, vector <int> & sqrt_table, int & num_steps)
{
  return sqrt_table[rint(input*num_steps)];
}
#else
double my_sqrt(double input)
{
  return my_operation(input);
}
#endif

double my_operation(double input)
{
  return exp(sqrt(exp(input)));
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: