OberonCore https://forum.oberoncore.ru/ |
|
Эффективность WITH https://forum.oberoncore.ru/viewtopic.php?f=81&t=914 |
Страница 1 из 3 |
Автор: | Vlad [ Четверг, 13 Март, 2008 17:22 ] |
Заголовок сообщения: | Эффективность WITH |
AVC писал(а): Alexey Veselovsky писал(а): Насчет производительности WITH vs dynamic_cast и проч. -- думаю тут гадать бессмысленно. А что тут гадать?И все-таки Интересно же, сколько это будет в граммах Я не поленился и написал вот такой тестик: 100 миллионов сравнений на принадлежность одному из 3 расширений типа. Код: MODULE TestCast; TYPE X = EXTENSIBLE RECORD END; X1 = EXTENSIBLE RECORD (X) END; X2 = EXTENSIBLE RECORD(X1) END; X3 = EXTENSIBLE RECORD(X2) END; PROCEDURE handle(IN x: X); END handle; PROCEDURE handle1(IN x: X1); END handle1; PROCEDURE handle2(IN x: X2); END handle2; PROCEDURE handle3(IN x: X3); END handle3; PROCEDURE test_cast(IN x: X); BEGIN WITH x: X3 DO handle3(x); | x: X2 DO handle2(x); | x: X1 DO handle1(x); ELSE handle(x); END END test_cast; PROCEDURE main*(); VAR x: X; x1: X1; x2: X2; x3: X3; i: INTEGER; BEGIN FOR i := 0 TO 100000000 DO test_cast(x); test_cast(x1); test_cast(x2); test_cast(x3); END END main; END TestCast. И вот такой аналогичный тест для C++ и его тормозного dynamic_cast: Код: struct X { virtual ~X(){} }; struct X1 : X { }; struct X2 : X1 { }; struct X3 : X2 { }; void handle(const X &x) { } void handle1(const X1 &x) { } void handle2(const X2 &x) { } void handle3(const X3 &x) { } void check_type(const X &x) { if (const X3 *x3 = dynamic_cast<const X3 *>(&x)) handle3(*x3); else if (const X2 *x2 = dynamic_cast<const X2 *>(&x)) handle2(*x2); else if (const X1 *x1 = dynamic_cast<const X1 *>(&x)) handle1(*x1); else handle(x); } int main() { X x; X1 x1; X2 x2; X3 x3; for (int i = 0; i < 100000000; i++) { check_type(x); check_type(x1); check_type(x2); check_type(x3); } return 0; } Все этом варианте все функции были разнесены по разным единацам компиляции, чтобы оптимизатор не повыкидывал все нафиг. Результат: BB: 2.4 с VC9: 49 с Вывод: решения на основе "oberon message bus" с использованием dynamic_cast в C++ действительно могут оказаться неэффективными с точки зрения производительности. Разница в скорости динамической проверки типа порядка 20 раз. |
Автор: | Илья Ермаков [ Четверг, 13 Март, 2008 17:36 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Влад, а согласитесь, что дело, в общем, не в реализации. А в том, что в Си-мире что-то в мозгах ещё до конца не щёлкнуло относительно динамики-рефлексии-типизации... Отсюда недооценка значимости многих средств. Вот ведь разработчикам компилятора наверняка даже в голову прийти не могло, что какой-то псих будет так dynamic_cast использовать. |
Автор: | Vlad [ Четверг, 13 Март, 2008 17:55 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Илья Ермаков писал(а): Влад, а согласитесь, что дело, в общем, не в реализации. А в том, что в Си-мире что-то в мозгах ещё до конца не щёлкнуло относительно динамики-рефлексии-типизации... Отсюда недооценка значимости многих средств. Ага. У меня вот тоже еще не "щелкнуло" - куда можно приткнуть именно свитч по типам. В смысле я представляю как оно используется в оберонах, но почему-то в задачах, котрые я решаю на C++, оказывается удобнее использовать старые добрые виртуальные функции или механизмы метапрограммирования. Илья Ермаков писал(а): Вот ведь разработчикам компилятора наверняка даже в голову прийти не могло, что какой-то псих будет так dynamic_cast использовать. dynamic_cast слишком тяжеловесен, потому что учитывает множественное и виртуальное наследование. Если ограничится "oberon-style" расширением типов, то можно и на C++ написать эффективную динамическую проверку типа. |
Автор: | Vlad [ Четверг, 13 Март, 2008 18:33 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Илья Ермаков писал(а): Вот ведь разработчикам компилятора наверняка даже в голову прийти не могло, что какой-то псих будет так dynamic_cast использовать. Прикинув, что это интересная задачка, я реализовал "obron cast" для "oberon-style расширений типа". Вот что получилось: Код: #include "oberon_cast.h" struct X : oberon::inherit<X> { }; struct X1 : oberon::inherit<X1, X> { }; struct X2 : oberon::inherit<X2, X1> { }; struct X3 : oberon::inherit<X3, X2> { }; void check_type(const X &x) { if (const X3 *x3 = oberon::cast<X3>(x)) handle3(*x3); else if (const X2 *x2 = oberon::cast<X2>(x)) handle2(*x2); else if (const X1 *x1 = oberon::cast<X1>(x)) handle1(*x1); else handle(x); } Так как все стало очень быстро, то я увеличил количество итераций. Вот результат: BB: 24 c VC9: 19 c Вывод: если очень хочется, то можно и на C++ Можно сделать еще быстрее, если ограничить число глубину наследований разумным числом (вряд ли на практике глубина будет больше 10). А вот и заветный "oberon_cast.h" для тех, кто вынужден писать на C++ (Владимир Лось?) и ему не хватает эффективного "oberon message bus" в C++ В решении не используются нестандартные расширения, голый C++. Компилируется VC/gcc/comeau. Код: namespace oberon {
typedef const int *type_signature; struct type_hierarchy { type_signature *m_phierarchy; int m_cn; }; struct type { static const int k_cn_inherited = -1; type() : m_type(0) {} const type_hierarchy *m_type; }; template <typename T> void init_type_info(type_signature *hierarchy) { hierarchy[T::k_cn_inherited] = &T::k_cn_inherited; init_type_info<typename T::base>(hierarchy); } template <> inline void init_type_info<type>(type_signature *hierarchy) { } template <typename T, typename B = type> struct inherit : B { typedef B base; static const int k_cn_inherited = base::k_cn_inherited + 1; struct type_info : type_hierarchy { type_signature m_hierarchy[k_cn_inherited + 1]; type_info() { m_phierarchy = m_hierarchy; m_cn = k_cn_inherited; init_type_info<T>(m_hierarchy); } }; inherit() { static type_info s_type_info; this->m_type = &s_type_info; } }; template <typename T> const T * cast(const type &o) { const type_hierarchy &dynamic_type = *o.m_type; if (dynamic_type.m_cn < T::k_cn_inherited || dynamic_type.m_phierarchy[T::k_cn_inherited] != &T::k_cn_inherited) return 0; return static_cast<const T *>(&o); } } // namespace oberon |
Автор: | Geniepro [ Четверг, 13 Март, 2008 18:46 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Ещё любопытнее, что вот такой код работает чуть дольше: Код: MODULE TestCase; Ваш тест у меня (Celeron 1.7) работает 6.25 сек, этот мой тест -- 7.0 сек, а на сам цикл уходит 0.25 сек...PROCEDURE handle (x: INTEGER); END handle; PROCEDURE handle1(x: INTEGER); END handle1; PROCEDURE handle2(x: INTEGER); END handle2; PROCEDURE handle3(x: INTEGER); END handle3; PROCEDURE test(x: INTEGER); BEGIN CASE x OF | 3: handle3(x); | 2: handle2(x); | 1: handle1(x); ELSE handle (x); END END test; PROCEDURE Do*(); VAR i: INTEGER; BEGIN FOR i := 0 TO 100000000 DO test(0); test(1); test(2); test(3); END END Do; END TestCase. Похоже WITH сделан очень даже неплохо, CASE и то хуже... :о) Что бы это значило? :о)) Переписал этот код на Си: Код: void handle (int x) { } Скомпилировал простейшим компилятором TinyCC, который генерирует весьма посредственный код, зато компилирует сверхбыстро, так время работы программы -- те же 7 сек. То есть Блэкбоксовый компилятор генерирует примерно такой же код, что и посредственный компилятор С... :о)void handle1(int x) { } void handle2(int x) { } void handle3(int x) { } void test(int x) { switch(x) { case 3: handle3(x); break; case 2: handle2(x); break; case 1: handle1(x); break; default: handle (x); break; } } void main(void) { int i; for (i = 0; i < 100000000; i++) { test(0); test(1); test(2); test(3); } } А вот GCC обошёлся круто -- 0.125 сек. Видимо, он там всё повыбрасывал, что мог... :о) Vlad писал(а): Вывод: решения на основе "oberon message bus" с использованием dynamic_cast в C++ действительно могут оказаться неэффективными с точки зрения производительности. Разница в скорости динамической проверки типа порядка 20 раз. Это спорное утверждение. В реальных программах все эти handlex будут занимать гораздо большее время, чем эти проверки типов, так что падение производительности будет не так заметно...
|
Автор: | Илья Ермаков [ Четверг, 13 Март, 2008 18:57 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Geniepro писал(а): Похоже WITH сделан очень даже неплохо, CASE и то хуже... :о) Что бы это значило? :о)) Это "бы значило", что все эти сравнения, когда речь не идёт об очевидных отличиях в разы (да и то проверять правильность постановки эксперимента надо), абсолютно произвольны, хотя бы в силу того, что мы работаем на Intel, который (в силу кеша, собственных оптимизаций и в силу того, что является в некотором роде виртуальной машиной на микрокоде) может вносить огроменные погрешности даже для практически одинакового маш. кода. |
Автор: | Vlad [ Четверг, 13 Март, 2008 20:48 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Geniepro писал(а): Похоже WITH сделан очень даже неплохо, CASE и то хуже... :о) Что бы это значило? :о)) Скорее всего основное время отжирает вызов функций, а несущественную разницу в результатах вносят особенности растактовки процессора для конкретного кода. |
Автор: | Сергей Губанов [ Пятница, 14 Март, 2008 11:51 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Vlad писал(а): А вот и заветный "oberon_cast.h" для тех, кто вынужден писать на C++ (Владимир Лось?) и ему не хватает эффективного "oberon message bus" в C++ :) В решении не используются нестандартные расширения, голый C++. Компилируется VC/gcc/comeau. Есть ещё одна деталь. В вашей реализации тег типа (указатель на дескриптор типа) внедрён в структуру. То есть размер структуры получается всегда на 4 (или на 8) байтов больше чем сумма размеров её полей. Если мы разместим такую тегированную структуру в массиве, то размер массива увеличится на N * 4 (или на 8) байтов, где N - длина массива. В обероне же этого не произойдёт. Там компилятор помещает тег типа структуры в дескриптор типа массива и никакого перерасхода памяти не происходит. То же самое происходит при внедрении тегированной структуры внутрь другой структуры -- опять её тег помещается в дескриптор типа структуры контейнера. То есть структура есть сама по себе, а тег её типа есть сам по себе, но компилятор всегда занет откуда его взять. Когда мы пишем в обероне: PROCEDURE Procedure (VAR r: MyRecord); то компилятор должен сгенерировать не один аргумент, а два -- тег типа передаётся в процедуру отдельно ("скрытым параметром"). В точке вызова этой процедуры компилятору известно откуда взять тег типа, вот он его автоматически и подставит. |
Автор: | Vlad [ Пятница, 14 Март, 2008 17:01 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Сергей Губанов писал(а): Есть ещё одна деталь. В вашей реализации тег типа (указатель на дескриптор типа) внедрён в структуру. То есть размер структуры получается всегда на 4 (или на байтов больше чем сумма размеров её полей. Если мы разместим такую тегированную структуру в массиве, то размер массива увеличится на N * 4 (или на байтов, где N - длина массива. В обероне же этого не произойдёт 1. Для организации message bus не нужны массивы структур. 2. Динамическая проверка типа вообще не имеет смысла для массива, тип его элементов всегда известен на этапе компиляции. Сергей Губанов писал(а): То же самое происходит при внедрении тегированной структуры внутрь другой структуры -- опять её тег помещается в дескриптор типа структуры контейнера. Ну и какая разница где эти 4(8) байтов будут отжирать память - в аггрегированной структуре или в аггрегирующей (или в довеске, который ходит рядом с ними)? Сергей Губанов писал(а): То есть структура есть сама по себе, а тег её типа есть сам по себе, но компилятор всегда занет откуда его взять. Когда мы пишем в обероне: PROCEDURE Procedure (VAR r: MyRecord); то компилятор должен сгенерировать не один аргумент, а два -- тег типа передаётся в процедуру отдельно ("скрытым параметром"). Покажите мне документ, в котором написано, что "компилятор должен..."? В описании языка этого нет. Я понимаю зачем в реализации оберона разумно сделать именно так, но все же это особенности реализации. И я не пытался сдеалать оберон из C++. Я решил конкретную задачу: "быстрая проверка динамического типа на C++". Решил ее применительно к считающемуся чуть ли не эксклюзивным для оберонов паттерну "message bus". Какого-то принципиального оверхеда применительно к этому паттерну вроде как нет. Есть немного вычурная запись для описания типов, ну и запись проверки типа не такая краткая как в обероне. Но зато мне не пришлось переписывать рантайм или компилятор |
Автор: | PGR [ Пятница, 14 Март, 2008 21:46 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Тот же тест для Java: Код: package pgr.tests; class X {} class X1 extends X {} class X2 extends X1 {} class X3 extends X2 {} public class TestCast { private static void handle(X x) {} private static void handle1(X1 x) {} private static void handle2(X2 x) {} private static void handle3(X3 x) {} public static void main(String[] args) { long t1 = System.currentTimeMillis(); mainTest(); long t2 = System.currentTimeMillis(); System.out.println(t2 - t1); } private static void mainTest() { X x = new X(); X1 x1 = new X1(); X2 x2 = new X2(); X3 x3 = new X3(); for (int i = 0; i <= 100000000; i++) { testCast(x); testCast(x1); testCast(x2); testCast(x3); } } private static void testCast(X x) { if (x instanceof X3) { handle3((X3) x); } else if (x instanceof X2) { handle2((X2) x); } else if (x instanceof X1) { handle1((X1) x); } else { handle(x); } } } Java: 4 c BlackBox: 4.3 c |
Автор: | Илья Ермаков [ Пятница, 14 Март, 2008 22:08 ] |
Заголовок сообщения: | Re: Эффективность WITH |
А вот с Java сравнивать неуместно - в Java Вы точно не станете использовать Message Bus в тех случаях, когда он применяется в Обероне. В Яве каждый экземпляр сообщения динамический. Таким образом, если в Обероне я не задумываясь могу заменить вызов процедуры на посылку сообщения, то в Яве уже нет (представьте себе, какая нагрузка на динамику будет, если приличная частота использования шины). |
Автор: | Евгений Темиргалеев [ Пятница, 14 Март, 2008 22:34 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Vlad писал(а): ...Ну и какая разница где эти 4(8) байтов будут отжирать память - в аггрегированной структуре или в аггрегирующей (или в довеске, который ходит рядом с ними)? ... Покажите мне документ, в котором написано, что "компилятор должен..."? В описании языка этого нет. Я понимаю зачем в реализации оберона разумно сделать именно так, но все же это особенности реализации. И я не пытался сдеалать оберон из C++. Разница есть: - описание типа лежит в единственном экземпляре для обоих типов структур (на все экземпляры этих типов); - тег типа аггрегированной структуры присутствует только внутри описания типа аггрегирующей; - при использовании аггрегирующей структуры ходит только её тег типа - экономия 4(8) байтов при единичном вложении. Language report писал(а): Appendix D: Mandatory Requirements for Environment Компилятор должен удовлетворять требованию 1. Как он это будет делать, действительно, особенности.
The Component Pascal definition implicitly relies on three fundamental assumptions. 1) There exists some run-time type information that allows to check the dynamic type of an object. This is necessary to implement type tests and type guards. 2) ... 3) ... An implementation that doesn't fulfill these compiler and environment requirements is not compliant with Component Pascal. |
Автор: | Vlad [ Суббота, 15 Март, 2008 03:11 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Илья Ермаков писал(а): В Яве каждый экземпляр сообщения динамический. В Яве GC по-приличее будет. И оптимизатор присутствует. Так что все не так однозначно. |
Автор: | PGR [ Суббота, 15 Март, 2008 16:17 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Илья Ермаков писал(а): А вот с Java сравнивать неуместно - в Java Вы точно не станете использовать Message Bus в тех случаях, когда он применяется в Обероне. В Яве каждый экземпляр сообщения динамический. Таким образом, если в Обероне я не задумываясь могу заменить вызов процедуры на посылку сообщения, то в Яве уже нет (представьте себе, какая нагрузка на динамику будет, если приличная частота использования шины). А что ж тогда использовать вместо Message Bus в Java? Да и с учётом оптимизатора, как уже написал Vlad, нагрузка на динамику может быть меньше, чем это себе можно представить... |
Автор: | Илья Ермаков [ Суббота, 15 Март, 2008 23:25 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Я не говорю, что это слишком неэффективно. Смотря для чего. Имею в виду только то, что это оказывается уже несопоставимо с простым вызовом процедуры. Например, графическая подсистема на сообщениях вместо методов, как в ББ, уже не пойдёт... разве что поползёт А для многоуровневых контейнеров с разношёрстными компонентами сообщения очень удобны. |
Автор: | Info21 [ Воскресенье, 16 Март, 2008 13:44 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Илья Ермаков писал(а): ... многоуровневых контейнеров с разношёрстными компонентами Надо запомнить термин, а то мычишь-мычишь... |
Автор: | Сергей Губанов [ Воскресенье, 16 Март, 2008 17:51 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Vlad писал(а): Динамическая проверка типа вообще не имеет смысла для массива Так не для массива! Пусть есть массив array: ARRAY 100 OF MyMessageObject; или запись с полем Код: MyRecord = RECORD ... field1: MyMessageObject; field2: MyMessageObject; field3: MyMessageObject; ... END; и есть обработчик PROCEDURE Handle (VAR msg: Message); тогда вызовы Handle(array[42]) и Handle(myRecord.field2) вполне корректны не смотря на то, что в памяти по адресу ADR(array[42]) или ADR(myRecord.field2) тега типа MyMessageObject нигде поблизости не записано (тег типа находится в дескрипторе типа массива array или дескриптора типа MyRecord). Компилятор передаст тег типа MyMessageObject внутрь процедуры Handle неявно. |
Автор: | Vlad [ Понедельник, 17 Март, 2008 03:05 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Сергей Губанов писал(а): тогда вызовы Handle(array[42]) и Handle(myRecord.field2) вполне корректны не смотря на то, что в памяти по адресу ADR(array[42]) или ADR(myRecord.field2) тега типа MyMessageObject нигде поблизости не записано Таки это частный случай и никакого отношения к организации message bus не имеет. Хотя если очень хочется, то можно сделать преобразование "структура без тега" <-> "структура с тегом". Ну серьезно, зачем может понадобиться массив сообщений? Контейнер абстрактных ссылок на сообщения - да, можно представить. А просто массив сообщений определенного типа - я не могу представить. |
Автор: | Vlad [ Понедельник, 17 Март, 2008 19:02 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Сергей Губанов писал(а): Компилятор передаст тег типа MyMessageObject внутрь процедуры Handle неявно. Дабы не быть голословным, вот чуть-чуть измененная реализация, в которой нет никаких "лишних байтов". В исходном примере поменялась только сигнатура хэндлера: Код: void check_type(const oberon::tagged<X> &x) oberon_cast.h: Код: namespace oberon {
typedef const int *type_signature; struct type_hierarchy { type_signature *m_phierarchy; int m_cn; }; struct type { static const int k_cn_inherited = -1; }; template <typename T> void init_type_info(type_signature *hierarchy) { hierarchy[T::k_cn_inherited] = &T::k_cn_inherited; init_type_info<typename T::base>(hierarchy); } template <> inline void init_type_info<type>(type_signature *hierarchy) { } template <typename T, typename B = type> struct inherit : B { typedef B base; static const int k_cn_inherited = base::k_cn_inherited + 1; struct type_info : type_hierarchy { type_signature m_hierarchy[k_cn_inherited + 1]; type_info() { m_phierarchy = m_hierarchy; m_cn = k_cn_inherited; init_type_info<T>(m_hierarchy); } }; }; template <typename T> struct tagged { template <typename U> tagged(const U &o) : m_o(o) { static U::type_info s_type_info; this->m_type = &s_type_info; } const T &operator * () const {return m_o;} const T &m_o; const type_hierarchy *m_type; }; template <typename T, typename U> const T * cast(const tagged<U> &o) { const type_hierarchy &dynamic_type = *o.m_type; if (dynamic_type.m_cn < T::k_cn_inherited || dynamic_type.m_phierarchy[T::k_cn_inherited] != &T::k_cn_inherited) return 0; return static_cast<const T *>(&o.m_o); } } // namespace oberon |
Автор: | Евгений Темиргалеев [ Вторник, 18 Март, 2008 00:01 ] |
Заголовок сообщения: | Re: Эффективность WITH |
Код: struct type В C++ уже можно определять значения константных статических членов внутри класса? Эх, отстал я от жизни Раньше это делали при помощи enum.
{ static const int k_cn_inherited = -1; }; |
Страница 1 из 3 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |