LINUX.ORG.RU
Форум — Development  

[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 в своем коде (как-то и эстетичнее оно), а тут такое...

★★★★
← [Коллективный разум] [Студентота, диплом] Виртуализация
Подскажите по алгоритмам →
 ← 1 2
Ответ на: комментарий от anonymous

> Это какой-то ужос. malloc, поля типов и прочие штуки из С.

тэг [C] как бы намекает.

anonymous
()

>Как вызов по указателю может быть медленнее цепочки сравнений?

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

pathfinder ★★★★
()

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

pathfinder ★★★★
()

Я имею ввиду сравнивать эти варианты бесполезно. Завтра выйдет процессор с какой-нибудь особенностью и результаты этого теста изменяться на противоположные.

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

С оптимизацией ничего принципиально не меняется, в ассемблере все ожидаемо - в невиртуальной функции вдвое больше инструкций, включая jmp/je, - всяко она выглядит хуже. А в виртуальной единственное, что привлекает внимание - 

  call *%eax
Получается, что это еще хуже, что и удивляет.

unsigned ★★★★
() автор топика

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

ahonimous
()
Ответ на: комментарий от anonymous 
typedef struct _Fruit *Fruit;
typedef struct _Apple *Apple;
typedef struct _Orange *Orange;

/********* Fruit *********/

typedef int (*FruitID)(Fruit);

struct _Fruit {
	int type;
	FruitID id;
};

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;
}

/*****  Apple ****/

struct _Apple {
	struct _Fruit base;
};

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;
}

void apple_delete(Apple a)
{
	free(a);
}

/******* Orange ********/

struct _Orange {
	struct _Fruit base;
};

int orange_id(Orange o)
{
	return 2;
}

Orange orange_new(void)
{
	Orange o = (Orange)malloc(sizeof(struct _Orange));
	o->base.type = 2;
	o->base.id = (FruitID)orange_id;
	return o;
}

void orange_delete(Orange a)
{
	free(a);
}

int main()
{
	Fruit a = (Fruit)apple_new();
	Fruit o = (Fruit)orange_new();
	unsigned i;
	long sum = 0;

	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
	printf("sum = %d\n", sum);

	orange_delete((Orange)o);
	apple_delete((Apple)a);
}
unsigned ★★★★
() автор топика
Ответ на: комментарий от namezys

нужно позволить компилятору оптимизирвоать полиморфизм

Как?

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

Виртуальная функция: 

fruit_id_virt:
	pushl %ebp
	movl %esp,%ebp
	subl $8,%esp
	movl 8(%ebp),%eax
	addl $-12,%esp
	pushl %eax
	movl 4(%eax),%eax
	call *%eax
	movl %ebp,%esp
	popl %ebp
	ret
Невиртуальная: 
fruit_id_nonvirt:
	pushl %ebp
	movl %esp,%ebp
	subl $8,%esp
	movl 8(%ebp),%edx
	movl (%edx),%eax
	cmpl $1,%eax
	je .L5
	cmpl $2,%eax
	je .L6
	jmp .L4
	.p2align 4,,7
.L5:
	addl $-12,%esp
	pushl %edx
	call apple_id
	jmp .L9
	.p2align 4,,7
.L6:
	addl $-12,%esp
	pushl %edx
	call orange_id
	jmp .L9
	.p2align 4,,7
.L4:
	xorl %eax,%eax
.L9:
	movl %ebp,%esp
	popl %ebp
	ret
gcc-2.95, -O2 задействован.

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

>Но разница в два раза - не верится, что железо может принципиально изменить результат.

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

pathfinder ★★★★
()
Ответ на: комментарий от unsigned 
.L25:
	addl	$1, %eax
	addl	CSWTCH.7+4, %edx
	cmpl	$100000, %eax
	jne	.L25

все очень просто

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

> ГМ. Никогда бы не подумал, что между call *%eax и call orange_id будет такая разница в скорости :)

а там call для первого случая и нет, по крайней мере у меня на gcc 4.4.4, тупо цикл + добавить значение

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

>а там call для первого случая и нет

Что, где? o_O

по крайней мере у меня на gcc 4.4.4

Я про выхлопы топикстартера

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

Это нормально. В продакшне до сих пор используется

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

> Я про выхлопы топикстартера

