- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
#include <iostream>
#include <stdlib.h>
#include <typeinfo>
using namespace std;
#define ololo for(volatile register int i=0;i<10;++i);
struct VB
{
virtual void f() const =0;
};
class V1: public VB
{
void f() const {ololo}
};
class V2: public VB
{
void f() const {ololo}
};
struct TU1
{
inline void f() const {ololo}
};
struct TU2
{
inline void f() const {ololo}
};
struct TUB
{
const type_info* type;
union
{
TU1 tu1;
TU2 tu2;
};
template<class T>
void ctor()
{
this->type=&typeid(T);
}
template<class T>
inline void call(const T& f)
{
if(this->type==&typeid(TU1))
f(this->tu1);
else
f(this->tu2);
}
};
enum {N=1000, N2=N*50};
int main() {
cout<<"ok"<<endl;
{
VB*v[N];
for(int i=0;i<N;++i)
if(rand()%2)
v[i]=new V1;
else
v[i]=new V2;
volatile clock_t a=clock();
for(int j=0;j<N2;++j)
for(int i=0;i<N;++i)
v[i]->f();
volatile clock_t b=clock();
cout<< (double)(b - a) / CLOCKS_PER_SEC<<endl;
}
cout<<"ok"<<endl;
{
TUB v[N];
for(int i=0;i<N;++i)
if(rand()%2)
v[i].ctor<TU1>();
else
v[i].ctor<TU2>();
struct Continuation
{
inline void operator()(const TU1& a) const {a.f();}
inline void operator()(const TU2& a) const {a.f();}
} cps;
volatile clock_t a=clock();
for(int j=0;j<N2;++j)
for(int i=0;i<N;++i)
v[i].call(cps);
volatile clock_t b=clock();
cout<< (double)(b - a) / CLOCKS_PER_SEC<<endl;
}
cout<<"ok"<<endl;
return 0;
}
Follow us!
Интересно, что это означает в контексте стандарта С++?
Ты обманываешь рандомом предсказатель переходов. В реальных ситуациях там не 50/50 а какой-то метод дергается чаще.
А в той же жабе instanceof прекрасно им оптимизируется.
Ну и сделай штук 5-6 полиморфных классов - интересно посмотреть. Плюс не стоит забывать про кейс. Хотя можно сказать заведомо что сишный кейс - кал.
Бенчи в ideone - это жестоко.
Не в 100%. Для косвенных переходов тоже есть предсказатель, правда, если мне не изменяет память, помнит он только самый последний вызов. Т.е. если дрючить одну и ту же виртуальную функцию - угадает, если разные по очереди - уже нет.
Да полиморфизм виртуальных функций должен ещё больше выиграть. Мне это почему то кажется очевидным, поэтому я ничего не делал. Даже если заюзать деление пополам у if в tagget union. Результаты могут пошатнутся в сторону tagget union только если мало полиморфных классов (типа 2) и притом одна ветка if всегда выполняется много чаще других (например первый полиморфный класс содержится в массиве v много чаще других).
Ещё наверное сравнение if(this->type==&typeid(TU1)) можно оптимизировать, ибо &typeid(TU1) неплохо бы заменить на константу. Оно константно, но компилятор может превратить это в вызов функции.
Да мне тоже много чего казалось очевидным, пока не начал креститься проверять лично.
PS> Внезапно на хабре сделали хороший, добротный тест:http://habrahabr.ru/post/118087
это к Тарасу
И он соснул.
virtual functions: 1.94 сек
tagget union: 1.6 сек
Видимо зависит от проца.
Мы кажется выяснили, что на IDEONE - AMD.
Возможно на liveworkspace.org - Intel или более древний\более новый AMD.
И повторюсь - делать бенчи в online ide - это конечно хардкор.
LispGovno
http://ideone.com/ICydFM
потому то микрософт мерзкий с99 никогда не внедрит
микрософт, как обычно, поддерживает только все самое последнее
> поддерживает только все самое последнее
т.е. c89?
А в чем особенности этих?
"Как программировать на C++ без извращений?".
В конце книги вывод: "Это очень просто. Не программировать на С++".
В главе "Благодарности и пожелания автору от рецензентов": "Как можно проще программируйте на С++ и не будьте таким развратным."
Не, я тоже нихуя не понял, что wvxvw имел в виду.
Like ordinary unions, tagged unions can save storage by overlapping storage areas for each type, since only one is in use at a time.
Полиморфные объекты тоже это умеют.
А вот структуры, которые могут одновременно хранить и Derived1, и Derived2, жрут лишнюю память, и про "использовать память под полезные нужны" имелось в виду именно в сравнении с простыми структурами.
И да, если разные ветки имеют ооочен разные размер, то полиморфные объекты могут дать выигрыш по памяти, потому что они всегда жрут сколько надо, и тегоюнион жрёт память в соответствии с размером самой длинной ветки.
1)Убирания долгой аллокации объекта по new из кучи.
2)Добавление кешфрендли объекту, тк нет отделения большим диапазоном адресов таблицы виртуальных методов от RTTI от самого объекта и от указателя на него.
3)Частичное убирание stall в конвейере команд процессора.
Пункт 1) также можно реализовать и через placement new в объекте подобном TUB (там внутри подобный унион или массив с размером максимального объекта, который можно разместить в TUB).
Может ещё кто-то знает назвначение подобной техники. Хотя конечно это бы оформить в библиотеку с кодогенерицией, а то сейчас выглядит паршиво как говнокод.
http://www.boost.org/doc/libs/1_51_0/doc/html/variant.html
Инстанцирование шаблона класса - создание кода класса на основе шаблона (кодогенерация).
>boost.org/doc/libs/1_51_0/doc/html/variant
больше 12 байт объекты не размещаются в boost::variant. Он выделяет объекты в куче с соответствующими последствиями.
template<class T>
inline void call(const T& f)
однако мне тоже интересно откуда дровишки
1) про 12 байт
2) O(log n) vs O(n) если там вообще compile-time
ну а про сложность (которая также compile-time) тоже интересно
ну разве что компилятору сложно - ну а кому в наше время легко
может я чего упустил?
Пора уже показывать над минусами тех, кто их поставил.
Сложность, если конечно не ошибаюсь, там действительно O(1) т.к. get() это проверка на соответствие запрашиваемого и реального типа да тупой каст.
в variant там все решается через перегрузку
типа такой:
> в variant там все решается через перегрузку
типа такой:
The get function allows run-time checked, type-safe retrieval of the content of the given variant.
Все-таки рантайм проверка там есть.
ран-тайм - имеется в виду, что при несоответствии типов будет в рантайме кинуто bad_get, а не ошибка компиляции
А это походу потому, что она видит что туда засунули. Попробуйте сделать тип зависящим от чего-нибудь типа argc - если 1 то foo() если 2 то bar(). Тогда, мне кажется, она вставит проверочку с вбросом bad_get.
http://liveworkspace.org/code/468230da8ae63feab65e99bede607fbd
Лол. У тебя же n классов в иерархии. И если ты не знаешь, какой там лежит класс в boost::variant, то у тебя n * O(1). То есть О(n).
А так я думаю очевидно, что boost::get работает за О(1).
> Тогда, мне кажется, она вставит проверочку с вбросом bad_get.
да, одну проверочку вставит, а не O(n)
@LispGovno
> И если ты не знаешь, какой там лежит класс в boost::variant, то у тебя n * O(1)утверждается, что для такого variant должно произойти 8 проверок, прежде чем мы убедимся, что тип == baz
однако:
утверждается, что для такого variant должно произойти 8 проверок, прежде чем мы убедимся, что тип == baz
Ну конечно. Ты сначала проверяешь через boost::get на int, потом на long, потом на ... и так до конца. Если ты что-то знаешь, то ты естественно часть проверок через boost::get опускаешь. В данном коде выше ты знал, что у тебя там baz лежит и сделал лишь одну проверку:
boost::get<baz>(v).print();
Другие варианте тебе были просто не нужны.
Фактически про О(n) я говорил, когда ты через boost::get моделируешь полиморфизм.
ладно
закрывая этот вопрос окончательно - ты имеешь в виду visitor для объекта variant - будем эмулировать полиморфизм
http://liveworkspace.org/code/374baab33e4f8e969fec16f3119f5345
вот этот код, как ни крути, у меня в релизе без оверхеда сразу выбирает нужный operator ()
Наконецто. Я о нем уже несколько раз в этом треде писал и о его проблемах.
всё что ты написал - ты не разобрался как он работает
Я сказал, что стратегию под оптимизацию другую выбрать нельзя визиторе, если профлаер указал на несостоятельность текущей стратегии поиска реального типа класса.
И ещё проблема, что не известно какая стратегия там вообще по умолчанию используется, если в исходники не заглядывать, тк в документации это не указано.
С чего ты взял что без оверхеда? Что там? O(1), O(log n) или всеже O(n)?
На счет O(1) я уверен, что оно там не используется, если смотреть на размер boost::variant. Значит там или O(log n) или О(n)
запустил в Release, но с /Zi /DEBUG
поставил бряку на apply_visitor и по асм коду (alt+8) прошелся f11
на любых исходных данных компилятор переходит в нужный обработчик за одну проверку
вникать в шаблонодебри сорцов варианта в первом часу ночи уже не хочется
edit
> за одну проверку
да там и нет в асм коде вообще ни таблицы сравнений, ни последовательности сравнений по списку
сразу куда нужно переходит - оверлоад, мать его
а, может быть, виноват хороший оптимизатор
так что надо будет еще потестировать завтра
сразу куда нужно переходит - оверлоад, мать его
Может это компилятор соптимизировал, раз знает, какой реально тип там лежит во время компиляции? К параметрам командной строки привезал тип, как ты делал выше?
Если исключил воможность оптимизации со стороны компилятора, то это довольно странно. Почему за О(1)?..
внутри variant хранится which - число - навроде "индекс" типа из шаблонного списка
apply_visitor в итоге строит конструкцию switch для вызова хендлера по конкретному индексу среди всех типов внутри variant - так что уж тут как компилятор отработает этот свич, такой O и будет (да, O(n) в худшем случае, то там return на каждую ветвь, так что оптимизатору есть где поработать)
ну а на /O2 микрософтовский компилер всю эту байду сокращает до банальщины - заранее кладет в стек нужные адреса при инициализации для каждого возможного argc (выбор из например 4 типов-то для 2 переменных не очень велик) и затем по конкретному argc где надо сразу достает нужные смещения и делает вид, что O(1) и так и задумано
буст:вариант
молодцы. Хоть стратегию поменять нельзя, но зато есть где развернутся оптимизатору. Уважуха.
http://liveworkspace.org/code/195391c0a3ddf544bf621ce16b0a316b
cstdio включен чтобы было легче разбираться в асме
Или этого больше нет в новых версиях, или это было в некоторых реализациях, либо так было реализовано в boost::any. Я склоняюсь к последнему.
> ну а про сложность (которая также compile-time) тоже интересно
Уж и не знаю что там со сложностью компилетайм, а вот сложность поиска находящегося в варианте класса из иерархии О(n), если он не известен через boost::get. В своей же реализации (например как в говнокоде выше) можно организовать поиск нужного класса в иерархии за О(log n), O(1) и О(n) с переборам классов в соответствии с вероятностью их появления. Через boost::get конечно тоже можно перебрать за О(n) с учетом вероятности, но это не удобно делать каждый раз, ибо перебор приходится харкодить везде по коду и если профлаер скажет поменять данный перебор, то придется менять вообще везде вручную возможно с ошибками. А так выбрал реализацию call нужную (в том числе и сгенерировал её код на крестах через метапрограммирование) и если профлайер скажет, мол медленно - ты сможешь поменять стратегию сгенерированного кода для call из говнокода выше.
А boost::apply_visitor не известно как работает и менять стратегию в угоду оптимизации не позволяет.
поясни мысль
когда variant инициализируется, он уже в курсе какой тип он хранит
поэтому в чем проблема для него сделать одну единственную проверку "если тип тот, то на тебе его, если тип не тот - лови эксепшен"
где тут O(n)?
разницу между any и variant улавливаешь?
из мануала:
> Boost.Variant provides compile-time checked visitation of its content.
какая еще стратегия? O(1)
А вот с твоим boost::get каши не сваришь. Он потребует проверку O(n) для перебора всей иерархии классов в любом случае, если ты моделируешь полиморфизм и не знаешь какой реальный тип из списка дозволеных, лежит в boost::variant.
Intel Core Architecture?
Давно по незнанию я также писал такой код, несмотря на его определенную громоздкость, считая что где-где, а в JVM там-то всё оптимизировано.
Ну и по ходу дела старался избегать instanceofов и прочих ifов с кейсами даже там где они были необходимы (правда кейсы - не очень, обычно их можно заменить мапом или обычным массивом).
Казалось бы взять адрес класса, найти метод в таблице, сделать call. Что может быть проще?
Наверное это таки быстрее чем проверять бранч на 10 условий.
Но вконец я в душе ненавидя ооп-парадигму, т.н. паттерны и громоздкость порождаемого ими кода, решил проверить "а велик ли прирост скорости от полиморфизма".
И выглядят они примерно таким вот образом:
Как мы видим это тот же кейс, от которго мы избавились с помощью полиморфизма, но только вот он всплыл в другом месте! Его перенесли в фабрику.
Еще есть способ: поднятие объектов по рефлексии, где из мапа достается класс объекта, но это в какой-то мере хак, причем тормозной.
Не, в правильной фабрике ещё воткнута регистрация с привязкой идентификатора типа к прототипу.
> долбоебов-оопешников с мозгом засраном под завязку паттернами
Паттерны по сути весьма забавная штука: они позволяют заменить 20 строк копипасты 40 строками разного кода
Ох ты ж сукин сын, да это то, что меня всё время мучало на интуитивном уровне и я долго пытался как-то выразить, но не мог подобрать слова. Это надо вынести в крылатые фразы говнокода.
Ща ещё виртуалами плюсану ^_^
Я только хотел писать коммент про подсознательное, интуитивное восприятие того что Роман выразил словами.
И про то что надо это где-нибудь на видном месте выбить в граните.
По факту выяснилось что Тарас был глубоко прав, постоянно кормя говном фанатов ооп.
Хоть большинство и считают это зеленью, но он-то прав.
if foo.tag /= tag_bar then throw Discriminant_Error; end if;
foo.bar;
В выпуске проверку можно убрать в бутленьке, если он хорошо проверен. Проверку можно убрать и в кулхацкерских целях.
Ещё в них разрешено пихать неподы. Потому что легко определить, какой из неподов, находящихся в разных ветках по одному адресу, надо убрать - посмотреть в тэг
Что за хуйню ты мелешь?
Там всё за O(1), что там может быть за O(n)?
Я тут узнал недавно, что typeid считается в рантайме.
Поэтому сделай, пожалуйста, нормальный свич и явный тэг.