Этюды для начинающих: мрамор и штукатурка эффективности

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

«Во имя эффективности в программировании было совершено больше прегрешений (причем не всегда ее удавалось достичь), чем по какой-либо другой причине, включая непроходимую глупость» 
В. Вульф

В программировании существуют как минимум два диаметрально противоположных подхода к эффективности, отличающиеся друг от друга как штукатурка от мрамора. Первый подход основан на «тайных знаниях» об эффективности битовых операций и о том, сдвиг всегда быстрее умножения, а наложение маски быстрее вычисления остатка. Второй подход исходит из того, что рубль всегда больше копейки, и замена алгоритма на более эффективный (например, квадратичного на линейный, или экспоненциального на квадратичный), даст такое увеличение эффективности, которое не в состоянии дать и 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

Ну, что, в три раза!

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

Gippopotam
Gippopotam аватар
Offline
Зарегистрирован: 12.09.2014

Отчаянно плюсую!

Вы на самом деле так красноречивы, или используете чьи-то материалы?

Про рекурсии обязательно напишите.

andriano
andriano аватар
Онлайн
Зарегистрирован: 20.06.2015

Замечание 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 секунд.
Прикрнув, что если я запущу программу, перебирающую варианты, на счет с вечера, то к утру данные будут посчитаны, я не стал более вникать в особенности конкретной программы, так что основной алгоритм так и остался для меня за семью печатями.
Но главный вывод - нужно правильно использовать циклы, не оставляя в них ничего лишнего. Особенно в цикле с максимальной вложенностью.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015
andriano,
 
некорректны не примеры, а Ваши замечания.
 
Я заранее чёрным по белому предупредил, что "Сразу предупреждаю, я не говорю о потенциальной эффективности того или иного трюка «вообще» на каких-то других процессорах или системах. Мне неинтересно что эффективно, а что нет на настольном PC, на андроиде или не Тианхе-2. Я буду лишь практически проверять «классические и бесспорные» утверждения об эффективности на конкретной ATMega328 с конкретным компилятором gcc, поставляемом с Arduino IDE".
 
А Вы мне что пишете?
 
1. "Современные компиляторы умеют ..." - конечно умеют. Я и говорю о совершенно конкретном компиляторе а вовсе не машинном коде или о чё-то ещё.
 
2. "... реально имеет место для некоторых процессоров ..." - я же предупреждал, что меня не интересуют "некоторые процессоры", всё написано для одного, конкретного процессора и одной конкретной системы программирования
 
3. " Вы немного жульничаете, используя знания о конкретных процессорах, т.к. результат сугубо спцифичен" - ДА, СПЕЦИФИЧЕН - я заранее написал, что это ТОЛЬКО для ...
 
4. " Могу утверждать, что на Intel " опять же, я заранее написал, что меня не волнует Intel как не волнует ни AMD, ни Power7, ни Longson
 
Люди, которые пока ещё ничего не знают про "некоторые процессоры", слышат байки и считают их универсальными. Я же хочу объяснить тем, кто программирует на Ардуино какие байки к ним относятся, а какие нет.
 
Весь материал посвящеё проверке мифов именно в среде Ардуино и нигде больше. Вы же наехали на меня за отсутсвие универсальности - не ставилась задача делать универсально и об этом было сразу ясно сказано.
 
Теперь поняли?
 
 
kisoft
kisoft аватар
Offline
Зарегистрирован: 13.11.2012

Было бы хорошо дополнять каждый пример ассемблерным кодом, тогда можно было бы видеть, что компилятор реализовал разные расчёты, а не оптимизировал код и он получился одинаковым. За одним можно были бы развить и эту тему, как получить ассемблерный исходник. Возможно кому то это бы пригодилось.

Сам я сторонник простого кода, который компилятор и без меня оптимизирует, но, при этом код остаётся читабельным, понятным. Это следствие постоянной работой в группе, да и опыт показывает, что это более эффективно, меньше возможностей допустить ошибку. Короче, детство давно прошло.

 

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

Верные замечания. Присоединюсь полностью.

Дополнительно по вариантам:

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 и подавно.

 

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

