C: Быстрый доступ к поисковым таблицам?

Ответ 1

Иногда трудно понять, что замедляет работу, но потенциально вы можете испортить попадания в кеш, вы можете попробовать поискать структуру

typedef struct 
{
  float bx1_sin;
  float bx2_sin;
  float bx3_sin;
  float bx4_sin;
  float bx1_cos;
 etc etc
 including  sine1,2,3,4 as well

} lookup_table

тогда

lookup_table  lookup[800]

теперь все при поиске kth будет в том же небольшом куске памяти.

также, если вы используете макрос, который принимает k в качестве параметра для выполнения содержимого цикла, скажем, SINE_CALC(k), или встроенную функцию...

Вы можете сделать

for (k = 0; k < 800; ++k)
{
  SINE_CALC(k); k++;
  SINE_CALC(k); k++;
  SINE_CALC(k); k++;
  SINE_CALC(k); k++;
  SINE_CALC(k); k++;
}

если вы делаете макрос, убедитесь, что k++ находится вне вызова макроса, как показано

Ответ 2

Попробуйте развернуть свои циклы следующим образом:

for (k = 0; k < 800; ++k)
{       
    sine1[k] = a1_lookup[k];
    sine2[k] = a2_lookup[k];
    sine3[k] = a3_lookup[k];
    sine4[k] = a4_lookup[k];
}
for (k = 0; k < 800; ++k)
{       
    sine1[k] *= ((bx1_sin_lookup[k] * c1_cos) + (c1_sin * bx1_cos_lookup[k]));
    sine2[k] *= ((bx2_sin_lookup[k] * c2_cos) + (c2_sin * bx2_cos_lookup[k]));
    sine3[k] *= ((bx3_sin_lookup[k] * c3_cos) + (c3_sin * bx3_cos_lookup[k]));
    sine4[k] *= ((bx4_sin_lookup[k] * c4_cos) + (c4_sin * bx4_cos_lookup[k]));
}
for (k = 0; k < 800; ++k)
{       
    sine1[k] += d1_lookup[k];
    sine2[k] += d2_lookup[k] + 50;
    sine3[k] += d3_lookup[k];
    sine4[k] += d4_lookup[k] + 50;
}

Получив меньшее количество таблиц поиска в каждом цикле, вы сможете оставаться в кеше. Средний цикл также можно разделить, но вам нужно создать промежуточную таблицу для одного из подвыражений.

Ответ 3

Использование простой таблицы поиска sin приведет к увеличению скорости на 20% на моей Linux-машине (vm, gcc, 64 бит). Интересно, что размер таблицы поиска (в пределах разумных значений размера кэша < L1) не влияет на скорость выполнения.

Использование простой реализации fastsin отсюда Я получил улучшение на 45%.

код:

#include <math.h>
#include <stdio.h>
#include <stdint.h>
#include <sys/time.h>
#include <time.h>

#define LOOKUP_SIZE 628


uint64_t currentTimestampUs( void )
{
  struct timeval tv;
  time_t localTimeRet;
  uint64_t timestamp = 0;
  //time_t tzDiff = 0;
  struct tm when;
  int64_t localeOffset = 0;

  {
    localTimeRet = time(NULL);
    localtime_r ( &localTimeRet, &when );
    localeOffset = when.tm_gmtoff * 1000000ll;
  }

  gettimeofday ( &tv, NULL );
  timestamp = ((uint64_t)((tv.tv_sec) * 1000000ll) ) + ( (uint64_t)(tv.tv_usec) );
  timestamp+=localeOffset;

  return timestamp;
}


const double PI   = 3.141592653589793238462;
const double PI2  = 3.141592653589793238462 * 2;

static float sinarr[LOOKUP_SIZE];

void initSinArr() {
  int a =0;
  for (a=0; a<LOOKUP_SIZE; a++) {
    double arg = (1.0*a/LOOKUP_SIZE)*((double)PI * 0.5);
    float sinval_f = sin(arg); // double computation earlier to avoid losing precision on value
    sinarr[a] = sinval_f;
  }
}

