Страницы

Скорость ООП сортировки вставками на Oberon, Objective-C, C++, Go


Продолжаю тестировать транслятор Оберона из проекта "Восток". На сей раз мой взор пал на производительность при использовании объектно ориентированного подхода. Ранее я уже проводил сравнение для Си, Objective-C, C++ на примере сортировки вставками. Недостатком того воплощения было то, что в нём испытывался только вызов виртуального метода, а безопасного приведения от общего типа к расширенному не было. Для Си это требовало написания большего количества текста, чем нужно, поэтому и для остальных языков оно было исключено. Теперь, когда у меня есть транслятор Оберона в Си, эту возможность задействовать куда проще, поэтому я соответствующим образом подправил тест, также заменив Си на Оберон.

Результаты интересные, судите сами.

Скорость пузырьковой сортировки на Oberon, C++, Go, Rust


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

Одним из преимуществ использования транслятора Оберона перед непосредственным написанием кода на C/C++ является лёгкая возможность добавления проверок границ массива и использования неинициализированных переменных. Современные компиляторы Си тоже не так просты и позволяют добавлять некоторые проверки (-fsanitize), впрочем, рассматриваемые авторами только как отладочная возможность. Сравним эти возможности.

Время работы с проверками границ массива
Язык:С++ vector.atС++ vector[]GoOberonRust
Опции компилятора:clang++ -O3-O3 -fsanitize=addressgo buildo7c | clang -O3rustc -O -C lto
Время сек.:1.411.081.840.540.52

Транслятор Оберона вставляет проверки с помощью стандартного для Си assert, поэтому для их отключения достаточно объявить макрос NDEBUG при компиляции.

Время работы без проверок границ массива
Язык:С++ vector[]OberonRust
Опции компилятора:clang++ -O3o7c | clang -DNDEBUG -O3rustc -opt-level=3 -C lto
Время сек.:0.530.470.52

Результаты забавные - программа на Обероне оказалась в 2-а раза быстрей С++ и лишь слегка уступила самому быстрому варианту на Rust для сортировки с проверкой границ, и оказалась самой быстрой для сортировки без проверки. С учётом того, что Оберон транслируется в Си, то это, по сути, победа Си. С той поправкой, что написание защищённой программы сразу на Си потребует от программиста бОльших усилий за счёт явного прописывания проверок и неизбежного допущения какого-то количества дополнительных ошибок при этом процессе.

Тестовая среда
OS:GNU/Linux Ubuntu 16.04
CPU:Intel i3-4160 3.60GHz
clang:3.5
go:1.6.2
rustc:1.7.0

Проект Восток. Поехали

Сообщения о трансляторе переехали в отдельный блог.

Выложил на github исходный код проекта "Восток", который представляет из себя транслятор Оберона. Это нулевая версия, и пока весьма нестабильная. Впрочем, транслятор может не так уж и мало - собрать сам себя, так как в лучших паскалевских традициях написан на собственном входном языке - Oberon-07.

Проект задумывался для возможности партизанского программирования в тылу у противника - коммерчески востребованных языков программирования, используя его как генератор C, C++, Javascript, Java кода и других. Для этого у Oberon есть все предпосылки: язык достаточно прост, чтобы его транслятор можно было создать 1-му человеку, отсутствие навороченных абстракций и низкоуровневых возможностей на уровне ядра языка позволяет относительно легко отображать его на другие языки программирования - как низкоуровневые, так и высокоуровневые, и при этом сам язык достаточно мощен, гибок и защищён от ошибок, чтобы программирование на нём было вполне удобным. Практический смысл этого - возможность использовать один и тот же код на самых разных платформах. Ранее для такой цели я использовал C, но удобным это назвать было сложно.

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

Но пока предстоит немало потрудиться над стабильностью транслятора и над качеством производимого C-кода, поэтому о других целях говорить рано.

Программирование без рекурсии

Многие рекомендации по программированию надёжных систем, в частности MISRA C, запрещают использование прямой или косвенной рекурсии из-за плохой предсказуемости этого подхода. В принципе, это разумно, учитывая «железячную» область применения таких рекомендаций — в ней практически нет потребности в рекурсивных алгоритмах, а эквивалентные циклические алгоритмы в императивных языках всегда будут выигрывать. Но что будет, если попытаться применить это жёсткое требование к универсальным применениям? Возможно ли нормальное программирование без рекурсии?

Естественно, меня интересуют алгоритмы рекурсивные по своей природе, так как для нерекурсивных ответ очевиден. Такие алгоритмы при запрете рекурсивных вызовов потребуют использования явной реализации рекурсии вместо встроенной.

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

Напишем грамматику исходного языка выражений на РБНФ:
expr = adder { ('+' | '-') adder }. 
adder = mult { ('*' | '/') mult }.
mult = number | '(' expr ')'.
number = digit { digit }.
digit = '0' .. '9'.
Для реализации я выбрал язык Go. Такой код у меня получился при использовании рекурсии:

Причина неприятия матерщины в кино.

     Я один из тех людей, кого раздражает грубая ругань в искусстве вообще и в кино, в частности. Раздражает даже в тех моментах, где она казалось бы уместна.

    Мне самому эта особенность казалась странной. Почему в кино, где по сценарию могут происходить ужасные вещи, вроде насилия и убийства, меня раздражает куда менее серьёзная вещь - матерная ругань?

Вы используете sudo неправильно или фундаментальная проблема $PATH

    Никогда не видел, чтобы хотя бы где-то правильно указывали, как использовать sudo. Ни-ко-гда. Во всех официальных инструкциях, в книгах, в статьях, на форумах — везде предлагают использовать sudo неправильно. И ни один из известных мне дистрибутивов GNU/Linux не препятствует этому.

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

   В чём же проблема?