kisoft, Ассемблерный код получить очень легко. Добавляете к той строке, которой компилиует ИДЕ текст без кавычек: "-Wa,-a=fname.asm" и получаете в текущем каталоге ассемблерный результат. Можно добавить ещё опций ассемблеру, линкеру и т.д., полностью ищите описание на avr-gcc там оно есть. Я - не помню. :)

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

andriano, ваш пример оптимизации - скорее всего относится к 14 типу по Касьянову: "оптимизация потока управления через поток данных". Надо заметить что 13 и 14 тип крайне сложно реализуются в компиляторах, а вот человеком применяются часто легко. Собственно это и называют "грамотным алгоритмом". :)

Клапауций 123
Offline
Зарегистрирован: 06.12.2015

kisoft пишет:

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

поддерживаю, иначе фигня, а не развенчание мифов получается.

andriano
andriano аватар
Онлайн
Зарегистрирован: 20.06.2015

ЕвгенийП,

1. Я не считаю, что подлежат удовлетворению требования ТС вроде "Тех, кто со мной не согласен, прошу в моей теме не писать".

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

3. Вас не смущает, что "Мифы" Вы берете из одной архитектуры (как правило, они справедливы для Intel или для некоторого прошлого поколения Intel), а "опровергаете" на совершенно другой?

4. Ничего, что "Пример второго подхода" на самом деле демонстрирует не правило, а исключение: на конкретной аппаратной платформе алгоритм сложности O(log(N)) оказывается быстрее алгоритма O(1)? Это что подтверждает? Что второй подход эффективней первого или, наоборот, что первый эффективней второго?

Цитата:

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

Это немного не соответствует тому, о чем Вы пишете в начале: существуют два подхода к оптимизации... Вы на самом деле показываете, что применительно к конкретной платформе AVR успеха можно добиться как с помощью одного, так и с помощью другого подхода.
С моей точки зрения, новичкам следует сначала понять, что реально существуют два подхода, и чем конкретно они различаются. После прочтения вашей темы у них, мне кажется, будет каша в голове, т.к. реально, в чем проявляется разница между подходами, они так и не поймут, зато вместо примера, демонстрирующего преимущество второго подхода, они получили пример, демонстрирующий преимущество первого (по видом второго).
 

 

PS. Я думаю, что тему Вы создали очень полезную, и что новичкам (а может, и не только новичкам) полезным окажется прочтение не только первого сообщения, но и всего обсуждения темы.

kisoft
kisoft аватар
Offline
Зарегистрирован: 13.11.2012

Arhat109-2 пишет:

kisoft, Ассемблерный код получить очень легко. Добавляете к той строке, которой компилиует ИДЕ текст без кавычек: "-Wa,-a=fname.asm" и получаете в текущем каталоге ассемблерный результат. Можно добавить ещё опций ассемблеру, линкеру и т.д., полностью ищите описание на avr-gcc там оно есть. Я - не помню. :)


Вы думаете я не знаю как получить ассемблерный код? Я предпочитаю получать его другим способом и только когда это нужно и не в текущем каталоге.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

kisoft пишет:

Было бы хорошо дополнять каждый пример ассемблерным кодом, 

Да, Господь с Вами, это же "этюды для начинающих". Всё, что я хотел сказать, это то. для данного компилятора своершенно неактуально заменять умножения на сдвиги и т.п. Сказал "не заменяйте", а почему ... это вопрос из другой лиги.

Кстати, заметили у меня в последнем примере танцы с бубнами вокруг глобальной переменной res? На самом деле, данный компилятор настолько умён, что стоит сделать её локальной, он второй цикл просто выбрасывает - время нулевое. Я сильно удивился и очень зауважал этот компилятор.

andriano
andriano аватар
Онлайн
Зарегистрирован: 20.06.2015

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

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

andriano пишет:
"Тех, кто со мной не согласен, прошу в моей теме не писать

У меня не было таких требований.

andriano пишет:
 Вы не видите противоречия в том, что поднимаете общетеоретическую тему оптимизации

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

andriano пишет:
Вас не смущает, что "Мифы" Вы берете из одной архитектуры 

Не согласен. Это общепрограмистские мифы. Я о них знал, когда интел ещё в сарае ютился

