Тест "Счастливые билеты"
В книге "Систематический подход к программированию"[1, стр. 100] из популярной серии приводились примеры реализации алгоритма поиска "счастливых" билетов. Книгу я использовал в процессе учёбы, поэтому некоторые моменты осели на чердаке памяти. Спустя почти 30 лет появилась идея использовать алгоритм перебора для оценки качества генерируемого компиляторами кода. Заметно выросшие вычислительные мощности ЭВМ вынуждают увеличивать сложность перебора на два порядка (до 8 цифр) для замера времени, которое в варианте для 6 цифр находится в пределах миллисекунды.
Теперь тот же тест в оригинальном виде может быть использован и для оценки быстродействия современных калькуляторов.
Задача
Билеты для проезда на транспорте нумеруются шестизначными цифрами. "Счастливым" считается билет, сумма первых трех цифр которого совпадает с суммой трех оставшихся цифр. Требуется найти общее количество "счастливых" билетов в серии 000000..999999.
Для проверки корректности тестовой программы, полученный результат должен быть равен 55252 с учетом номера 000000 или на единицу меньше без учета.
Перебор без оптимизации
Наиболее простым вариантом является перебор всех 106 вариантов с вычислением и сравнением соответствующих сумм разрядов на каждом шаге. Полный перебор всех вариантов является обязательным условием теста без алгоритмической оптимизации.
Программы для МК61/52/161
К сожалению, ПМК обладает всего 4 регистрами циклов, поэтому два оставшихся приходится реализовывать условными переходами. Для сокращения времени счета, условные переходы используются для внешнего и первого циклов из шести. Также мы используем не меняющий результат интервал 1..10 вместо 0..9 для каждого разряда. Программа выглядит так:
00 01 02 03 04 05 06 07 08 09 00 0 П7 1 0 П8 П5 ИП8 П4 ИП8 П3 10 ИП8 П2 ИП8 П1 ИП8 П0 ИП0 ИП1 + ИП2 20 + ИП3 - ИП4 - ИП5 - Fx=0 33 ИП7 30 1 + П7 FL0 16 FL1 14 FL2 12 FL3 40 10 ИП4 1 - П4 Fx=0 08 ИП5 1 - 50 П5 Fx=0 06 ИП7 С/П
Запуск: В/0, С/П
Для старых моделей МК61/52 время счет должно составлять долгие часы, поэтому просто оценим его, взяв время выполнения самого нижнего цикла и умножив его на 105. Вводим следующую программу:
00 01 02 03 04 05 06 07 08 09 00 ИП8 П0 ИП0 ИП1 + ИП2 + ИП3 - ИП4 10 - ИП5 - Fx=0 19 ИП7 1 + П7 FL0 20 03 С/П
В регистры заносим: 1 П1 П2 П3 П4 П5, 0 П7, 10 П8.
Запуск: В/0, С/П
На моём МК52 время счета нижнего цикла составило 40 секунд (результат: 1 билет). Соответственно, общее потребное время можно оценить как 40*105 секунд, что составит порядка 1111 часов или 46 дней! Не думаю, что имеет смысл делать реальный тест на таком вычислительном оборудовании.
Другие модели
Для других моделей предлагаю вначале оценить время счета нижнего цикла, после чего принимать решение о реальном тесте. Просьба приводить программы и хронометраж с точностью до минут или минут и секунд, если время окажется в пределах нескольких минут, итоговые результаты будут сведены в таблицу.
Оптимизация
Кроме теста на производительность, задача является полем для аналитической оптимизации. Например, в нижний цикл имеет смысл входить только если сумма-разность предыдущих пяти разрядов больше нуля.
Результаты
Без алгоритмической оптимизации
Программа без алгоритмической оптимизации должна производить полный перебор всех вариантов номеров от 0 до 999999.
Модель ПМК | Время счёта (без оптимизации), минуты |
---|---|
МК52 | 66667 (оценка) |
МК161 | 92 |
Casio 9750 GII | 96 |
DM42 | 12'35" |
SHARP PC-G850S | 23 |
HP35s | 2010 (оценка) |
HP50g UserRPL | 282 |
HP50g SysRPL | 5 |
С оптимизацией
Модель ПМК | Время счёта (без оптимизации), мин:сек |
---|---|
Casio 9750 GII | 56:05 |
Casio fx-9860G Slim | 46:48 |
Casio fx-9860G SD | 49:07 |
SHARP PC-G850S | 13:22 |
Литература
- Вьюкова Н.И., Галатенко В.А., Ходулев А.Б. Систематический подход к программированию. Под ред. Ю.М. Банковского. - М.: Наука, 1988. - 208 с. Серия: Библиотечка программиста.
- Serguei_Tarassov's blog
- Log in or register to post comments
- Просмотров 29092
Комментарии
МК-161, полный тест
Permalink
МК-161 (версия прошивки 1.20), полный тест: 1 час 32 мин
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Соответствует
Permalink
Время, в целом, соответствует. Еще на тесте "8 ферзей" разница по скорости с МК61/52 была примерно в 1300 раз. Т.е. ожидалось около 1 часа.
P.S. Как же я чертыхался, переписывая эту программу без меток в абсолютных адресах... В "МК61 Gold" надо ввести режим вставки.
Да, примерно та
Permalink
Да, примерно та же пропорция скорости.
Надо бы hp35s проверить на полном тесте
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Мой вариант "билетов"
Permalink
Навскидку набросал свой вариант "билетов", перебор всех 1000000 вариантов, из номера выделяется по одной цифре, начиная с младшей, и сравниваются суммы цифр младшей и старшей половин номера. Используются всего два цикла, первый - миллион билетов, второй выделение трёх цифр каждой половины номера, после испытания программу оптимизировал чтобы сумма цифр старшей половины рассчитывалась только после перебора младших половин.
Собственно программа:
Программа занимает 53 байта. Запуск В/О, С/П, после останова в регистре РХ выводится число "счастливых билетов", равное 55252.
Назначение регистров Р0 - счётчик билетов, Р1 - счётчик цифр половин номера, Р7 - номер билета, Р8 - номер "счастливого" билета, Р9=10, РА - регистр для выделения цифр, РВ - сумма цифр младшей половины, РС - сумма цифр младшей половины.
Время выполнения теста на эмуляторе 2:30 на процессоре Athlon 2500+ 1,8 ГГц, программа Сергея Тарасова на том же эмуляторе работает всего минуту) Написано в 19:33.
Добавлено в 23:53: На "железном" МК-161 с прошивкой 1.20 мой тест выполнился за 3:29:28)
Сайт
На тему задачи
Permalink
подборка статей из Кванта и других популярных изданий про "Счастливые билеты":
http://www.ega-math.narod.ru/Quant/Tickets.htm
Целочисленный Форт в msp430g2553: 40 сек
Permalink
Допилил "Счастливые билеты" под Форт на msp430g2553. Результат: 40 секунд.
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Лишние переменные
Permalink
Можно избавиться от переменных ls и rs, результаты суммирования оставлять в стеке.
Да, видимо. Это
Permalink
Да, видимо.
Это мой первый блин в Forth, вообще
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Блины
Permalink
Блин хороший. Я бы использовал i вместо n6 @, j вместо n5 @ (это стандартные слова, которые есть в любом Форте) и определил собственные слова, берущие из стека возвратов значения других переменных цикла:
: k вместо VARIABLE n4
: l вместо VARIABLE n3
: m вместо VARIABLE n2
: n вместо VARIABLE n1
Тогда это будет классическим Фортовским решением, когда пишутся слова, в которых формулируется завершающее слово программы.
Цикл DO хранит значение своей переменной в стеке возвратов. В Форте должно быть слово, дающее адрес вершины стека возвратов. В Каллисто это RP@
По некоторым смещениям относительно этой вершины и находятся i j k l m n, переменные вложенных циклов. Точные значения смещений можно узнать либо из исходного кода Форта, либо экспериментально — просматривая дамп памяти изнутри самого внутреннего цикла.
Обычно стек возвратов растёт вниз (смещения тогда будут положительные), но если внезапно переменные циклов не найдутся, можно проверить и отрицательные смещения.
Это пока высший
Permalink
Это пока высший пилотаж для меня :)
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
минус 11 секунд
Permalink
Избавление от переменных еще избавило от 11 секунд :) Результат: 29 секунд
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Счастливые билеты 2сек(другой проверенный Форт код на STM32L100)
Permalink
\ Опробовал такой код на VFX Forth STM32L (тактовая 32МГц)
\ при компилировании кода вместе с системой
\ 1-й вариант 2,5 сек
variable tmp1
variable cnt1
: howmuch
10 0 DO I
10 0 DO I
10 0 DO I
10 0 DO I
10 0 DO I tmp1 !
10 0 DO
2OVER 2OVER tmp1 @ I
+ + >R
+ + R> = IF 1 cnt1 +! THEN
LOOP
LOOP
DROP LOOP
DROP LOOP
DROP LOOP
DROP LOOP
cnt1 @ .
;
howmuch 55252
\ 2-й немного изменённый вариант и время выполнения 2сек
variable tmp1
variable cnt1
: howmuch
10 0 DO I
10 0 DO I
10 0 DO I
10 0 DO I
10 0 DO I tmp1 !
10 0 DO
2OVER 2OVER tmp1 @ I
+ + 2SWAP + ROT +
= IF 1 cnt1 +! THEN
LOOP
LOOP
DROP LOOP
DROP LOOP
DROP LOOP
DROP LOOP
cnt1 @ .
;
howmuch 55252
P.S. По варианту с использованием переменных замер дал 3.4 сек (18сек если программа введена интерактивно)
и по выше вариантам 11.07 и 11.3 при интерактивном вводе программы по Уарт интерфейсу.
т.е. без оптимизационных возможностей компилятора.
P.S. https://atariwiki.org/wiki/Wiki.jsp?page=Forth%20Benchmarks
Некоторые ещё измеренные Forth Benchmarks разного железа
3.4 секунды
Permalink
P.S. По варианту с использованием переменных замер дал 3.4 сек
Это тот вариант, что у меня выше был 29 секунда на msp430 ?
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Да, 3.4 сек (с оговоркой при целевой компиляции)
Permalink
18 сек при "трансляции", но как то по разнице в тактовых частотах (если 8 МГц у MSP430 vs 32MГц)
отличия по времени не настолько ощутимы. Вероятнее внутренние затраты на организацию Форт системы
и обслуживание тиков таймера и уарта (навскидку) и сохранение при этом некоторого контекста
у STM32L VFX более трудозатратно архитектурно.
P.S. Можно и код ассемблерный в разных вариантах рассмотреть.
VFX Forth для MSP430 тоже доступен. http://www.mpeforth.com/xc7lite.htm
Посмотрел про VFX Forth
Permalink
интересно!
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
AmForth для AVR - Счастливые билеты
Permalink
Проверил и получилось 2 мин 8 сек (~8МГц)
P.S. VFX Forth "ковырял" на предмет его дизасемблирования и тоже с задействованием Форт инструментария.
Есть даже какие то результаты. :)
Это AmForth тормоз или AVR тормоз?
Permalink
понятно, что msp430 16-битный и другой архитектуры, но, тем не менее
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Вопрос не так однозначен для AmForth
Permalink
Думаю разрядность вносит главные задержки для 16 разрядности (этим конечно можно гибче управлять),
к тому же у MSP430 по общему ощущению более удачная система команд для реализации классики Форт
и вероятнее более эффективнее реализация механизма выполнения FVM кода.
Но при желании, при генерации кода, можно провести некоторые критические оптимизации
и существенно улучшить временные характеристики прохождения теста.
Какие то ключевые слова в AmForth могут быть определены высокоуровневыми.
На fforum.winglion.ru есть ссылки и на другие Форт системы для AVR.
P.S. И ещё. Есть некоторое сомнение что ядро MSP430 запущено на 8МГц, а не на 16МГц.
Без "препарирования" кода выводы будут всегда неоднозначны
Кстати, может таки и на 16
Permalink
Кстати, может таки и на 16 МГц
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Casio 9750 GII
Permalink
Casio 9750 GII
Результат 55252 1час 36мин
SHARP PC-G850S
Permalink
SHARP PC-G850S
Результат s=55252 22мин 54c
SHARP PC-G850S
Permalink
С оптимизацией
SHARP PC-G850S
Результат s=55252 13мин 22c
C оптимизацией
Permalink
C оптимизацией
Casio 9750 GII
Результат 55252 56мин 05с
HP35s для 4-значных билетов: 20 минут
Permalink
HP35s для 4-значных билетов: 20 минут
Для 6-значных билетов, в идеальном случае: 20х100 минут или 33 часа с половиной часа, тестировать я поленился.
UPDATE:
Из теста 8-ферзей:
http://pmk.arbinada.com/node/30
МК-161 с той прошивкой быстрее hp35s в 16.8 раз. Исходя из этого, "Счастливые билеты" для HP35s для 6 цифр должны быть около 1550 минут.
В любом случае HP35s тормоз чуть менее чем полностью.
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Совпадает
Permalink
Совпадает и с тестом "Пустой цикл". Такое впечатление, что эмулятор, гоняющий прошивку прежнего HP35 поверх нового камня, еле ворочается.
Если там эмуляция старого HP35, то (+)
Permalink
это объясняет, конечно. Да, на что-то серьезное hp35s не годится.
5800P (между которым и HP35s я колебался при покупке последнего) не сказать, что сильно быстрее, судя по 8-ферзям:
После этого 29 секунд целочисленного Форта в микроконтроллере впечатляют.
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Хороший калькулятор
Permalink
Хороший калькулятор - свой калькулятор. Это следует из принципа "хочешь сделать хорошо - сделай сам".
Да, свой
Permalink
Да, свой калькулятор лучше. Форт или Рапира :)
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
HP-50g
Permalink
Программа для HP-50g на UserRPL.
Результат:
# 55252d
16963.7645264, то есть 282 минуты
P.S. Ждем выхода newRPL :)
Ого,
Permalink
Ого, патриарх-то тоже тормоз :)
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Ему простительно :)
Permalink
Слишком много уровней трансляций:
UserRPL->SysRPL->Saturn->Asm
SysRPL
Permalink
Судя по тесту "Пустой цикл", на SysRPL должно быть 6 минут. На сатурновском ассемблере - еще на порядок меньше, не говоря уже о долях секунд на C.
Сила HP50g в том, что можно и так, и этак и по-другому и даже еще вот как.
HP-50g SysRPL
Permalink
Результат:
¤ 55252d
859.24597168, то есть 14 минут 19 секунд
Добавил
Permalink
Спасибо, все добавил
Преимущества стековой архитектуры
Permalink
Результат:
¤ 55252d
320.372192383, то есть 5 минут 20 секунд
Если условие переписать:
то результат:
¤ 55252d
282.681762695, то есть 4 минуты 43 секунды
Теперь соответствует
Permalink
Вот теперь время соответствует соотношению в тесте пустого цикла, а то 14 минут долго. Округлил до 5 минут. На сатурновском ассемблере будет еще на порядок быстрее, в пределах минуты.
Честность в сравнении
Permalink
Всё же последние версии программы оптимизированы, за счёт использования ранее вычисленных сумм цифр. Просто при использовании стека это делается органично и, как бы, не заметно. Поэтому рекомендую оставить 14 минут для не оптимизированной версии.
Последняя оптимизация - взята из примера Ardo_79:
Условие:
выдает:
¤ 55252d
244.788330078, то есть 4 минуты 5 секунд.
Если вместо ISTOP@ и JSTOP@ использовать BINT10, то время выполнения ещё сократиться на 3,5 секунды.
Если использовать FEVAL (повышение частоты до 200 МГц) - то самая оптимизированная версия выполнится за 171,3600107422, то есть 2 минуты 51 секунду.
Оптимизация
Permalink
Оптимизация - это избавление от циклов или вхождений в них по предусловию. Использование стека - документированная стандартная возможность данных ПМК, такая же, как использование FL0..FL3 в МК61.
Слишком узкая трактовка.
Permalink
Оптимизация - это любые мероприятия приводящие к сокращению времени выполнения программы. Иногда это делает человек, иногда компьютер (компилятор+Acovea). Ничто не мешает использовать частичные суммы в программах для калькуляторов Casio и Sharp. Время вычислений сократиться существенно.
Оптимизация
Permalink
Оптимизация бывает двух видов: алгоритмическая и техническая. Техническая предусматривает написание программы по заданному алгоритму с использованием всех технических возможностей устройства.
Если вы меняли алгоритм, то тогда да, такая оптимизация не соответствует условиям первой части тестов. Но, насколько я вижу, там по-прежнему 6 вложенных циклов без предусловий, т.е. осуществляется полный перебор. Или я что-то упускаю из виду?
Обязательное условие алгоритма - полный перебор всех вариантов, а как его реализовать - дело программиста.
Цель теста
Permalink
сравнить скорость вычислений калькуляторов, что имеет смысл только при одинаковом кол-ве арифметических операций. Вот только сейчас проверил, что делает оптимизатор gcc с опцией -O2 с нашими вложенными циклами.
ИЗ:
ПОЛУЧАЕТЬСЯ:
P.S. GCC меня переиграл :)
Это ещё не всё. :-)
Permalink
Можно f сравнивать с abc-de, да и вообще от de избавиться.
Дальше уже пойдёт то, что Арбинада не любит — вместо самого внутреннего цикла сравнивать, укладывается ли abc-de в диапазон [0;9].
Casio fx-9860G
Permalink
Casio fx-9860G Slim
Результат: 55252 46мин 48с ( Программа аналогична Casio fx-9750G II c оптимизацией)
Casio fx-9860G SD
Результат: 55252 49мин 07с ( Программа аналогична Casio fx-9750G II c оптимизацией)
Псевдокод
Permalink
Программы для разных калькуляторов, увы, кодируют разные алгоритмы и поэтому выполняются за разное время.
Вот самый быстрый алгоритм прямого перебора, укладывающегося в условие задачи. Реализовав его для своего любимого калькулятора, можно немножко приподнять его в топе. :-)
Уже
Permalink
реализовано мной в программе для HP-50g на SysRPL. Но, вариант GCC получше на одну переменную, что позволяет их все разместить в регистрах. Единственное улучшение, - это циклы с декрементом, так как сравнение с нулем обычно быстрее.
P.S. 2:0 в пользу GCC :-)
Опираясь на Ваш
Permalink
Опираясь на Ваш алгоритм можно существенно оптимизировать предыдущую программу
Результат s=55252 8мин 37c
Псевдокод-2
Permalink
Циклы «с нулём» действительно быстрее. Вот псевдокод, в котором переменные цикла сравниваются с нулём.
Если важно экономить регистры (уменьшить количество переменных), можно использовать ab, abc, g и h в качестве переменных циклов напрямую — избавившись от более очевидных (для читателя программы) b, c, d и e. Конечно, инициализация переменной цикла станет сложнее, как и условие окончания цикла. Зато в циклах не будет лишней арифметической операции.
Вот этот псевдокод:
Красиво!
Permalink
Всё таки машины пока ещё не могут достичь пределов человеческого ума в некоторых задачах :)
Конечно быстрее
Permalink
Конечно быстрее! Любой, хоть раз писавший на ассемблере, мог убедиться в этом на своем опыте. По исходной ссылке на тест для компиляторов приведен ассемблерный код в качестве "минимально плохого".
Оптимизирующие компиляторы обычно превращают инкрементный цикл в декрементный без вмешательства человека. Даже Delphi.
По-идее,
Permalink
По-идее, хороший компилятор должен еще последний цикл заменить простой проверкой.
Псевдокод-3
Permalink
Подобрал хорошие названия для двух оставшихся переменных, заменив g и h на ef и ff. Кому-нибудь интересно сделать тест «Счастливые билеты» для Каллисто? :-) Я могу проверить и измерить быстродействие на «железе», если у вас почему-то ещё нет МК-161.
Короткий и быстрый вариант с выносом арифметики из тела цикла в инициализацию:
HP-50g newRPL
Permalink
Вывод:
55252
37.6 секунд
Версия с использованием ранее вычисленных сумм - 23,4 секунды :)
P.S. Интерфейс у newRPL пока неудобный.
newRPL
Permalink
Почитал на форуме HP про newRPL.
Похоже на то, что мы планируем с Каллисто — на том этапе, когда будем переносить её в W77LE516P. Разве что у англоязычных лучше знание аппаратуры HP 50g, т.к. HP в отличии от самобытной СЕМИКО не засекречивает от владельцев калькуляторов используемую прошивку.
Впрочем, фирменная прошивка использовалась в newRPL лишь как источник информации о том, как работает железо HP 50g. Сам закопирайченный исходный код любителями не используется. И правильно делают, известны случаи наездов западных корпораций на тех, кто поступает иначе.
Главное — у зарубежного сообщества появится свободный (и переносимый) код калькулятора с newRPL. Который можно будет использовать при написании приложений, создании собственного оборудования и т.п.
Некоторые подходы newRPL интересны. Но его разработчики отталкиваются от уже гораздо более развитого языка, чем язык МК. Да и вычислительные ресурсы в их распоряжении на поколения больше, 200 МГц 32-битного процессора против 22 МГц 8-битки.
А вот так не получится?
Хотя синтаксис newRPL здесь уродлив, конечно. IF в Форте достаточно хорош. Если заимствовать из Модулы-2, то не синтаксис IF, а разделение модулей на интерфейс и реализацию (инкапсуляция по Вирту).
Я уже давно думаю, как эту модульность можно реализовать в Каллисто. Пока пасьянс не сложился. Возможно, здесь тоже задачка на несколько десятилетий.
Получится,
Permalink
но я уже вернул родную прошивку. newRPL пока сыроват, но скорость впечатляет. Кроме HP-50g newRPL могут портировать на HP Prime. Вот это будет бомба. А мы и так справимся - Путь домой
Мультиклет Р1 0,84с на ... 80МГц?!
Permalink
Сделал тест "счастливых билетов" под мультиклетовский си-компилятор:
Результат ажно 0,84 секунды при тактовой частоте процессора 80МГц, получившееся быстродействие порядка 10млн. операций в секунду, это очень мало! Ежели выкинуть выражение if ((a+b+c)==(d+e+f)) g++; то время выполнения программы падает вдвое, всё-таки распараллеливание операций по клеткам есть, но сама компиляция организована не лучшим образом! Даже если учесть отсутствие распараллеливания из-за циклов, то производительность должна быть всё равно минимум почти на порядок выше!
Вердикт: пока лучше грызть ассемблер!
Сайт
0,78с
Permalink
Оптимизировал алгоритм, время расчёта уменьшилось до 0,78с:
Сайт
0,63 с на асме мультиклета ;-(
Permalink
Сделал "Счастливые билеты" на мультиклетовском асме, я прямо в недоумении от результата... Порядка 30 млн. оп./с. Ещё особенность программрования на асме вылезла - внутри микропрограммы не должно быть больше одной ссылки на одну микропрограмму, а также больше одной ссылки на один и тот же регистр. Может быть ветвление, но со ссылками на разные микропрограммы. Можно подумать по оптимизации программы, но похоже сильно много не выжмешь, миллион пустых циклов выполняются за 0,22 секунды, всё равно как-то не вяжется с 80МГц. Похоже время жрёт подгрузка микропрограмм в ядро. Операнды целочисленные, использовались только регистры общего назначения.
Сайт
Ардуино
Permalink
Тест на ардуине к моему изумлению дал 0,78с при частоте ATMega328P 16МГц!
А вот миллион пустых циклов выполняется ажно 6 секунд, так что ардуиновый компилятор весьма неоднозначен.
Сайт
MSTN-M100
Permalink
В России весной 2017 выпустили отечественную плату на основе миландровского микроконтроллера марки К1986ВЕ92QI, а в качестве IDE разработчики платы взяли бесплатную NetBeans со своими дополнениями.
Время выполнения теста при тактовой частоте 80МГц составило 0,105с, то есть всего 105мс! В среднем, на выполнение главного цикла уходит шесть операций, плюс операция на внешние циклы, то получается, что результирующее быстродействие на уровне 67 млн. оп/с, то есть, по тактам, порядка 83% от теоретического, хотя если считать по даташиту в 1,25 млн. оп./с. на 1МГц, то выходит 67% теоретического быстродействия!
Поскольку флешпамять микроконтроллера имеет задержку в четыре такта, хоть и разбита на четыре параллельно работающих банка, я думаю, что код программы компилятор вполне мог поместить в оперативную память микроконтроллера. Кстати, есть один тонкий момент, у ядра ARM Cortex-M3 есть несколько команд, выполняющих по две операции за такт, например умножение плюс сложение, поэтому такие впечатляющие результаты могут получаться за счёт архитектурных особенностей микроконтроллера. Впечатляюще, не правда, ли?
Результат рассчитывается честно, не 55251, и не 55253, а честных 55252 билета)
Добавлено. Разобрался с функциями и переменными, выложил обновлённый тест, результаты прежние.
Исправлено. Убраны вводящие в заблуждения результаты, полученные в результате ошибки в программе расчёта миллиона пустых циклов, из-за которой я сделал неправильные выводы.
Сайт
Попробуй
Permalink
Попробуй полностью отключить оптимизацию у компилятора. Там наверняка GNU C, он с этой задачкой справляется на уровне -o2 очень неплохо.
Оптимизация
Permalink
Пробовал я вместо набора команд С11 ставить С89 и С99, вместо режима оптимизации О2 ставил О0, результаты такие же. А потом я вместо 80МГц поставил 16МГц и что же?! Тоже самое, и нагрев кристалла остался прежним! Похоже, настроенный интэковцами компилятор нагло игнорит все мои поползновения в сторону уменьшения оптимизации при компиляции программы. Добавлю, что в Кейле тактовая частота действительно устанавливалась 16МГц и микросхема была холодной.
Сайт
Нашёл ошибку!
Permalink
Нашёл ошибку в программе миллион пустых циклов! Вместо миллиона пустых циклов программа выполняла миллион включений или выключений светодиода, а поскольку неэффективный алгоритм включения/выключения единичного пина даёт задержку, то и получалось резкое увеличение времени выполнения.
А вот написание программы выполнения миллионов пустых циклов, не дало возможности измерить период выполнения, период расчёта можно измерить только осциллографом или частотомером. По-видимому интеллекта оптимизатора хватает на то, чтобы обратить внимание на миллион пустых вычислений, и, по-видимому, в готовой программе меняется алгоритм, для подгонки результата! Поэтому миллион пустых циклов можно считать заведомо не пригодным для оценки эффективности компиляторов, которые его могут просто обходить.
Прошу извинения за ошибочную оценку. И никто мордой не ткнул)
Сайт
Быстродействие операций ввода-вывода
Permalink
Допущенная ошибка в попытке оценить время выполнения миллиона пустых циклов дала интересный побочный результат. Миллион операций вывода одного дискретного бита в порт микроконтроллера на основе библиотеки stdio.h выполняется за 0,84с то есть порядка 1,2 млн оп. выв. /с. Если оценить затраты на цикл в три операции, то выходит, что функция вывода в порт выполняется от 20 (по тактам) до 25 (по даташиту) операций!
Добавлено.
Скомпилировал вот такой код:
Итого, время выполнения цикла... 2деления х 2мкс/дел х 0,2 множитель развертки, итого... 0,8мкс... В общем, затраты времени только на операцию вывода бита в порт.
Прошу специалистов прокомментировать код, по-моему где-то я ошибся.
Сайт
Конвейер
Permalink
Не рассматривали такую особенность современных ARM-ов? Это сильно может сбить ввод-вывод.
???
Permalink
А как конвейер может уменьшить выполнение функции for (a=1000000; a>=1; a--); до ста тактов? Где я ошибся?
Сайт
Конвейер не может, зато компилятор отлично может
Permalink
вообще выбросить ваш пустой цикл из бинарника
Пустой цикл
Permalink
Пустой цикл был нужен для оценки быстродействия скомпилированной программы по сравнению со "Счастливыми билетами", видимо компилятор действительно заменяет миллион пустых циклом, одним с вычетом миллиона вместо декремента.
Сайт
Ватник wrote: вообще
Permalink
А это легко проверить - посмотреть lst файл.
Электромонтёр wrote: А как
Permalink
Предсказание переходов, очень даже может.
MSTN-M100
Permalink
Тема перенесена на форум
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
DM42, полный тест
Permalink
Питание от батареи: 31 мин 40 сек; от USB: 12 мин 35 сек. Подробнее тут.
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
По сравнению с МК-161...
Permalink
Втрое быстрее МК-161 при работе от аккумулятора и в семь раз быстрее при работе от USB? Я ожидал более впечатляющих результатов!
Сайт
Соотношение
Permalink
Соотношение быстродействия к частоте процессора у DM42 вдвое ниже, см. тест пустого цикла.
STM32L476 против W77LE516P
Permalink
В DM42 стоит 32-битный STM32L476, который выполняет одну команду за такт, а в МК-161 стоит 8-битный W77LE516P, выполняющий команду за четыре такта, всё равно DM42 по идее должен в полтора-два раза быстрее считать :) даже без учёта сопроцессора и со скидкой на компилятор.
Начал искать даташит на W77LE516P, поиск стал ссылки на МК-161 выдавать.
Сайт
А ещё у Cortex-M4
Permalink
есть всякие SIMD расширения и аппаратное деление, + конвейер, которого в убогом W77LE516P быть не может.
STM32L476
Permalink
Внутри DM42 это? Откуда дровишки?
DM42
Permalink
Да: https://pmk.arbinada.com/ru/node/1317
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Рекорд неэффективности?
Permalink
Написал php-скрипт для MB77.07 на микросхеме К1879ХБ1Я. Результат: 1,98 с на частоте 324МГц. В зависимости от нагрузки на процессор, значение несколько меняется. С учётом быстродействия ядра ARM1176JZF-S на уровне 1,25 DMIPS/MHz эффективность составляет 0,9%. Пожалуй, php5-fpm 5.6.38 это рекорд неэффективности?
Обновлено: - рекорд побит Питоном.
Сайт
PHP
Permalink
Ну так то же интерпретируемый PHP. Интересно было бы сравнить на Питоне, запущенном на этом же микрокомпьютере.
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
То же самое
Permalink
И Похапэ и Питон компилируются в П-код, выполняемый на своей виртуальной машине/процессоре. Разница в производительности может иметь место, но не принципиальная.
PHP против С на i5 :)
Permalink
Отослал тест Антону Прибора -
Сайт
Зато
Permalink
Зато, судя по первой же статье, Антон знает, почему надо писать плохой код :) Прикладного программиста от сохи видно за версту.
Пхп супротив Питон
Permalink
Да, поэтому мне и интересно узнать, кто из этих байт-кодных машин быстрее :)
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Ruby бьёт антирекорд PHP5-FPM!
Permalink
Тест на Ruby 2.1.15 Процессор тот же, результат:

