OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 12 Декабрь, 2019 02:05

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.
Автор Сообщение
СообщениеДобавлено: Вторник, 16 Февраль, 2010 00:11 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2318
Откуда: Россия, Томск
Выделено: viewtopic.php?p=42858#p42858

Интереса ради сравнил скорость выполнения трёх написанных мною примеров. Естественно, единица измерения - секунды, делённые на сферических попугаев в вакууме (сек/спв).

Взята матрица arr: ARRAY 1000, 1000 OF INTEGER (16-битные слова в XDS). Во все элементы помещены значения 999, и только последний элемент arr[999, 999] := 1000. Соответственно, сделан поиск значения 1000 тремя вышеприведенными программами по 1000 раз (взято минимальное значение времени из 11 запусков подряд).

Результаты замеров (чем меньше, тем лучше):
- один WHILE: 13.635 сек/спв;
- два вложенных WHILE: 6.804 сек/спв;
- с локальной процедурой: 2.422 сек/спв. WIN!

Потом подумал: "Ой, чего это я в отладочном режиме проверяю?!" Включил всю оптимизацию, отключил все рантайм-проверки и запустил снова.
Результаты (чем меньше, тем лучше):
- один WHILE: 2.376 сек/спв;
- два вложенных WHILE: 1.279 сек/спв;
- с локальной процедурой: 0.813 сек/спв; WIN!

Прирост производительности за счёт оптимизации составил (чем меньше, тем лучше):
- один WHILE: 13.635/2.376=5.7386;
- два вложенных WHILE: 6.804/1.279=5.3198;
- с локальной процедурой: 2.422/0.813=2.9791. WIN!

Получается, что поиск с использованием локальной процедуры выигрывает по всем статьям. В случае с включенной оптимизацией он в полтора раза быстрее двух вложенных WHILE (из-за вынужденных лишних IF-ов внутри, которые тормозят работу), и в три раза быстрее единственного WHILE. В случае с отключенной оптимизацией, то есть, когда всякие проверки индексов выполняются в полном объёме, он почти в три раза быстрее двух WHILE и в пять с половиной раз быстрее одного WHILE. При этом состоит из простейших компонентов - паттерновых линейных поисков - и увеличивает читабельность, давая процедурное имя внутреннему циклу. Как говорится, EPIC WIN.

Два вложенных WHILE вдвое быстрее одного WHILE, что тоже интересно. : )

Если кому-то хочется, могу выложить исходники проекта на XDS.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Вторник, 16 Февраль, 2010 09:05 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1040
Откуда: Россия, Чебоксары
Александр Ильин писал(а):
Получается, что поиск с использованием локальной процедуры выигрывает по всем статьям. В случае с включенной оптимизацией он в полтора раза быстрее двух вложенных WHILE (из-за вынужденных лишних IF-ов внутри, которые тормозят работу), и в три раза быстрее единственного WHILE. В случае с отключенной оптимизацией, то есть, когда всякие проверки индексов выполняются в полном объёме, он почти в три раза быстрее двух WHILE и в пять с половиной раз быстрее одного WHILE.
Тестирование некорректно, как и анализ результатов.

1) В принципе вариант с процедурой не может быть эффективнее двух вложенных циклов (из-за накладных расходов на вызов процедуры). Максимум, чего можно добиться - оптимизирующий компилятор подставит процедуру inline, и будут те же два вложенных цикла.

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

Вывод: применённый хак имеет мало отношения к алгоритмизации и программированию, а чисто основан на использовании фич конкретного компилятора конкретного языка.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Вторник, 16 Февраль, 2010 12:02 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Александр Ильин писал(а):
Получается, что поиск с использованием локальной процедуры выигрывает по всем статьям.
Я тоже проверил в ББ. Сравнивал вариант со вложенной процедурой с симуляцией цикла Дейкстры с помощью LOOP.

При размере матрицы 1000*1000 вложенная процедура победила с отрывом в 28%,
но при размере матрицы 100*100 победил цикл Дейкстры с отрывом в 53%
(для матрицы 32*32 цикл Дейкстры победил с отрывом уже в 92%).