andriano пишет:
Ничего, что "Пример второго подхода" ... Это что подтверждает?

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

andriano пишет:
После прочтения вашей темы у них, мне кажется, будет каша в голове

Боюсь, что здесь Вы правы, раз каша появилась даже у Вас судя по тому, как упорно Вы приписываете мне общетеоретический замах :)

 

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

kisoft пишет:

а не оптимизировал код и он получился одинаковым. 

Понимаете мне всё равно получился он одинаковым или нет. Я лишь говорю, что на данном компиляторе в данной платформе нет смысла заменять умножение сдвигом. Голворю и привожу доказательство. Почему так? Одинаковый ли код? Я не про это. Мне всё равно! Я утверждаю, что смысла нет и демонстрирую это. Не ищите в этой статье то, чего в ней нет. Она не теоретическая - она о практике использования конкретной среды разработки и не более того.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Arhat109-2, ну на претензии к неуниверсальности я уже ответил другому коллеге, можете почитать, а вот один Ваш пассаж меня немного "улыбнул":

Arhat109-2 пишет:

А вообще, по кодовой оптимизации и оптимизации алгоритмов на высоком уровне настоятельно рекомендую освоить книжку Касьянова по оптимизационным преобразованиям программ.

Вы это рекомендуете мне или "новичкам"? :))) Если мне, я передам Вашу рекомендацию Виктору Николаевичу, он тоже улыбнётся. А если серьъёзно, то глобальной оптимизации я учился у Валентина Федоровича Турчина а метавычислениям и суперкомпиляции у Сергея Михайловича Абрамова. Так что боюсь, что у Виктора Николаевича мне учится нечему :)))

Клапауций 123
Offline
Зарегистрирован: 06.12.2015

ЕвгенийП пишет:

kisoft пишет:

Было бы хорошо дополнять каждый пример ассемблерным кодом, 

Да, Господь с Вами, это же "этюды для начинающих".

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

kisoft пишет:

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

Клапауций 123
Offline
Зарегистрирован: 06.12.2015

ЕвгенийП пишет:

Понимаете мне всё равно получился он одинаковым или нет. Я лишь говорю, что на данном компиляторе в данной платформе нет смысла заменять умножение сдвигом. Голворю и привожу доказательство. Почему так? Одинаковый ли код? Я не про это. Мне всё равно! Я утверждаю, что смысла нет и демонстрирую это. Не ищите в этой статье то, чего в ней нет. Она не теоретическая - она о практике использования конкретной среды разработки и не более того.

я понял, это статья для тех, кто не может замерить время исполнения кода!

andriano
andriano аватар
Онлайн
Зарегистрирован: 20.06.2015

ЕвгенийП пишет:

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

Еще раз: Вы демонстрируете результаты измерений, согласно которым алгоримтм сложности O(log(N)) оказывается эффективнее алгоритма сложности O(1).

Лично я вижу здесь только две вещи:
1. Торжество первого подхода (кодовой оптимизации) над вторым (оптимизацией алгоритмической).
2. Демонстрацию конкретных особенностей (недостатков?) платформы AVR.
Если Вы видите что-то другое, напишите, что именно.

 

andriano
andriano аватар
Онлайн
Зарегистрирован: 20.06.2015

Клапауций 123 пишет:

я понял, это статья для тех, кто не может замерить время исполнения кода!

Напрасно иронизируете.

Корректный замер времени выполнения кода при оптимизирующем компиляторе - задача нетривиальная.

Logik
Offline
Зарегистрирован: 05.08.2014

Пасиба паржал. Дизассамблируем первый пример

000000be <_Z2m8i>:
  be:	9c 01       	movw	r18, r24
  c0:	83 e0       	ldi	r24, 0x03	; 3
  c2:	22 0f       	add	r18, r18
  c4:	33 1f       	adc	r19, r19
  c6:	8a 95       	dec	r24
  c8:	e1 f7       	brne	.-8      	; 0xc2 <_Z2m8i+0x4>
  ca:	c9 01       	movw	r24, r18
  cc:	08 95       	ret

