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;

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.
Ваш тест у меня (Celeron 1.7) работает 6.25 сек, этот мой тест -- 7.0 сек, а на сам цикл уходит 0.25 сек...
Похоже WITH сделан очень даже неплохо, CASE и то хуже... :о) Что бы это значило? :о))

Переписал этот код на Си:
Код:
void handle (int x) { }
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);
    }
}
Скомпилировал простейшим компилятором TinyCC, который генерирует весьма посредственный код, зато компилирует сверхбыстро, так время работы программы -- те же 7 сек. То есть Блэкбоксовый компилятор генерирует примерно такой же код, что и посредственный компилятор С... :о)
А вот 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 (или на 8) байтов больше чем сумма размеров её полей. Если мы разместим такую тегированную структуру в массиве, то размер массива увеличится на N * 4 (или на 8) байтов, где 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
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.
Компилятор должен удовлетворять требованию 1. Как он это будет делать, действительно, особенности.

Автор:  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
{
    static const int k_cn_inherited = -1;
};
В C++ уже можно определять значения константных статических членов внутри класса? Эх, отстал я от жизни :) Раньше это делали при помощи enum.

Страница 1 из 3 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/