у тебя libastral развит? :) он показал код процедур - ну так он и уменя сгенерировался, вот только обращения к ним нет

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

Ты про функцию main? У меня там честные call'ы обеих функций: 

.L6:
	addl $-12,%esp
	movl -4(%ebp),%eax
	pushl %eax
	call fruit_id_virt
	movl %eax,%ebx
	addl $-12,%esp
	pushl %edi
	call fruit_id_virt
	addl %ebx,%eax
	addl %eax,-8(%ebp)
	addl $32,%esp
	incl %esi
	cmpl $268435455,%esi
	jne .L6
а что у тебя - не понимаю. Ты хочешь сказать, что компилятор статично подставил значения функций? Ну значит слишком умный компилятор, используй gcc-2.95!

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

> Ты хочешь сказать, что компилятор статично подставил значения функций? Ну значит слишком умный компилятор, используй gcc-2.95

я лучше новым умным буду пользоваться :) в моем случае разница между вариантами была в 12 раз, причем самый быстрый на 0xFFFFFFF итерациях завершился за 0.08сек

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

> в моем случае разница между вариантами была в 12 раз

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

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

> Да, впечатляет

таки 4 ядра по 4Гц ( хотя реально конечно одно работало )

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

Пример с виртуальными (gcc -O2) 

sum = 805306365

real	0m1.328s
user	0m1.328s
sys	0m0.000s
Пример без вируальных (gcc -O2) 
sum = 805306365

real	0m0.698s
user	0m0.688s
sys	0m0.000s

Мой пример на С++ (g++ -O2)
Результат в сотни раз быстрее и код намного понятнее 

sum = 805306365

real	0m0.002s
user	0m0.000s
sys	0m0.000s

#include <iostream>
using namespace std;

class Fruit
{
public:
	virtual int GetID() = 0;
};

class Apple : public Fruit
{
public:
	int GetID() { return 1; }
};

class Orange : public Fruit
{
public:
	int GetID() { return 2; }
};

int main()
{
	Apple a;
	Orange o;

	long sum = 0;
	for(unsigned i = 0; i != 0xFFFFFFF; ++i)
	{
		sum += a.GetID() + o.GetID();
	}	
	cout << "sum = " << sum << endl;
	
	return 0;
}
anonymous
()
Ответ на: комментарий от unsigned 
long GetSum()
{
	Apple a;
	Orange o;
	long sum = 0;
	for(unsigned i = 0; i != 0xFFFFFFF; ++i)
	{
		sum += a.GetID() + o.GetID();
	}
	return sum;
}

Такую функцию g++ -O2 превращает в 1 инструкцию «movl $805306365, %esi»

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

> Мой пример на С++ (g++ -O2) Результат в сотни раз быстрее и код намного понятнее

И где тут виртуальный вызов?

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

У меня 0.2 секунды о_О

Понять бы, как они это делают. Я плюсовый ассемблер не осилю.

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

Да, пардон. С виртуальностью стало «лучше», 3.3 секунды. Все равно лучше чем С.

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

А вы таки уверены, что компилятор не заинлайнил ваши виртуальные функции? А ведь мог бы

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

Точно, нету. Исправление 

#include <iostream>
using namespace std;

class Fruit
{
public:
	virtual int GetID() = 0;
};

class Apple : public Fruit
{
public:
	int GetID() { return 1; }
};

class Orange : public Fruit
{
public:
	int GetID() { return 2; }
};

long GetSum()
{
	Apple a;
	Orange o;
	Fruit *c1=&a, *c2=&o;
	long sum = 0;
	for(unsigned i = 0; i != 0xFFFFFFF; ++i)
	{
		sum += c1->GetID() + c2->GetID();
	}
	return sum;
}

int main()
{
	cout << "sum = " << GetSum() << endl;
	return 0;
}
Результат такой же, как и с «виртуальными» фунциями в примере на С 0m1.293s.

anonymous
() 
#include <stdio.h>
#include <malloc.h>


typedef struct _Fruit *Fruit; 
typedef struct _Apple *Apple; 
typedef struct _Orange *Orange; 
 
/********* Fruit *********/ 
 
typedef int (*FruitID)(Fruit); 
 
struct _Fruit { 
   int type; 
   FruitID id; 
}; 
 
int fruit_id_virt(Fruit f) 
{ 
   return f->id(f); 
} 
 