000000ce <_Z2s3i>:
  ce:	9c 01       	movw	r18, r24
  d0:	93 e0       	ldi	r25, 0x03	; 3
  d2:	22 0f       	add	r18, r18
  d4:	33 1f       	adc	r19, r19
  d6:	9a 95       	dec	r25
  d8:	e1 f7       	brne	.-8      	; 0xd2 <_Z2s3i+0x4>
  da:	c9 01       	movw	r24, r18
  dc:	08 95       	ret

Какая из двух одинаковых функций быстрей?! А умножение здесь ТС видит? Я нет.

Пример второй меняем в расчете int на long int. Получаем противоположный результат. 

*10 = 4603
<< 3 + << 1 = 3621
 
Эксперимент поставленный заинтересованным в результате лицом может подтвердить любую теорию.
Надо же 32 бита авр умнжать не умеет одной командой.
 
Мифы 3 и 4 кроме ТС похоже никто не слышал. Я тоже.
 
С утверждением о том что быстрый алгоритм работает быстрей медленного согласен целиком!
 
ТС курить опции оптимизации gcc до просветления, в перерывах изучать препроцессор начиная с раздела вычисления константного выражения.
 
 
 
Клапауций 123
Offline
Зарегистрирован: 06.12.2015

andriano пишет:

Напрасно иронизируете.

Корректный замер времени выполнения кода при оптимизирующем компиляторе - задача нетривиальная.

блин! я подозревал, что всё не так однозначно(с).

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Logik пишет:

Какая из двух одинаковых функций быстрей?! А умножение здесь ТС видит? Я нет.

Блин, да Вы будете читать, что написано? Третьему уже объясняю - я писал о использовании умножения и свдигов в конкретном компиляторе для конкретной среды. То, что компилятор соптимизирует, я знаю не хуже Вас. Я всего лишь сказал, что при программировании для данного компилятором нет смысла заменять умножения на сдвиги. У Вас есть возражения? По-моему Вы только подтвердили мои слова своим дизассемблером. Вы это можете понять?

Logik пишет:

ТС курить опции оптимизации gcc до просветления, в перерывах изучать препроцессор начиная с раздела вычисления константного выражения.
 
 
Я бы Вас очень попросил не хамить. Если Вам не трудно, конечно. 
kisoft
kisoft аватар
Offline
Зарегистрирован: 13.11.2012

Ок, "лекция для колхозников", пожалуй, тогда нет смысла мешать.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

andriano пишет:

Еще раз: Вы демонстрируете результаты измерений, согласно которым алгоримтм сложности O(log(N)) оказывается эффективнее алгоритма сложности O(1).

Это у метода Ньютона сложность O(1)? Ну, даже не знаю. Я никак не буду это комментировать. 

Gippopotam
Gippopotam аватар
Offline
Зарегистрирован: 12.09.2014

ЕвгенийП, плюньте вы...

Главное продолжайте тему.

Клапауций 123
Offline
Зарегистрирован: 06.12.2015

ЕвгенийП пишет:

Блин, да Вы будете читать, что написано? Третьему уже объясняю - я писал о использовании умножения и свдигов в конкретном компиляторе для конкретной среды. То, что компилятор соптимизирует, я знаю не хуже Вас. Я всего лишь сказал, что при программировании для данного компилятором нет смысла заменять умножения на сдвиги. У Вас есть возражения? По-моему Вы только подтвердили мои слова своим дизассемблером. Вы это можете понять?

Я бы Вас очень попросил не хамить. Если Вам не трудно, конечно. 

мне трудно не хамить, но ты ЕвгенийП выносишь мосг уже не новичкам, а профессионалам и у тебя это неплохо получается.

народ путается в мутной воде твоей статьи, не понимая, что ты пытаешься донести - по сути пять строк сложно было написать, вместо бесполезной простыни?

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

ЕвгенийП пишет:
Вы это рекомендуете мне или "новичкам"? :))) Если мне, я передам Вашу рекомендацию Виктору Николаевичу, он тоже улыбнётся.

Вам конечно, но, в таком разе, не стоит писать ерунду и тем более новичкам. Один из ваших примеров я вам "опроверг", что называется наглядно. :)

