LINUX.ORG.RU

[C] switch vs function pointer benchmark

 


0

1

s3r_rea@ararat:~/c/test1> gcc t.c -O3
s3r_rea@ararat:~/c/test1> ./a.out
LOX is testing...
G_i: 10029202
Time: 2974 ms.

FP array is testing...
 G_i: 20027413
Time: 3026 ms.

s3r_rea@ararat:~/c/test1> cat t.c
#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>
#include <time.h>

static int G_i=0;

typedef void (*cmd)();

void cmd1(){ G_i += 1; }
void cmd2(){ G_i -= 1; }
void cmd3(){ G_i += 2; }
void cmd4(){ G_i -= 2; }
void cmd5(){ G_i += 3; }
void cmd6(){ G_i -= 3; }
void cmd7(){ G_i += 4; }
void cmd8(){ G_i -= 4; }
void cmd9(){ G_i += 1; }

void cmd11(){ G_i += 1; }
void cmd12(){ G_i -= 1; }
void cmd13(){ G_i += 2; }
void cmd14(){ G_i -= 2; }
void cmd15(){ G_i += 3; }
void cmd16(){ G_i -= 3; }
void cmd17(){ G_i += 4; }
void cmd18(){ G_i -= 4; }
void cmd19(){ G_i += 1; }


static cmd  aCmd[] = {
&cmd1, &cmd2, &cmd3, &cmd4, &cmd5, &cmd6, &cmd7, &cmd8, &cmd9,
&cmd11, &cmd12, &cmd13, &cmd14, &cmd15, &cmd16, &cmd17, &cmd18, &cmd19
 };

void LOX(int i){
        switch(i){
    case 0: cmd1(); break;
    case 1: cmd2(); break;
    case 2: cmd3(); break;
    case 3: cmd4(); break;
    case 4: cmd5(); break;
    case 5: cmd6(); break;
    case 6: cmd7(); break;
    case 7: cmd8(); break;
    case 8: cmd9(); break;

    case 9: cmd11(); break;
    case 10: cmd12(); break;
    case 11: cmd13(); break;
    case 12: cmd14(); break;
    case 13: cmd15(); break;
    case 14: cmd16(); break;
    case 15: cmd17(); break;
    case 16: cmd18(); break;
    case 17: cmd19(); break;
    default: break;
        }
}

long long getMS(const struct timeval *start, const struct timeval *end){
  long long seconds, useconds;

  seconds  = end->tv_sec  - start->tv_sec;
  useconds = end->tv_usec - start->tv_usec;

  return ((seconds) * 1000 + useconds/1000.0) + 0.5;
}


int main(){
  struct timeval start, end;
  long long mtime;
  srand (time (NULL));
  int i, j, Max = 10000000;

  printf("LOX is testing...\n");
  gettimeofday(&start, NULL);
  for(i=0; i < Max; i++)
    for(j = 0; j < 9; j++)
       LOX(rand () % 18);
  gettimeofday(&end, NULL);
  printf("G_i: %d \n", G_i);
  printf("Time: %lld ms. \n\n",  getMS(&start, &end));


  printf("FP array is testing...\n ");
  gettimeofday(&start, NULL);
  for(i=0; i < Max; i++)
    for(j = 0; j < 9; j++)
      (*(aCmd + (rand () % 18)))();
  gettimeofday(&end, NULL);
  printf("G_i: %d \n", G_i);
  printf("Time: %lld ms. \n\n",  getMS(&start, &end));

  return 0;
}
s3r_rea@ararat:~/c/test1> ls
a.out  t.c
s3r_rea@ararat:~/c/test1>
 

Забавно, не правда ли?

у меня разница еще больше, а ответ прост - на switch компилятор легко может заинлайнить все что посчитает нужным, а потом это все еще скопом оптимизируется, что собс-но и используется в том же SQLite - где много функций представляют собой «простыни» из switch + case, и это все еще потом собирается из множества файлов в один, чтоб компилятор сразу оптимизировал весь код по SQLite

aho
()

М.б. вызов функции очень-медленная-операция? )

И -O3 нечестно. +когда функций станет больше, метод с указателями точно зарулит.

different_thing
()
Ответ на: комментарий от aho

Я подозреваю, что эти свичи как раз и конвертятся в код похожий на вариант с указателями на функцию при компиляции. И в ассемблере эти варианты уже как бы идентичны.

gandjubas
() автор топика
Ответ на: комментарий от gandjubas

> И в ассемблере эти варианты уже как бы идентичны.