int fruit_id_nonvirt(Fruit f) ; /* see below */
 
/*****  Apple ****/ 
 
struct _Apple { 
   struct _Fruit base; 
}; 
 
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; 
} 
 
void apple_delete(Apple a) 
{ 
   free(a); 
} 
 
/******* Orange ********/ 
 
struct _Orange { 
   struct _Fruit base; 
}; 
 
int orange_id(Orange o) 
{ 
   return 2; 
} 
 
Orange orange_new(void) 
{ 
   Orange o = (Orange)malloc(sizeof(struct _Orange)); 
   o->base.type = 2; 
   o->base.id = (FruitID)orange_id; 
   return o; 
} 
 
void orange_delete(Orange a) 
{ 
   free(a); 
} 
 
#define DEF_FRUIT(name,fr_id) \
struct _##name { struct _Fruit base; }; \
int name##_id(struct _##name * o) { return (fr_id); } \
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(Repa,3)
DEF_FRUIT(Arbue,4)
DEF_FRUIT(Coco,5)
DEF_FRUIT(Banana,6)
DEF_FRUIT(Tomato,7)
DEF_FRUIT(Shaverma,8)

int fruit_id_nonvirt(Fruit f) 
{ 
   switch(f->type) { 
      case 1: 
         return apple_id((Apple)f); 
      case 2: 
         return orange_id((Orange)f); 
      case 3: 
         return Repa_id((struct _Repa *)f); 
      case 4: 
         return Arbue_id((struct _Arbue *)f); 
      case 5: 
         return Coco_id((struct _Coco *)f); 
      case 6: 
         return Banana_id((struct _Banana *)f); 
      case 7: 
         return Tomato_id((struct _Tomato *)f); 
      case 8: 
         return Shaverma_id((struct _Shaverma *)f); 
   } 
   return 0; 
} 
#define LEN(x) (sizeof(x)/sizeof(x[0]))
int main() 
{ 
   Fruit fruits[32];
   unsigned i,j; 
   long sum = 0; 
 
   for(i = 0; i != LEN(fruits); ++i) 
   {
        switch (i%4+1) {
        case 1: 
           fruits[i] = (Fruit)apple_new(); break;
        case 2: 
           fruits[i] = (Fruit)orange_new(); break;
        case 3: 
           fruits[i] = (Fruit)Repa_new(); break;
        case 4: 
           fruits[i] = (Fruit)Arbue_new(); break;
        case 5: 
           fruits[i] = (Fruit)Coco_new(); break;
        case 6: 
           fruits[i] = (Fruit)Banana_new(); break;
        case 7: 
           fruits[i] = (Fruit)Tomato_new(); break;
        case 8: 
           fruits[i] = (Fruit)Shaverma_new(); break;
        }
   }
   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 
   }
   }
   printf("sum = %ld\n", sum); 
 
   for(i = 0; i != LEN(fruits); ++i) 
   {
        switch (i%4+1) {
        case 1: 
           apple_delete((Apple)(fruits[i])); break;
        case 2: 
           orange_delete((Orange)(fruits[i])); break;
        case 3: 
           Repa_delete((struct _Repa *)(fruits[i])); break;
        case 4: 
           Arbue_delete((struct _Arbue *)(fruits[i])); break;
        case 5: 
           Coco_delete((struct _Coco *)(fruits[i])); break;
        case 6: 
           Banana_delete((struct _Banana *)(fruits[i])); break;
        case 7: 
           Tomato_delete((struct _Tomato *)(fruits[i])); break;
        case 8: 
           Shaverma_delete((struct _Shaverma *)(fruits[i])); break;
        }
   }
   return 0;
}
┌[user@localhost ~/programming]
└> gcc -o apple apple.c -Wall -Wextra  -O2
apple.c: В функции ‘apple_id’:
apple.c:31: предупреждение: параметр ‘a’ не используется
apple.c: В функции ‘orange_id’:
apple.c:55: предупреждение: параметр ‘o’ не используется
apple.c: В функции ‘Repa_id’:
apple.c:85: предупреждение: параметр ‘o’ не используется
apple.c: В функции ‘Arbue_id’:
apple.c:86: предупреждение: параметр ‘o’ не используется
apple.c: В функции ‘Coco_id’:
apple.c:87: предупреждение: параметр ‘o’ не используется
apple.c: В функции ‘Banana_id’:
apple.c:88: предупреждение: параметр ‘o’ не используется
apple.c: В функции ‘Tomato_id’:
apple.c:89: предупреждение: параметр ‘o’ не используется
apple.c: В функции ‘Shaverma_id’:
apple.c:90: предупреждение: параметр ‘o’ не используется
┌[user@localhost ~/programming]
└> gcc -o apple.virt apple.c -Wall -Wextra -DVIRT -O2
apple.c: В функции ‘apple_id’:
apple.c:31: предупреждение: параметр ‘a’ не используется
apple.c: В функции ‘orange_id’:
apple.c:55: предупреждение: параметр ‘o’ не используется
apple.c: В функции ‘Repa_id’:
apple.c:85: предупреждение: параметр ‘o’ не используется
apple.c: В функции ‘Arbue_id’:
apple.c:86: предупреждение: параметр ‘o’ не используется
apple.c: В функции ‘Coco_id’:
apple.c:87: предупреждение: параметр ‘o’ не используется
apple.c: В функции ‘Banana_id’:
apple.c:88: предупреждение: параметр ‘o’ не используется
apple.c: В функции ‘Tomato_id’:
apple.c:89: предупреждение: параметр ‘o’ не используется
apple.c: В функции ‘Shaverma_id’:
apple.c:90: предупреждение: параметр ‘o’ не используется
┌[user@localhost ~/programming]
└> for i in 1 2 3; do time ./apple.virt ; done;for i in 1 2 3; do time ./apple ; done
sum = 671088560