В общем, для больших матриц рулит вложенная процедура, для малых - симуляция цикла Дейкстры с помощью LOOP.

Интересно было бы ещё проверить в Oberon-07 в котором цикл Дейкстры "родной". Там, по идее, если компилятор не сглупит, ЦД должен бы побеждать и на больших матрицах тоже.

Код:
MODULE TestSearch2D;

   IMPORT Log := StdLog, Services;

   CONST N = 1000;
      cpuClock = 2.21; (* частота моего процессора в гигагерцах *)

   VAR
      a: ARRAY 1000, 1000 OF INTEGER;
      i, j, v, n: INTEGER;
      t: LONGINT;
      dt: REAL;

   PROCEDURE FindInLine (IN a: ARRAY OF INTEGER; OUT pos: INTEGER): BOOLEAN;
      VAR i: INTEGER;
   BEGIN i := 0;
      WHILE (i < LEN(a)) & ~(a[i] = v) DO INC(i) END;
      pos := i;
      RETURN (i < LEN(a))
   END FindInLine;

BEGIN
   FOR i := 0 TO LEN(a, 0) -1 DO
      FOR j := 0 TO LEN(a, 1) -1 DO
         a[i, j] := 999
      END
   END;
   v := 1000;
   a[LEN(a, 0)-1, LEN(a, 1)-1] := v;

   (************************************)

   t := Services.Ticks();
   FOR n := 1 TO N DO
      i := 0; j := 0;
      LOOP IF (j < LEN(a, 1)) & ~(a[i, j] = v) THEN
         INC(j)
      ELSIF (j = LEN(a, 1)) & (i < LEN(a, 0)) THEN
         j := 0; INC(i)
      ELSE EXIT END END;
   END;
   dt := Services.Ticks() - t;
   Log.String("Симуляция цикла Дейкстры:"); Log.Ln;
   Log.String("i = "); Log.Int(i); Log.Ln;
   Log.String("j = "); Log.Int(j); Log.Ln;
   Log.Real(dt); Log.String(" секунд на весь тест"); Log.Ln;
   Log.Real(dt / N * 1000); Log.String(" микросекунд на один поиск"); Log.Ln;
   Log.Real(dt / N * 1000000 * cpuClock / (LEN(a, 0)*LEN(a, 1))); Log.String(" тактов на элемент"); Log.Ln;

   (************************************)

   t := Services.Ticks();
   FOR n := 1 TO N DO
      i := 0; j := 0;
      WHILE (i < LEN(a, 0)) & ~FindInLine(a[i], j) DO INC(i) END
   END;
   dt := Services.Ticks() - t;
   Log.String("Использование процедуры:"); Log.Ln;
   Log.String("i = "); Log.Int(i); Log.Ln;
   Log.String("j = "); Log.Int(j); Log.Ln;
   Log.Real(dt); Log.String(" секунд на весь тест"); Log.Ln;
   Log.Real(dt / N * 1000); Log.String(" микросекунд на один поиск"); Log.Ln;
   Log.Real(dt / N * 1000000 * cpuClock / (LEN(a, 0)*LEN(a, 1))); Log.String(" тактов на элемент"); Log.Ln
END TestSearch2D.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Поиск элемента матрицы
СообщениеДобавлено: Вторник, 16 Февраль, 2010 12:09 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1040
Откуда: Россия, Чебоксары
Друзья, ну некорректно же с такой процедурой сравнивать! viewtopic.php?p=42887#p42887

Перепишите тогда два цикла с такой же оптимизацией, как в случае процедуры!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Вторник, 16 Февраль, 2010 12:21 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8215
Откуда: Троицк, Москва
Сергей Губанов писал(а):
проверил в ББ. Сравнивал вариант со вложенной процедурой с симуляцией цикла Дейкстры с помощью LOOP.

