Стек Vs. Куча (8 стр) / Программирование / Форум / Флейм / GameDev.ru

Читать осторожно, это может быть корм для троллей.
Чтоб как-то занять массив, решил сначала записать в него прогрессию, а потом взять сумму. Данных не много, 256к, у кого кеш меньше - поправьте.

#include <stdlib.h>
#include <stdio.h>

#define DataCnt 65536

struct TData
{
  float a[DataCnt];
};

unsigned long long int Timer()
{
  union {
    unsigned long long int t12;
    struct {int t1,t2;};
  } temp;
  asm ("rdtsc" :"=a"(temp.t1),"=d"(temp.t2) );
  return(temp.t12);
}

unsigned long long int t;
struct TData *data;

void StartTimer()
{
  t=Timer();
}

void StopTimer(const char *s)
{
  unsigned long long int dt = Timer()-t;
  printf("%s %lld\n",s,dt);
}

float TestStack(float k)
{
  struct TData d;
  int i;
  float s;
  StartTimer();
  s=1.0;
  for (i=0; i<DataCnt; i++)
  {
    d.a[i]=s;
    s=s*k;
  }
  s=0.0;
  for (i=0; i<DataCnt; i++) s=s+d.a[i];
  StopTimer("stack");
  return(s);
}

float TestHeap(struct TData *d, float k)
{
  int i;
  float s;
  StartTimer();
  s=1.0;
  for (i=0; i<DataCnt; i++)
  {
    d->a[i]=s;
    s=s*k;
  }
  s=0.0;
  for (i=0; i<DataCnt; i++) s=s+d->a[i];
  StopTimer("heap ");
  return(s);
}

void main()
{
  data=malloc(sizeof(struct TData));
  TestStack(0.9); TestStack(0.9); TestStack(0.9);
  TestHeap(data,0.9); TestHeap(data,0.9); TestHeap(data,0.9);
  free(data);
}

Компилировал гнутым cc -O2 test.c, ниже один из вариантов запуска:

stack 9146038
stack 8755568
stack 8718442
heap  9048172
heap  8663116
heap  8662825

можно позапускать много раз, результаты, конечно, плавают.

Nomad
Постоялец

#108
6:10, 1 ноя 2010

Wtf am i reading?

Ты сделай чтобы указатели на указатели на указатели на данные были. И операции с такими данными, запись, чтение, потом что-то радикально другое сделай (процессор спустит твой хип из кеша), и опять вернись к исходной задаче.

Nomad
Постоялец

#109
6:11, 1 ноя 2010

А, и в следующий раз без говнокода, пожалуйста. Людям ещё читать. Форматируй по-человечески.

stopkin
Постоялец

#110
7:10, 1 ноя 2010

stopkin
Постоялец

#111
7:30, 1 ноя 2010

Вопрос людям: у кого какие идеи, почему куча оказалась на 1% быстрее стека? Асм одинаковый, с точностью до регистров. Вот, например, вырезка первых циклов из TestHeap и TestStack соответственно:

...
.L8:
  fsts  (%ecx,%eax,4)
  addl  $1, %eax
  cmpl  $65536, %eax
  fmul  %st(1), %st
  jne  .L8
...
.L15:
  fsts  (%edx,%eax,4)
  addl  $1, %eax
  cmpl  $65536, %eax
  fmul  %st(1), %st
  jne  .L15
...

Pushkoff
Удалён

#112
12:30, 1 ноя 2010

stopkin
> а вызвать 1 раз new - религия не позволяет?
а если у тебя 5 разных объектов с которыми нужно работать? и перекрестные ссылки в них?

stopkin
это не тест, это фейл...
можешь добавить префетч и получить еще большую производительность...

>:) а ведь кто-то до сих пор выделяет выделяет память по int-но, и читает файлы побайтно.
а для них ты открыл америку

Zefick
Постоялец

#113
12:45, 1 ноя 2010

Непонимаю, зачем такое шаманство с rdtsc, обычного clock() разве мало? Тесты надо проводить так, чтобы они не несколько наносекунд работали, а минимум по полсекунды, тогда любой таймер устроит и флуктуаций, связанных с работой системного планировщика потоков не будет.

stopkin
Постоялец

#114
16:33, 1 ноя 2010

Pushkoff
>добавить префетч
Префеч по-разному влияет на стек и кучу?

Zefick
>Непонимаю, зачем такое шаманство с rdtsc
:) А вот захотелось точно в граммах свесить и заинлайнить.
>Тесты надо проводить так, чтобы они не несколько наносекунд работали
Нанотехнологии же, но ты все равно прогнал на 6 порядков.