real	0m2.437s
user	0m0.940s
sys	0m0.217s
sum = 671088560

real	0m2.344s
user	0m0.901s
sys	0m0.216s
sum = 671088560

real	0m2.378s
user	0m0.947s
sys	0m0.174s
sum = 671088560

real	0m0.846s
user	0m0.250s
sys	0m0.133s
sum = 671088560

real	0m0.838s
user	0m0.305s
sys	0m0.076s
sum = 671088560

real	0m0.828s
user	0m0.296s
sys	0m0.087s
┌[user@localhost ~/programming]
legolegs ★★★★★
()

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

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

Если ничего не путаю, интеловские процессоры умеют делать такие спекуляции лишь начиная с Core2.

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

> ваш процессор

а ваш умеет? вы какой используете? учитывая современную распространённость C++-приложений вопрос не праздный.

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

2legolegs: в приведённом примере fruit_id_virt просто обязанна быть дольше чем «не-виртуальный» аналог :) практически на любой архитектуре. Можете убедится сами просто используя gdb по шагам.

Посудите сами - «виртуальная функция» сначала вытаскивает из структуры адрес (функцию) которую нужно вызвать, потом производит вызов по адресу с параметром.

«невиртуальная» делает сравнение с константой (загоняя мимоходом аргумент в кеш) и делает вызов по фиксированному адресу, который определён на этапе компиляции. К тому-же -O2 как бы намекает, что сравнение целого с малой константой и вызов по адресу могут быть (не поручусь) оптимизированы.

ЗЫ. Кстати функции не совсем корректно закодины. fruit_id_nonvirt должен иметь default выбор, fruit_id_virt наверное сравнение с NULL и отсылку к apple_id();

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

Мопед не мой, я просто расширил его. Кстати, там баг, последние 4ре типа никогда не создаются.

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

Погонял на GCC 4.4.4 с оптимизациями и без, поглядел ассемблерный выхлоп (если кто не знает, «gcc -S -o asm.s source.c»). Выяснил следующее:

при -O2 в моём варианте, расширенном до 16ти типов фруктов fruit_id_nonvirt вылядит так: 

fruit_id_nonvirt:
	pushl	%ebp
	movl	%esp, %ebp
	movl	8(%ebp), %eax
	movl	(%eax), %edx
	xorl	%eax, %eax
	subl	$1, %edx
	cmpl	$15, %edx
	ja	.L37
	movl	CSWTCH.46(,%edx,4), %eax
.L37:
	popl	%ebp
	ret
CSWTCH - это тупо таблица из чисел (человек бы обошёлся и без неё, кстати). Вызовов функций *_id нет.

С -O0 оно выглядит гораздо честнее: 