у меня свитч выигрывает до 1.5 раза по времени, т.е. таки не идентичны

aho
()
Ответ на: комментарий от different_thing

Ха-ха как бы не так (дело в том, что умозрительное количество операций у свича уже превышает количество равное 2-м: смещение по массиву и взятие адреса). И что значит «нечестно»?

gandjubas
() автор топика
Ответ на: комментарий от gandjubas

> И что значит «нечестно»?

Да не, ничё. Тут ведь интересно, как компилятор будет оптимизировать, это я по глупости написал, да)

А чем собирал?

different_thing
()
Ответ на: комментарий от different_thing

gcc (GCC) 4.1.2 20070115 (SUSE Linux)
Copyright (C) 2006 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

gandjubas
() автор топика
Ответ на: комментарий от gandjubas

> эти свичи как раз и конвертятся в код похожий на вариант с указателями на функцию при компиляции.

таки да, только для switch таблица для jmp, а для варианта с процедурами для call

aho
()

> Забавно, не правда ли?

Различие в 2% на специально подобранном бенчмарке? Нет, не забавно. Смешно немного.

tailgunner ★★★★★
()
Ответ на: комментарий от gandjubas

> А как бы сделали вы?

А я бы не делал. Просто потому, что использование указателей на функции - это другой уровень гибкости по сравнению со switch, и другой сценарий использования.

А в остальном - ты просто замерял оверхед вызова по указателю, он составил 2%. Теперь представь (или замерь случай), когда у вызывемых функций нетривиальные тела.

tailgunner ★★★★★
()

А теперь попробуй сделать не так.

А, например, поиск функции по имени: для case у тебя будет нерасширяемый вариант с набором костыелй. Для указателей - хешмап или дерево и выиграть во времени поиска нужно функции.

kifer
()
Ответ на: комментарий от tailgunner
s3r_rea@ararat:~/c/test1> gcc t.c -O3
s3r_rea@ararat:~/c/test1> ./a.out
LOX is testing...
G_i: 427518280
Time: 3160 ms.

FP array is testing...
 G_i: 854991901
Time: 2984 ms.

s3r_rea@ararat:~/c/test1> cat t.c
#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>
#include <time.h>

static long long G_i=0;

typedef void (*cmd)();

void cmd1(){static int s = 0; G_i += (s % 2); s++; }
void cmd2(){static int s = 1; G_i += (s % 3); s++; }
void cmd3(){static int s = 2; G_i += (s % 4); s++; }
void cmd4(){static int s = 3; G_i += (s % 5); s++; }
void cmd5(){static int s = 4; G_i += (s % 6); s++; }
void cmd6(){static int s = 5; G_i += (s % 7); s++; }
void cmd7(){static int s = 6; G_i += (s % 8); s++; }
void cmd8(){static int s = 7; G_i += (s % 9); s++; }
void cmd9(){static int s = 8; G_i += (s % 10); s++; }

void cmd11(){static int s = 9; G_i += (s % 11); s++; }
void cmd12(){static int s = 10; G_i += (s % 12); s++; }
void cmd13(){static int s = 11; G_i += (s % 13); s++; }
void cmd14(){static int s = 12; G_i += (s % 14); s++; }
void cmd15(){static int s = 13; G_i += (s % 15); s++; }
void cmd16(){static int s = 14; G_i += (s % 16); s++; }
void cmd17(){static int s = 15; G_i += (s % 17); s++; }
void cmd18(){static int s = 16; G_i += (s % 18); s++; }
void cmd19(){static int s = 17; G_i += (s % 19); s++; }

static cmd  aCmd[] = {
&cmd1, &cmd2, &cmd3, &cmd4, &cmd5, &cmd6, &cmd7, &cmd8, &cmd9,
&cmd11, &cmd12, &cmd13, &cmd14, &cmd15, &cmd16, &cmd17, &cmd18, &cmd19
 };

void LOX(int i){
        switch(i){
    case 0: cmd1(); break;
    case 1: cmd2(); break;
    case 2: cmd3(); break;
    case 3: cmd4(); break;
    case 4: cmd5(); break;
    case 5: cmd6(); break;
    case 6: cmd7(); break;
    case 7: cmd8(); break;
    case 8: cmd9(); break;

    case 9: cmd11(); break;
    case 10: cmd12(); break;
    case 11: cmd13(); break;
    case 12: cmd14(); break;
    case 13: cmd15(); break;
    case 14: cmd16(); break;
    case 15: cmd17(); break;
    case 16: cmd18(); break;
    case 17: cmd19(); break;
    default: break;
        }
}