P.S. Да, и компилятор довольно таки глупый. Ни разу не понимает что AVR это разрядность 8/16 бит .. и длинные числа гоняет в пачке регистров, заместо того, чтобы переставить команды и пользовать один и тот же байтовый. Как "итого" работа с длинными целыми вырождается в гемморой и вылезание на стек или в память. Ну и второй косяк: похоже он совсем не понимает структур на регистрах, из-за чего их использование как локалов - сильно ограничено.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Logik пишет:

Мифы 3 и 4 кроме ТС похоже никто не слышал. Я тоже.

Ну, знаете, про №3 - не я виноват, что Вы не читали Уоррена. Видимо, у Вас другие любимые авторы. А про №4 - даже не знаю, про этом много где пишется.
ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Arhat109-2 пишет:

Один из ваших примеров я вам "опроверг", что называется наглядно. 

Ничерта Вы не опровергли. Вы просто привели другой пример. Мой пример был про умножение, а Ваш с делением. Вы не видите разницы? Ну, это не моя проблема.

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

То есть, вы ссылаетесь на "ветерана IBM" в статье для начинающих на AVR?!? .. о-о-о... молчу, молчу. :)

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Gippopotam пишет:

Главное продолжайте тему.

Да не знаю. Те, кому это было бы полезно - не читают. Уже третий этю и не было ни одного вопроса от "целевой аудитории".

Приходят два типа читателей: спецы, которые ждут от статьи чего-то другого и возмущаются. что не дождались. И "полуспецы", которые изо всех сил стараются "умность свою показать".

Мне бы пофигу, но беда в том, что целевая аудитория как раз не читает вовсе, а тогда какой смысл писать?

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

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

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

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

Вот после такого, извините, но общаться далее не хочется, ув. "кулхацкер". :(

Клапауций 123
Offline
Зарегистрирован: 06.12.2015

ЕвгенийП пишет:

Приходят два типа читателей: спецы, которые ждут от статьи чего-то другого и возмущаются. что не дождались. И "полуспецы", которые изо всех сил стараются "умность свою показать".

нда - не повезло тебе с народом: строем не ходят, пишут шопопало и не те, кому нужно писать.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Уважаемый, Клапауций,

мне почему-то казалось, что мы с Вами уже всё выяснили и попрощались с месяц назад. С тех пор я ни разу к Вам не обращался и ни разу не комментировал Ваши посты.

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

Нет, если Вам трудно, то конечно - валяйте, бумага (а тем более. диски на сервере) всё стерпит. Только ответов не будет (это последнее, что я Вам пишу). Я Вам уже объяснил, что Вы для меня не существуете и был бы чрезвычайно признателен, если это было взаимно.

Клапауций 123
Offline
Зарегистрирован: 06.12.2015

ЕвгенийП пишет:

Уважаемый, Клапауций,

мне почему-то казалось, что мы с Вами уже всё выяснили и попрощались с месяц назад. С тех пор я ни разу к Вам не обращался и ни разу не комментировал Ваши посты.

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

Нет, если Вам трудно, то конечно - валяйте, бумага (а тем более. диски на сервере) всё стерпит. Только ответов не будет (это последнее, что я Вам пишу). Я Вам уже объяснил, что Вы для меня не существуете и был бы чрезвычайно признателен, если это было взаимно.

ну, с чего бы мне перестать комментировать посты кого-либо на этом форуме?

я потратил время на попытку найти суть проблемы в твоей статье - пришёл к выводу, что ты в очередной раз вынес читателям мосг - вместо выяснения причины сабжа, ты констатировал факт, т.е. сделал половину из ожидаемого читателями, дело закончилось выяснением, кто кому, где и что должен писать.

*и, "да" - тебе показалось. :D

SU-27-16
SU-27-16 аватар
Offline
Зарегистрирован: 13.08.2012

Дорогие новички, запомните, профессиональные врачи никогда не называют известные части тела их не менее известными фольклорными названиями, а профессиональные программисты называют программы программами, а серверы – серверами. Если же Вам доведётся встретить на своём пути «кул хацкера», проявите уважение, угостите его пивом и выслушайте восторженную речь про очередную «прогу» от которой, построившись в шеренгу, рыдают в платочек тупые майкрософтовцы, айбиэмовцы и прочая шушера. А когда он Вам скажет что знает Линуса Торвальдса, ради Бога не спрашивайте, а знает ли Торвальдс его! А вот к советам его отнеситесь осторожно. Если что-то кажется разумным, лучше перепроверьте сами, а так ли оно хорошо, как Вам расписывают.

"ЕвгенийП, плюньте вы...
Главное продолжайте тему."

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

Я бы процитировал ещё одно место в связи с указанием инициалов Касьянова: "... А когда он Вам скажет что знает Линуса Торвальдса, ради Бога не спрашивайте, а знает ли Торвальдс его! ..."

Вот поэтому и не стал "спрашивать". :)

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

