Этюды для начинающих: мрамор и штукатурка эффективности
- Войдите на сайт для отправки комментариев
Вс, 13/12/2015 - 14:22
«Во имя эффективности в программировании было совершено больше прегрешений (причем не всегда ее удавалось достичь), чем по какой-либо другой причине, включая непроходимую глупость»
В. Вульф
В программировании существуют как минимум два диаметрально противоположных подхода к эффективности, отличающиеся друг от друга как штукатурка от мрамора. Первый подход основан на «тайных знаниях» об эффективности битовых операций и о том, сдвиг всегда быстрее умножения, а наложение маски быстрее вычисления остатка. Второй подход исходит из того, что рубль всегда больше копейки, и замена алгоритма на более эффективный (например, квадратичного на линейный, или экспоненциального на квадратичный), даст такое увеличение эффективности, которое не в состоянии дать и 100500 замен умножения на сдвиг. Первый подход зависит от всего: процессора, компилятора и т.п. и даёт выигрыш на проценты и доли процентов. Второй же подход не зависит ни от чего, а выигрыш даёт в разы и на порядки.
Сторонники первого подхода – в основном «кул хацкеры», которые называют программы «прогами», клавиатуру «клавой», а себя считают круче всего тупого Microsoft вместе взятого. Стоит начинающему программисту познакомиться с таким «кульным хацкером», как в его кодах сразу же появляются невообразимые нагромождения битовых операций, нечитаемые конструкции из значков верхней строки клавиатуры, только вот коды как толком не работали, так толком и не работают. Зато он теперь знает, что «i/2» пишут только лохи, а реальные пацаны всегда пишут «i >> 1» и от этого у бедняги – новичка сильно повышается самооценка, а всем известный орган начинает быстро увеличиваться в длине до невероятных размеров.
Дорогие новички, запомните, профессиональные врачи никогда не называют известные части тела их не менее известными фольклорными названиями, а профессиональные программисты называют программы программами, а серверы – серверами. Если же Вам доведётся встретить на своём пути «кул хацкера», проявите уважение, угостите его пивом и выслушайте восторженную речь про очередную «прогу» от которой, построившись в шеренгу, рыдают в платочек тупые майкрософтовцы, айбиэмовцы и прочая шушера. А когда он Вам скажет что знает Линуса Торвальдса, ради Бога не спрашивайте, а знает ли Торвальдс его! А вот к советам его отнеситесь осторожно. Если что-то кажется разумным, лучше перепроверьте сами, а так ли оно хорошо, как Вам расписывают.
Вот такой проверкой некоторых распространённых мифов об эффективности программных трюков мы сегодня и займёмся. Сразу предупреждаю, я не говорю о потенциальной эффективности того или иного трюка «вообще» на каких-то других процессорах или системах. Мне неинтересно что эффективно, а что нет на настольном PC, на андроиде или не Тианхе-2. Я буду лишь практически проверять «классические и бесспорные» утверждения об эффективности на конкретной ATMega328 с конкретным компилятором gcc, поставляемом с Arduino IDE. Утверждения, которые мы будем проверять, настолько хрестоматийны, что большинство людей просто ни на бит не сомневаются в их истинности.
Итак, приступим:
Миф №1. Умножение целого числа на степень двойки намного эффективнее реализуется сдвигом влево на соответствующее количество позиций
Пишем скетч, в котором определяем две функции m8 – умножение на восемь и s3 – сдвиг на три, и необходимую оснастку для запуска этих функций одинаковое количество раз с замером времени.
///////////////////////////
//
// Сравнение умножения на 8 и сдвига на 3
//
template <typename T> inline Print & operator << (Print &s, T n) { s.print(n); return s; }
const int m8(const int n) {
return n * 8;
}
const int s3(const int n) {
return n << 3;
}
const unsigned long TestIt(const int (* f)(const int), int & res) {
res = 0;
unsigned long start = millis();
for (int k = 0; k <= 256; k++)
for (int a = 0; a <= 3200; a++) res += f(a);
return millis() - start;
}
void setup() {
Serial.begin(115200);
int res = 0;
Serial << "*8 = " << TestIt(m8, res) << '\n';
Serial << "<< 3 = " << TestIt(s3, res) << '\n';
res ++;
}
void loop() {}
Получаем результат:
*8 = 2177 << 3 = 2177
Вывод: миф провалился. В нашей системе абсолютно безразлично что использовать: умножение на 8 или сдвиг на три.
Миф №2. Умножение целого числа на константу всегда эффективнее заменить на несколько сдвигов и сложений
На самом деле это следствие первого мифа, потому мы вправе ожидать такого же результата. Проверим:
///////////////////////////
//
// Сравнение умножения на 10 и сумма сдвигов на 3 и на 1
//
template <typename T> inline Print & operator << (Print &s, T n) { s.print(n); return s; }
const int m10(const int n) {
return n * 10;
}
const int s31(const int n) {
return (n << 3) + (n << 1);
}
const unsigned long TestIt(const int (* f)(const int), int & res) {
res = 0;
unsigned long start = millis();
for (int k = 0; k <= 256; k++)
for (int a = 0; a <= 3200; a++) res += f(a);
return millis() - start;
}
void setup() {
Serial.begin(115200);
int res = 0;
Serial << "*10 = " << TestIt(m10, res) << '\n';
Serial << "<< 3 + << 1 = " << TestIt(s31, res) << '\n';
res ++;
}
void loop() {}
Получаем результат:
*10 = 1865 << 3 + << 1 = 2436
Вывод: миф провалился. В нашей системе умножить на 10 заметно эффективнее, чем сложить результаты сдвигов на три и на один.
Миф №3. Для определения попадает ли число в заданный интервал, вместо двойного сравнения и операции И, намного эффективнее использовать вычитание и одно сравнение. Например, для проверки попадает ли n в интервал [40 - 90], вместо
n >= 40 && n <= 90
следует писать
(unsigned)(n-40) <= 50
Опять же, пишем скетч и замеряем время:
///////////////////////////
//
// Сравнение двойного неравенства и одинарного с вычитанием
//
template <typename T> inline Print & operator << (Print &s, T n) { s.print(n); return s; }
const int dn(const int n) {
return n >= 40 && n <= 90;
}
const int on(const int n) {
return (unsigned)(n-40) <= 50;
}
const unsigned long TestIt(const int (* f)(const int), int & res) {
res = 0;
unsigned long start = millis();
for (int k = 0; k <= 256; k++)
for (int a = 0; a <= 3200; a++) res += f(a);
return millis() - start;
}
void setup() {
Serial.begin(115200);
int res = 0;
Serial << "Double = " << TestIt(dn, res) << '\n';
Serial << "Single = " << TestIt(on, res) << '\n';
res ++;
}
void loop() {}
Получаем результат:
Double = 1916 Single = 1917
Вывод: миф провалился. В нашей системе заметной разницы нет.
Миф №4. При инвертировании переменной, выбор из двух вариантов значительно медленнее вычитания текущего значения из суммы вариантов
Например n всегда принимает только одно из двух значений: a или b. Стоит задача инвертирования, если n==a, то присвоить n=b, а если n==b, присвоить n=a. Можно это записать как:
n = (n == a) ? b : a;
но миф утверждает, что гораздо эффективнее так:
n = (a + b) - n
Проверим:
///////////////////////////
//
// Сравнение выбора из двух против вычитания
//
template <typename T> inline Print & operator << (Print &s, T n) { s.print(n); return s; }
volatile int a = 10, b = 18;
const int Ch(const int n) {
return (n == a) ? b : a;
}
const int Sub(const int n) {
return (a + b) - n;
}
const unsigned long TestIt(const int (* f)(const int), int & res) {
res = 0;
unsigned long start = millis();
for (int k = 0; k <= 256; k++)
for (int a = 0; a <= 3200; a++) res += f(a);
return millis() - start;
}
void setup() {
Serial.begin(115200);
int res = 0;
Serial << "Choose = " << TestIt(Ch, res) << '\n';
Serial << "Substract = " << TestIt(Sub, res) << '\n';
res ++;
}
void loop() {}
Получаем результат:
Choose = 2021 Substract = 2125
Вывод: как видите, вычитание не то что, не лучше, а даже немного хуже.
Заметим, что если a и b – константы, и сумму a+b посчитать заранее, то миф всё равно проваливается. Модифицируйте скетч и проверьте это самостоятельно.
А ТЕПЕРЬ ПРИМЕР ВТОРОГО ПОДХОДА
При изготовлении движущихся роботов, или при рисовании окружностей и иных вещей на экране, частенько нужно вычислять квадратный корень (теорему Пифагора не может отменить даже Госдума!). При этом координата пиксела на экране – всегда целое число, а расстояния в комнате достаточно считать в целом количестве миллиметров (а то и сантиметров) – точнее не нужно.
Перед нами задача: для данного целого числа n определить целочисленный квадратный корень из него, т.е. определить наиболее близкое к точному значению корня целое число.
Можно поступить «в лоб» и записать нечто вроде:
const int fsqrt(const int n) {
return (n < 2) ? n : (int)(sqrt((double)n)+0.5);
}
Сравнение n < 2 нам нужно для учёта того факта, что корень из нуля всё равно равен 0, а корень из 1 – 1. Заодно и отбросим отрицательные значения n от греха подальше.
Основа этого решения – библиотечная функция sqrt. Мне лень сейчас лезть в исходники avr’овской библиотеки, но по опыту могу сказать, что на 95% она использует метод Ньютона, а на оставшиеся 5% – может быть разложение по формуле Тэйлора.
Функция sqrt хороша для вещественных чисел. Но у нас-то задача – получить целочисленное значение корня! Поэтому мы пойдём другим путём!
Для начала заметим, что максимальное число типа int в нашей системе – 32 767. Корень из него равен 181,0166, т.е., целый корень – 181. Теперь, зная, что искомое решение всегда больше 1 и не более 181 будем искать целый корень из n методом половинного деления. Т.е. делим интервал поиска пополам, смотрим куда попадает решение и ту половину куда оно попало, считаем новым интервалом поиска. Довольно быстро размер интервала сократится до 1 и тогда мы возьмём готовое решение. Примерно, так:
1. Установим нижнюю границу поиска L = 1
2. Установим верхнюю границу поиска H = 181
3. Если разность (H-L) меньше 2, вернём результат: ближайшее к точному решению из H и L
4. Возьмём середину между H и L (mid = (H+L) / 2)
5. Если mid*mid больше N, установим H=mid; иначе установим L=mid
6. Вернёмся к шагу 3.
Давайте напишем такую функцию. Как всегда, есть 100500 способов сделать это. Например, можно так:
inline const int _isqrt(const int n, const int l, const int h) {
register const int mid = (h + l) >> 1;
if (mid == l) return ((n - l*l) > (h*h - n)) ? h : l;
return (mid * mid > n) ? _isqrt(n, l, mid) : _isqrt(n, mid, h);
}
const int isqrt(const int n) {
return (n < 2) ? n : _isqrt(n, 1, 181);
}
Потребовалась вспомогательная функция _isqrt которая, к тому же, вызывает саму себя (в последней строке)! Такие функции называются рекурсивными (если хотите, я могу сделать о них отдельный этюд).
Итак, поехали, сравниваем решение через sqrt с решением на основе половинного деления.
template <typename T> inline Print & operator << (Print &s, T n) { s.print(n); return s; }
const int fsqrt(const int n) {
return (n < 2) ? n : (int)(sqrt((double)n)+0.5);
}
inline const int _isqrt(const int n, const int l, const int h) {
register const int mid = (h + l) >> 1;
if (mid == l) return ((n - l*l) > (h*h - n)) ? h : l;
return (mid * mid > n) ? _isqrt(n, l, mid) : _isqrt(n, mid, h);
}
const int isqrt(const int n) {
return (n < 2) ? n : _isqrt(n, 1, 181);
}
int res;
void setup() {
Serial.begin(115200);
unsigned long beg, en;
beg = millis();
for (int i = 0; i < 32767; res = isqrt(i++));
en = millis();
Serial << "ITime = " << (en - beg) << '\n';
beg = millis();
for (int i = 0; i < 32767; res = fsqrt(i++));
en = millis();
Serial << "FTime = " << (en - beg) << '\n';
}
void loop() {}
Результат
ITime = 493 FTime = 1509
Ну, что, в три раза!
Вот так, господа. Такая вот эффективность. Надеюсь, Вы поняли, подумать над алгоритмом куда как полезнее выискивания копеечной экономии на спичках отдельных машинных операциях.
Отчаянно плюсую!
Вы на самом деле так красноречивы, или используете чьи-то материалы?
Про рекурсии обязательно напишите.
Замечание 0. Сам я принадлежу к искренним приверженцам второго подхода (первый метод я называю кодовой оптимизацией, а второй - алгоритмической оптимизацией).
Замечание 1. Лично встречался с ситуациями, когда кодовая оптимизация давала выигрыш в разы и даже более порядка. Правда, примеры основаны на архитектуре Intel, что, впрочем, объяснимо, т.к. мое знакомство с Intel в несколько десятков раз продолжительнее, чем с Ардуино. А с AVR я вообще даже не приступал к знакомству в связи с Замечанием 0.
По поводу Мифа 1: Пример некорректен. Современные компиляторы умеют производить замену деления сдвигом. Так что реально выполняется один и тот же код. Не следует недооценивать оптимизирующие компиляторы.
По поводу Мифа 2: Пример необъективен. Он реально имеет место для некоторых процессоров, даже имеющих аппаратную операцию умножения (например, тот же IntelX86, где умножение на 10 выполняется медленнее 2 сдвигов и сложения), но для AVR это не так. Это просто нужно запомнить.
По поводу Мифа 3: Пример неочевиден: в примере используется арифметическая операция с неподдерживаемым аппаратно типом данных. Не вижу причин, по которым это должно работать быстро. Другими словами, нет такого мифа!
По поводу Мифа 4: Где Вы берете такие мифы, почему я о них ничего не знаю?
По поводу контрпримера: мне кажется, Вы немного жульничаете, используя знания о конкретных процессорах, т.к. результат сугубо спцифичен. Могу утверждать, что на Intel результат получится в обратную сторону, причем коэффициент окажатся поболее тройки. Разница специфики имеется с обеих сторон: для AVR это - отсутствие аппаратной порддержки операций с плавающей точкой, а для Intel - длинный конвейер, благодаря которому неправильно предсказанные переходы (а при двоичном поиске правильно их предсказать более, чем в 50% случаев невозможно) приводят к существенно бОльшим "пенальти", чем длительность арифметической операции с плавающей точкой.
В целом же с заявленным тезисом вполне согласен, жаль только, что для его подтверждения использованы не совсем корректные примеры.
Из собственного опыта вспоминаю два случая.
В одной из конференций FIDO пользователь взял пример реализации решета Эратосфена из SWAG (популярного сборника исходников) и как мог, оптимизировал его (кодовая оптимизация). После чего выложил, собственно, на конференцию с вопросом, можно ли еще чего оптимизировать. Надо сказать, что алгоритм "решета Эратосфена" имеет лишь словесную формулировку, предполагающую вычеркивание чисел на листе бумаги (грифельной доске, etc.), но без четко сформулированного алгоритма. Сам примененный алгоритм показался мне крайне неэффективным и программа, в которой был применен другой (неоптимизированный) алгоритм того же "решета Эратосфена" оказалась примерно в 4200 раз быстрее. И, хотя выложенный мной алгоритм был явно неоптимизированный, применять к нему какую-либо кодовую оптимизацию больше никто не решился.
С другим прмеро столкнулся по работе. Была некоторая програма, которая производила некоторые вычисления. Делала она это в течение 12 минут. Для научной программы время вполне вменяемое - некоторые считаются месяцами. Но меня оно не устроило, т.к. требовалось провести порядка 10000 расчетов.
Заглянул внутрь исходника.
Аогоритм обработки данных мне был неизвестен, но смутило использование циклов.
Первое, что сделал, переставил в тексте 2 строки в другое место. Длина исходника, естественно, осталась прежней, набор строк - тоже (изменился лишь их порядок), неизменным оказался и результат расчета. Но программа вместо 12 минут работала 40 секунд.
Вдохновленный первым успехом, я решил на этом не останавливаться: ввел два дополнительных массива и изменил еще 4-5 строк с целью использовать эти массивы. При неизменном результате расчета время сократилось до 2 секунд.
Прикрнув, что если я запущу программу, перебирающую варианты, на счет с вечера, то к утру данные будут посчитаны, я не стал более вникать в особенности конкретной программы, так что основной алгоритм так и остался для меня за семью печатями.
Но главный вывод - нужно правильно использовать циклы, не оставляя в них ничего лишнего. Особенно в цикле с максимальной вложенностью.
Было бы хорошо дополнять каждый пример ассемблерным кодом, тогда можно было бы видеть, что компилятор реализовал разные расчёты, а не оптимизировал код и он получился одинаковым. За одним можно были бы развить и эту тему, как получить ассемблерный исходник. Возможно кому то это бы пригодилось.
Сам я сторонник простого кода, который компилятор и без меня оптимизирует, но, при этом код остаётся читабельным, понятным. Это следствие постоянной работой в группе, да и опыт показывает, что это более эффективно, меньше возможностей допустить ошибку. Короче, детство давно прошло.
Верные замечания. Присоединюсь полностью.
Дополнительно по вариантам:
1. avr-gcc легко оптимизирует умножение сдвигами и даже сам догадывается когда сдвиги правильнее сводить в цикл, а когда сделать их подряд в лоб. Оптимизация не работает когда оба множителя в переменных .. но тут только "знание" о содержимом одного из множителей (делителе) может помочь: заменить умножение/деление сдвигом в цикле по второму операнду.
2. Пример некорректен. Как раз в системах имеющих аппаратное умножение заменять его сдвигами и сложениями - не комильфо. Кодовая оптимизация предполагает замену долгих вычислений библиотечных функций аппаратным коротким циклом. Тут вам полезнее будет пример с делением: преобразование микросекунд в сантиметры - рекомендуется в Wiring деление на константу 59 .. в то время как можно умножить на 343 и сдвинуть на 11 бит. Проверяем..
/////////////////////////// // // Сравнение умножения на 10 и сумма сдвигов на 3 и на 1 // template <typename T> inline Print & operator << (Print &s, T n) { s.print(n); return s; } const int m10(const int n) { return n / 59; } const int s31(const int n) { return (n * 343)>>11; } const unsigned long TestIt(const int (* f)(const int), int & res) { res = 0; unsigned long start = millis(); for (int k = 0; k <= 1000; k++) for (int a = 0; a <= 1000; a++) res += f(a); return millis() - start; } void setup() { Serial.begin(9600); int res = 0; Serial << "*10 = " << TestIt(m10, res) << '\n'; Serial << "<< 3 + << 1 = " << TestIt(s31, res) << '\n'; res ++; } void loop() {} Результат: *10 = 15558 << 3 + << 1 = 2899Я даже не стал полностью править ваш код .. как видим "выигрыш" от кодовой оптимизации более 5 раз. вывод: "не всё то золото, что блестит". :)
3. Первый раз слышу про ТАКОЙ миф .. возможно, где-то, когда-то так могло быть .. скорее всего там, где 2 ветвления могут существенно разсинхронизировать конвеер предвыборок. Тогда, да: лучше вычесть и один раз проверить (предсказатель подберет ОБА вариант и конвеер не развалится) вместо того, чтобы внезапно начать перезаливать кеш команд..
В любом случае, для AVR - не актуально.
4. Полностью аналогично 3 варианту. Весь вопрос в ветвлении: сбивает ли оно конвеер и насколько.
А вообще, по кодовой оптимизации и оптимизации алгоритмов на высоком уровне настоятельно рекомендую освоить книжку Касьянова по оптимизационным преобразованиям программ. Там есть описание, мат. доказательство и примеры применения всех 14 видов оптимизационного преобразования.
.. и часто "второй подход" - есть просто результат применения к некоему исходному алгоритму всех 14 типов преобразовний, что называется "влоб", итеративным методом. Это, когда-то оч. хорошо умел делать "Watcom C/C++ Compiler" (12 типов из 14) а также "Транслятор Альфа-6 системы Дубна" .. какой ещё компилятор-оптимизатор такое умеет - не в курсе. Но уж точно не Микрософт с Интелом и уж не avr-gcc и подавно.
kisoft, Ассемблерный код получить очень легко. Добавляете к той строке, которой компилиует ИДЕ текст без кавычек: "-Wa,-a=fname.asm" и получаете в текущем каталоге ассемблерный результат. Можно добавить ещё опций ассемблеру, линкеру и т.д., полностью ищите описание на avr-gcc там оно есть. Я - не помню. :)
andriano, ваш пример оптимизации - скорее всего относится к 14 типу по Касьянову: "оптимизация потока управления через поток данных". Надо заметить что 13 и 14 тип крайне сложно реализуются в компиляторах, а вот человеком применяются часто легко. Собственно это и называют "грамотным алгоритмом". :)
Было бы хорошо дополнять каждый пример ассемблерным кодом, тогда можно было бы видеть, что компилятор реализовал разные расчёты, а не оптимизировал код и он получился одинаковым.
поддерживаю, иначе фигня, а не развенчание мифов получается.
ЕвгенийП,
1. Я не считаю, что подлежат удовлетворению требования ТС вроде "Тех, кто со мной не согласен, прошу в моей теме не писать".
2. Вы не видите противоречия в том, что поднимаете общетеоретическую тему оптимизации, но согласны рассматривать ее исключительно на примере единственной конкретной архитектуры, причем, в некоторых случаях особенности этой архитектуры ставите вперед приоритета алгоритмической оптимизации над кодовой?
3. Вас не смущает, что "Мифы" Вы берете из одной архитектуры (как правило, они справедливы для Intel или для некоторого прошлого поколения Intel), а "опровергаете" на совершенно другой?
4. Ничего, что "Пример второго подхода" на самом деле демонстрирует не правило, а исключение: на конкретной аппаратной платформе алгоритм сложности O(log(N)) оказывается быстрее алгоритма O(1)? Это что подтверждает? Что второй подход эффективней первого или, наоборот, что первый эффективней второго?
Люди, которые пока ещё ничего не знают про "некоторые процессоры", слышат байки и считают их универсальными. Я же хочу объяснить тем, кто программирует на Ардуино какие байки к ним относятся, а какие нет.
Это немного не соответствует тому, о чем Вы пишете в начале: существуют два подхода к оптимизации... Вы на самом деле показываете, что применительно к конкретной платформе AVR успеха можно добиться как с помощью одного, так и с помощью другого подхода.
С моей точки зрения, новичкам следует сначала понять, что реально существуют два подхода, и чем конкретно они различаются. После прочтения вашей темы у них, мне кажется, будет каша в голове, т.к. реально, в чем проявляется разница между подходами, они так и не поймут, зато вместо примера, демонстрирующего преимущество второго подхода, они получили пример, демонстрирующий преимущество первого (по видом второго).
PS. Я думаю, что тему Вы создали очень полезную, и что новичкам (а может, и не только новичкам) полезным окажется прочтение не только первого сообщения, но и всего обсуждения темы.
kisoft, Ассемблерный код получить очень легко. Добавляете к той строке, которой компилиует ИДЕ текст без кавычек: "-Wa,-a=fname.asm" и получаете в текущем каталоге ассемблерный результат. Можно добавить ещё опций ассемблеру, линкеру и т.д., полностью ищите описание на avr-gcc там оно есть. Я - не помню. :)
Вы думаете я не знаю как получить ассемблерный код? Я предпочитаю получать его другим способом и только когда это нужно и не в текущем каталоге.
Было бы хорошо дополнять каждый пример ассемблерным кодом,
Да, Господь с Вами, это же "этюды для начинающих". Всё, что я хотел сказать, это то. для данного компилятора своершенно неактуально заменять умножения на сдвиги и т.п. Сказал "не заменяйте", а почему ... это вопрос из другой лиги.
Кстати, заметили у меня в последнем примере танцы с бубнами вокруг глобальной переменной res? На самом деле, данный компилятор настолько умён, что стоит сделать её локальной, он второй цикл просто выбрасывает - время нулевое. Я сильно удивился и очень зауважал этот компилятор.
Да, компилятор хороший. Что одновременно довольно сильно усложняет написание программ, измеряющих скорость вычислений либо замер производительности.
У меня не было таких требований.
Я НЕ поднимаю общетеоретическую тему оптимизации. Я пишу о программировании в конкретной среде для конкретных процессора и компилятора, которые явно обозначил. Если мой текст навёл Вас на общетеоретические рассуждения, рассуждайте, но не приписывайте общетеоретические рассуждения мне.
Не согласен. Это общепрограмистские мифы. Я о них знал, когда интел ещё в сарае ютился
Это подтверждает главную мысль статьи: если правильно подойти к алгоритму, то можно получить существенную оптимизаицю здесь и сейчас (эта мысль, кстати, верна для любой платформы, раз уж Вы так любите универсальность)
Боюсь, что здесь Вы правы, раз каша появилась даже у Вас судя по тому, как упорно Вы приписываете мне общетеоретический замах :)
а не оптимизировал код и он получился одинаковым.
Понимаете мне всё равно получился он одинаковым или нет. Я лишь говорю, что на данном компиляторе в данной платформе нет смысла заменять умножение сдвигом. Голворю и привожу доказательство. Почему так? Одинаковый ли код? Я не про это. Мне всё равно! Я утверждаю, что смысла нет и демонстрирую это. Не ищите в этой статье то, чего в ней нет. Она не теоретическая - она о практике использования конкретной среды разработки и не более того.
Arhat109-2, ну на претензии к неуниверсальности я уже ответил другому коллеге, можете почитать, а вот один Ваш пассаж меня немного "улыбнул":
А вообще, по кодовой оптимизации и оптимизации алгоритмов на высоком уровне настоятельно рекомендую освоить книжку Касьянова по оптимизационным преобразованиям программ.
Вы это рекомендуете мне или "новичкам"? :))) Если мне, я передам Вашу рекомендацию Виктору Николаевичу, он тоже улыбнётся. А если серьъёзно, то глобальной оптимизации я учился у Валентина Федоровича Турчина а метавычислениям и суперкомпиляции у Сергея Михайловича Абрамова. Так что боюсь, что у Виктора Николаевича мне учится нечему :)))
Было бы хорошо дополнять каждый пример ассемблерным кодом,
Да, Господь с Вами, это же "этюды для начинающих".
да, ладно - я, хронически начинающий, внимательно жру попкорн и жду публикации корректной аргументации оптимальности кода.
Было бы хорошо дополнять каждый пример ассемблерным кодом, тогда можно было бы видеть, что компилятор реализовал разные расчёты, а не оптимизировал код и он получился одинаковым.
Понимаете мне всё равно получился он одинаковым или нет. Я лишь говорю, что на данном компиляторе в данной платформе нет смысла заменять умножение сдвигом. Голворю и привожу доказательство. Почему так? Одинаковый ли код? Я не про это. Мне всё равно! Я утверждаю, что смысла нет и демонстрирую это. Не ищите в этой статье то, чего в ней нет. Она не теоретическая - она о практике использования конкретной среды разработки и не более того.
я понял, это статья для тех, кто не может замерить время исполнения кода!
Это подтверждает главную мысль статьи: если правильно подойти к алгоритму, то можно получить существенную оптимизаицю здесь и сейчас (эта мысль, кстати, верна для любой платформы, раз уж Вы так любите универсальность)
Еще раз: Вы демонстрируете результаты измерений, согласно которым алгоримтм сложности O(log(N)) оказывается эффективнее алгоритма сложности O(1).
я понял, это статья для тех, кто не может замерить время исполнения кода!
Напрасно иронизируете.
Корректный замер времени выполнения кода при оптимизирующем компиляторе - задача нетривиальная.
Пасиба паржал. Дизассамблируем первый пример
Какая из двух одинаковых функций быстрей?! А умножение здесь ТС видит? Я нет.
Пример второй меняем в расчете int на long int. Получаем противоположный результат.
Напрасно иронизируете.
Корректный замер времени выполнения кода при оптимизирующем компиляторе - задача нетривиальная.
блин! я подозревал, что всё не так однозначно(с).
Какая из двух одинаковых функций быстрей?! А умножение здесь ТС видит? Я нет.
Блин, да Вы будете читать, что написано? Третьему уже объясняю - я писал о использовании умножения и свдигов в конкретном компиляторе для конкретной среды. То, что компилятор соптимизирует, я знаю не хуже Вас. Я всего лишь сказал, что при программировании для данного компилятором нет смысла заменять умножения на сдвиги. У Вас есть возражения? По-моему Вы только подтвердили мои слова своим дизассемблером. Вы это можете понять?
Ок, "лекция для колхозников", пожалуй, тогда нет смысла мешать.
Еще раз: Вы демонстрируете результаты измерений, согласно которым алгоримтм сложности O(log(N)) оказывается эффективнее алгоритма сложности O(1).
Это у метода Ньютона сложность O(1)? Ну, даже не знаю. Я никак не буду это комментировать.
ЕвгенийП, плюньте вы...
Главное продолжайте тему.
Блин, да Вы будете читать, что написано? Третьему уже объясняю - я писал о использовании умножения и свдигов в конкретном компиляторе для конкретной среды. То, что компилятор соптимизирует, я знаю не хуже Вас. Я всего лишь сказал, что при программировании для данного компилятором нет смысла заменять умножения на сдвиги. У Вас есть возражения? По-моему Вы только подтвердили мои слова своим дизассемблером. Вы это можете понять?
мне трудно не хамить, но ты ЕвгенийП выносишь мосг уже не новичкам, а профессионалам и у тебя это неплохо получается.
народ путается в мутной воде твоей статьи, не понимая, что ты пытаешься донести - по сути пять строк сложно было написать, вместо бесполезной простыни?
Вам конечно, но, в таком разе, не стоит писать ерунду и тем более новичкам. Один из ваших примеров я вам "опроверг", что называется наглядно. :)
P.S. Да, и компилятор довольно таки глупый. Ни разу не понимает что AVR это разрядность 8/16 бит .. и длинные числа гоняет в пачке регистров, заместо того, чтобы переставить команды и пользовать один и тот же байтовый. Как "итого" работа с длинными целыми вырождается в гемморой и вылезание на стек или в память. Ну и второй косяк: похоже он совсем не понимает структур на регистрах, из-за чего их использование как локалов - сильно ограничено.
Мифы 3 и 4 кроме ТС похоже никто не слышал. Я тоже.
Один из ваших примеров я вам "опроверг", что называется наглядно.
Ничерта Вы не опровергли. Вы просто привели другой пример. Мой пример был про умножение, а Ваш с делением. Вы не видите разницы? Ну, это не моя проблема.
То есть, вы ссылаетесь на "ветерана IBM" в статье для начинающих на AVR?!? .. о-о-о... молчу, молчу. :)
Главное продолжайте тему.
Да не знаю. Те, кому это было бы полезно - не читают. Уже третий этю и не было ни одного вопроса от "целевой аудитории".
Приходят два типа читателей: спецы, которые ждут от статьи чего-то другого и возмущаются. что не дождались. И "полуспецы", которые изо всех сил стараются "умность свою показать".
Мне бы пофигу, но беда в том, что целевая аудитория как раз не читает вовсе, а тогда какой смысл писать?
Я вижу более общую рекомендацию, которую вы умолчали, однако: "при отсутствии у процессора аппаратной команды - полезнее воспользоваться сдвигами вместо их имитации библиотечной функцией". Равно относится как к умножению, так и к делению. Например длинных целых, что вам уже показали. А вашей трактовке - получается ерунда, что меня и возмутило в этом этюде.
Вот после такого, извините, но общаться далее не хочется, ув. "кулхацкер". :(
Приходят два типа читателей: спецы, которые ждут от статьи чего-то другого и возмущаются. что не дождались. И "полуспецы", которые изо всех сил стараются "умность свою показать".
нда - не повезло тебе с народом: строем не ходят, пишут шопопало и не те, кому нужно писать.
Уважаемый, Клапауций,
мне почему-то казалось, что мы с Вами уже всё выяснили и попрощались с месяц назад. С тех пор я ни разу к Вам не обращался и ни разу не комментировал Ваши посты.
Не могли бы и Вы также игнорировать меня, если Вам не трудно, конечно?
Нет, если Вам трудно, то конечно - валяйте, бумага (а тем более. диски на сервере) всё стерпит. Только ответов не будет (это последнее, что я Вам пишу). Я Вам уже объяснил, что Вы для меня не существуете и был бы чрезвычайно признателен, если это было взаимно.
Уважаемый, Клапауций,
мне почему-то казалось, что мы с Вами уже всё выяснили и попрощались с месяц назад. С тех пор я ни разу к Вам не обращался и ни разу не комментировал Ваши посты.
Не могли бы и Вы также игнорировать меня, если Вам не трудно, конечно?
Нет, если Вам трудно, то конечно - валяйте, бумага (а тем более. диски на сервере) всё стерпит. Только ответов не будет (это последнее, что я Вам пишу). Я Вам уже объяснил, что Вы для меня не существуете и был бы чрезвычайно признателен, если это было взаимно.
ну, с чего бы мне перестать комментировать посты кого-либо на этом форуме?
я потратил время на попытку найти суть проблемы в твоей статье - пришёл к выводу, что ты в очередной раз вынес читателям мосг - вместо выяснения причины сабжа, ты констатировал факт, т.е. сделал половину из ожидаемого читателями, дело закончилось выяснением, кто кому, где и что должен писать.
*и, "да" - тебе показалось. :D
Дорогие новички, запомните, профессиональные врачи никогда не называют известные части тела их не менее известными фольклорными названиями, а профессиональные программисты называют программы программами, а серверы – серверами. Если же Вам доведётся встретить на своём пути «кул хацкера», проявите уважение, угостите его пивом и выслушайте восторженную речь про очередную «прогу» от которой, построившись в шеренгу, рыдают в платочек тупые майкрософтовцы, айбиэмовцы и прочая шушера. А когда он Вам скажет что знает Линуса Торвальдса, ради Бога не спрашивайте, а знает ли Торвальдс его! А вот к советам его отнеситесь осторожно. Если что-то кажется разумным, лучше перепроверьте сами, а так ли оно хорошо, как Вам расписывают.
"ЕвгенийП, плюньте вы...
Главное продолжайте тему."
Я бы процитировал ещё одно место в связи с указанием инициалов Касьянова: "... А когда он Вам скажет что знает Линуса Торвальдса, ради Бога не спрашивайте, а знает ли Торвальдс его! ..."
Вот поэтому и не стал "спрашивать". :)
А давайте продолжим тему. :)
Начну с простых вещей: определение пинов в скетчах.
Много где в рекомендациях к программированию для Ардуино пишут о том, что номера пинов правильнее определять как константы через #define, а не как переменные в памяти через int или другой целый тип. Типа:
Тем не менее, Wiring позволяет делать и так и эдак, а знатоки создающие библиотеки просто обожают второй подход. Аргументация: "это же либа! Откуда она узнает куда подключил юзверь этот девайс?"
Разница в результате, к примеру для Blink.ino - катастрофическая: рост размера примерно в 3 раза - цена за номер пина в переменной. И соответствующая его тормознутость в теже разы.
На самом деле, если учесть что все девайсы, а особенно дополнительные функции пинов в аппаратной реализации находятся на своих, жестко прописанных для них пинах платы, то решения как выйти из положения "я - писатель либы" - тривиальны:
1. Вариант "С": хранение номера пина в переменной и использование switch-case в либе для ветвления по конкретным командам управления нужным пином, где пин может быть привязан к диапазону. Так к примеру, есть 4 UART и, соответственно, конкретный пин передатчика (Tx) может быть 1 из 4 возможных. Можно предоставить юзверю переменную для хранения номера передатчика, и в коде либы втыкнуть switch(), который будет дергать требуемые регистры при конкретном значении переменной. Способ подходит для оптимизации использования аппаратных возможностей микроконтроллеров. Плата за него - ветвление по номеру в переменной.
*Примечание. Я не рассматриваю вариант получения номера пина из статического массива и формирования команды косвенного обращения к памяти по причине того, что этот подход реализован в Wiring и "оптимизирует" только ликвидацию "защит от дурака" в его функциях. Затраты на преобразование номера пина, к примеру у Мега2560 - несколько массивов по 70 штук, да ещё и по 2 байта на запись ибо храним "адрес" пина. Собственно это и есть "главный" рост размера.
2. Вариант "С++": использование классов - интерфейсов и/или TEMPLATE компиляции либы.
3. Смешанный вариант: реализация TEMPLATE компиляции силами препроцессора "С". Не так красиво выглядит в реализации, как вариант 2, но позволяет делать практически "тоже самое".
Как правило (на тех примерах, что мне присылали пользователи arhat.h), на больших скетчах выигрыш от перехода даже на вариант 1 позволяет сократить размер скетчей на 1000 - 1500 байт и ускорить их выполнение "на порядок" в первую очередь за счет устранения вызовов функций в "ногодрыгах".
"ЕвгенийП, плюньте вы...
Главное продолжайте тему."
Поддержу. А насчет отсутствия вопросов от конкретной аудитории, так информация должна уложиться, трансформироваться, а главное - потребоваться. Кому интересно, читают.
Комментарии зубров, тоже полезны, заставляют задуматься.
Про подход большинства неофитов я уже говорил - они пишут. Любимое слово - "ДАЙ".
Следующий момент "оптимизации" под Ардуино:
Все временные функции и многие либы активно используют типы (unsigned) long и их производные. На самом деле, микропроцессор не имеет встроенных команд для работы с таким типом данных, а равно компилятор не понимает что длинное целое это 4 отдельных байта. Ну и надо заметить, что количество доступных регистров для такого типа данных вовсе не 32, а существенно меньше, ибо часть из общего пула регистров занята "спец. задачами" у компилятора. Как итого, функция, имеющая 3-4 длинных локала резко возрастает в своем размере и теряет в скорости исполнения, ибо работа с такими локалами происходит "в памяти" микроконтроллера, а учитывая их локальность, то можно сказать точнее: "на стеке возвратов" ..
Как следствие, скетч может "внезапно" уходить в перезагрузку по причине "переполнения стека" и перезаписи его глобалом или прямым распределением из malloc(), ибо "памяти маловато". При компиляции, вроде как все кучеряво и даже есть "небольшой запас памяти" .. а при исполнении все валится в никуда. К сожалению, отловить ошибки такого рода - практически всегда крайне проблематично.
Особенно это опасно при наличии рекурсивных решений в скетчах. Это когда функция прямо или косвенно вызывает саму себя некоторое количество раз. Часто, в описаниях "эффективных" алгоритмов на других системах - рекурсия выглядит очень привлекательно и работает достаточно шустро. Но, об этой особенности рекурсий программист должен помнить всегда, и при необходимости понимать, что любой рекурсивный алгоритм преобразуется в линейный с помощью дополнительного цикла.
Ну и как рекомендация: не использовать без необходимости длинные целые числа, помня о том, что они резко просаживают общую производительность микроконтроллера. Каждое такое число, переданное как параметр увеличивает каждый вызов функции на 6(шесть) байт по сравнению с 16-и битным целым. То есть, размер вашего скетча растет пропорционально количеству таких вызовов без какой-либо пользы.
В этом смысле, типовые и крайне часто используемые функции времени из Wiring - и есть тот костыль из-за которого все работает "медленно и печально" и "жрет флеш и данные". Чем больше ковыряюсь в исходниках, тем сильнее прихожу к мысли, что разработчики приложили много усилий к тому, чтобы сделать скетчи для Ардуино плохо исполняемыми и стимулировали переход к нормальному ПО для програмирования, в противовес разработчикам Atmel, которые приложили супер много усилий, чтобы програмирование микроконтроллера выглядело легко и непринужденно. :)
Вот поэтому и не стал "спрашивать". :)
И совершенно напрасно. Всегда лучше спросить. чем что-то додумывать. Я открыт для вопросов.
А что касается, моих знакомств, таки да :)))) Например, вот здесь ежегодно собираются и общаются все, кто имеет отношение к соответсвующей отрасли - от студентов до академиков, от инжененеров до директоров заводов. Используются все формы общения: доклады, семинары, рюмка чая вечерком - всё. И это не единственное подобное мероприятие есть ещё 3-4 и тоже каждый год.
Спасибо за посты №39 и №41. Это как раз то, чего мне хотелось бы видеть в этой ветке.
Чем больше ковыряюсь в исходниках, тем сильнее прихожу к мысли, что разработчики приложили много усилий к тому, чтобы сделать скетчи для Ардуино плохо исполняемыми и стимулировали переход к нормальному ПО для програмирования,
Подозреваю, что цель была иная - чтобы любая кухарка могла не затрачивая особых усилий помигать диодом, посоветовать подружке купить подобный девайс и почувствовать себя программистом. Рынокс.
Ну и третий и четвертый, общие вопросы глобальной оптимизации скетчей:
3. "куча, локалы или глобалы а то и константы"?
Как ни странно, но в данном случае надо отдавать предпочтение с конца. То есть, если нечто у вас в скетче или либе НЕ изменяется, то это константа. Даже если это "настроечная константа в либе". Лучше вынести её в требуемый перед подключением либы #define или Template C++ чем хранить в переменной, даже глобальной.
Глобал часто предпочтительнее локала по причине, озвученной выше: плохо контролируемый расход стека. Ну и локал далеко не всегда ложится в регистр микроконтроллера. Чем длиннее тип данных - тем меньше шансов. А структурные типы данных не ложатся на регистры по причине "не умелости" компилятора.
Кучу в микроконтроллерах надо использовать вообще с особой острожностью, ибо памяти маловато. Отсюда, "классовое программирование" в целом нерекомендуется для микроконтроллеров. Ибо оператор new myClass() - полезет размещать объект в куче с высокой долей вероятности.
В целом тут должно действовать общее правило: "Чем раньше можно вынести решение о месте хранения компилятору (распределить объект в память), тем лучше".
4. C или С++, ООП, наследование и перегрузка операций особенно виртуальными методами.
Тут для микроконтроллеров в целом надо принимать тоже правило с точностью "наоборот": то, что так красиво и технично выглядит в тексте, зачастую требует дополнительных ресурсов как по объему, так и по скорости исполнения. Однако, стоит заметить, что ресурсов у микроконтроллера "с гулькин нос" и приносить их в жертву "красивости" кода не стоит ибо зачастую неоправдано. Как правило, код пишется один раз, и потом прошивается в микроконтроллер. После этой операции, уже в общем-то "все равно" насколько он красиво написан.
Поясню.
Все прелести ООП в виде виртуализации и наследования сводятся к созданию простой таблицы методов класса и последующим косвенным вызовам. Это "плата" за красивость текста на этапе его каждомоментного исполнения. Каждый вызов занимает 4-5 тактов. Косвенный вызов по таблице методов требует ещё тактов на поиск метода (формирование указателя) и он один у микроконтроллера. То есть ещё на его сохранение в стеке, доставание оттудова после вызова и т.д. В итого получаем проигрыш только на вызовах в 2-3 раза по сравнению со статической функцией. А если учесть, что ООП часто пользуют для реализации разных геттеров-сеттеров, то и того хуже: компилятор вполне справляется с inline подстановками коротких функций в 2-3 действия.
Так что, вывод: как только видим ООП, смотрим какой уровень наследований реализован (сколько дочерних классов, чтобы добраться непосредственно до кода) и .. выбрасываем такой код на помойку. :)
Для этого не требуется wiring ни в одном глазу. Atmel сделал все для того чтобы "любая кухарка..." :)
Ну вот меня там не было .. :)
Да и ваще .. читать конечно читаю, но даже в "прошлом" какое-то время работал в "закрытом режиме" и потом ещё 15 лет нигде не светился .. :)
Для этого не требуется wiring ни в одном глазу. Atmel сделал все для того чтобы "любая кухарка..." :)
Не соглашусь. Для вхождения при помощи метода Ардуино требуется: Скачать IDE, подключить плату, открыть пример "Blink", залить в контроллер. Супер, я программист и умею мигать диодом. Максимум полчаса.
Сколько займет времени по методу Atmel?
На моей практике - ровно столько же. Поставить авр-студию, скачать пример, залить в МК. :)
Кстати, есть промежуточный вариант. Уже.
Скачать Ардуино ИДЕ, скачать из сети arhat.h залить пример, всё. Вы - супер. :)
P.S. а если вы обладатель Ардуино Мега2560, то ещё и в почти три раза "суперовее", ибо в вашем варианте ваш скетч занимает 1500 с хвостиком, а в моем 550. :)
Ну вот меня там не было .. :)
Это ежегодное мероприятие. Welcome в 2016.
Ну и как рекомендация: не использовать без необходимости длинные целые числа, помня о том, что они резко просаживают общую производительность микроконтроллера.
Примеры, где примеры? Как можно обойтись без unsigned long в задаче Blink withour delay?