воскресенье, 21 ноября 2010 г.

Оберон & real to integer

Для справки: Oberon, Oberon2 (в дальнейшем O2), ComponentPascal (CP), считается в определенных кругах (в прицнипе не без причин) эталоном базисности и простоты. Эдакий базис императивных языков. BlackBox component builder (в дальнейшем ЧорныйЯщик) -- самая популярная реализация оного Component Pascal'я особенно в постсоветском пространстве.

Однако, как показывает практика и на старуху бывает проруха. В тех несчастных 20ти страницах описания языка тоже можно сесть в лужу и отойти от той самой базисности.

В процессе ковыряния oo2c и, заодно, сообщений о языках O2 и CP выяснил интересную вещь. Оказывается в O2 и CP НЕТ простого и быстрого способа конвертации real -> integer. Т.е. чтобы это выражалось в одну машинную инструкцию. Подобные преобразования в обероне-2 и CP (до оберона я пока не добрался) занимают примерно в ДВА раза больше времени нежели в иных языках. Ну и имеют другую, более сложную семантику. А также не отображается на прямую в одну sse инструкцию. Преобразование real->integer в Обероне2 и CP осуществляется посредством встроенной функции ENTIER.

ENTIER работает аналогично связке стандартной сишной функции floor + преобразование типов. т.е. ENTIER(x) = (int)floor(x); Чего-то более простого в арсенале оберонщика нет.

Вот такой вот код на Обероне-2 собранный oo2c:
MODULE T;
IMPORT Out, SYSTEM;
CONST
N = 10000;
PI = 3.1415;
VAR
r : LONGINT
I : LONGINT;
J : LONGINT;
BEGIN
I := N;
J := I;
WHILE I > 0 DO
WHILE J > 0 DO
r := ENTIER(PI*J*I);
DEC(J);
END;
DEC(I);
J := N;
END;
END T.
Отрабатывает за 3.4 секунды. (никаких оптимизаций).
Вот такой вот код на С++:
int main()
{
const float pi = 3.1415;
const int n = 10000;
int r = 0;

for (int i = n; i>0; i--)
for (int j = n; j>0; j--)
r = (int)(pi*i*j);
}
Отрабатывает за 1.6 секунды.
Если строчку r = (int)(pi*i*j); заменить на r = (int)floorf(pi*i*j); то будут те же самые 3.4 секунды. Да, оптимизация естественно отключена.

С готишным ЧорнымЯщиком вообще всё весело. Код:
MODULE Test;

IMPORT StdLog, Services;

CONST
N = 10000;
PI = 3.1415;

PROCEDURE Do*;
VAR t: LONGINT;
I : LONGINT;
J : LONGINT;
r : LONGINT;
BEGIN
t := Services.Ticks();
I := N;
J := I;

WHILE I > 0 DO
WHILE J > 0 DO
r := ENTIER(PI*J*I);
DEC(J);
END;
DEC(I);
J := N;
END;

t := Services.Ticks() - t;
StdLog.Int(SHORT(t))
END Do;

END Test.
Обычно функция Do отрабатывает где-то за 3.7-3.8 секунды. Однако иногда, ВНЕЗАПНО время подскакивает почти в два раза:
3759 3744 4992 3744 ...
3744 3759 3807 7441 3806 3775 4446 7800 3744 3744 3744
Да, система при этом ничем постороннем не загружена.

PS. В Обероне-07 всё это поправлено. Там ENTIER заменен на FLOOR, который не floor, а который простое отбрасывание дробной части, т.е. FLOOR(x) = (int)(x);

PPS. Первоначально этот пост был отправлен на форум оберонщиков всея руси, однако наши оберонщики, как показала практика, критики своего языка-фетиша не выдерживают ни в каком виде, и посему пост был моментально перемещен в закрытую от посторонних глаз секцию форума (видимо, чтобы нагуглить "компромат" на оберон было не возможно).

4 комментария:

valexey комментирует...

В оригинальной ветке кто-то заметил, что:
> Функция ENTIER универсальная,
> убивает сразу 3-х зайцев (round,
> ceil, floor)

По этому поводу я написал отдельный пост: http://valexey.blogspot.com/2010/11/floor-trunc.html

Анонимный комментирует...

Сергей Губанов ответил:
Хрень намеряли.

1) Блэкбоксовскому REAL в С/С++ соответствует double, а не float.
2) Блэкбоксовскому LONGINT в С/С++ соответствует 64-битный long long.

Это в Обероне LONGINT 32-битный, а в Компонентном Паскале он 64-битный.

Для ББ сделайте INTEGER <--> int, REAL <--> double.

Заменил ошибочно использованный 64-битный LONGINT на 32-битный INTEGER и скорость Блэкбоксовой программы увеличилась более чем в 2.5 раза.

Было 3047, стало 1187

3047 / 1187.0 = 2.56698

valexey комментирует...

Во-первых на счет оберона-2 это вы всё врёте. Там LONGINT это не 32 бита, равно как и в C/C++ int это не 32 бита. И там и там битность зависит от реализации и от платформы. Репорт в первом и стандарт во втором никак не ограничивает фантазию разработчика компилятора (кроме того, что LONGINT >= INTEGER и т.п.).

Во-вторых непосредственно тип REAL я нигде в тесте не использовал. Использовались лишь литералы. Вопрос -- как указать компилятору что этот литерал должен иметь тип SHORTREAL?

В-третьих встроенная функция ENTIER всегда возвращает именно LONGINT. Вернуть INTEGER она физически не способна. Поэтому потребуется "преобразование" типов. Преобразование в кавычках т.к. на САМОМ ДЕЛЕ там будет преобразование типов в том случае если не сделать преобразование типов. От того и тормоза. Крайне очевидная логика, не правда ли?

А на счет скорости -- там скорее всего hand made функция вроде той что написал я.

Смоей функцией Floor сишненький код у меня работает где-то за 1.4 секунды c использованием sse инструкций, и 1.5-1.6 секунды без использования оной. Тест с преобразованием типов (т.е. без преобразований типов) в ЧорномЯщике работает 1.5-1.6 секунды. Как видим, чудес не бывает.

Простой Trunk без sse работает 1.5-1.6, с sse работает за 1.2 секунды (да, это всё на старом-старом gcc, под виндой. на новом и под линуксом где-то за 0.4 секунды, да без оптимизаций естественно).

Unknown комментирует...

Реквестирую добавление тега "клеветы". ;-)