А давайте продолжим тему. :)

Начну с простых вещей: определение пинов в скетчах.

Много где в рекомендациях к программированию для Ардуино пишут о том, что номера пинов правильнее определять как константы через #define, а не как переменные в памяти через int или другой целый тип. Типа:

#define pinLed 13 // так правильно
int        pinLed = 13; // так НЕ правильно
byte     pinLed = 13; // так и с любым иным типом тоже НЕ правильно.

Тем не менее, 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 байт и ускорить их выполнение "на порядок" в первую очередь за счет устранения вызовов функций в "ногодрыгах".

bwn
Онлайн
Зарегистрирован: 25.08.2014

SU-27-16 пишет:

"ЕвгенийП, плюньте вы...
Главное продолжайте тему."

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

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

Следующий момент "оптимизации" под Ардуино:

Все временные функции и многие либы активно используют типы (unsigned) long  и их производные. На самом деле, микропроцессор не имеет встроенных команд для работы с таким типом данных, а равно компилятор не понимает что длинное целое это 4 отдельных байта. Ну и надо заметить, что количество доступных регистров для такого типа данных вовсе не 32, а существенно меньше, ибо часть из общего пула регистров занята "спец. задачами" у компилятора. Как итого, функция, имеющая 3-4 длинных локала резко возрастает в своем размере и теряет в скорости исполнения, ибо работа с такими локалами происходит "в памяти" микроконтроллера, а учитывая их локальность, то можно сказать точнее: "на стеке возвратов" ..

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

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

Ну и как рекомендация: не использовать без необходимости длинные целые числа, помня о том, что они резко просаживают общую производительность микроконтроллера. Каждое такое число, переданное как параметр увеличивает каждый вызов функции на 6(шесть) байт по сравнению с 16-и битным целым. То есть, размер вашего скетча растет пропорционально количеству таких вызовов без какой-либо пользы.

В этом смысле, типовые и крайне часто используемые функции времени из Wiring - и есть тот костыль из-за которого все работает "медленно и печально" и "жрет флеш и данные". Чем больше ковыряюсь в исходниках, тем сильнее прихожу к мысли, что разработчики приложили много усилий к тому, чтобы сделать скетчи для Ардуино плохо исполняемыми и стимулировали переход к нормальному ПО для програмирования, в противовес разработчикам Atmel, которые приложили супер много усилий, чтобы програмирование микроконтроллера выглядело легко и непринужденно. :)

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Arhat109-2 пишет:

Вот поэтому и не стал "спрашивать". :)

И совершенно напрасно. Всегда лучше спросить. чем что-то додумывать. Я открыт для вопросов.

А что касается, моих знакомств, таки да :)))) Например, вот здесь ежегодно собираются и общаются все, кто имеет отношение к соответсвующей отрасли - от студентов до академиков, от инжененеров до директоров заводов. Используются все формы общения: доклады, семинары, рюмка чая вечерком - всё. И это не единственное подобное мероприятие есть ещё 3-4 и тоже каждый год.

Спасибо за посты №39 и №41. Это как раз то, чего мне хотелось бы видеть в этой ветке.

bwn
Онлайн
Зарегистрирован: 25.08.2014

Arhat109-2 пишет:

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

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

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

Ну и третий и четвертый, общие вопросы глобальной оптимизации скетчей:

3. "куча, локалы или глобалы а то и константы"?