Объектно-ориентированное программирование в Си(без ++). Пример

Я вижу лишь одну причину использовать ООП в Си - это желание иметь один интерфейс для по-разному реализованных сущностей-объектов, в том числе и не написанных на момент создания кода, использующего этот единый интерфейс. Эта ситуация часто возникает при создании библиотек для организации обратной связи либо для однообразного обращения к разнородным источникам данных. Для решения этой задачи достаточно подхода Абстрактный Интерфейс — Реализация, который может быть легко реализован в чистом Си с помощью функциональных переменных и возможности использования указателей на структуры, без предварительного указания их содержимого.

Объявим интерфейс объекта в object.h:

typedef struct Object_ClosedRealization Object;
typedef struct Object_ContextRealization ObjectContext;

С указателем на Object будет взаимодействовать клиент интерфейса. ObjectContext нужен реализации интерфейса для передачи контекста объекта в его методы; переменную этого типа можно воспринимать как аналог this во многих ООП — языках.

Добавим объявление функции создания экземпляра объекта и его методы:

extern Object* objectCreate(
    ObjectContext **context, int contextSize,
    int method(ObjectContext *c, int a),
    void release(ObjectContext *c));

extern int objectMethod(Object *o, int a);
extern void objectRelease(Object **o);

Функция objectCreate нужна только при реализации интерфейса, функции objectMethod и objectRelease будут использованы клиентским кодом.

Создадим object.c, нужный для поддержки интерфейса объекта во время исполнения:

/* В месте этого объявления содержимое структуры увязывается с ранее объявленным Object. При этом, содержимое доступно только в object.c */

struct Object_ClosedRealization {
    int (*method)(ObjectContext *c, int a);
    void (*release)(ObjectContext *c);
    ObjectContext *context;
};

extern Object* objectCreate(
    ObjectContext **c, int contextSize,
    int method(ObjectContext *c, int a),
    void release(ObjectContext *c))
{
    Object *o;
    o = (Object *)malloc(sizeof(Object) + contextSize);
    o->method = method;
    o->release = release;
    o->context = (ObjectContext *)(sizeof(Object) + (long unsigned)o);
    *c = o->context;
    return o;
}

extern int objectMethod(Object *o, int a) {
    return o->method(o->context, a);
}

extern void objectRelease(Object **o) {
    if (NULL != *o) {
        (*o)->release((*o)->context);
        free(*o);
        *o = NULL;
    }
}

Как видно из реализации objectMethod, можно было бы обойтись и вызовом метода в виде o->method(o->context, a) без введения специальной функции, но тогда бы пришлось открывать полный доступ ко внутренней структуре для пользователя интерфейса, что нежелательно по многим причинам.

Создадим парочку реализаций интерфейса.

object-mult.c:

/* Тело структуры опять объявлено внутри Си-файла, поэтому её содержимое скрыто от стороннего кода */

struct Object_ContextRealization {
    int mult;
};

/* Методы должны быть объявлены как static, чтобы не мешаться в общей области видимости. Связываются они всё равно через указатели */

static int method(ObjectContext *this, int a) {
    printf("%d * %d", a, this->mult);
    return a * this->mult;
}

static void release(ObjectContext *this) {
    printf("object-mult %d released\n", this->mult);
}

/* в ООП терминах функция objectMultCreate наиболее близка к фабрике типов, но не конструктору */

extern Object* objectMultCreate(int mult) {
    Object *o;
    ObjectContext *c;
    /* связывание методов с объектом через функциональные переменные*/
    o = objectCreate(&c, sizeof(ObjectContext), method, release);
    c->mult = mult;
    return o;
}

Создадим аналогичный файл object-add.c, в котором умножение заменим на сложение. Его содержимое мы пропустим, так как его отличия от object-mult.c тривиальны.

Теперь напишем код main.c, который всё это использует:

extern int main(void) {
    Object *a[4];
    int i, j;

    /* создадим комбинацию из 2-х реализаций с 2-мя контекстами */
    a[0] = objectMultCreate(1);
    a[1] = objectAddCreate(1);
    a[2] = objectAddCreate(2);
    a[3] = objectMultCreate(2);

    for (i = 0; i < sizeof(a) / sizeof(a[0]); ++i) {
        printf("%d) ", i);
        /* вызов одной и той же функции-метода с одинаковым 
           параметром для разных указателей-объектов */
        j = objectMethod(a[i], 3);
        printf(" = %d\n", j);
    }

    for (i = 0; i < sizeof(a) / sizeof(a[0]); ++i) {
        objectRelease(a + i);
    }

    return 0;
}

Результат работы программы — примера:

0) 3 * 1 = 3
1) 3 + 1 = 4
2) 3 + 2 = 5
3) 3 * 2 = 6
object-mult(1) released
object-add(1) released
object-add(2) released
object-mult(2) released

Итак, что же получилось:

  1. Простейшее наследование объектов Интерфейс — Реализация.
  2. Настоящее динамическое ООП — более одной реализации одного интерфейса могут сосуществовать в одной области видимости одновременно.
  3. Содержимое объектов недоступно извне в обход методов.
  4. Типизированные указатели объектов, что даёт отслеживание компилятором ошибки присваиваний между разными интерфейсами.
  5. Чистый Си без дополнительных библиотек и магии макросов.
  6. Довольно объёмно по количеству кода и непривычный для ООП вызов методов за счёт необходимости явного выписывания того, что в ООП-языках подразумевается неявно.

Полный исходный код примера доступен на github.

Три года назад я сравнивал производительность такого подхода со встроенными возможностями ООП в C++ и Objective-C.