float sinlookup(float val) {
  float normval = val;
  while (normval < 0) {
    normval += PI2;
  }
  while (normval > PI2) {
    normval -= PI2;
  }
  int index = LOOKUP_SIZE*(2*normval/PI);

  if (index > 3*LOOKUP_SIZE) {
    index = -index + 4*LOOKUP_SIZE;//LOOKUP_SIZE - (index-3*LOOKUP_SIZE);
    return -sinarr[index];
  } else if (index > 2*LOOKUP_SIZE) {
    index = index - 2*LOOKUP_SIZE;
    return -sinarr[index];
  } else if (index > LOOKUP_SIZE) {
    index = 2*LOOKUP_SIZE - index;
    return sinarr[index];
  } else {
    return sinarr[index];
  }
}


float sin_fast(float x) {
  while (x < -PI)
      x += PI2;

  while (x >  PI)
      x -= PI2;

  //compute sine
  if (x < 0)
      return 1.27323954 * x + .405284735 * x * x;
  else
      return 1.27323954 * x - 0.405284735 * x * x;

}

int main(void) {
  initSinArr();
  int a = 0;
  float val = 0;
  const int num_tries = 100000;

  uint64_t startLookup = currentTimestampUs();

  for (a=0; a<num_tries; a++) {
    for (val=0; val<PI2; val+=0.01) {
      float compval = sinlookup(val);
      (void)compval;
    }
  }

  uint64_t startSin = currentTimestampUs();

  for (a=0; a<num_tries; a++) {
    for (val=0; val<PI2; val+=0.01) {
      float compval = sin(val);
      (void)compval;
    }
  }

  uint64_t startFastSin = currentTimestampUs();

  for (a=0; a<num_tries; a++) {
    for (val=0; val<PI2; val+=0.01) {
      float compval = sin_fast(val);
      (void)compval;
    }
  }
  uint64_t end = currentTimestampUs();

  int64_t lookupMs = (startSin - startLookup)/1000;
  int64_t sinMs = (startFastSin - startSin)/1000;
  int64_t fastSinMs = (end - startFastSin)/1000;
  printf(" lookup: %lld ms\n", lookupMs );
  printf("    sin: %lld ms\n", sinMs );
  printf("   diff: %lld ms\n", sinMs-lookupMs);
  printf("  diff%: %lld %\n", 100*(sinMs-lookupMs)/sinMs);

  printf("fastsin: %lld ms\n", fastSinMs );
  printf("    sin: %lld ms\n", sinMs );
  printf("   diff: %lld ms\n", sinMs-fastSinMs);
  printf("  diff%: %lld %\n", 100*(sinMs-fastSinMs)/sinMs);
}

Пример результата:

 lookup: 2276 ms
    sin: 3004 ms
   diff: 728 ms
  diff%: 24 %
fastsin: 1500 ms
    sin: 3004 ms
   diff: 1504 ms
  diff%: 50 %

Ответ 4

Процессоры Intel могут прогнозировать последовательный доступ (и выполнять предварительную выборку) до 4-х массивов как для прямого, так и для обратного хода. По крайней мере, это было в дни Core 2 Duo. Разделите свой вариант на:

for (k = 0; k < 800; ++k)
    sine1[k] = a1_lookup[k] * ((bx1_sin_lookup[k] * c1_cos) + (c1_sin * bx1_cos_lookup[k])) + d1_lookup[k];
for (k = 0; k < 800; ++k)
    sine2[k] = a2_lookup[k] * ((bx2_sin_lookup[k] * c2_cos) + (c2_sin * bx2_cos_lookup[k])) + d2_lookup[k] + 50;
for (k = 0; k < 800; ++k)
    sine3[k] = a3_lookup[k] * ((bx3_sin_lookup[k] * c3_cos) + (c3_sin * bx3_cos_lookup[k])) + d3_lookup[k];
for (k = 0; k < 800; ++k)
    sine4[k] = a4_lookup[k] * ((bx4_sin_lookup[k] * c4_cos) + (c4_sin * bx4_cos_lookup[k])) + d4_lookup[k] + 50;

Я думаю, у вас больше нагрузки на кеш, чем в других тестах, так что это имеет значение. Я рекомендую вам не разворачивать циклы, компиляторы делают это хорошо.