Как ни странно, но в данном случае надо отдавать предпочтение с конца. То есть, если нечто у вас в скетче или либе НЕ изменяется, то это константа. Даже если это "настроечная константа в либе". Лучше вынести её в требуемый перед подключением либы #define или Template C++ чем хранить в переменной, даже глобальной.

Глобал часто предпочтительнее локала по причине, озвученной выше: плохо контролируемый расход стека. Ну и локал далеко не всегда ложится в регистр микроконтроллера. Чем длиннее тип данных - тем меньше шансов. А структурные типы данных не ложатся на регистры по причине "не умелости" компилятора.

Кучу в микроконтроллерах надо использовать вообще с особой острожностью, ибо памяти маловато. Отсюда, "классовое программирование" в целом нерекомендуется для микроконтроллеров. Ибо оператор new myClass() - полезет размещать объект в куче с высокой долей вероятности.

В целом тут должно действовать общее правило: "Чем раньше можно вынести решение о месте хранения компилятору (распределить объект в память), тем лучше".

4. C или С++, ООП, наследование и перегрузка операций особенно виртуальными методами.

Тут для микроконтроллеров в целом надо принимать тоже правило с точностью "наоборот": то, что так красиво и технично выглядит в тексте, зачастую требует дополнительных ресурсов как по объему, так и по скорости исполнения. Однако, стоит заметить, что ресурсов у микроконтроллера "с гулькин нос" и приносить их в жертву "красивости" кода не стоит ибо зачастую неоправдано. Как правило, код пишется один раз, и потом прошивается в микроконтроллер. После этой операции, уже в общем-то "все равно" насколько он красиво написан.

Поясню.

Все прелести ООП в виде виртуализации и наследования сводятся к созданию простой таблицы методов класса и последующим косвенным вызовам. Это "плата" за красивость текста на этапе его каждомоментного исполнения. Каждый вызов занимает 4-5 тактов. Косвенный вызов по таблице методов требует ещё тактов на поиск метода (формирование указателя) и он один у микроконтроллера. То есть ещё на его сохранение в стеке, доставание оттудова после вызова и т.д. В итого получаем проигрыш только на вызовах в 2-3 раза по сравнению со статической функцией. А если учесть, что ООП часто пользуют для реализации разных геттеров-сеттеров, то и того хуже: компилятор вполне справляется с inline подстановками коротких функций в 2-3 действия.

Так что, вывод: как только видим ООП, смотрим какой уровень наследований реализован (сколько дочерних классов, чтобы добраться непосредственно до кода) и .. выбрасываем такой код на помойку. :)

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

Для этого не требуется wiring ни в одном глазу. Atmel сделал все для того чтобы "любая кухарка..." :)

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

Ну вот меня там не было .. :)

Да и ваще .. читать конечно читаю, но даже в "прошлом" какое-то время работал в "закрытом режиме" и потом ещё 15 лет нигде не светился .. :)

bwn
Онлайн
Зарегистрирован: 25.08.2014

Arhat109-2 пишет:

Для этого не требуется wiring ни в одном глазу. Atmel сделал все для того чтобы "любая кухарка..." :)

Не соглашусь. Для вхождения при помощи метода Ардуино требуется: Скачать IDE, подключить плату, открыть пример "Blink", залить в контроллер. Супер, я программист и умею мигать диодом. Максимум полчаса.

Сколько займет времени по методу Atmel?
 

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

На моей практике - ровно столько же. Поставить авр-студию, скачать пример, залить в МК. :)

Кстати, есть промежуточный вариант. Уже.

Скачать Ардуино ИДЕ, скачать из сети arhat.h залить пример, всё. Вы - супер. :)

P.S. а если вы обладатель Ардуино Мега2560, то ещё и в почти три раза "суперовее", ибо в вашем варианте ваш скетч занимает 1500 с хвостиком, а в моем 550. :)

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Arhat109-2 пишет:

Ну вот меня там не было .. :)

Это ежегодное мероприятие. Welcome в 2016.

Tomasina
Tomasina аватар
Offline
Зарегистрирован: 09.03.2013

Ну и как рекомендация: не использовать без необходимости длинные целые числа, помня о том, что они резко просаживают общую производительность микроконтроллера.

Примеры, где примеры? Как можно обойтись без unsigned long в задаче Blink withour delay?