При размере матрицы 1000*1000 вложенная процедура победила с отрывом в 28%,
но при размере матрицы 100*100 победил цикл Дейкстры с отрывом в 53%
(для матрицы 32*32 цикл Дейкстры победил с отрывом уже в 92%).

В общем, для больших матриц рулит вложенная процедура, для малых - симуляция цикла Дейкстры с помощью LOOP.

Интересно было бы ещё проверить в Oberon-07 в котором цикл Дейкстры "родной". Там, по идее, если компилятор не сглупит, ЦД должен бы побеждать и на больших матрицах тоже.
Не должен. Только граница, где процедура начинает обгонять, могла бы сдвинуться (см. ранее), и то вряд ли (цикл Дейкстры никак нельзя реализовать по особенному по сравнению с LOOP IF ELSIF ELSE EXIT END END).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Поиск элемента матрицы
СообщениеДобавлено: Вторник, 16 Февраль, 2010 12:43 

Зарегистрирован: Среда, 30 Сентябрь, 2009 14:45
Сообщения: 147
Тогда до кучи алгоритм от партизана :D
Код:
VAR
   arr: ARRAY N, M OF INTEGER;
   i, k: INTEGER;
   find,found: BOOLEAN;
BEGIN
   i := 0;  k := 0;
   find := TRUE;
   WHILE find DO
       found := arr [i, k] = x;
       IF found THEN
          find:=FALSE;
       ELSEIF i<N-1 THEN
            INC (i)
       ELSEIF k<M-1 THEN
            INC (k); i:=0
       ELSE
            find:=FALSE
       END
   END
END


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Вторник, 16 Февраль, 2010 12:46 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Info21 писал(а):
Не должен. Только граница, где процедура начинает обгонять, могла бы сдвинуться (см. ранее), и то вряд ли (цикл Дейкстры никак нельзя реализовать по особенному по сравнению с LOOP IF ELSIF ELSE EXIT END END).
Вот ЦД:

WHILE (j < LEN(a, 1)) & ~(a[i, j] = v) DO INC(j)
ELSIF (j = LEN(a, 1)) & (i < LEN(a, 0)) DO j := 0; INC(i)
END

Обратим внимание на первую строчку

WHILE (j < LEN(a, 1)) & ~(a[i, j] = v) DO INC(j)

Если компилятор не сглупит, то он заменит её на такую:

WHILE (j < LEN(b)) & ~(b[j] = v) DO INC(j)

где "b = a[i]". И тогда ЦД будет выполняться не медленнее чем в случае со вложенной процедурой, так как именно этот цикл написан в её теле.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Поиск элемента матрицы
СообщениеДобавлено: Вторник, 16 Февраль, 2010 13:47 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Придумал ещё один вариант:
Код:
      i := -1;
      REPEAT
         j := 0; INC(i);
         IF i < LEN(a, 0) THEN
            WHILE (j < LEN(a, 1)) & ~(a[i, j] = v) DO INC(j) END;
         END
      UNTIL j < LEN(a, 1);

      IF i < LEN(a, 0) THEN нашли ELSE не нашли END

Он чуть-чуть обгоняет симуляцию ЦД на больших матрицах, но отстаёт на малых.

Компилятор упорно тупит не желая оптимизировать строку

WHILE (j < LEN(a, 1)) & ~(a[i, j] = v) DO INC(j) END;

до строки

WHILE (j < LEN(b)) & ~(b[j] = v) DO INC(j) END;

где "b = a[i]".


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Поиск элемента матрицы
СообщениеДобавлено: Вторник, 16 Февраль, 2010 13:56 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2318
Откуда: Россия, Томск
Сергей, раз уж вы этим занимаетесь, проверьте, пожалуйста, влияет ли на быстродействие замена LEN(a) на соответствующую константу (N либо M)?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Поиск элемента матрицы
СообщениеДобавлено: Вторник, 16 Февраль, 2010 14:01 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 531
Откуда: Москва
У Вас LEN(a) меняется внутри цикла что ли? Зачем ее каждый раз вычислять?
UPD: опоздал :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Поиск элемента матрицы
СообщениеДобавлено: Вторник, 16 Февраль, 2010 16:04 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8215
Откуда: Троицк, Москва
Peter Almazov писал(а):
У Вас LEN(a) меняется внутри цикла что ли? Зачем ее каждый раз вычислять?
А она не вычисляется, а берется.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Вторник, 16 Февраль, 2010 16:18 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8215
Откуда: Троицк, Москва
Сергей Губанов писал(а):
Вот ЦД:
Да, это тоже цикл Дейкстры. Только мой лучше :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Поиск элемента матрицы
СообщениеДобавлено: Вторник, 16 Февраль, 2010 17:02 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Если тип массива объявлен с фиксированным размером (что тут и сделано), то LEN(a) - константа подставляемая во время компиляции.

Если тип массива объявлен открытым, то LEN(a) - переменная доступная только для чтения. Вводить вместо неё другую переменную (которая к тому же ещё и будет доступна для записи) смысла нет (или даже вредно).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Вторник, 16 Февраль, 2010 17:06 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Info21 писал(а):
Только мой лучше :)
А мой последний вариант с REPEAT-ом ещё лучше :D


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Вторник, 16 Февраль, 2010 18:41 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8215
Откуда: Троицк, Москва
Сергей Губанов писал(а):
Info21 писал(а):
Только мой лучше :)
А мой последний вариант с REPEAT-ом ещё лучше :D
хум хау.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Поиск элемента матрицы
СообщениеДобавлено: Среда, 17 Февраль, 2010 00:09 

Зарегистрирован: Среда, 04 Июль, 2007 16:43
Сообщения: 235
Сергей Губанов писал(а):

Компилятор упорно тупит не желая оптимизировать строку

WHILE (j < LEN(a, 1)) & ~(a[i, j] = v) DO INC(j) END;

до строки

WHILE (j < LEN(b)) & ~(b[j] = v) DO INC(j) END;

где "b = a[i]".


Так вроде компилятор в ББ неоптимизирующий?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Поиск элемента матрицы
СообщениеДобавлено: Среда, 17 Февраль, 2010 07:30 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8215
Откуда: Троицк, Москва
QWERTYProgrammer писал(а):
Так вроде компилятор в ББ неоптимизирующий?
И слава богу!
(Свят, свят, свят!...)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Поиск элемента матрицы
СообщениеДобавлено: Среда, 17 Февраль, 2010 11:36 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
QWERTYProgrammer писал(а):
Так вроде компилятор в ББ неоптимизирующий?
Смотря что под этим понимать. Программы ББ работают удовлетворительно шустро. В то же самое время если, например, в MS VS C# снять галку "оптимизация", то тормоза будут ещё те.

Кстати, сравнивая с C# обнаружил следующее различие. Если в Обероне объявлена процедура

PROCEDURE f (VAR line: ARRAY OF INTEGER);

и объявлена переменная

VAR a: ARRAY 10, 10 OF INTEGER;

то в ту процедуру можно засунуть строку матрицы: f(a[2]). А в C# этого сделать нельзя!

void f (int[] x)

int[,] a = new int[10, 10];

f(a[2]); <-- низя!!!

То есть самый быстрый выриант с процедурой (в которой осуществлялся проход по строке) в C# нереализуем!!!


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 17 Февраль, 2010 11:51 

Зарегистрирован: Среда, 30 Сентябрь, 2009 14:45
Сообщения: 147
А где же Свидетель Си с алгоритмом на низкоуровневых массивах - в одну строчку и пустым телом цикла?
Нехорошо-с, совсем распугали оппонентов :D


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Поиск элемента матрицы
СообщениеДобавлено: Среда, 17 Февраль, 2010 12:28 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8215
Откуда: Троицк, Москва
Сергей Губанов писал(а):
то в ту процедуру можно засунуть строку матрицы: f(a[2]). А в C# этого сделать нельзя!
Любопытно. Чем же они думали.

Эта вещь нередко встречается при работе с матрицами и т.п.
Естественная такая вещь.

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


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB