LINUX.ORG.RU

[C] Полиморфные тормоза

 


0

0

Есть абстрактный тип:

typedef int (*FruitID)(Fruit);
 
typedef struct _Fruit {
    int type;
    FruitID id;
} *Fruit;
и его реализация:
typedef struct _Apple {
    struct _Fruit base;
} *Apple;
 
int apple_id(Apple a)
{
    return 1;
}
 
Apple apple_new(void)
{
    Apple a = (Apple)malloc(sizeof(struct _Apple));
    a->base.type = 1;
    a->base.id = (FruitID)apple_id;
    return a;
}
Теперь добираюсь до поля объекта абстрактного типа двумя методами - «честный» полиморфизм и кондовый switch:
int fruit_id_virt(Fruit f)
{
    return f->id(f);
}
 
int fruit_id_nonvirt(Fruit f)
{
    switch(f->type) {
        case 1:
            return apple_id((Apple)f);
        case 2:
            return orange_id((Orange)f);
    }
    return 0;
}
и провожу замеры времени:
Fruit a = (Fruit)apple_new();
Fruit o = (Fruit)orange_new();
for(i = 0; i != 0xFFFFFFF; ++i)
#ifdef VIRT
  sum += fruit_id_virt(a) + fruit_id_virt(o);
#else
  sum += fruit_id_nonvirt(a) + fruit_id_nonvirt(o);
#endif
с помощью time(1). Грубо, конечно, но результат очевиден:

с fruit_id_virt: 0m9.644s

c fruit_id_nonvirt: 0m4.849s

ЧЯДНТ, отчего такое падение скорости? Как вызов по указателю может быть медленнее цепочки сравнений? Я уже хотел немного избавиться от if/switch в своем коде (как-то и эстетичнее оно), а тут такое...

★★★★
Ответ на: комментарий от fa652897

А я не сказал? Забыл значит. Всё равно невиртуальная быстрее. Время:

(3.493+3.514+3.539)/(2.174+2.172+2.186)
1.61451316595223515003

Нужно что-то более сложное, чем выяснение id, иначе в виртуальности нет смысла

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

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