long long getMS(const struct timeval *start, const struct timeval *end){
  long long seconds, useconds;

  seconds  = end->tv_sec  - start->tv_sec;
  useconds = end->tv_usec - start->tv_usec;

  return ((seconds) * 1000 + useconds/1000.0) + 0.5;
}


int main(){
  struct timeval start, end;
  long long mtime;
  srand (time (NULL));
  int i, j, Max = 10000000;

  printf("LOX is testing...\n");
  gettimeofday(&start, NULL);
        for(i=0; i < Max; i++)
                for(j = 0; j < 9; j++)
                        LOX(rand () % 18);
  gettimeofday(&end, NULL);
  printf("G_i: %d \n", G_i);
  printf("Time: %lld ms. \n\n",  getMS(&start, &end));


  printf("FP array is testing...\n ");
  gettimeofday(&start, NULL);
  for(i=0; i < Max; i++)
    for(j = 0; j < 9; j++)
      (*(aCmd + (rand () % 18)))();
  gettimeofday(&end, NULL);
  printf("G_i: %d \n", G_i);
  printf("Time: %lld ms. \n\n",  getMS(&start, &end));

        return 0;
}
s3r_rea@ararat:~/c/test1>

Это ничуть не лучше не смотря на. У меня, признаться, ещё не прошёл шок от того, что свич может быть быстрее адресной арифметики.

А товарищ ахо вообще утверждает, что у него свич в 1,5 раза быстрее.

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

gandjubas
() автор топика
Ответ на: комментарий от gandjubas

2% не оправдывают столько писанины

тем более с O3

А товарищ ахо вообще утверждает, что у него свич в 1,5 раза быстрее.

А кто-то утверждает что цой и ленин жив.

kifer
()
Ответ на: комментарий от gandjubas

> А товарищ ахо вообще утверждает, что у него свич в 1,5 раза быстрее.

на последнем варианте уже практически одинаковое время, разве что на gcc-4.4 вариант switch на 100мс быстрее

aho
()
Ответ на: комментарий от aho

>для данного случае оно с O2 одинаково, по крайней мере у меня

Троллешь да? Речь о том что с gcc вообще нельзя тестировать с какими либо оптимизациями. Нередки случай когда после оптимизации корректные приложения вообще перестают работать.

kifer
()
Ответ на: комментарий от gandjubas

> Это ничуть не лучше не смотря на.

Несмотря на что? Или ты считаешь «G_i += (s % 8); s++;» нетривиальным телом?

У меня, признаться, ещё не прошёл шок от того, что свич может быть быстрее адресной арифметики.

Какой-какой арифметики?

tailgunner ★★★★★
()
alex@linux ~/Dev $ gcc -O3 t.c -o test; ./test
LOX is testing...
G_i: 9980668 
Time: 3552 ms. 

FP array is testing...
 G_i: 19965522 