fruit_id_nonvirt:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$4, %esp
	movl	8(%ebp), %eax
	movl	(%eax), %eax
	cmpl	$16, %eax
	ja	.L100
	movl	.L117(,%eax,4), %eax
	jmp	*%eax
	.section	.rodata
	.align 4
	.align 4
.L117:
	.long	.L100
	.long	.L101
	.long	.L102
	.long	.L103
	.long	.L104
	.long	.L105
	.long	.L106
	.long	.L107
	.long	.L108
	.long	.L109
	.long	.L110
	.long	.L111
	.long	.L112
	.long	.L113
	.long	.L114
	.long	.L115
	.long	.L116
	.text
.L101:
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	apple_id
	jmp	.L118
.L102:
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	orange_id
	jmp	.L118
.L103:
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	Repa_id
	jmp	.L118
.L104:
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	Arbue_id
	jmp	.L118
.L105:
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	Coco_id
	jmp	.L118
.L106:
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	Banana_id
	jmp	.L118
.L107:
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	Tomato_id
	jmp	.L118
.L108:
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	Shaverma_id
	jmp	.L118
.L109:
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	fru9_id
	jmp	.L118
.L110:
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	fru10_id
	jmp	.L118
.L111:
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	fru11_id
	jmp	.L118
.L112:
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	fru12_id
	jmp	.L118
.L113:
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	fru13_id
	jmp	.L118
.L114:
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	fru14_id
	jmp	.L118
.L115:
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	fru15_id
	jmp	.L118
.L116:
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	fru16_id
	jmp	.L118
.L100:
	movl	$0, %eax
.L118:
	leave
	ret
, но если кто-то думает, что switch - это всё равно что цепочка if else if - он крупно заблуждается. Как видно, даже при выключенной оптимизации программа прыгает сразу на нужную строчку, без лишних сравнений.

Что будет, если id назначать случайно? Я попробывал, вот резльтат с -O2: 

fruit_id_nonvirt:
	pushl	%ebp
	movl	%esp, %ebp
	movl	8(%ebp), %eax
	movl	(%eax), %edx
	movl	$813, %eax
	cmpl	$813, %edx
	je	.L57
	jle	.L61
	cmpl	$1254, %edx
	movl	$1254, %eax
	je	.L57
	jg	.L55
	cmpl	$1013, %edx
	movw	$1013, %ax
	je	.L57
	cmpl	$1182, %edx
	movw	$1182, %ax
	je	.L57
	cmpl	$992, %edx
	movw	$992, %ax
	je	.L57
.L36:
	xorl	%eax, %eax
	.p2align 4,,7
	.p2align 3
.L57:
	popl	%ebp
	ret
	.p2align 4,,7
	.p2align 3
.L61:
	cmpl	$487, %edx
	movw	$487, %ax
	je	.L57
	jle	.L62
	cmpl	$643, %edx
	movl	$643, %eax
	je	.L57
	cmpl	$782, %edx
	movw	$782, %ax
	je	.L57
	cmpl	$583, %edx
	movw	$583, %ax
	je	.L57
	xorl	%eax, %eax
	jmp	.L57
	.p2align 4,,7
	.p2align 3
.L55:
	cmpl	$1422, %edx
	movl	$1422, %eax
	je	.L57
	jle	.L63
	cmpl	$1516, %edx
	movl	$1516, %eax
	je	.L57
	cmpl	$1687, %edx
	movw	$1687, %ax
	je	.L57
	xorl	%eax, %eax
	jmp	.L57
	.p2align 4,,7
	.p2align 3
.L62:
	cmpl	$2, %edx
	movw	$2, %ax
	je	.L57
	cmpl	$399, %edx
	movw	$399, %ax
	je	.L57
	cmpl	$1, %edx
	movw	$1, %ax
	jne	.L36
	jmp	.L57
	.p2align 4,,7
	.p2align 3
.L63:
	cmpl	$1374, %edx
	movb	$94, %al
	jne	.L36
	.p2align 4,,3
	jmp	.L57
Присмотревшись к этой каше можно видеть, что функции *_id по-прежнему не вызываются, а поиск осуществляется бинарный, по прежнему никакого тупого перебора. gcc сцуко не особо умный, но хитрый.

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

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

legolegs ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
 ← 1 2
← [Коллективный разум] [Студентота, диплом] Виртуализация
Development
Подскажите по алгоритмам →