В C++ это будет особенно оригинально :(

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

Возможно, ваш процессор не умеет спекулировать по коду (то есть спекулятивно декодировать/выполнять тело функции apple_id _до_ того, как адрес функции будет считан из памяти через AX)

Слабо представляю, как можно узнать адрес функции до того, как он считан из памяти. Разве что какое-то хитрое кэширование (поскольку у нас цикл) этого адреса. Ну и конечно не хотелось бы зависеть от процессора.

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

В c++ возможно есть спецотимизации для такого. А для си они могут быть почему-либо отключены.

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

switch выигрывает у виртуальных функций только лишь за счёт отсутствия вызова (inline) этих самых функций в switch

#include <iostream>
#include <cstdlib>
#include <time.h>
#include <inttypes.h>

using namespace std;

double diff_milli(timespec end, timespec start)
{
	return ((end.tv_sec-start.tv_sec) * 1e9 + (end.tv_nsec-start.tv_nsec)) * 1e-6;
}

struct A { int Type; };
struct B { int (*Func)(); };

const int MAX=3;
A t[MAX];
B f[MAX];

__attribute__((noinline)) int f0_no_inline() { volatile int a = 10; return a; }
__attribute__((noinline)) int f1_no_inline() { volatile int a = 20; return a; }
__attribute__((noinline)) int f2_no_inline() { volatile int a = 30; return a; }

__attribute__((always_inline)) int f0_inline () { volatile int a = 10; return a; }
__attribute__((always_inline)) int f1_inline() { volatile int a = 20; return a; }
__attribute__((always_inline)) int f2_inline() { volatile int a = 30; return a; }

int switch_no_inline(int type)
{
	switch(type)
	{
		case 0: return f0_no_inline();
		case 1: return f1_no_inline();
		case 2: return f2_no_inline();
	}
	exit(1);
}
int switch_inline(int type)
{
	switch(type)
	{
		case 0: return f0_inline();
		case 1: return f1_inline();
		case 2: return f2_inline();
	}
	exit(1);
}
void Init()
{	
	t[0].Type = 0;
	t[1].Type = 1;
	t[2].Type = 2;
	f[0].Func = f0_no_inline;
	f[1].Func = f1_no_inline;
	f[2].Func = f2_no_inline;
}

void Run(int Max, A* t, B* f)
{
	timespec t_start, t_end;
	uint64_t sum;

	clock_gettime(CLOCK_REALTIME, &t_start);
	sum = 0;
	for (uint64_t i = 0; i < 0xFFFFFFF; ++i)
	{
		for(int o = 0; o < Max; ++o)
		{
			sum += switch_inline(t[o].Type);
		}
	}
	clock_gettime(CLOCK_REALTIME, &t_end);
	cout << "switch inline: sum = " << sum;
	cout << " time = " << diff_milli(t_end, t_start)  << endl;

	clock_gettime(CLOCK_REALTIME, &t_start);
	sum = 0;
	for (uint64_t i = 0; i < 0xFFFFFFF; ++i)
	{
		for(int o = 0; o < Max; ++o)
		{
			sum += switch_no_inline(t[o].Type);
		}
	}
	clock_gettime(CLOCK_REALTIME, &t_end);
	cout << "switch no inline: sum = " << sum;
	cout << " time = " << diff_milli(t_end, t_start)  << endl;

	clock_gettime(CLOCK_REALTIME, &t_start);
	sum = 0;
	for (uint64_t  i = 0; i < 0xFFFFFFF; ++i)
	{
		for(int o = 0; o < Max; ++o)
		{
			sum += f[o].Func();
		}
	}
	clock_gettime(CLOCK_REALTIME, &t_end);
	cout << "virt: sum = " << sum;
	cout << " time = " << diff_milli(t_end, t_start)  << endl;
}

int main()
{
	Init();
	Run(MAX, t, f);
	return 0;
}
switch inline: sum = 16106127300 time = 1010.66
switch no inline: sum = 16106127300 time = 3027.6
virt: sum = 16106127300 time = 1792.34

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

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

Запомнить, каким он был в прошлый раз.

Ну и конечно не хотелось бы зависеть от процессора.


Так не бывает.

Manhunt ★★★★★
()

<trollmode> Как только люди не извращаются, лишбы не использовать С++ </trollmode>

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

Спасибо, интересно. Моя вера в кроссплатформенность C подорвана :(

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

Из-за кеша нихрена не понятно

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

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

double diff_milli(struct timespec end, struct timespec start) 
{ 
   return ((end.tv_sec-start.tv_sec) * 1e9 + (end.tv_nsec-start.tv_nsec)) * 1e-6; 
} 

typedef struct _Fruit *Fruit; 
 
/********* Base Fruit *********/ 
 
typedef int (*FruitID)(Fruit); 
 
struct _Fruit { 
   int type; 
   FruitID id; 
}; 
 
int fruit_id_virt(Fruit f) 
{ 
   return f->id(f); 
}
 
#define DEF_FRUIT(name,fr_id) \
struct _##name { struct _Fruit base; }; \
int name##_id(struct _##name * o) { return sizeof(#name #fr_id)+o->base.type; } \
struct _##name * name##_new(void) \
{ \
   struct _##name * o = (struct _##name *)malloc(sizeof(struct _##name)); \
   o->base.type = (fr_id); \
   o->base.id = (FruitID)name##_id; \
   return o; \
} \
void name##_delete(struct _##name * a) { free(a); } 

DEF_FRUIT(Apple,123)
DEF_FRUIT(Orange,261)
DEF_FRUIT(Repa,399)
DEF_FRUIT(Arbue,487)
DEF_FRUIT(Coco,583)
DEF_FRUIT(Banana,643)
DEF_FRUIT(Tomato,782)
DEF_FRUIT(Shaverma,813)
DEF_FRUIT(fru9,992)
DEF_FRUIT(fru10,1013)
DEF_FRUIT(fru11,1182)
DEF_FRUIT(fru12,1254)
DEF_FRUIT(fru13,1374)
DEF_FRUIT(fru14,1422)
DEF_FRUIT(fru15,1516)
DEF_FRUIT(fru16,1687)
#undef DEF_FRUIT
int fruit_id_nonvirt(Fruit f) 
{ 
   switch(f->type) { 
      case 123: 
         return Apple_id((struct _Apple *)f); 
      case 261: 
         return Orange_id((struct _Orange *)f); 
      case 399: 
         return Repa_id((struct _Repa *)f); 
      case 487: 
         return Arbue_id((struct _Arbue *)f); 
      case 583: 
         return Coco_id((struct _Coco *)f); 
      case 643: 
         return Banana_id((struct _Banana *)f); 
      case 782: 
         return Tomato_id((struct _Tomato *)f); 
      case 813: 
         return Shaverma_id((struct _Shaverma *)f); 
      case 992: 
         return fru9_id((struct _fru9 *)f); 
      case 1013: 
         return fru10_id((struct _fru10 *)f); 
      case 1182: 
         return fru11_id((struct _fru11 *)f); 
      case 1254: 
         return fru12_id((struct _fru12 *)f); 
      case 1374: 
         return fru13_id((struct _fru13 *)f); 
      case 1422: 
         return fru14_id((struct _fru14 *)f); 
      case 1516: 
         return fru15_id((struct _fru15 *)f); 
      case 1687: 
         return fru16_id((struct _fru16 *)f); 
   } 
   return 0; 
} 
#define MK_FRUIT(x) { (void * (*)())x##_new, (void (*)(void*))x##_delete }
struct {
void * (*ctor)();
void (*dtor)(void*);
} fruitfabric[] = {
MK_FRUIT(Apple),
MK_FRUIT(Orange),
MK_FRUIT(Repa),
MK_FRUIT(Arbue),
MK_FRUIT(Coco),
MK_FRUIT(Banana),
MK_FRUIT(Tomato),
MK_FRUIT(Shaverma),
MK_FRUIT(fru9),
MK_FRUIT(fru10),
MK_FRUIT(fru11),
MK_FRUIT(fru12),
MK_FRUIT(fru13),
MK_FRUIT(fru14),
MK_FRUIT(fru15),
MK_FRUIT(fru16),
};
#undef MK_FRUIT

#define LEN(x) (sizeof(x)/sizeof(x[0]))
//#define HASH(i,max) (i % max) //fruit_id_nonvirt быстрее чем fruit_id_virt в 1.6 раз 
#define HASH(i,max) (i%2 ? 0 : (i/2 % max)) //fruit_id_nonvirt чуточку быстрее чем fruit_id_virt
//#define HASH(i,max) ((size_t)(((float)random()/RAND_MAX)*max)) //fruit_id_nonvirt медленнее чем fruit_id_virt в 1.3 раза 

#define SRAND_SEED 1
int main() 
{ 
   Fruit fruits[(1u << COUNT)];
   unsigned i,j; 
   unsigned long sum = 0; 
   srand(SRAND_SEED);
   for(i = 0; i != LEN(fruits); ++i) 
   {
        fruits[i] = (Fruit)fruitfabric[ HASH(i, LEN(fruitfabric)) ].ctor();
   }
   struct timespec t_start, t_end; 
   clock_gettime(CLOCK_REALTIME, &t_start);
   for(j = 0; j != 0xFFFFFFF/LEN(fruits); ++j)
   {
      for(i = 0; i != LEN(fruits); ++i) 
      {
#ifdef VIRT 
         sum += fruit_id_virt(fruits[i]); 
#else 
         sum += fruit_id_nonvirt(fruits[i]); 
#endif 
      }
   }
   clock_gettime(CLOCK_REALTIME, &t_end); 
   fprintf(stderr,"sum = %ld\ttime = %lf\n", sum, diff_milli(t_end, t_start)); 
   printf("%lf", diff_milli(t_end, t_start)); 
   
   srand(SRAND_SEED);
   for(i = 0; i != LEN(fruits); ++i) 
   {
        fruitfabric[ HASH(i, LEN(fruitfabric)) ].dtor(fruits[i]);
   }
   return 0;
}
#!/bin/bash

REPEAT=5
echo -e "size\tnonvirt\tvirt"
for i in `seq 1 20`; do
  gcc -o apple apple.c -O2 -Wall -Wextra -lrt -DCOUNT=$i || break
  gcc -o apple.virt apple.c -O2 -Wall -Wextra -lrt -DVIRT -DCOUNT=$i || break
  ((c= (1<<i) ))
  echo -ne "$c\t"
  echo -ne $((echo -n '(';for j in `seq 1 $REPEAT`; do ./apple 2> /dev/null; echo -n '+';done;echo "0)/$REPEAT") | bc -l) "\t"
  (echo -n '(';for j in `seq 1 $REPEAT`; do ./apple.virt 2> /dev/null; echo -n '+';done;echo "0)/$REPEAT") | bc -l
done

В программе три разных хеш-функции для раскладывания объектов. Они _очень_ сильно влияют на производительность. Пруфграфик.

Плиз, попробуйте с каждой.

legolegs ★★★★★
()
Ответ на: Из-за кеша нихрена не понятно от legolegs

Удивительно, но даже switch с 100 вариантами со случайными числами работает быстрее, чем непосредственный вызов функции по заданному адресу

#include <iostream>
#include <cstdlib>
#include <time.h>
#include <inttypes.h>

using namespace std;

double diff_milli(timespec end, timespec start)
{
	return ((end.tv_sec-start.tv_sec) * 1e9 + (end.tv_nsec-start.tv_nsec)) * 1e-6;
}

struct Obj { int Type; int (*Func)(); int data[1000000];};

const int MAX=100;

#define F_n(n) __attribute__((noinline)) int f##n##_no_inline() { volatile int a = n; return a; }
F_n(810588) F_n(15604) F_n(265841) F_n(245900) F_n(909304)
F_n(598460) F_n(237627) F_n(822796) F_n(987005) F_n(689470)
F_n(840729) F_n(441055) F_n(789344) F_n(826188) F_n(385763)
F_n(820633) F_n(426678) F_n(163993) F_n(929908) F_n(925444)
F_n(639200) F_n(667458) F_n(793465) F_n(290395) F_n(856668)
F_n(864441) F_n(601180) F_n(437128) F_n(137158) F_n(179520)
F_n(691312) F_n(947746) F_n(195125) F_n(473506) F_n(709998)
F_n(620781) F_n(71966) F_n(947625) F_n(959930) F_n(58972)
F_n(153448) F_n(317011) F_n(16379) F_n(459144) F_n(143199)
F_n(918494) F_n(279777) F_n(569877) F_n(82487) F_n(726038)
F_n(11673) F_n(238039) F_n(393496) F_n(321491) F_n(528435)
F_n(766517) F_n(185932) F_n(645967) F_n(719997) F_n(323090)
F_n(825488) F_n(927661) F_n(787189) F_n(536965) F_n(401167)
F_n(497187) F_n(157746) F_n(473134) F_n(961165) F_n(117676)
F_n(48458) F_n(114613) F_n(434688) F_n(581189) F_n(90109)
F_n(94239) F_n(16036) F_n(369887) F_n(180469) F_n(98523)
F_n(612277) F_n(192142) F_n(852915) F_n(522125) F_n(513633)
F_n(381350) F_n(804994) F_n(215918) F_n(543669) F_n(524991)
F_n(55360) F_n(369157) F_n(452653) F_n(842549) F_n(906122)
F_n(370172) F_n(856089) F_n(580221) F_n(359658) F_n(817254)

#define Case_n(n) case n: return f##n##_no_inline();
int switch_no_inline(int type)
{
	switch(type)
	{
	Case_n(810588) Case_n(15604) Case_n(265841) Case_n(245900) Case_n(909304)
	Case_n(598460) Case_n(237627) Case_n(822796) Case_n(987005) Case_n(689470)
	Case_n(840729) Case_n(441055) Case_n(789344) Case_n(826188) Case_n(385763)
	Case_n(820633) Case_n(426678) Case_n(163993) Case_n(929908) Case_n(925444)
	Case_n(639200) Case_n(667458) Case_n(793465) Case_n(290395) Case_n(856668)
	Case_n(864441) Case_n(601180) Case_n(437128) Case_n(137158) Case_n(179520)
	Case_n(691312) Case_n(947746) Case_n(195125) Case_n(473506) Case_n(709998)
	Case_n(620781) Case_n(71966) Case_n(947625) Case_n(959930) Case_n(58972)
	Case_n(153448) Case_n(317011) Case_n(16379) Case_n(459144) Case_n(143199)
	Case_n(918494) Case_n(279777) Case_n(569877) Case_n(82487) Case_n(726038)
	Case_n(11673) Case_n(238039) Case_n(393496) Case_n(321491) Case_n(528435)
	Case_n(766517) Case_n(185932) Case_n(645967) Case_n(719997) Case_n(323090)
	Case_n(825488) Case_n(927661) Case_n(787189) Case_n(536965) Case_n(401167)
	Case_n(497187) Case_n(157746) Case_n(473134) Case_n(961165) Case_n(117676)
	Case_n(48458) Case_n(114613) Case_n(434688) Case_n(581189) Case_n(90109)
	Case_n(94239) Case_n(16036) Case_n(369887) Case_n(180469) Case_n(98523)
	Case_n(612277) Case_n(192142) Case_n(852915) Case_n(522125) Case_n(513633)
	Case_n(381350) Case_n(804994) Case_n(215918) Case_n(543669) Case_n(524991)
	Case_n(55360) Case_n(369157) Case_n(452653) Case_n(842549) Case_n(906122)
	Case_n(370172) Case_n(856089) Case_n(580221) Case_n(359658) Case_n(817254)
	}
	cerr << "no " << type << endl;
	exit(1);
}

#define Set(n, t) x[n].Type = t; x[n].Func = f##t##_no_inline;
void Random_Init(Obj* x)
{
	Set(0,580221) Set(1,961165) Set(2,925444) Set(3,947625) Set(4,719997)
	Set(5,137158) Set(6,369887) Set(7,906122) Set(8,473134) Set(9,359658)
	Set(10,117676) Set(11,856089) Set(12,153448) Set(13,513633) Set(14,90109)
	Set(15,601180) Set(16,804994) Set(17,185932) Set(18,789344) Set(19,497187)
	Set(20,163993) Set(21,543669) Set(22,524991) Set(23,569877) Set(24,689470)
	Set(25,82487) Set(26,321491) Set(27,426678) Set(28,856668) Set(29,909304)
	Set(30,864441) Set(31,434688) Set(32,290395) Set(33,16379) Set(34,639200)
	Set(35,820633) Set(36,180469) Set(37,279777) Set(38,842549) Set(39,581189)
	Set(40,98523) Set(41,959930) Set(42,245900) Set(43,215918) Set(44,381350)
	Set(45,987005) Set(46,528435) Set(47,195125) Set(48,612277) Set(49,927661)
	Set(50,522125) Set(51,766517) Set(52,11673) Set(53,143199) Set(54,179520)
	Set(55,929908) Set(56,918494) Set(57,369157) Set(58,709998) Set(59,370172)
	Set(60,620781) Set(61,55360) Set(62,691312) Set(63,238039) Set(64,71966)
	Set(65,667458) Set(66,393496) Set(67,265841) Set(68,536965) Set(69,840729)
	Set(70,94239) Set(71,473506) Set(72,726038) Set(73,58972) Set(74,192142)
	Set(75,825488) Set(76,385763) Set(77,441055) Set(78,645967) Set(79,452653)
	Set(80,16036) Set(81,852915) Set(82,323090) Set(83,822796) Set(84,598460)
	Set(85,114613) Set(86,787189) Set(87,793465) Set(88,237627) Set(89,157746)
	Set(90,48458) Set(91,317011) Set(92,817254) Set(93,401167) Set(94,15604)
	Set(95,810588) Set(96,947746) Set(97,437128) Set(98,826188) Set(99,459144)
}

void Run(int Max, Obj* x)
{
	const unsigned ITER_COUNT = 10000000;
	timespec t_start, t_end;
	uint64_t sum;
	clock_gettime(CLOCK_REALTIME, &t_start);
	sum = 0;
	for (uint64_t i = 0; i < ITER_COUNT; ++i)
	{
		for(int o = 0; o < Max; ++o)
		{
			sum += switch_no_inline(x[o].Type);
		}
	}
	clock_gettime(CLOCK_REALTIME, &t_end);
	cout << "switch no inline: sum = " << sum;
	cout << " time = " << diff_milli(t_end, t_start)  << endl;

	clock_gettime(CLOCK_REALTIME, &t_start);
	sum = 0;
	for (uint64_t  i = 0; i < ITER_COUNT; ++i)
	{
		for(int o = 0; o < Max; ++o)
		{
			sum += x[o].Func();
		}
	}
	clock_gettime(CLOCK_REALTIME, &t_end);
	cout << "virt: sum = " << sum;
	cout << " time = " << diff_milli(t_end, t_start)  << endl;
}

int main()
{
	Obj* x = new Obj[MAX];	
	Random_Init(x);
	Run(MAX, x);
	return 0;
}

Результат

switch no inline: sum = 495632330000000 time = 8878.02
virt: sum = 495632330000000 time = 9455.67
cy
()
Ответ на: комментарий от cy

switch выигрывает у виртуальных функций только лишь за счёт отсутствия вызова (inline) этих самых функций в switch

И только при -O0 и -O3 ;)

$ for f in '' -O1 -O2 -Os -O3; do echo $f; g++ $f file.c -lrt; ./a.out; done

switch inline: sum = 16106127300 time = 6002
switch no inline: sum = 16106127300 time = 11266.5
virt: sum = 16106127300 time = 10547.3
-O1
switch inline: sum = 16106127300 time = 4246.23
switch no inline: sum = 16106127300 time = 5559.07
virt: sum = 16106127300 time = 6188.24
-O2
switch inline: sum = 16106127300 time = 3536.28
switch no inline: sum = 16106127300 time = 3789.65
virt: sum = 16106127300 time = 6100.18
-Os
switch inline: sum = 16106127300 time = 4485
switch no inline: sum = 16106127300 time = 4525.78
virt: sum = 16106127300 time = 6372.97
-O3
switch inline: sum = 16106127300 time = 738.912
switch no inline: sum = 16106127300 time = 2864.67
virt: sum = 16106127300 time = 1570.16
pv4 ★★
()

Опыт со сравнением 1000 «виртуальных» функций и switch с 1000 элементов case показал следующее:

1) При переходе от 100 функций к 1000 функций картина меняется и виртуальные функции начинают выигрывать в 3 раза по сранению с полем типа со switch.

2) Конструкцию switch компилятор GCC реализует в виде двоичного поиска с последующим переходом к функции через jmp с адресом.

3) Процессору при небольших switch (в пределах 100) проще обработать кучу кода и пройти по условным и безусловным переходам с непосредственными адресами в командах (cmp, je, jmp и др.) в двоичном поиске, чем использовать несколько команд, но с вызовом функции, получая её адрес через обращения к памяти (call [QWORD PTR [r14+8]]).

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