Руби занимает второе место по неэффективности - 0,35%
Вот сам скрипт:
Обновлено: рекорд побит Питоном.
Сайт
Новый антирекорд python3 - 14 секунд.
Permalink
Python 3.4.2 дал наихудший результат - от 14 до 20 секунд, в среднем 17:

Эффективность - 0,13%! Питон с достоинством занимает первое место моего хит-парада по неэффективности :)
РНР-то оказывается не так уж и плох :)
Почему-то заметный разброс, у PHP и Ruby порядка, ±5% а у питона достигает ±15%
Скрипт:
Стоит отдать должное - у Питона довольно удобный синтаксис. Однако, за удобство приходится платить
кровьюпроизводительностью. Если выполнение теста требует 7 млн. операций и занимает 14 секунд, то в результате от 405млн (324х1,25) оп./с остаётся жалкие 0,5 млн. оп./с. А это значит, что благодаря Питону российская 90-нм СБИС К1879ХБ1Я 2010 года скатывается до советской 6-мкм БИС К580ИК80 1977 года, на 33 года назад!Сайт
Набортный Perl
Permalink
На десерт запустил тест на бортовом Perl 5.20.2, cредний результат 9,5 с:
Эффективность - 0,18%.
Скрипт:
Получается, из всех скриптовых интерпретаторов наименьшим злом является Rubi, вдвое хуже - Perl и втрое - Python.
Сайт
Ещё какой нибудь Форт проверить
Permalink
тоже интересно бы было :)
Python3 на BeagleBone Black: 3.4сек
Permalink
Проверил вышеупомянутый скрипт на Питоне3 под BeagleBone Black, AM335x 1GHz ARM® Cortex-A8:
А вообще было интересно увидеть, что ПХП быстрее Питона. Мнда
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Преимущество архитектура Cortex-A8 перед 1176
Permalink
Ядро ARM1176 СБИС К1879ХБ1Я имеет производительность 1,25DMIPS/MHz, а ARM Cortex-A8 2,0 DMIPS/MHz, то есть AM335x на 1ГГц должно быть впятеро производительнее ARM-ядра К1879ХБ1Я на 324МГц. Если у меня на Питоне минимальный результат был 14с, то у тебя должно получится 2,8с :) Хотя, если учитывать среднее значение 17с, то получается в аккурат 3,4с :)
Да, получилось значительно быстрее :)
Сайт
Питон 2 vs 3
Permalink
Второй питон побыстрее тут:
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Довнгрейд помог Питону )
Permalink
Да разница