Чешете языком воздух, ребята. Никто не заметил, что разница между "еще не в кеше" и "уже в кеше" (одинаково, как для стека, так и для кучи) - всего ~5% при конструкции вида "операция-запись-чтение-операция". Увеличение операций только нивелирует разницу. Никто не посчитал такты на итерацию, что проц на таких объемах начинает попутно записывать модифицированный кеш в память. И, естественно, скорости в случаях "еще нет сброса в память" и "уже начался" отличаются на порядок. Хотя 256к - это маленькая часть L2, но сброс в оперативку уже идет. Вот так.

ashujon
Постоялец

#115
17:37, 1 ноя 2010

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

Pushkoff
Удалён

#116
18:20, 1 ноя 2010

stopkin
> Чешете языком воздух, ребята.
алгоритмы которые ты тестил идеальны для кеш оптимизаций, и они очень редки на практике...
возьми какой нибудь реальный алгоритм - типа полтыщи объектов (разных классов, унаследованных от единого интерфейса) по полкилобайта-килобайту, с ссылками на друг друга, виртуальными вызовами и непоследовательной обработкой (допустим дерево) ну и выложи результаты, мне допустим и самому интересно на них глянуть...

namot
Удалён

#117
20:49, 1 ноя 2010

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <sys/time.h>

#define LIST_LEN    (8*1024)

static unsigned long
get_usec()
{
  struct timeval    tv;

  gettimeofday(&tv, NULL);

  return tv.tv_usec + tv.tv_sec * 1000UL * 1000UL;
}

static int
prime_test(int val, int *tail, int len)
{
  int    prime = 1;

  while (len > 0) {
    if (!(val % *tail)) {
      prime = 0;
      break;
    }
    tail++;
    len--;
  }

  return prime;
}

static unsigned long
on_stack()
{
  int    list[LIST_LEN];
  unsigned long  t0, t1;
  int    len = 0;
  int    i;

  list[len++] = 2;

  t0 = get_usec();

  while (len < LIST_LEN) {
    for (i = list[len - 1] + 1; i < INT_MAX; ++i) {
      if (prime_test(i, list, len)) {
        list[len++] = i;
        break;
      }
    }
  }

  t1 = get_usec();

  /* */
  malloc(list[len - 1] * 19);

  return t1 - t0;
}

static unsigned long
on_heap()
{
  int    *list;
  unsigned long  t0, t1;
  int    len = 0;
  int    i;

  list = malloc(sizeof(int) * LIST_LEN);
  list[len++] = 2;

  t0 = get_usec();

  while (len < LIST_LEN) {
    for (i = list[len - 1] + 1; i < INT_MAX; ++i) {
      if (prime_test(i, list, len)) {
        list[len++] = i;
        break;
      }
    }
  }

  t1 = get_usec();

  /*free(list);*/
  malloc(list[len - 1] * 19);

  return t1 - t0;
}

int main(int argc, char *argv[])
{
  unsigned long  tv_stack;
  unsigned long  tv_heap;
  unsigned long  tval;
  int    i;

  tv_stack = on_stack();
  tv_heap = on_heap();

  for (i = 0; i < 16; ++i) {
    tval = on_stack();
    tv_stack = (tval < tv_stack) ? tval : tv_stack;
    tval = on_heap();
    tv_heap = (tval < tv_heap) ? tval : tv_heap;
  }

  for (i = 0; i < 16; ++i) {
    tval = on_stack();
    tv_stack = (tval < tv_stack) ? tval : tv_stack;
  }

  for (i = 0; i < 16; ++i) {
    tval = on_heap();
    tv_heap = (tval < tv_heap) ? tval : tv_heap;
  }

  printf("Stack result %lu usec \n", tv_stack);
  printf("Heap result %lu usec \n", tv_heap);

  return 0;
}

$ ./test 
Stack result 1074805 usec 
Heap result 1074712 usec

Зря потратил время на ещё один неудачный тест.

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

Pushkoff
Удалён

#118
21:43, 1 ноя 2010

> Зря потратил время на ещё один неудачный тест.
а зачем было терять время? доказательство ради доказательства?

stopkin
Постоялец

#119
22:26, 1 ноя 2010

Pushkoff
>типа полтыщи объектов
>мне допустим и самому интересно на них глянуть...
... критикуешь - предлагай, предлагаешь - делай ...

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