Time: 3486 ms. 
gcc (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5
chinarulezzz ★★
()
Ответ на: комментарий от tailgunner

for(j = 0; j < 9; j++)
      (*(aCmd + (rand () % 18)))();

Это какая арифметика, по-вашему?

Несмотря на что? Или ты считаешь "G_i += (s % 8); s++;" нетривиальным телом?

Критикуешь - предлагай.

gandjubas
() автор топика

Во втором варианте 4762 LOX против 2551 (1.9 раз) на gcc 4.1.2

AMD Athlon X2 6600+, если чё. Разница не маленькая и в противоположную сторону. switch тормознее, что и ожидалось

different_thing
()
int main(){
    //...
    return 0;
}

В C99 это делать не нужно. Main сама вернёт нолик, если достигнет своего конца.

Obey-Kun ★★★★★
()
Ответ на: комментарий от gandjubas

>> (*(aCmd + (rand () % 18)))();

Это какая арифметика, по-вашему?

По-моему, это честный вызов функции. Ты сравниваешь его непонятно с чем - вероятно, с переходом по адресу.

Несмотря на что? Или ты считаешь «G_i += (s % 8); s++;» нетривиальным телом?

Критикуешь - предлагай.

Я предлагаю тебе понять, что с чем ты сравниваешь. Например, посмотреть на ассемблерный код.

tailgunner ★★★★★
()

gcc 4.5.2

Без оптимизации

LOX is testing...
G_i: 10029723 
Time: 6075 ms. 

FP array is testing...
 G_i: 20023494 
Time: 5652 ms.

Os

LOX is testing...
G_i: 10012315 
Time: 5764 ms. 

FP array is testing...
 G_i: 20021070 
Time: 5698 ms.

O1

LOX is testing...
G_i: 9961234 
Time: 5014 ms. 

FP array is testing...
 G_i: 19990611 
Time: 5142 ms. 

O2

LOX is testing...
G_i: 9989143 
Time: 4837 ms. 

FP array is testing...
 G_i: 19994622 
Time: 5333 ms. 

O3

LOX is testing...
G_i: 9964897 
Time: 4629 ms. 

FP array is testing...
 G_i: 19938452 
Time: 5045 ms.

Obey-Kun ★★★★★
()
Ответ на: комментарий от tailgunner

Это чтобы обмануть хитрый компилятор, который попытается(?) вычислить кого вызывать заранее. Раньше там был честный цикл по j.

А если вы посмотрите на значение Max и вспомните закон больших чисел, то ваше веселье поубавится.

gandjubas
() автор топика

Такая тема уже когда-то поднималась, не?

yoghurt ★★★★★
()
Ответ на: комментарий от gandjubas

> Это ничуть не лучше не смотря на. У меня, признаться, ещё не прошёл шок от того, что свич может быть быстрее адресной арифметики.

gcc -S

vasily_pupkin ★★★★★
()
Ответ на: комментарий от Obey-Kun

ЧИТД, показательно, что амозглики проведут тест с оптимизайцией, а потом раздувают целый тред из ничего, точнее из своей глупости.

kifer
()
Ответ на: комментарий от kifer

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

обычно наоборот. Хотя в gcc глюков хватает.

true_admin ★★★★★
()
Ответ на: комментарий от true_admin

в смысле если после оптимизации приложение упало то это проблема приложения в большинстве случаев.

true_admin ★★★★★
()

тест не совсем корректный. надо srand дергать перед каждым циклом с одним и тем же seed'ом, а еще лучше написать свой rand, чтобы можно было потестить на разных компиляторах

Reset ★★★★★
()
Ответ на: комментарий от Reset

С точки зрения алгебры - да, а с точки зрения мат. статистики - нет.

s3r_rea@ararat:~/c/test1> gcc t.c -O3
s3r_rea@ararat:~/c/test1> ./a.out
LOX is testing...
G_i: 427555068
Time: 3015 ms.

FP array is testing...
 G_i: 855110153
Time: 2946 ms.

s3r_rea@ararat:~/c/test1> cat t.c
#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>
#include <time.h>

static long long G_i=0;

typedef void (*cmd)();

void cmd1(){static int s = 0; G_i += (s % 2); s++; }
void cmd2(){static int s = 1; G_i += (s % 3); s++; }
void cmd3(){static int s = 2; G_i += (s % 4); s++; }
void cmd4(){static int s = 3; G_i += (s % 5); s++; }
void cmd5(){static int s = 4; G_i += (s % 6); s++; }
void cmd6(){static int s = 5; G_i += (s % 7); s++; }
void cmd7(){static int s = 6; G_i += (s % 8); s++; }
void cmd8(){static int s = 7; G_i += (s % 9); s++; }
void cmd9(){static int s = 8; G_i += (s % 10); s++; }

void cmd11(){static int s = 9; G_i += (s % 11); s++; }
void cmd12(){static int s = 10; G_i += (s % 12); s++; }
void cmd13(){static int s = 11; G_i += (s % 13); s++; }
void cmd14(){static int s = 12; G_i += (s % 14); s++; }
void cmd15(){static int s = 13; G_i += (s % 15); s++; }
void cmd16(){static int s = 14; G_i += (s % 16); s++; }
void cmd17(){static int s = 15; G_i += (s % 17); s++; }
void cmd18(){static int s = 16; G_i += (s % 18); s++; }
void cmd19(){static int s = 17; G_i += (s % 19); s++; }

static cmd  aCmd[] = {
&cmd1, &cmd2, &cmd3, &cmd4, &cmd5, &cmd6, &cmd7, &cmd8, &cmd9,
&cmd11, &cmd12, &cmd13, &cmd14, &cmd15, &cmd16, &cmd17, &cmd18, &cmd19
 };

void LOX(int i){
        switch(i){
    case 0: cmd1(); break;
    case 1: cmd2(); break;
    case 2: cmd3(); break;
    case 3: cmd4(); break;
    case 4: cmd5(); break;
    case 5: cmd6(); break;
    case 6: cmd7(); break;
    case 7: cmd8(); break;
    case 8: cmd9(); break;

    case 9: cmd11(); break;
    case 10: cmd12(); break;
    case 11: cmd13(); break;
    case 12: cmd14(); break;
    case 13: cmd15(); break;
    case 14: cmd16(); break;
    case 15: cmd17(); break;
    case 16: cmd18(); break;
    case 17: cmd19(); break;
    default: break;
        }
}

long long getMS(const struct timeval *start, const struct timeval *end){
  long long seconds, useconds;

  seconds  = end->tv_sec  - start->tv_sec;
  useconds = end->tv_usec - start->tv_usec;

  return ((seconds) * 1000 + useconds/1000.0) + 0.5;
}


int main(){
  struct timeval start, end;
  long long mtime;
  time_t seed = time (NULL);
  int i, j, Max = 10000000;

  srand (seed);

  printf("LOX is testing...\n");
  gettimeofday(&start, NULL);
        for(i=0; i < Max; i++)
                for(j = 0; j < 9; j++)
                        LOX(rand () % 18);
  gettimeofday(&end, NULL);
  printf("G_i: %d \n", G_i);
  printf("Time: %lld ms. \n\n",  getMS(&start, &end));

  srand (seed);

  printf("FP array is testing...\n ");
  gettimeofday(&start, NULL);
  for(i=0; i < Max; i++)
    for(j = 0; j < 9; j++)
      (*(aCmd + (rand () % 18)))();
  gettimeofday(&end, NULL);
  printf("G_i: %d \n", G_i);
  printf("Time: %lld ms. \n\n",  getMS(&start, &end));

  return 0;
}
s3r_rea@ararat:~/c/test1>

Результат по смыслу данного теста до «корректировки» и после - абсолютно одинаковый.

gandjubas
() автор топика
Ответ на: Слово _КОРРЕКТНЫЕ_ от kifer

надо было ешще сильнее выделить?

покажи мне конструкцию которая корректна с точки зрения C, но оптимизатор её превращает в некорректную.

true_admin ★★★★★
()
Ответ на: комментарий от true_admin

Если ты решил позанудствовать, то получи взад свое занудство, корректная - любая которую съедает компилятор без предупреждений и ошибок.

kifer
()
Ответ на: комментарий от kifer

он «намекает», что простого примера ты не напишешь, а в сложном - скорее всего была твоя лажа, а не компилятора

aho
()
Ответ на: комментарий от kifer

и чо? У меня система на генте была собрана, приложений для которых нужны были костыли типа понижения оптимизации было очень мало. А из тех что были половина кривая внутри.

GCC в целом работает нормально, большинство «проблем с оптимизацией» это кривые руки прогеров. Большинство прог в дистре собрано с -O2 и нормально пашут. Если что не работает то welcome to bugs.gcc.org

true_admin ★★★★★
()
Ответ на: комментарий от true_admin

>GCC в целом работает нормально, большинство «проблем с оптимизацией» это кривые руки прогеров

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

kifer
()
Ответ на: комментарий от kifer

Если посмотреть выше то там видно в моём посте что я писал про баги.

Разница в том что я знаю про то что делает -O2 и какой код ломает а ты нет.

true_admin ★★★★★
()
Ответ на: комментарий от kifer

Мне не надо ничего признавать, я знаю как обстоят дела на самом деле, я с ним работал. Просто тебе нравится кричать о том «какое gcc глючное г» а я из этого вырос.

true_admin ★★★★★
()
Ответ на: комментарий от true_admin

А ведь ты, таки, признал это.

И еще ты выложил свой аргумент на стол и призываешь меня померятся понтами. Но речь не об этом, спрячь свои аргументы в штаны и перечитай топик, речь о _тестах_, а не о тебе, милок.

kifer
()
Ответ на: А ведь ты, таки, признал это. от kifer

Да-да, возвращаясь к тестам. Выдвигаю на перл дня фразу «gcc нельзя тестировать с оптимизациями». Ещё что-нить в этом духе у тебя есть? Расскажи нам про то что «gcc нельзя тестировать с -fomit-frame-pointer» или про какие ты там флаги знаешь.

true_admin ★★★★★
()
Ответ на: комментарий от true_admin

Ура, ты осилил вспомнить тему топика, теперь осиль вспомнить что про твое больное место - gcc я ничего не говорил, а говорил я про оптимизации, и спрячь свои аргументы второй раз.

kifer
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.