двухкратнаяполуторная.Простой довнгрейд буквально вдвое улучшил обстановку :) Вот не ожидал!
Обновлено: Путём многократного запуска теста, преимущество второго питона оказалось не столь значительно.
Сайт
На RaspberryPi Zero иначе
Permalink
На RaspberryPi Zero иначе: 5.3 и 5.1 сек соответственно:
"Малинка" Zero на 1GHz ARM11 процессоре.
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Для чистоты эксперимента
Permalink
Вполне согласуется с моими результатами, у К1879ХБ1Я частота втрое ниже.
Для чистоты эксперимента перепрошил микрокомпьютер. В общем, руби как был 5 секунд, так и остался, перл 10 с, второй питон 9-11с, третий питон 14-17с. Второй питон больше разброс даёт.
Сайт
"Билеты" на GCC
Permalink
Для логического завершения экспериментов по тестированию эффективности различных интерпретаторов по предложению Vitasam провёл тест "Счастливые билеты", скомпилированные компилятором GCC. Вот тестовая программа:
Поскольку, GCC имеет регулировку оптимизации, я проверил на всех доступных уровнях- по умолчанию, О0, О1, О2 и О3:
Тест проводился на ARM1176 ядре СБИС К1879ХБ1Я, работающем на частоте 324 МГц и обладающий усреднённой производительностью 324х1,25 = 405 млн.оп/с.
Итак, результат оптимизации по умолчанию - 0,174 с, быстродействие - 40 млн.оп./с, эффективность - 10%. Что-то не очень, хотя уже в десять раз быстрее php и в 81 раз быстрее python 3.
Результат с выключенной оптимизации О0 тот же - 0,174 с, быстродействие - 40 млн.оп./с, эффективность - 10%. Очевидно, в gcc по умолчанию оптимизация отключена.
Результат с начальной оптимизацией О1 в семь раз лучше - 0,024 с, быстродействие - 290 млн.оп./с, эффективность - 72%. Вот это уже похоже на правду, вот она мощь процессора!
Результат со средней оптимизацией О2 - 0,02 с, быстродействие - 350 млн.оп./с, эффективность - 86%. Можно сказать, что результат приближается к ассемблерному.
Наконец, максимальное ускорение! Результат с наибольшей оптимизацией О3 поражает - 0,014 с, быстродействие - 500 млн.оп./с, эффективность - 123% :) Чудес не бывает, а вечный двигатель построить ещё никому не удалось. Компилятор явно развернул внутренний цикл.
По результатам экспериментов тиснул статейку :)
З.Ы. Если кто найдёт простую реализацию ЧПУ на RaspberryPi вместо GRBL на ардуине, дайте ссылку. Простую - это значит, как на ардуине, залил прошивку и работай, безо всяких сборок и перекомпиляций ядра из сорцов :)
Сайт
Хорошее исследование
Permalink
Хорошее исследование!
А про простую реализацию ЧПУ на Raspberry. Имеется в виду чтобы без операционки?
Тогда надо смотреть в сторону Bare Metal программирования.
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
ЧПУ
Permalink
Это образ с ЧПУ программой, чтобы залил и работай.
Сайт
Образ для Распберри
Permalink
А ЧПУ существует под Линукс/Распберри? В таком случае проще всего сделать просто образ SD-карточки. PiBakery, к примеру.
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
LinuxCNC
Permalink
Да, есть LinuxCNC, требует специально пропатченного ядра для реалтайма, и меньше и хуже документирован чем Mach3. Натыкался на видео на ютубе, как рационализатор на заводе переделывал советский ЧПУ станок с разбомблённой НЦ-31 на LinuxCNC, правда до автосмены инструмента он не дошёл.
Сайт
Ход конём!
Permalink
Запуск скомпилированного GCC теста на уровне -О2 из скрипта РНР!
Сам скрипт предельно прост:
Но из скрипта запускается заранее скомпилированный со средним уровнем оптимизации файл:
Результат - 0,06с, и из них только треть тратится на расчёт!

Недостаток - только одно значение можно вывести. Выход - из скомпилированной программы писать в файл, а уже из файла читать данные скриптом.
Сайт
Код
Permalink
А в чем смысл использования "больше или равно" и декремента в циклах?
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Код
Permalink
"Больше или равно" просто удобнее, а декремент эффективнее с точки зрения компиляции. Правда, компилятор очень умный и при возможности сам переделывает инкрементный цикл в декрементный при компиляции. Сравнение с нулём - только флаг проверить, а для сравнения с числом надо операцию вычитания делать.
Сайт
Компиляторы и платформы
Permalink
Подозреваю, что современные архитектуры давно уже имеют соответствующие single-операторы для таких сравнений. Ну, и компиляторы умные. Так что да, писать код нынче надо для удобства понимания и обслуживания кода*, а оптимизацией займется компилятор.
(* в разумных пределах, конечно же).
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Неудивительно
Permalink
Неудивительно, в ПХП вложены миллионы от корпораций типа Фейсбука, которым важно разогнать виртуальную машину до предела для обеспечения производительности нагруженных приложений. Питон для этого практически не используется, это современный аналог Бейсика для быстрой прикладной разработки программ любителями под свои задачи.
С другой стороны, странно
Permalink
С другой стороны, странно. Data mining и ИИ, в основном, на Питоне сейчас пилятся. Видимо, удобство языка перевешивает
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Не пишут
Permalink
Не пишут, а настраивают. Типа, ядро нейросетки на Си, а обучающие скрипты на питоне.
Ну, это понятно
Permalink
что высокопроизводительные вычисления это в сторону Си. Но для Питона много модулей, NumPy один чего стоит - удобно быстро набросать рабочий проект.
Ну таки не только любителями :)
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Космическая обсерватория «Кеплер» и Python
Permalink
Тут интересная статья про орбитальный телескоп-искатель экзопланет "Кеплер". Все основные программные инструменты, используемые для обработки данных с телескопа, написаны на Питоне (и они почти все выложены на Гитхабе):
---------------------------
Истина где-то рядом
www.litres.ru/vitaliy-samurov/dozvonitsya-do-devy/
Тест на моём смартфоне :)
Permalink
Тест на моём DEXP Ixion P135 с процессором MT6572A 2x Cortex-A7 1 ГГц на Android 4.4.2 с расчётной производительностью 2х1900 млн.оп./с. Компилятор - мобильный С 2.5.2, 2013 год.
Результат - 5,05 мc, производительность - 1385 млн.оп./с.

Код использован от МВ77.07:
Поскольку программа явно выполняется на одном ядре, то эффективность кода мобильного компилятора выходит - 73%.
Не ожидал от андройда такой прыти :) но компиляция программы жрёт в сто раз больше - полсекунды :(
Сайт