Comments 142
Спасибо за статью.
x86-64 процессор имеет 16 регистров для целых чисел и 16 YMM регистров для чисел с плавающей точкой.
Читал, что в суперскалярных процессорах (по крайней мере, начиная с Pentium) число физических регистров существенно превышает число архитектурных (физических несколько сотен, архитектурных 16). Почему ухудшение производительности у вас проявлялось при 20 аккумуляторах? Можете нащупать границу более точно? Возможно, производительность ограничивалась чем-то другим?
Производительность ограничивается именно архитектурными регистрами. Физические регистры компилятор использовать не может, их может только сам процессор использовать для своих внутренних оптимизаций, потому когда счётчиков становится много компилятору ничего не остаётся кроме как сложить их на стек. А дальше — читайте раздел про указатели, но уже применительно к «оптимизирующему» процессору, а не оптимизирующему компилятору.
Прочел на одном дыхании, спасибо за статью. Подскажите, можно ли как-то узнать количество функциональных блоков того или иного назначения и прочие параметры процессора в рантайме?
Последний пример впечатлил. Казалось, что в функции minmax1 операций меньше и она должна работать быстрее, чем в minmax2, где и операций больше и присваивания происходят на каждой итерации.
Как раз то, что присваивания происходят на каждой итерации и спасает: можно обойтись без проверок. А это — для процессора самое страшное.
Насколько я знаю, minmax2 можно ещё ускорить заменив [ ] на указатели, поскольку выражение a[ i ] воспринимается компилятором как: *(a + i * sizeof(int)), если вместо a[ i ] использовать *( a + i ), то необходимость в умножении отпадает, значит должна возрасти производительность.
void minmax2(int * a, int * b, int n)
{
for (int i = 0; i < n; i++) {
int min = *(a + i) < *(b + i)? *(a + i): *(b + i);
int max = *(a + i) < *(b + i)? *(b + i): *(a + i);
*(a + i) = min;
*(b + i) = max;
}
}
void minmax2(int * a, int * b, int n)
{
for (int i = 0; i < n; i++) {
int min = *(a + i) < *(b + i)? *(a + i): *(b + i);
int max = *(a + i) < *(b + i)? *(b + i): *(a + i);
*(a + i) = min;
*(b + i) = max;
}
}
Эти оптимизации были актуальны году так в 90.
Через двадцать лет компиляторы таки научились понимать основные паттерны, и правильно генерировать для них код.
Конечно баловаться указателями не стоит и сейчас, это ничуть не поможет производительности. С другой стороны тенденции процессоростроения приводят к тому что циклы, которые 5 лет назад нельзя было векторизовать, сейчас векторизуются.
Кстати про векторизацию в статье я не заметил — как же так?? (Заметил небольшой абзац… Очень странно что такой мелкий — векторизация это ключ к эффективности).
Вообщем мой совет — перестаньте думать о том как написать А+Б. Думаете алгоритмами, О-сложностями. Ручной анролл цикла — самая плохая идея, потому что мне надоело их заанроливать обратно. Компилятор прекрасно делает это сам, причем учитывает количество регистров на целевой архитектуре автоматически, делает вершнинг, если ваша развертка не кратна длинне вектора.
Так что — думайте алгоритмикой, не стесняйтесь пользоваться матбиблиотеками (где цикл вида A=B+C) уже и так вылизан. А такую оптимизацию — бросьте, не нужна она…
Через двадцать лет компиляторы таки научились понимать основные паттерны, и правильно генерировать для них код.
Конечно баловаться указателями не стоит и сейчас, это ничуть не поможет производительности. С другой стороны тенденции процессоростроения приводят к тому что циклы, которые 5 лет назад нельзя было векторизовать, сейчас векторизуются.
Кстати про векторизацию в статье я не заметил — как же так?? (Заметил небольшой абзац… Очень странно что такой мелкий — векторизация это ключ к эффективности).
Вообщем мой совет — перестаньте думать о том как написать А+Б. Думаете алгоритмами, О-сложностями. Ручной анролл цикла — самая плохая идея, потому что мне надоело их заанроливать обратно. Компилятор прекрасно делает это сам, причем учитывает количество регистров на целевой архитектуре автоматически, делает вершнинг, если ваша развертка не кратна длинне вектора.
Так что — думайте алгоритмикой, не стесняйтесь пользоваться матбиблиотеками (где цикл вида A=B+C) уже и так вылизан. А такую оптимизацию — бросьте, не нужна она…
IMHO, вы путаете пример и метод. Всегда найдётся алгоритм, которого нет в стандартных библиотеках. Или он есть, но неизвестно где. Или известно, но эту библиотеку нельзя использовать по причине несовпадения лицензий.
Так или иначе, нужно как минимум иметь представление о базовых методах оптимизации.
Так или иначе, нужно как минимум иметь представление о базовых методах оптимизации.
Эти оптимизации были актуальны году так в 90.Да ну? А что сейчас произошло? Почему сегодня, сейчас, мы получаем десятикратную оптимизацию от этих техник?
Через двадцать лет компиляторы таки научились понимать основные паттерны, и правильно генерировать для них код.Тем не менее они остались связаны рамками стандартов C/C++. Пример minmax1 vs minmax2 — очень показателен.
Кстати про векторизацию в статье я не заметил — как же так?? (Заметил небольшой абзац… Очень странно что такой мелкий — векторизация это ключ к эффективности).В очень ограниченном числе алгоритмов. Подавляющее большинство алгоритмов либо векторизуются плохо (и с этим ничего нельзя поделать), либо, наоборот — векторизуются очень хорошо (и тогда GPGPU — наше всё).
А такую оптимизацию — бросьте, не нужна она…Разработчики TensorFlow тоже так думали. Потому сделали логику на Питоне и «молотилку» — на C++ (и даже, говорят, специализированные железки есть). В результате на больших серверах больше половины времени уходит на исполнение питоновского скрипта, который «никого тормозить не может».
Ваша ссылка на TensorFlow лишний раз показывает что вы поверхностно вникаете в тему.
Да будет вам известно, для молотилки было сделано абсолютно ровно то, что я посоветовал ответом выше — «не стесняйтесь пользоваться матбиблиотеками». Для молотилки в TF используется Eigen.
https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwiryoftyorPAhXmJJoKHdkNDUMQFggeMAA&url=http%3A%2F%2Feigen.tuxfamily.org%2F&usg=AFQjCNGi0wxMLU4MgkIA4YRyJUH2dkiKCg&sig2=kMAXRZVw6H3HNc_Yw85JRg
Про TF я могу вам много чего рассказать. Главная к нему претензия что distributed версия там написана сыро.
>>В очень ограниченном числе алгоритмов. Подавляющее большинство алгоритмов либо векторизуются плохо (и с этим ничего нельзя поделать), либо, наоборот — векторизуются очень хорошо (и тогда GPGPU — наше всё).
Я бы сначала взглянул на вашу статистику, чтобы понять откуда взялось это странное высказывание.
Особенно в свете того что я выше написал «тенденции процессоростроения приводят к тому что циклы, которые 5 лет назад нельзя было векторизовать, сейчас векторизуются».
Да будет вам известно, для молотилки было сделано абсолютно ровно то, что я посоветовал ответом выше — «не стесняйтесь пользоваться матбиблиотеками». Для молотилки в TF используется Eigen.
https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwiryoftyorPAhXmJJoKHdkNDUMQFggeMAA&url=http%3A%2F%2Feigen.tuxfamily.org%2F&usg=AFQjCNGi0wxMLU4MgkIA4YRyJUH2dkiKCg&sig2=kMAXRZVw6H3HNc_Yw85JRg
Про TF я могу вам много чего рассказать. Главная к нему претензия что distributed версия там написана сыро.
>>В очень ограниченном числе алгоритмов. Подавляющее большинство алгоритмов либо векторизуются плохо (и с этим ничего нельзя поделать), либо, наоборот — векторизуются очень хорошо (и тогда GPGPU — наше всё).
Я бы сначала взглянул на вашу статистику, чтобы понять откуда взялось это странное высказывание.
Особенно в свете того что я выше написал «тенденции процессоростроения приводят к тому что циклы, которые 5 лет назад нельзя было векторизовать, сейчас векторизуются».
Ага. Вот как раз сейчас разбираюсь, почему в Eigen процедура умножения RowMajor матрицы на 3d вектор работает в 18 раз медленнее, чем написанная самостоятельно, при компиляции в в VS2015.
Вообще, в статьях не описаны различные хинты для C++, позволяющие ему автоматически векторизовать код и т.д.
Например, есть модификатор для pointer, который говорит о том, что его область данных (на которую он указывает со всеми adds/subs) не пересекается с другими.
Что автоматом разрешает кучу оптимизаций.
И таких модификаторов в C++ сейчас много.
Эх, примкну к меньшинству — согласен с тем, что на одном размышлении о тривиальных операциях много не получишь в скорости. За исключением очень (очень!) специфичных задач с которыми 99.9% процентов программистов не сталкиваются, любая проблема производительности решается тремя основными подходами:
1. Алгоритм (нотация большого О, о чем говорит предыдущий оратор)
2. Локальность данных (вот отличная статья на эту тему)
3. Отсутствие блокировок и узких мест (многопотчность)
1. Алгоритм (нотация большого О, о чем говорит предыдущий оратор)
2. Локальность данных (вот отличная статья на эту тему)
3. Отсутствие блокировок и узких мест (многопотчность)
Эх, примкну к меньшинству — согласен с тем, что на одном размышлении о тривиальных операциях много не получишь в скорости.Я получал в нескольких случаях ускорение от 3 до 10 раз на вот таких «тривиальных операциях». Да, код становилось сложнее читать и править — но подобное ускорение может быть, в зависимости от задачи, очень полезным.
2. Локальность данных (вот отличная статья на эту тему)Собственно почти вся описанная тут статья является небольшой частью этого подхода. В данном случае речь идёт о том, что обращение к регистрами — на порядок быстрее, чем даже к кешу L1, а вычисления — на порядок быстрее, чем принятие решений (ветвления) и нужно бы сделать так, чтобы компилятору ничто не мешало их использовать.
Ручной анролл цикла — самая плохая идея, потому что мне надоело их заанроливать обратно
Мой скромный опыт говорит ровно об обратном — развертки цикла очень хорошая техника. Я лично смог ускорить одну из операций (конвертация одного colorspace в другой) в 5 раз (одна из последних версий GCC). И такие примеры мне встречаются постоянно. В данном случае я занимался оптимизацией нашего медиасервера.
Ну давайте, скопируйте последний пример в http://gcc.godbolt.org/ и увидите что первый цикл ни один компайлер не смог осилить.
Второй (minmax2) был успешно векторизован, чем и обьясняется ускорение.
>> Думаете алгоритмами, О-сложностями.
Вот это как раз совет из 90х
Это конечно важно, но паттерны работы с памятью важнее.
Второй (minmax2) был успешно векторизован, чем и обьясняется ускорение.
>> Думаете алгоритмами, О-сложностями.
Вот это как раз совет из 90х
Это конечно важно, но паттерны работы с памятью важнее.
Откопал год как пылящийся хабровский пароль только ради выражения своего «фи». У вас получился невероятно самодовольный категоричный комментарий напрочь игнорирующий контр-примеры из статьи. Что забавно, вы продолжили игнорировать их упоминание и в последующих обсуждениях. Можете уже ясно и без экивоков пояснить, как пафосная фраза про
Через двадцать лет компиляторы таки научились понимать основные паттерны, и правильно генерировать для них код
может существовать в мире с оптимизацией minmax1() в minmax2()?
Ускорил код в 123 раза ручными оптимизациями. Шёл 2017 год. Компилятор — не искуственный интеллект. Он видит код, но не Понимает его. Ему надо ручками всё показывать, всё самому делать. Тогда и код быстрый будет.
Очень приятная статья. Прочитал с удовольствием, хотя всё это я знаю и применяю. Буду кидать этой ссылкой в начинающих программистов.
Насчет ветвлений — я лично столкнулся с проблемой производительности LFSR. Внутренний цикл LFSR Галуа проверяет равенство младшего бита нулю и в зависимости от этого ксорит или не ксорит содержимое регистра с константой. Когда мне удалось (путем написания программы на ассемблере) избавиться от условного перехода во внутреннем цикле — производительность возросла очень ощутимо. Во сколько раз — не измерял, но до оптимизации программа не справлялась с нагрузкой, а после оптимизации стала справляться. А все дело в том, что LFSR — это практически генератор случайных чисел, поэтому процессор, пытаясь предсказать переход на следующем проходе цикла, ошибается в среднем в 50% случаев. Это приводит к частому обнулению конвейера и большим задержкам в работе программы. Поэтому избавление от условного перехода и дает такой прирост производительности.
Кстати, избавление от условного перехода я делал не на основе cmovcc (хотя это было бы возможно), а на основе старого доброго sbc eax,eax. Это такой красивый трюк, и его можно реализовать на множестве процессоров. Познакомился я с ним на Z80 (SBC A,A). Даже там, без конвейера, он зачастую позволяет сильно оптимизировать программу за счет избавления от условных переходов.
Дык компилятор делает также — зачем вам ассемблер приспичил?
Если бы мой компилятор (VS2013) такое тогда делал — то я бы ассемблером и не занимался. Компилятор не смог — а какие у меня были основания ожидать, что какой-то другой компилятор это сможет? Плюс время на установку другого компилятора, портирование программы под него, испытания? Вы считаете, что это быстрее, чем написать внутренний цикл на ассемблере?
Если я знаю и умею, как написать на ассемблере быстрый код, и это быстрее, чем найти способ «подшаманить» C-код так, чтобы компилятор его хорошо скомпилировал — то почему не сделать на ассемблере? Если мы начинаем вникать в тонкости процессора с целью оптимизации программ — то логичный шаг писать на ассемблере, где все под контролем. Знание ассемблера в любом случае требуется. Но в первом случае требуется знание только ассемблера и процессора, а во втором — еще и знание тонкостей компилятора и/или библиотек. Что проще?
Если я знаю и умею, как написать на ассемблере быстрый код, и это быстрее, чем найти способ «подшаманить» C-код так, чтобы компилятор его хорошо скомпилировал — то почему не сделать на ассемблере? Если мы начинаем вникать в тонкости процессора с целью оптимизации программ — то логичный шаг писать на ассемблере, где все под контролем. Знание ассемблера в любом случае требуется. Но в первом случае требуется знание только ассемблера и процессора, а во втором — еще и знание тонкостей компилятора и/или библиотек. Что проще?
только MSVC не умеет компилировать ассемблерные вставки для x64 и ARM.
Я забыл уточнить, что разрабатываемая программа была предназначена для испытаний некоего железа, и она должна была работать именно и только на отдельно взятом компьютере — том, который стоял у меня на столе. Надеюсь, вы не станете утверждать, что при разработке такой программы необходимо обеспечить ее портируемость? Или что мне надо было купить более быстрый комп?
Вы считаете, что это быстрее, чем написать внутренний цикл на ассемблере?Я считаю что если вас волнует скорость работы вашей программы то первым делом нужно выкинуть никуда негодный интсрумент (MSVC) и взять годный (Intel C++ или Clang). Потом заниматься чем-то ещё.
Если я знаю и умею, как написать на ассемблере быстрый код, и это быстрее, чем найти способ «подшаманить» C-код так, чтобы компилятор его хорошо скомпилировал — то почему не сделать на ассемблере?Потому что всю программу вы не сможете писать на ассемблере. И «подшаманивать» код не нужно — достаточно сделать так, чтобы его можно выло ускорить хитрыми манипуляциями не меняя семантики — дальнейшее приличные компиляторы сделают за вас. Ещё раз, для тех кто в танке: MSVC приличным компилятором не является и никогда не являлся (хотя потихоньку движется в этом направлении — но качество генерируемого кода для его разработчиков имеет явно не самый высокий приоритет).
P.S. Есть случаи, когда даже clang, gcc и intel compiler не умеют генерировать хороший код (работа с битовыми массивами, например). В этом случае ассемблерные вставки вполне уместны.
первым делом нужно выкинуть никуда негодный интсрумент (MSVC) и взять годный (Intel C++ или Clang)
В общем случае — может быть. Но я решал частную задачу. И я ее решил наиболее быстрым и дешевым из доступных способов. Intel C++ стоит немалых денег. Clang нужно было ставить, портировать программу под него и испытывать. На это нужно время. Значительно большее, чем занимает написание на ассемблере внутреннего цикла LFSR. А что если бы и Clang не смог ускорить программу необходимым образом? Откуда мне было знать, может он это или нет? Вот в данном конкретном случае люди подсказали, что он может. Интересно, в 2014 мог ли? А ведь есть и другие случаи оптимизации, когда и Clang/Intel C++ не поможет. И что тогда? Так что ваше решение даже как общее не всегда годится. Оно затратнее.
Потому что всю программу вы не сможете писать на ассемблере.
Я этого и не делал. Я написал на ассемблере только коротенькую процедуру.
И «подшаманивать» код не нужно — достаточно сделать так, чтобы его можно выло ускорить хитрыми манипуляциями не меняя семантики — дальнейшее приличные компиляторы сделают за вас.
То, что вы описали, я и имел в виду под «подшаманить». Подумайте: чтобы написать C-код таким образом, чтобы компилятор смог его ускорить хитрыми манипуляциями, необходимо: 1) знать ассемблер и тонкости работы процессора; 2) знать, как данный конкретный компилятор компилирует те или иные конструкции языка в ассемблер, особенно те моменты, которые могут повлиять на возможность оптимизации; 3) написать программу, проверить с помощью дизассемблера, как она компилируется, и если не так, как хочется — то продолжать «шаманить»; 4) при необходимости сменить компилятор и вернуться к п. 2).
Это затратнее и по времени на подготовку, и по времени собственно работы. Даже по деньгам затратно (если требуется покупать лицензию на дорогой компилятор). Напротив, для написания нужного фрагмента на ассемблере требуется осуществить только п. 1).
Добавлю, что иногда оптимизация не помогает — код не удается ускорить в достаточной степени ни с помощью компилятора, ни с помощью ассемблера. В таких случаях приходится искать другие решения. Такие, как отказ от обработки данных в реальном времени, покупка вычислительных мощностей и т.д. И если действительно окажется, что оптимизация не помогает — то желательно это выяснить как можно раньше, чтобы избежать лишних затрат на нее времени и денег.
Лучше уж интринсики, ИМХО.
Интринизики — это хорошо, но они не всё покрывают. Скажем у процессора, начиная c лохматого 1985 года, есть операции для работы с битовыми массивами. И они реально дают ускорение. Но вот интринзиков — нету. В подобных случаях — выбора нет, только вставки на ассемблере.
А так — да, конечно, интринзики — безопаснее. Хотя «внутри» компилятора разницы нет.
Больше информации для аллокатора регистров у компилятораСтолько же. Вот не больше, не меньше, а ровно столько же. По крайней мере если использовать gcc/clang. Вставки на ассемблере и интринзики используют один и тот же синтаксис вообще! Фактически интринзики — это ассемблерные вставки, которые разработчики компилятора в него включили при «изготовлении». Разница только в том, что на интринзики — больше «глаз» смотрят, ошибки менее вероятны. Но с точки зрения генерации кода — разницы никакой.
Многие удивляются, откуда в GCC/Clang'е такой сложный и хитрый способ описания ассеблерных вставок — а ларчик просто открывался: этот синтаксис изначально не для ассемблерных вставок делался! Он используется при «изготовлении» компилятора для описания того, чего умеет CPU. Соответственно в RTL ассемблерные вставки, интринзики и даже «обычные» операции порождают более-менее одинаковые узлы…
а что за трюк? Если я не забыл, такая команда выставит флаг нуля и сбросит флаг переноса — независимо от того, что было в регистре А. И что дальше? Все равно же нужен переход.
К тому же — в чем смысл? На Z80 каждая команда занимает свое фиксированное кол-во тактов, которое задокументировано. Там надо избавляться от тактов, а не от переходов.
К тому же — в чем смысл? На Z80 каждая команда занимает свое фиксированное кол-во тактов, которое задокументировано. Там надо избавляться от тактов, а не от переходов.
Трюк в том, что будет в регистре eax после выполнения этой команды. Поскольку число вычитается само из себя — то результат был бы всегда 0, но команда sbc учитывает значение флага переноса ©. Если C=1, то в регистре после вычитания окажутся все единицы — 0xFFFFFFFF. Если C=0, то будет 0. После этого можно выполнить команду AND с константой. Таким образом, в eax будет либо 0, либо эта константа. Потом с ней ксорим состояние LFSR. Ксор регистра с нулем не изменяет его значение. Вот и получается, что мы либо ксорим регистр с константой, либо не ксорим, что и требовалось. И все без переходов.
Что же касается Z80, то там на переходы тоже требуется время (такты), хоть и фиксированное. Избавление от переходов = экономия тактов. Также облегчается выравнивание веток по количеству тактов, если это требуется для процедур реального времени, таких, как работа с магнитофоном или звуком.
Что же касается Z80, то там на переходы тоже требуется время (такты), хоть и фиксированное. Избавление от переходов = экономия тактов. Также облегчается выравнивание веток по количеству тактов, если это требуется для процедур реального времени, таких, как работа с магнитофоном или звуком.
вот пример для Z80 решения задачи: загрузить в аккумулятор число 1 либо число 6 в зависимости от состояния флага C:
Выполняется всегда за 18 тактов. С условными переходами было бы что-то вроде:
Это выполняется за 17 либо за 27 тактов, в среднем 22 (если оба значения флага C при входе в программу равновероятны).
SBC A,A
AND 7
XOR 1
Выполняется всегда за 18 тактов. С условными переходами было бы что-то вроде:
JP NC,XXX
LD A,6
JP YYY
XXX: LD A,1
YYY:
Это выполняется за 17 либо за 27 тактов, в среднем 22 (если оба значения флага C при входе в программу равновероятны).
Внутренний цикл LFSR Галуа проверяет равенство младшего бита нулю и в зависимости от этого ксорит или не ксорит содержимое регистра с константой.Вы имеете в виду что-то подобное, как я понял:
constexpr int xor_const = 57;
int foo(unsigned int a, unsigned int b) {
return a ^ ((b & 1) ? 0 : 57);
}
Так вроде бы компилятор с этим отлично справляется:
$ g++ -std=c++11 -O3 -S test.c -o- | c++filt .file "test.c" .text .p2align 4,,15 .globl foo(unsigned int, unsigned int) .type foo(unsigned int, unsigned int), @function foo(unsigned int, unsigned int): .LFB0: .cfi_startproc andl $1, %esi cmpl $1, %esi sbbl %eax, %eax andl $57, %eax xorl %edi, %eax ret .cfi_endproc .LFE0: .size foo(unsigned int, unsigned int), .-foo(unsigned int, unsigned int) .ident "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4" .section .note.GNU-stack,"",@progbits
Зачем тут ассемблер? Избавление от условного перехода — штука хорошая, но в ассеблер-то сразу зачем ударяться?
Мой компилятор (VS 2013) на момент написания программы (2014г) такого не сумел. Может быть, нужно было написать C-код с какими-то плясками с бубном, чтобы он смог оптимизировать, но я такой вариант не нашел. Может быть, это мог уже тогда GCC или LLVM, но… Скажу честно, мне проще и быстрее написать на ассемблере, чем выяснять, какой компилятор умеет делать такую оптимизацию и как надо писать C-код, чтобы он это сделал.
Я вообще не понимаю стремления «избавиться от ассемблера во что бы то ни стало». Может быть, для тех, кто с ассемблером знаком чисто теоретически, такой совет и полезен. Но не для меня. Я на нем писал большие и сложные программы много лет.
Я вообще не понимаю стремления «избавиться от ассемблера во что бы то ни стало». Может быть, для тех, кто с ассемблером знаком чисто теоретически, такой совет и полезен. Но не для меня. Я на нем писал большие и сложные программы много лет.
Может быть, для тех, кто с ассемблером знаком чисто теоретически, такой совет и полезен.Такой совет полезен для тех, кто работает в команде. Где, ужас, да, бывают люди, не знающие x86 ассемблера, а знающие ассемлер SPARC или там PowerPC. А C — у них у всех один.
Вы, случайно, не из тех людей, кто рекомендует писать программу «Hello World» в стиле "Enterprise"?
Упомянутая программа писалась мной единолично и для личного же применения. Вы этого не учли.
Упомянутая программа писалась мной единолично и для личного же применения. Вы этого не учли.
в функциях combine3 и combine4 переменная i объявляется 2 раза. статья норм.
Хорошая статья и просто написано. Жаль не указана версия gcc, но с векторизацией что gcc что msvc пока только делают первые робкие шаги.
С интересом прочёл про реассоциацию и условное копирование, такие простые вещи я не знал. Но постоянное в статье: «оптимизируем цикл на несколько циклов» это просто жесть, программисты узнают слово такты, раньше чем начинают учить ассемблер и это статья от программиста!?
«Поскольку не все наши лентопротяжные устройства были в порядке, я в срочном порядке был призван к порядку, чтобы сортировать данные разных порядков на несколько порядков быстрее.» Если не ошибаюсьэто Хигмана «Сравнительное изучение языков программирования», 1969 год
Как думают другие хабражители, стоит ли заменить «цикл» в статье на «такт»?
Автор, спасибо за статью! Хотелось бы добавить небольшое уточнение:
Может. Стандарт С99 ввёл ключевое слово restrict, которое сообщает компилятору, что области памяти не могут пересекаться. Разумеется, ответственность за непересечение ложится на программиста, но компилятор может применять оптимизации «как в Фортране». В С++ это ключевое слово так и не попало, но разработчики компиляторов его часто реализуют в виде расширения, например __restrict__ в GCC.
Компилятор не может точно знать, будут ли два указателя указывать на одну и ту же область памяти, и поэтому не выполняет некоторые оптимизации.
Может. Стандарт С99 ввёл ключевое слово restrict, которое сообщает компилятору, что области памяти не могут пересекаться. Разумеется, ответственность за непересечение ложится на программиста, но компилятор может применять оптимизации «как в Фортране». В С++ это ключевое слово так и не попало, но разработчики компиляторов его часто реализуют в виде расширения, например __restrict__ в GCC.
> Компиляторы могут применять только безопасные оптимизации. Это значит, что компилятор может изменять программу только так, чтобы это не изменило её поведение для всех входных данных.
Это несколько упрощенно.
1) Поведение может быть изменено для ситуации, не документированной в стандарте. Как пример — gcc 6.1 при -O2 выкидывает проверки this на NULL.
https://habrahabr.ru/company/abbyy/blog/308346/
2) Компилятор может выкинуть memset, используемый для очистки автоматической переменной от чувствительных данных (например, паролей). Ну и вообще плохо понимает, что кроме программы — есть ещё и окружение.
http://www.viva64.com/ru/d/0208/
3) gcc, начиная с -O2 использует strict-aliasing, то есть подразумевает, что в разных параметрах указатели указывают на разную память.
https://habrahabr.ru/post/114117/
4) В оптимизаторе могут быть ошибки. То есть автор оптимизации считает, что она безопасна, а на самом деле — не так. И в некоторых случаях это приводит к катастрофе. Классический пример — FORTRAN OE на OS 360, который выкидывал проверку на делителя на ноль. Точнее сначала делил, а потом уже проверял, не равен ли нуля делитель. Это у него так оптимизация общих подвыражений отработала.
5) -Ofast в gcc включает, например, такую небезопасные оптимизации, как -funsafe-math-optimizations и -fno-math-errno
Так что вариантов, как получить небезопасную оптимизацию — много. Мораль простая — отлаживаться сразу на нужном уровне оптимизации.
Это несколько упрощенно.
1) Поведение может быть изменено для ситуации, не документированной в стандарте. Как пример — gcc 6.1 при -O2 выкидывает проверки this на NULL.
https://habrahabr.ru/company/abbyy/blog/308346/
2) Компилятор может выкинуть memset, используемый для очистки автоматической переменной от чувствительных данных (например, паролей). Ну и вообще плохо понимает, что кроме программы — есть ещё и окружение.
http://www.viva64.com/ru/d/0208/
3) gcc, начиная с -O2 использует strict-aliasing, то есть подразумевает, что в разных параметрах указатели указывают на разную память.
https://habrahabr.ru/post/114117/
4) В оптимизаторе могут быть ошибки. То есть автор оптимизации считает, что она безопасна, а на самом деле — не так. И в некоторых случаях это приводит к катастрофе. Классический пример — FORTRAN OE на OS 360, который выкидывал проверку на делителя на ноль. Точнее сначала делил, а потом уже проверял, не равен ли нуля делитель. Это у него так оптимизация общих подвыражений отработала.
5) -Ofast в gcc включает, например, такую небезопасные оптимизации, как -funsafe-math-optimizations и -fno-math-errno
Так что вариантов, как получить небезопасную оптимизацию — много. Мораль простая — отлаживаться сразу на нужном уровне оптимизации.
Поведение может быть изменено для ситуации, не документированной в стандарте.Не может.
Как пример — gcc 6.1 при -O2 выкидывает проверки this на NULL.Эта ситуация документирована в стандарте. В правильно написанной программе она возникать не должна.
Компилятор может выкинуть memset, используемый для очистки автоматической переменной от чувствительных данных (например, паролей).Эта ситуация также документирована, да.
gcc, начиная с -O2 использует strict-aliasing, то есть подразумевает, что в разных параметрах указатели указывают на разную память.И это — тоже задокументеровано.
В оптимизаторе могут быть ошибки.И не только в оптимизаторе. В любой программе на сотни тысяч строк могут встречаться ошибки, увы.
Мораль простая — отлаживаться сразу на нужном уровне оптимизации.Да, причина тут другая: очень много вещей в разных библиотеках C++ рассчитаны на то, что компилятор будет оптимизировать программу. Оптимизируя программу под -O0 вы породите кучу ужаса…
Опровержение простое — https://habrahabr.ru/post/136283/ — посмотрите на пример 2. Ну и на https://habrahabr.ru/post/216189/ на разделение между undefined, unspecified и implementation-defined. Для undefined — поведение может меняться между неоптимизированным и оптимизированным кодом.
Насчет кучи ужаса — очень спорно. Оптимизируя алгоритм — я иногда получаю выигрыш по скорости в тысячу раз. А оптимизация компилятора — дает процентов 5-10 общего времени выполнения программы. Если у вас медленный кусок исполняется миллион раз в цикле — оптимизация сильно поможет. А если исполняется один раз — вы этого не заметите.
Ну ещё одно. Ориентация на возможности оптимизатора — это привязка к конкретному компилятору. Если нужна переносимость — лучше не закладываться на наличие оптимизаций. А inline — это не оптимизация, это свойство языка такое. Его как раз есть смысл всегда включать.
Насчет кучи ужаса — очень спорно. Оптимизируя алгоритм — я иногда получаю выигрыш по скорости в тысячу раз. А оптимизация компилятора — дает процентов 5-10 общего времени выполнения программы. Если у вас медленный кусок исполняется миллион раз в цикле — оптимизация сильно поможет. А если исполняется один раз — вы этого не заметите.
Ну ещё одно. Ориентация на возможности оптимизатора — это привязка к конкретному компилятору. Если нужна переносимость — лучше не закладываться на наличие оптимизаций. А inline — это не оптимизация, это свойство языка такое. Его как раз есть смысл всегда включать.
Для undefined — поведение может меняться между неоптимизированным и оптимизированным кодом.И любое из них будет корректным. Я уже писал статью про это: неопределённого поведения в программе быть не должно. Точка. Есть разные интсрументы, помогающие это реализовать, но если ваша программа содержит в себе неопределённое поведение, то вы ССЗБ.
А оптимизация компилятора — дает процентов 5-10 общего времени выполнения программы.Вы это серьёзно? Вы вообще когда-нибудь что-нибудь бенчмаркали? -O2 от -O0 отличается в типичном случае раза в 2-3, а иногда разница может быть и десятикратной.
Ориентация на возможности оптимизатора — это привязка к конкретному компилятору. Если нужна переносимость — лучше не закладываться на наличие оптимизаций.О как. А ничего что вся стандартная библиотека завязана на предположения о том, что оптимизирующий компилятор сделает с программой? Снизу доверху? Все эти iterator_traits и std::begin без приличного оптимизатора смысла не имеют.
А inline — это не оптимизация, это свойство языка такое.О как. Ну ладно.
Его как раз есть смысл всегда включать.А зачем? В соответствии со спецификациями от него одни беды: нужно убеждаться что разные модули включают одно и то же определение, что нет никаких конфликтов и т.д. и т.п. При этом на скорость работы программы это не влияет никак. Компилятор интерпретирующий
inline как satic — является полностью соответствующим стандарту, а вы же сами сказали, что завязываться на свойства конкретного компилятора как бы нехорошо.Прошу прощения за поздний ответ. Просто долго собирался померить.
> И любое из них будет корректным.
В это верится до первой лично пойманной ошибки в оптимизаторе. Ну, например, crash компилятора — явно не является корректным поведением. Правильная программа или нет — но компилятор вылетать не должен…
> если ваша программа содержит в себе неопределённое поведение, то вы ССЗБ.
Не факт. Это просто ограничение переносимости. Пример:
J.2 Undefined behavior
A program in a hosted environment does not define a function named main using one
of the specified forms (5.1.2.2.1).
Вы действительно думаете, что это запрет на написание ОС, драйверов, dll и библиотек, вызываемых из других языков? Нет, это лишь намек на то, что линкер может выкинуть все, не вызываемое из main. И ему надо специальным образом указать, что main отсутствует, и пролог вызывать не нужно (или нужно его явно вызвать нестандартными способами)
Так что когда вы пишите про то, что Си создан для написания переносимой ОС — не забывайте, что по стандарту Си написание ОС — это UB, то есть ССЗБ с вашей точки зрения.
А отношение авторов стандарта к UB хорошо показывает вот это место
J.5 Common extensions
J.5.1 Environment arguments
1 In a hosted environment, the main function receives a third argument, char *envp[],
that points to a null-terminated array of pointers to char, each of which points to a string
that provides information about the environment for this execution of the program
То есть третий аргумент в main — это UB. Но пользоваться можно.
> -O2 от -O0 отличается в типичном случае раза в 2-3, а иногда разница может быть и десятикратной.
Вы думаете оптимизация ускоряет передачу данных по ком-порту? Или работу с файлами? Даже если приложение работает с файлом данных и не ждет комп-порта — скорость определяется временем работы с диском. А уж на ARM920 при отсутствии FPU — и подавно. Ну вот вам результаты по самому затратному для процессора куску. На АРМ было лень, мерял на I386. Если интересно — перемеряю на ARM.
Счетная задача (кусок реальной), 10 тысяч циклов.
GCC 4.8.4 I386/ubuntu-IA64:
-O0 132.5 мкс на цикл
-Og 76.5 мкс на цикл
-Os 55.2 мкс на цикл
-O1 42.3 мкс на цикл
-O2 39.6 мкс на цикл
-O3 42.2 мкс на цикл
-Ofast 34.2 мкс на цикл
CLang 3.4-1 I386/ubuntu-IA64 FPU:
-O0 116.2 мкс на цикл
-Os 35.4 мкс на цикл
-O1 35.3 мкс на цикл
-O2 37.8 мкс на цикл
-O3 37.6 мкс на цикл
-Ofast 37.5 мкс на цикл
С++ Builder 5.0, FPU
без оптимизации — 122 мкс на цикл
с оптимизацией — 128 мкс на цикл
без оптимизации и с автоматическими регистровыми переменным — 120.5 мкс на цикл
с оптимизацией и с автоматическими регистровыми переменным — 52 мкс на цикл
Выводы:
1) Как и предполагалось, разница между -O1 и O2-O3 — порядка 7%.
2) -O2 и -O3 не обязательно ускоряют программу. Могут и тормозить.
3) -O1 нужен как-минимум из за inline и размещений локальных переменных в регистрах.
4) -O2 и -O3 в наших задачах применять не стоит. Ускорения почти нет, а опасность сбоя при оптимизации достаточно велика.
Если интересно, то можно исследовать подробнее, какие оптимизации что дают.
> А ничего что вся стандартная библиотека завязана на предположения о том, что оптимизирующий компилятор сделает с программой? Снизу доверху?
Да ну?! sin завязан? или read???
> Все эти iterator_traits и std::begin без приличного оптимизатора смысла не имеют.
А вот это — в нашей области ССЗБ. Использовать кучу есть смысл только, если виртуальная памяти больше физической. То есть имеется swap. А когда swap нету, зато памяти 480 килобайт — кучу можно использовать только одним спосбом — при старте выделить все нужно и дальше не трогать. Иначе это даже не ССЗБ — это МИНА. Из-за фрагментации кучи в любой момент может просто памяти не хватить.
Да и медленное это дело, куча. Если бы в выше протестированном примере вместо размещения массивов в стеке использовалось бы их размещение в куче — ну было бы минимум раза в 3 тормознее.
> Компилятор интерпретирующий inline как satic — является полностью соответствующим стандарту,
И что? Это не отменяет, что inline и register — свойства языка.
> а вы же сами сказали, что завязываться на свойства конкретного компилятора как бы нехорошо.
ОТНЮДЬ. я сказал, что не стоит завязываться на наличие оптимизаций. Потому что в любой момент может оказаться, что единственный компилятор — это gcc 2.95.4 из МСВС 3.0. Или что-то ещё хуже. Так что пишем примерно на С89 + пара фишек из С++ + нестандартные, но обычные вещи типа #pragma pack.
С другой стороны, следование стандарту не дает полной переносимости. Как вам машинка с 32битными байтами? Все ваши программы там пойдут? А машинка без кучи? А машинка, куда не влезает большая часть стандартной библиотеки? А машинка, где не все служебные подпрограммы gcc есть? То есть нету тех частей, что завязаны на ОС. Например — не работает инициализация статических переменных из подпрограмм.
Так что все оценивается комплексно. Если уж у вас Windows и GUI — так явно у вас машина с дополнительным кодом с litle endian. И все, что будет UB при big endian — тогда уж неважно.
> И любое из них будет корректным.
В это верится до первой лично пойманной ошибки в оптимизаторе. Ну, например, crash компилятора — явно не является корректным поведением. Правильная программа или нет — но компилятор вылетать не должен…
> если ваша программа содержит в себе неопределённое поведение, то вы ССЗБ.
Не факт. Это просто ограничение переносимости. Пример:
J.2 Undefined behavior
A program in a hosted environment does not define a function named main using one
of the specified forms (5.1.2.2.1).
Вы действительно думаете, что это запрет на написание ОС, драйверов, dll и библиотек, вызываемых из других языков? Нет, это лишь намек на то, что линкер может выкинуть все, не вызываемое из main. И ему надо специальным образом указать, что main отсутствует, и пролог вызывать не нужно (или нужно его явно вызвать нестандартными способами)
Так что когда вы пишите про то, что Си создан для написания переносимой ОС — не забывайте, что по стандарту Си написание ОС — это UB, то есть ССЗБ с вашей точки зрения.
А отношение авторов стандарта к UB хорошо показывает вот это место
J.5 Common extensions
J.5.1 Environment arguments
1 In a hosted environment, the main function receives a third argument, char *envp[],
that points to a null-terminated array of pointers to char, each of which points to a string
that provides information about the environment for this execution of the program
То есть третий аргумент в main — это UB. Но пользоваться можно.
> -O2 от -O0 отличается в типичном случае раза в 2-3, а иногда разница может быть и десятикратной.
Вы думаете оптимизация ускоряет передачу данных по ком-порту? Или работу с файлами? Даже если приложение работает с файлом данных и не ждет комп-порта — скорость определяется временем работы с диском. А уж на ARM920 при отсутствии FPU — и подавно. Ну вот вам результаты по самому затратному для процессора куску. На АРМ было лень, мерял на I386. Если интересно — перемеряю на ARM.
Счетная задача (кусок реальной), 10 тысяч циклов.
GCC 4.8.4 I386/ubuntu-IA64:
-O0 132.5 мкс на цикл
-Og 76.5 мкс на цикл
-Os 55.2 мкс на цикл
-O1 42.3 мкс на цикл
-O2 39.6 мкс на цикл
-O3 42.2 мкс на цикл
-Ofast 34.2 мкс на цикл
CLang 3.4-1 I386/ubuntu-IA64 FPU:
-O0 116.2 мкс на цикл
-Os 35.4 мкс на цикл
-O1 35.3 мкс на цикл
-O2 37.8 мкс на цикл
-O3 37.6 мкс на цикл
-Ofast 37.5 мкс на цикл
С++ Builder 5.0, FPU
без оптимизации — 122 мкс на цикл
с оптимизацией — 128 мкс на цикл
без оптимизации и с автоматическими регистровыми переменным — 120.5 мкс на цикл
с оптимизацией и с автоматическими регистровыми переменным — 52 мкс на цикл
Выводы:
1) Как и предполагалось, разница между -O1 и O2-O3 — порядка 7%.
2) -O2 и -O3 не обязательно ускоряют программу. Могут и тормозить.
3) -O1 нужен как-минимум из за inline и размещений локальных переменных в регистрах.
4) -O2 и -O3 в наших задачах применять не стоит. Ускорения почти нет, а опасность сбоя при оптимизации достаточно велика.
Если интересно, то можно исследовать подробнее, какие оптимизации что дают.
> А ничего что вся стандартная библиотека завязана на предположения о том, что оптимизирующий компилятор сделает с программой? Снизу доверху?
Да ну?! sin завязан? или read???
> Все эти iterator_traits и std::begin без приличного оптимизатора смысла не имеют.
А вот это — в нашей области ССЗБ. Использовать кучу есть смысл только, если виртуальная памяти больше физической. То есть имеется swap. А когда swap нету, зато памяти 480 килобайт — кучу можно использовать только одним спосбом — при старте выделить все нужно и дальше не трогать. Иначе это даже не ССЗБ — это МИНА. Из-за фрагментации кучи в любой момент может просто памяти не хватить.
Да и медленное это дело, куча. Если бы в выше протестированном примере вместо размещения массивов в стеке использовалось бы их размещение в куче — ну было бы минимум раза в 3 тормознее.
> Компилятор интерпретирующий inline как satic — является полностью соответствующим стандарту,
И что? Это не отменяет, что inline и register — свойства языка.
> а вы же сами сказали, что завязываться на свойства конкретного компилятора как бы нехорошо.
ОТНЮДЬ. я сказал, что не стоит завязываться на наличие оптимизаций. Потому что в любой момент может оказаться, что единственный компилятор — это gcc 2.95.4 из МСВС 3.0. Или что-то ещё хуже. Так что пишем примерно на С89 + пара фишек из С++ + нестандартные, но обычные вещи типа #pragma pack.
С другой стороны, следование стандарту не дает полной переносимости. Как вам машинка с 32битными байтами? Все ваши программы там пойдут? А машинка без кучи? А машинка, куда не влезает большая часть стандартной библиотеки? А машинка, где не все служебные подпрограммы gcc есть? То есть нету тех частей, что завязаны на ОС. Например — не работает инициализация статических переменных из подпрограмм.
Так что все оценивается комплексно. Если уж у вас Windows и GUI — так явно у вас машина с дополнительным кодом с litle endian. И все, что будет UB при big endian — тогда уж неважно.
> Все эти iterator_traits и std::begin без приличного оптимизатора смысла не имеют.
> кучу, кучу, кучи, куча, куче
При чем здесь куча? std::array, например, на стеке живет, но для него работают итераторы.
> кучу, кучу, кучи, куча, куче
При чем здесь куча? std::array, например, на стеке живет, но для него работают итераторы.
СПС, согласен. НО:
1) Непонятно, чем это лучше обычного массива
2) Это С++11, а у нас часть компиляторов понимает только С89 и С++ v.2 по Страустрапу
3) Думаю, что -O1 тоже хватит. Ибо главное — включить inline.
1) Непонятно, чем это лучше обычного массива
2) Это С++11, а у нас часть компиляторов понимает только С89 и С++ v.2 по Страустрапу
3) Думаю, что -O1 тоже хватит. Ибо главное — включить inline.
1) Непонятно, чем это лучше обычного массива
— Унифицирован с остальными контейнерами
— Есть свойство size()
— На нем определены оператор присвоения, swap
— Унифицирован с остальными контейнерами
— Есть свойство size()
— На нем определены оператор присвоения, swap
Но это же не наследование, а только унификация… То есть для написания короткого кода — удобно, А библиотеку матобработки на него переписывать смысла нету.
И вообще, пока жива МСВС — за рамки gcc 2.95.4 не выходим.
В МСВС просто код или собственноручно написанный или пришедший вместе с МСВС. И ВСЕ. Никакого другого кода ставит нельзя, ибо нарушается защищенность.
И вообще, пока жива МСВС — за рамки gcc 2.95.4 не выходим.
В МСВС просто код или собственноручно написанный или пришедший вместе с МСВС. И ВСЕ. Никакого другого кода ставит нельзя, ибо нарушается защищенность.
>Но это же не наследование
В STL и нет наследования. Там другие механизмы — концепты и черты (traits).
В STL и нет наследования. Там другие механизмы — концепты и черты (traits).
Потому и непонятно, зачем они нужны. Городить огород на темплейтах, ради совместимости с std::vector? Так вектор это куча. А куча — это уже нужна большая виртуальная память…
Вы не понимаете STL…
УГУ. я не понимаю, зачем в Си использовать STL. Более того, очень похоже, что это и комитет по стандартизации не понимает. В С++ есть несколько элементов, которые хочется использовать в Си. Но это далеко не STL.
Если можете — то объясните.
P.S. Если ещё точнее — я не понимаю, какие преимущества в конкретной задаче мне даст STL.
Если можете — то объясните.
P.S. Если ещё точнее — я не понимаю, какие преимущества в конкретной задаче мне даст STL.
УГУ. я не понимаю, зачем в Си использовать STL
Если вопрос «зачем STL именно в Си» — я вас обрадую: его там и нет. Ежели стоит вопрос «зачем STL если можно писать в Си-стиле»: используя STL, мы получаем более простой в написании и чтении, быстрый в написании, отладке и изменении, а также переносимый код с примерно таким же быстродействием, (высоковероятно) меньшим числом ошибок и всё за те же деньги.
Повторю вопрос «какие преимущества в конкретной задаче мне даст STL»? Именно в конкретной. С математической обработкой матриц небольшого, заранее известного размера.
АНАЛОГИЯ. Преимущества классов начинаются с наследования и полиморфизма. И если у нас в программе 3 солитона (и более никаких объектов) — скорее всего такую программу лучше писать без классов.
Прtимущества STL — это независимость от базового типа. Но базовый тип у нас всегда double.
Недостатки STL (точнее std::vector и аналогичных вещей):
1) До появления auto (C++11) код малочитаем.
2) Если использовать С++ — получается резкое уменьшение числа платформ. Фактически на С++11 есть всего 3 компилятора: gcc, clang и VCC++. Вылетает полувоенное и военное применение — МСВС
3) Разбухает размер кода (важно на FreeRTOS)
4) Ухудшается скорость за счет худшего использования кэша (заметно, когда мы бегаем по столбцам матрицы)
5) значительно ухудшается отладка алгоритма. Попробуйте сделать условный брейпоинт на A[1.1] > A[2,2]*100.
6) При передаче в качестве dll значительные части алгоритма передабтся исходным кодом в .h.
Это только слова. Для какой-то области они могут быть верны, для нашей — маловероятно. Перепишите этот метод на STL — посмотрим, что будет с читаемостью и переносимостью. язык- лучше С++ ver 2 (2ое издание Страустрапа)
АНАЛОГИЯ. Преимущества классов начинаются с наследования и полиморфизма. И если у нас в программе 3 солитона (и более никаких объектов) — скорее всего такую программу лучше писать без классов.
Прtимущества STL — это независимость от базового типа. Но базовый тип у нас всегда double.
Недостатки STL (точнее std::vector и аналогичных вещей):
1) До появления auto (C++11) код малочитаем.
2) Если использовать С++ — получается резкое уменьшение числа платформ. Фактически на С++11 есть всего 3 компилятора: gcc, clang и VCC++. Вылетает полувоенное и военное применение — МСВС
3) Разбухает размер кода (важно на FreeRTOS)
4) Ухудшается скорость за счет худшего использования кэша (заметно, когда мы бегаем по столбцам матрицы)
5) значительно ухудшается отладка алгоритма. Попробуйте сделать условный брейпоинт на A[1.1] > A[2,2]*100.
6) При передаче в качестве dll значительные части алгоритма передабтся исходным кодом в .h.
получаем более простой в написании и чтении, быстрый в написании, отладке и изменении, а также переносимый код с примерно таким же быстродействием, (высоковероятно) меньшим числом ошибок и всё за те же деньги.
Это только слова. Для какой-то области они могут быть верны, для нашей — маловероятно. Перепишите этот метод на STL — посмотрим, что будет с читаемостью и переносимостью. язык- лучше С++ ver 2 (2ое издание Страустрапа)
Обращение матриц методом Гаусса, переписано с Фортрана
bool Gauss_T1(int N, MATRIX& m1)
{
const double eps=1.0e-8;
const double minuseps=-eps;
bool Res = true;
for (int k = 0; k < N; k++) {
double mdiag = m1.A[k][k];
if ((mdiag < eps)&&(mdiag > minuseps)) {
for (int it = 0; it < N; it++)
m1.A[it][k] = m1.A[k][it] = 0.0;
Res = false;
} else {
double d = 1.0 / mdiag;
m1.A[k][k] = d;
double minusd = -d; // Чтобы избежать ошибки при оптимизации BC 3.1
int i;
for (i = 0; i < N; i++) {
if (i != k) {
m1.A[i][k] *= minusd;
m1.A[k][i] *= d;
};
};
for (i = 0; i < N; i++) {
if (i != k) {
for (int j = 0; j < N; j++) {
if (j != k)
m1.A[i][j] += m1.A[i][k] * m1.A[k][j] / d;
} // end for j
} // end if i != k
} // end for i
} // end else
}; // end for k
return Res;
}
>1) До появления auto (C++11) код малочитаем.
>2)… Вылетает полувоенное и военное применение — МСВС
Вместо того, чтобы доносить до нас то, что МСВС не может в C++11, лучше доносите до ВНИИИНС, или кого там, что C++11 — это хорошо.
>3) Разбухает размер кода
Только если в отладочной версии.
>4) Ухудшается скорость за счет худшего использования кэша
Поясните, с чего бы это хуже используется кэш?
>5) значительно ухудшается отладка алгоритма. Попробуйте сделать условный брейпоинт на A[1.1] > A[2,2]*100
Поясните. Не вижу проблем с этим у C++.
>2)… Вылетает полувоенное и военное применение — МСВС
Вместо того, чтобы доносить до нас то, что МСВС не может в C++11, лучше доносите до ВНИИИНС, или кого там, что C++11 — это хорошо.
>3) Разбухает размер кода
Только если в отладочной версии.
>4) Ухудшается скорость за счет худшего использования кэша
Поясните, с чего бы это хуже используется кэш?
>5) значительно ухудшается отладка алгоритма. Попробуйте сделать условный брейпоинт на A[1.1] > A[2,2]*100
Поясните. Не вижу проблем с этим у C++.
лучше доносите до ВНИИИНС, или кого там, что C++11 — это хорошо.
Точные цены не помню, но сертификация МСВС на конкретную железку — это примерно год и куча денег. Если железка уже сертифицирована — никто заново платить не будет.
>3) Разбухает размер кода
Только если в отладочной версии..
В любой. Разбухание идет за счет библиотечного кода. Судя по всему там iostream'овское ядро прилинковывается. Напишите программу без iostream но с STL и посмотрите по MAP, что подлинкуется, а что нет. Но на 100% не поручусь, просто разок эффект видел.
Поясните, с чего бы это хуже используется кэш?
Когда мы работаем с матрицей, она выделяется не одним куском, а построчно, причем при неудаче — в очень разных местах кучи. Проявляется, если мы ходим по столбцам. Ну как пример. 16К кэша.данных, две матрицы double 30*30. Если одним куском — они влезает в кэш. Если строки в 10 разных частях памяти — скорее всего не влезет.
>Попробуйте сделать условный брейпоинт на A[1.1] > A[2,2]*100
Поясните. Не вижу проблем с этим у C++.
Ну расскажите, как это сделать? И в каких отладчиках это возможно? Даже если отладчик позволяет вызывать функции, он не умеет на лету компилировать темплейты.
>Точные цены не помню, но сертификация МСВС на конкретную железку — это примерно год и куча денег. Если железка уже сертифицирована — никто заново платить не будет.
Я имел в виду вообще, а не «прямо сейчас». А то уже не в первый раз слышу, что в военных старинный компилятор.
>Когда мы работаем с матрицей, она выделяется не одним куском, а построчно, причем при неудаче — в очень разных местах кучи
А как вы это в Си делаете?
На счет условных брейкпоинтов — потыкался, действительно, работает через раз.
Я имел в виду вообще, а не «прямо сейчас». А то уже не в первый раз слышу, что в военных старинный компилятор.
>Когда мы работаем с матрицей, она выделяется не одним куском, а построчно, причем при неудаче — в очень разных местах кучи
А как вы это в Си делаете?
На счет условных брейкпоинтов — потыкался, действительно, работает через раз.
Я имел в виду вообще, а не «прямо сейчас».
А «вообще» там люди грамотные, цену проверки кода gcc на закладки понимают.
А как вы это в Си делаете?
double A[_MATR_SIZE_][_MATR_SIZE_];
Вся матрица — одним куском памяти.
Вся матрица — одним куском памяти.
std::array<double,_MATR_SIZE_,_MATR_SIZE_> A;
Вся матрица — тем же самым одним куском памяти.
Согласен. Вот только std::array — это С++11. А в С++ ver 2 по Страустрауп — только std:vector.
Вспомнился бородатый анекдот
— Армяне, лучше, чем грузин.
— Чем лучше?
— Чем грузин!
— Чем лучше?
— Чем грузин!
Да, можно взять явно непригодное средство и приделать к нему костыли. Но инженеры (в отличие от школьников), при выборе решения оценивают его плюсы и минусы.
Примерно понятно, что выиграет eigen от добавки туда наших алгоритмов. А что выиграем мы? Затраты на переделку кода понятны. Но что окупит хотя бы 10% этих затрат?
Поскольку все равно переписывать, то лучше добавить в eigen отсутствующие методы. Ну то же быстрое обращение симметричных матриц. Скорее всего у нас оно быстрее, чем то, что в eigen.
Когда делаешь что-то как хобби — можно делать как лучше. Когда работаешь — вопрос в том, как сделать эффективнее. И в ближайше переспективе и на 5-10 лет вперед. я не вижу преимуществ для нас от переделки под eigen.
Почитайте вот. Люди навелосипедили — и обогнали всех. Потому что любой велосипед — будет хорош для конкретной задачи, под которую его делали. А библиотека — делается под многие задачи, она проиграет велосипеду в конкретных тестах, но выиграет в куче других областей.
Когда делаешь что-то как хобби — можно делать как лучше. Когда работаешь — вопрос в том, как сделать эффективнее. И в ближайше переспективе и на 5-10 лет вперед. я не вижу преимуществ для нас от переделки под eigen.
Почитайте вот. Люди навелосипедили — и обогнали всех. Потому что любой велосипед — будет хорош для конкретной задачи, под которую его делали. А библиотека — делается под многие задачи, она проиграет велосипеду в конкретных тестах, но выиграет в куче других областей.
Не понял этого логического перехода, ну да ладно.
для перехода на eigen 5 тысяч строк кода надо будет переписать. При этом разумно оставить деление на прикладной код и библиотеку. И отсутствующие в eigen библиотечные методы добавить в него же.
Вы проверяли?
и у нас и в eigen — N**3. Но у нас ускорение за счет того, что метод применяется к заведомо симметричной матрице. Значит на больших N — выиграем. Дело же не в качестве кодирования, дело в алгоритмах. Найти бы хотя бы N*N*log(N) — ускорение было бы приличное.
Для меня эффективнее, во-первых, входит в критерии «лучше»
Ноев Ковчег строили любители, профессионалы строили Титаник.
Путь любителей — это делать шедевр. Увеличить качество на 5% за счет увеличения трудоемкости в 10 раз.
А путь профессионалов — работать с высоким КПД. Результат должен быть приличным по качеству. Но не таким идеальным, как у любителей.
у меня тоже бывало, что clang генерировал более эффективный код,
Вот-вот, я об этом. Пара процентов быстродействия — это путь любителей. Меня интересует только О(N). Вот сменить N**3 на N*logN — это классно. А мелочи оптимизации — малоинтересны. Чуть иная плата — и все меняется. Потому что скорость памяти на разных платах разная, тактовая проца разная… А когда мы оптимизируем последние проценты — речь идет о балансе между процом, памятью и кэшем.
Потому у них и ровные графики для их библиотеки — они оптимизировали ровно на свой комп.
Увы, нет, std::array строго одномерный, посмотрите документацию.
Правда можно написать свою реализацию подобного массива с произвольной мерностью.
Правда можно написать свою реализацию подобного массива с произвольной мерностью.
А завтра я подумал, что double — многовато,
я всегда говорю деткам, что я старый и глупый. Я не думаю — я знаю Расстояние до спутника GPS — 20 тысяч км. Точность измерения (псевдофаза) — 0.01 герц, то есть 2 миллиметра. 11 значащих цифр — это минимум. А во float — 7.5. Уж не говорю том, что по стандарту Си все вычисления идут в double (но это gcc умеет обходить). И вам придется переписывать sin и cos, причем ускорение вы получите только на машинах, с аппаратной float-математикой, но без аппаратного double.
Это проблема языка, а не STL. Причём, надо сказать, весьма старого.
Это проблема STL. В eigen её просто нет, потому что eigen использует модель индексов, а не указателей.
Плохой, негодный велосипед, откажусь от него, даже когда мне надо сгонять в магазин за хлебом.
ЕЩЁ РАЗ. я старый дурак, я не думаю — я знаю. Нам по болотам надо. Деньги мы так зарабатываем. По болотам — в болотных сапогах, в театр — в смокинге. А одна одежка на все — это для тех, кто «думает». А мы — знаем, куда мы идем. И почему мы одеты именно так.
Отдыхать и играться — можно и с STL и с кучей других технологий. Но на болото в смокинге я не полезу.
МСВС 3.0 с gcc 2.95.4 — это наши будни. Точнее были буднями, сменили все-таки на 5.0. Ибо ядро 2.4 — это очень жестоко. Но в любой момент может появится железка с ровно этой системой. или ещё хуже — с MS-DOS.
Ну так смените row-major на column-major layout, проблем-то, тоже мне
вы умный вы думаете. а я глупый. я знаю, что с одной и той же матрицей — то по строкам, то по столбцам. А транспонировать — медленно. Да и вообще, зачем героически преодолевать трудности, когда можно их просто не делать?
Я написал существенно более одного математического алгоритма, и ни разу мне не нужно было ставить подобные брейкпоинты
Ноль проблем. Приходите к нам работать. Это сильно дешевле — взять вас к нам на работу, чем мне в 50 лет переучиваться. я же не математик, так что с удовольствием всю матобработку вам отдам.
Вот только когда вы неделю просидите за ловлей хитрого плавающего бага — приду я и за день найду. Тупыми методами грубой силы. Но за конечное известное время. Зарабатывал я этим. Ловлей багов в чужих программах, в которых я ни черта не понимаю.
Так что давай уж сойдемся на том, что мне брекпоинты нужны. Причем хитрые, на комбинацию данных.
То у вас хипа нет и код разбухает, то аж shared object'ы есть.Речь о другом. У нас есть алгоритмы, которые мы даже под NDA не хотим распространять. А вы мне их предлагаете в темплейт вставить и в .h передавать.
Вспоминая недавний наш с вами разговор, random forest — достаточно наша область?
НЕ-А. Какая у вас железка? Можете фото кинуть? Вт если вы скажите, что у вас влезло на плату весом 110 грамм (без БП разумеется) — будет наша область. :-) Ну вот вам одна из наших железок. Старая, железо ещё не наше, а смежников, наш только софт. Тяжелая, килограмм 5, ибо рассчитана на то, что пара кубометров льда может влететь на капитанский мостик.
Наша программа - в ящике справа
Я не хочу вас расстраивать, но не во всех задачах обрабатываются данные со спутника GPS.Зато я вас огорчу — вы забыли тему разговора. Напоминаю мои слова "Прtимущества STL — это независимость от базового типа. Но базовый тип у нас всегда double.". У нас — так. Примите это как данность. Ей богу, я знаю наши задачи.
И вам придется переписывать sin и cos,Не придётся, у меня тут плюсы.
Прошу пояснений. Что, в С++ завелся float sin(float)? А если не переписывать — считать он будет в double.
Это как бы немножко разные вещи, и сравнивать их некорректно.Есть задача — представление векторов и матриц неопределенного (заранее неизвестного) размера. STL её решает неудобно. Eigen — намного более удобней. Сравнивается решение конкретной, нужной задачи. А сравнивать решения ненужных задач — это к тем, у кого сервера со 128 ядрами. Пусть опыты на себе ставят (типа на кошках. :-) ).
Да ладно там, согласны. Вы ведь почему-то ещё считаете, что это единственно правильный путь
УГУ. Потому что мы не ДУМАЕМ, а ЗНАЕМ. Но это уже политика. На нашем рынке -5-6 западных фирм. больших, по тысяче человек. И мы, вообще-то единственная российская компания. Нас — семеро. Мы делаем в 2 раза хуже, но в 10-20 раз дешевле. И собираемся на несколько лет захватить некий сегмент мирового рынка (пока китайцы не скопируют).
Вы предлагаете отказываться от контрактов, закрыть фирму и клепать, как все на PHP. А нам это неинтересно. Зато интересна наша работа. Более того, мы многое делаем под чужими именами. Контракт выигрывает огромная госкорпорация, а делаем-то все равно мы.
МСВС — это семечки. Ягодки — это грядущая работа микропроцессором с российскими микросхемами объемом… не падайте… 128 килобайт. Чтобы набрать 32 мега под linux — надо 256 корпусов. Нравится? Потому придется без линкуса совсем. ТЗ там такое, забавное, пару страниц прочитать можно, остальные — вообще говоря, нельзя. :-)
Потому что вы согласны туда идти. Не были бы согласны, авось, стоимость поиска адекватных специалистов была бы повыше.
УГУ. Мы решаем задачи. Решаем методами, пригодными для конкретных задач. А вы — дальше верьте, что ваши методы идеальны и… отказывайтесь от решения. Чем больше народу будут думать в «one C++ STL way» — тем больше контрактов перепадет нам. И тем больше будет лично у меня зарплата.
Так что разубеждать вас мне не выгодно. Выгодней для личного кармана — поддерживать ваши заблуждения, что только так и можно работать.
Какой-то сервер то ли HP, то ли Dell,
То есть у вас совсем другие работы. Ну тогда вы правы. Ставьте на себе опыты, обкатывайте технологию. Лет через 10-20 на вас технология обкатается — вот тогда и мы её применим.
>Что, в С++ завелся float sin(float)?
Не только float sin(float) http://en.cppreference.com/w/cpp/numeric/math/sin
но даже и complex<T> sin(const complex<T>&) http://en.cppreference.com/w/cpp/numeric/complex/sin
Не только float sin(float) http://en.cppreference.com/w/cpp/numeric/math/sin
но даже и complex<T> sin(const complex<T>&) http://en.cppreference.com/w/cpp/numeric/complex/sin
Вот только flt / 2.f все равно по стандарту Си будет иметь тип double. Или они и это заломали?
Стандарт C11 (думаю, и более старые тоже) гласит:
>6.3.1.8 Usual arithmetic conversions
>…
> Otherwise, if the corresponding real type of either operand is float, the other operand is converted, without change of type domain, to a type whose
corresponding real type is float
>The values of floating operands and of the results of floating expressions may be represented in greater range and precision than that required by the type; the types are not changed thereby
Так что компилятору разрешено промоутить промежуточный результат, но в результате все равно будет float.
C++ работает так же, ясное дело.
Так что если ваш компилятор выражение flt / 2.f превращает в double в результате, то он работает не по стандарту.
>6.3.1.8 Usual arithmetic conversions
>…
> Otherwise, if the corresponding real type of either operand is float, the other operand is converted, without change of type domain, to a type whose
corresponding real type is float
>The values of floating operands and of the results of floating expressions may be represented in greater range and precision than that required by the type; the types are not changed thereby
Так что компилятору разрешено промоутить промежуточный результат, но в результате все равно будет float.
C++ работает так же, ясное дело.
Так что если ваш компилятор выражение flt / 2.f превращает в double в результате, то он работает не по стандарту.
А обращение матриц лучше не переизобретать, а взять dlib, eigen или, упаси б-же, GSL.
Так может вообще, не писать самим, а взять стандартный RTKLIB? Этим путем пошли конкуренты. Вот только на все просьбы показать или устроить сравнительные испытания идет отказ. Потому что оно работает. Иногда. Когда помех совсем нету. А в реальных условиях — ну в общем не пашет. Так что у конкурентов решение как бы есть, статьи писать можно. Но вживую его никто никогда не видел. А мы — готовы показать в любой момент. Хоть у нас, хоть в Москве…
Из протокола испытаний лет 20 назад
Прибор работает: потребляет заданную мощность. Задача: обеспечить выработку требуемых измерений.
Так что уж разрешите нам своим путем идти.Чтобы оно работалоЮ а не только мощность потребляло Можно?
Я уже пытался ему объяснить вкус устриц.
Если вкратце, то стоит просто посмотреть, в какой машинный код превращается программа с использованием STL при компиляции с разной степенью оптимизации. Тогда можно начинать спорить.
Если вкратце, то стоит просто посмотреть, в какой машинный код превращается программа с использованием STL при компиляции с разной степенью оптимизации. Тогда можно начинать спорить.
Смотреть после опытов
Как ни странно, но STL-шаблоны бывают эффективнее С-кода. И можно сделать кастомный аллокатор на стеке, если смущает куча.
Сложно объяснять вкус устриц тому, кто ими уже отравился.
По опытам модернизации кода с STL
1) Код плохо читается. За нагромождением итераторов не видно структуры двухмерных и трехмерных массивов. Возможно «пару лет так пролежите, а потом привыкните».
2) Код плохо отлаживается. Сложно посмотреть содержимое массивов, не говоря уже о том, чтобы поставить условный брекпоинт.
3) Целый ряд специфических ошибок, связанных с указателями на уже отданную в систему память, выходом за границы массивов и так далее. Чуть исходные данные вышли из ожидаемого программистом — и опаньки. Возможно — дело в квалификации, но там, где STL не использовался, код был более толерантен к данным у тех же программеров.
4) Размер исходного кода больше, скорость написания и модернизации — ниже.
ВЫВОД: Не вижу смысла использовать STL, пока не нужно основное его преимущество — независимость от типа данных. Ну или хотя бы дополнительное преимущество — контейнеры переменного размера.
Не на стеке, а в статике надо. Ну как пример — объект, инкапсулирующий матрицу и алгоритмы к ней. При этом, чтобы все данные были внутри объекта, то есть адресуемы просто по адресу объекта. И чтобы была возможность статически создать такой объект. Выйдет? :-))))
По опытам модернизации кода с STL
1) Код плохо читается. За нагромождением итераторов не видно структуры двухмерных и трехмерных массивов. Возможно «пару лет так пролежите, а потом привыкните».
2) Код плохо отлаживается. Сложно посмотреть содержимое массивов, не говоря уже о том, чтобы поставить условный брекпоинт.
3) Целый ряд специфических ошибок, связанных с указателями на уже отданную в систему память, выходом за границы массивов и так далее. Чуть исходные данные вышли из ожидаемого программистом — и опаньки. Возможно — дело в квалификации, но там, где STL не использовался, код был более толерантен к данным у тех же программеров.
4) Размер исходного кода больше, скорость написания и модернизации — ниже.
ВЫВОД: Не вижу смысла использовать STL, пока не нужно основное его преимущество — независимость от типа данных. Ну или хотя бы дополнительное преимущество — контейнеры переменного размера.
И можно сделать кастомный аллокатор на стеке
Не на стеке, а в статике надо. Ну как пример — объект, инкапсулирующий матрицу и алгоритмы к ней. При этом, чтобы все данные были внутри объекта, то есть адресуемы просто по адресу объекта. И чтобы была возможность статически создать такой объект. Выйдет? :-))))
Вообще то статья не о качестве исходного кода, а об оптимизации.
STL наоборот, дает еще преимущества отсутствия необходимости работы с указателями и дает некоторую защиту от выхода за рейнж при отладке.
Зачем оптимизировать метод Гаусса компилятором или пытаться прикрутить к нему STL, если есть гораздо более эффективные _алгоритмы_? Неудачный пример, но не надо конечно везде совать шаблоны, согласен.
Статически или на стеке — для скорости работы не важно. Но невозможно для компилятора создать объект неизвестного заранее размера с фиксированным адресом. Да и не нужно.
Пример стекового аллокатора я привел, как оптимизация в плане исключения запросов выделения памяти ОС.
STL наоборот, дает еще преимущества отсутствия необходимости работы с указателями и дает некоторую защиту от выхода за рейнж при отладке.
Зачем оптимизировать метод Гаусса компилятором или пытаться прикрутить к нему STL, если есть гораздо более эффективные _алгоритмы_? Неудачный пример, но не надо конечно везде совать шаблоны, согласен.
Статически или на стеке — для скорости работы не важно. Но невозможно для компилятора создать объект неизвестного заранее размера с фиксированным адресом. Да и не нужно.
Пример стекового аллокатора я привел, как оптимизация в плане исключения запросов выделения памяти ОС.
STL наоборот, дает еще преимущества отсутствия необходимости работы с указателями
А зачем работать с указателями, когда можно обойтись индексами? Тип фиксирован, максимальный размер известен, зачем городить указатели?
Зачем оптимизировать метод Гаусса компилятором или пытаться прикрутить к нему STL, если есть гораздо более эффективные _алгоритмы_?
Буду крайне благодарен более эффективному алгоритму обращения матрицы. Мы искали, но не нашли.
Но невозможно для компилятора создать объект неизвестного заранее размера с фиксированным адресом.
КОНЕЧНО. Но даже когда размер известен — это очень трудно сделать с помощью STL. Зато запросто — на обычных массивах.
Пример стекового аллокатора я привел, как оптимизация в плане исключения запросов выделения памяти ОС.
Стек плох тем, что ссылка на такой объект перестает быть валидной при завершении процедуры. Или передавать десяток объектов параметрами, или наворачивать умные указатели… Объект в стеке — это все-таки временный объект. А не постоянный.
А зачем работать с указателями, когда можно обойтись индексами? Тип фиксирован, максимальный размер известен, зачем городить указатели?Ммм, ну я не знаю, откуда ты взял проблемы в своем п.3
Индексы в С это и есть указатели, точнее смещение к указателю.
Ладно, с алгоритмом обращения я похоже спутал какой то другой алгоритм, который в новостях недавно пробегал.
Прекращаю оффтопить.
Индексы в С это и есть указатели, точнее смещение к указателю.
Не совсем так… Арифметика с указателями пришла в язык Си от языка B и PDP-8, которая была словной машиной. То есть p+3 в B — на самом деле означало добавит 3 к указателю. А в Си это означает добавить 3 * sizeof(элемента).
Ммм, ну я не знаю, откуда ты взял проблемы в своем п.3
Задача — хранить списки подобластей в массиве.
Индекс 3 — валиден всегда. Итератор, указывающий на третий элемент — валиден лишь до переаллокации массива. Внесли в середину алгоритма метод, меняющий число элементов — все, итераторы поехали. Значит — итераторы отставляем, храним индексы.
Но тогда получается, что нам нужно и крутить цикл по индексами — и двигать итератор. Но тогда легко словить рассинхронизацию.
В итоге получается, что итераторы — это зло. В смысле для данной задачи зло.
Есть ещё проблемка с указателями. При 10 элементах в массиве индекс 11 — это индекс за границей массива, но это не UB (пока не пытаемся взять 11ый элемент). А вот итератор за end — это уже UB, он может быть как больше end, так и меньше.
То есть мы не можем просто так прибавить к итератору 7 и проверить, не вышел ли он за end.
Нужно это было для выделения в траектории (наборе точек) разных интересных участков.
То есть мы не можем просто так прибавить к итератору 7 и проверить, не вышел ли он за end.
Нужно это было для выделения в траектории (наборе точек) разных интересных участков.
То есть мы не можем просто так прибавить к итератору 7 и проверить, не вышел ли он за end.Вы и индексами не всегда можете это сделать. Или вы Borland C++ не застали и все эти Compact и Large модели памяти?
А в конкретном компиляторе это может и не быть UB — сразу или при использовании какого-нибудь флажка. Точно также проверка «if x + 1 < x» бессмысленна и будет выкинута из вашей программы компилятором — но только если вы не используете опцию
-fwrapv.А вообще все ваши потуги очень явственно показывают, что эту статью вам читать рано. Просто… рано. Вы просто ещё работаете с технологиями, которые устарели лет 10-15 назад. Вот в 2040м — может быть и поймёте почему люди, которым нужно работать с матрицами сегодня, сейчас, используют STL, шаблоны и Eigen, а не MSVC и индексы в массивах.
А сегодня — с вами это обсуждать смысла нет. Проблемы работы с памятью на машинах со 128 ядрами вам неинтересны и не нужны. Но они не интересны и не нужны вам, потому что вы просто проигнорировали всё, что в XXI веке в IT-индустрии произошло — но почему вы считаете что это стандартная точка отсчёта для других читателей этой статьи???
Вы и индексами не всегда можете это сделать
Могу. Причем ВСЕГДА. Всегда найдется тип, максимальное значение которого будет больше максимального реального размера массива. Связано это с тем, что даже в гарвардской архитектуре массив не может занимать всю память. — нужно будет место хотя бы для служебных переменных RTL.
Видимо вы имели ввиду, что не всегда нужным типом будет int. Это верно. Иногда нужен long unsigned. Или long long, Но ввиду некоторых особенностей языка си — нужный тип найдется.
Проблемы работы с памятью на машинах со 128 ядрами вам неинтересны и не нужны. Но они не интересны и не нужны вам, потому что вы просто проигнорировали всё, что в XXI веке в IT-индустрии
"Молодёжь нынче пошла испорченная, старших не слушает" (с) Геродот.
- Когда вы подрастете, то сами поймете, что средство выбирается под задачу. А вовсе не потому, что оно модное, современное и так далее. Это только в молодости кажется, что модное средство — затычка для каждой бочки. С годами приходит понимание, для какой бочки оно годится, а для какой — нет. Ну и умение пропускать мимо ушей маркетинговые крики.
- Все новое — хорошо забытое старое. То, что вам так нравится — было новым и очень модным в 1966ом году. А к 1975ому — стало на свое, очень незначительное, место. Сейчас новый всплеск моды, через 10 лет он пройдет, а на его место вылезет другая, тоже очень старая технология. Например — введение в язык собственных конструкций (типа if then elif).
- ЭВМ разработки 1969ого года поддерживала работу 5-6 программистов в режиме разработки и отладки программ на 63 килобайтах памяти и 2Мгц тактовой. Сумеете сделать на «современных» технологиях систему в 100 хуже? 6.3Мб памяти и одно ядро на 200Мгц? А на старых — делается. Да, новые технологи удобнее в 10 раз. Зато и затратнее — в тысячи раз. Сейчас мы делаем прибор в 10 раз дешевле западных аналогов. Хотим — в 100 раз. Потому и технологиии нам лучшее старые, быстрые и не затратные. Но это не означает, что старые технологии лучше везде.
- Ещё один момент. Знаете какой GPS-приемник на тех аирбасах и боингах, на которых вы летаете? А приемник там — в 10 раз хуже, чем в китайском GPS-навигаторе. Нечувствительный, неточный, медленный… Приемник примерно 1985ого года на элементарной базе 1975ого года. У него одно преимущество — НАДЕЖНОСТЬ.. А для надежности железа -недостаточно расчетов. Нужно чтобы компоненты 5-10-20 лет отработали и была бы реальная статистика отказов. Нужно дать отработать плате в сборе. Аналогично и для софтверных технологий. Сначала — проводить эксперименты на кошках. На тех самых серверах со 128 ядрами. И лишь потом, выяснив на кошках все плюсы и минусы — использовать новую технологию в ответственных применениях. Вот потому и работает в банкоматах Windows XP, а не Windows 7/8/10. И у нас аналогично — брать модную сырую технологию вроде С++14 — это ССЗБ.
почему вы считаете что это стандартная точка отсчёта для других читателей этой статьи???
Потому что читателей — вряд ли дома есть «машина со 128 ядрами». Зато у них есть:
- домофон
- лифт
- микроволновка
- стиральная машина
- телевизор
- клавиатура
- принтер
- GSM-модем
И во всех них — embedded. То есть принципы написания — примерно те же. Так что ваши «сервера со 128 ядрами» — всего лишь «испытания на кошках» для той техники, что нас окружает постоянно.
За наводку на eigen спасибо. Надо будет математику перекинуть одну идею, подсмотренную там. Но это не единственная библиотека, а темплейты — не единственный метод реализации. GSL, например, написан на чистом Си без всяких темплейтов.
СПАСИБО. Так юность навеяло. Эх, где мои 15 лет и одноклассницы, путавшие индекс с индексацией.
Объяснение на уровне одноклассниц
#define VECT_SIZE 10
double v[VECT_SIZE] = {0};
int i=11; // это не UB
if (i < VECT_SIZE) / / и это не UB, ибо индекс, а не итератор
v[i] = 42;
else {
// v[i] = 15; // вот тут было бы UB
printf("ЛОПАТА, сэр!\n");
}
Итератор не у нас, итератор в STL. Дизайн у него такой.
А какая разница? Получили из-за ошибки в коде. Движемся по массиву точек траектории. Подозреваем что-то интересное (поворот) — запускаем внутренний цикл на проверку — поворот или просто шум такой. Ну и где-то пропустили сравнение. Бед тут две:
То есть использование STL в этом случае привело к плохо отлаживаемому коду.
На самом деле основная ошибка была в том, что взяли на работу программиста, верящего в STL и всякие новомодные технологии. Ну он и навалял. То есть со сферической лошадью в вакууме его код работает идеально. А с реальными данными хреново. Потому что в реальных данных бывает что угодно.
ПРИМЕР. Надо определить момент начала движения. Теоретически, нашли СКО на первых точках, вышли за 3 СКО — значит едем. Практически бывает:
Товарищ в общем-то полным идиотом не был и ассерты поставил. И если данные нормальные и ассерты не срабатывали — все работало. Но нам-то надо, чтобы работало на любых РЕАЛЬНЫХ данных! Пришлось ассерты убирать. И тут полез вагон плавающих ошибок.
Самый эффективный метод — это в точке ошибки глянуть на данные и поставить точку останова по этим данным пораньше. И в динамике посмотреть, как работает алгоритм и как его надо переписать.
Но с STL это не проходит. Так что или вычитывать 5 тысяч строк кода — или, как вы, по логам. Но с брекпоинтами ошибка находится за 15-20 минут. А по логам — медленней раз в 10.
Ну скажем так: я пока не видел мест, где использование одного std::vector привело к более понятному и более качественному коду. Они, несомненно, существуют, но — не в нашей области. Скорее всего что для получения выгоды от STL надо задействовать пяток разных контейнеров.
- Итератор запросто в коде не проверить. И брекпоинт сложно поставить.
- Если компилятор сумеет понять, что итератор всегда вылезает за end — это UB. А UB компилятор может просто выкинуть из кода.
То есть использование STL в этом случае привело к плохо отлаживаемому коду.
На самом деле основная ошибка была в том, что взяли на работу программиста, верящего в STL и всякие новомодные технологии. Ну он и навалял. То есть со сферической лошадью в вакууме его код работает идеально. А с реальными данными хреново. Потому что в реальных данных бывает что угодно.
ПРИМЕР. Надо определить момент начала движения. Теоретически, нашли СКО на первых точках, вышли за 3 СКО — значит едем. Практически бывает:
- движение может начаться с первой точки
- может выброс в 5 СКО, не означающий движения
- движение может начинаться с медленного дрейфа
Товарищ в общем-то полным идиотом не был и ассерты поставил. И если данные нормальные и ассерты не срабатывали — все работало. Но нам-то надо, чтобы работало на любых РЕАЛЬНЫХ данных! Пришлось ассерты убирать. И тут полез вагон плавающих ошибок.
Самый эффективный метод — это в точке ошибки глянуть на данные и поставить точку останова по этим данным пораньше. И в динамике посмотреть, как работает алгоритм и как его надо переписать.
Но с STL это не проходит. Так что или вычитывать 5 тысяч строк кода — или, как вы, по логам. Но с брекпоинтами ошибка находится за 15-20 минут. А по логам — медленней раз в 10.
Ну скажем так: я пока не видел мест, где использование одного std::vector привело к более понятному и более качественному коду. Они, несомненно, существуют, но — не в нашей области. Скорее всего что для получения выгоды от STL надо задействовать пяток разных контейнеров.
Надеялся почитать в такой же лёгкой манере про «SSE или AVX» — не написали. Жаль. Буду ждать продолжения про векторизацию вычислений.
Все программы должны быть корректными, но некоторые программы должны быть быстрыми.
Почему собственно некоторые? Если бы все были быстрыми — может наступило бы счастье?
Но нужно немного подождать =)
быстрые программы медленно пишутся, и, соответственно, дорого стоят
Встречный вопрос, нужно ли программе быть настолько быстрой, если через такт она ждёт ответа от периферии? Требуется ли быть максимально быстрой программе, которая запускается один раз в день, глубокой ночью, и формирует суточные отчёты о проделанной работе (30 минут или 40 она проработает тут разницы нет).
Электричества больше сожрет, например. Тоже денежка
а почему она ждет ответа от периферии?
может потому что драйвер периферии корректный, но медленный ;)?
может потому что драйвер периферии корректный, но медленный ;)?
А может потому что периферия — это механические детали, сервоприводы и т.п., которые требуют время на выполнение своих действий?
Потому что физические процессы таковы. что скорость не нужна. Можно измерять температуру больного каждую миллисекунду, но чаще раза в минуту это в принципе никому не нужно.
Ну тут дело не в том, что надо каждый код вылизывать подобным образом отдельно, а в том что можно (и может быть даже нужно) использовать паттерны эффективного программирования вообще.
То есть вы не оптимизируете алгоритмы в своей программе для отчетов один раз в день глубокой ночью, а просто изначально пишете эту программу с использованием пресловутых паттернов. Ну и вообще, везде их используете)
То есть вы не оптимизируете алгоритмы в своей программе для отчетов один раз в день глубокой ночью, а просто изначально пишете эту программу с использованием пресловутых паттернов. Ну и вообще, везде их используете)
Потому что скорость многих программ определяется скоростью прокладки между экраном и клавиатурой. Или скоростью прихода данных. И вместо быстроты используется критерий требовательности к ресурсам процессора и памяти. И, если ресурсов хватает, намного важнее требование надежности работы. Или требование не задирать цену разработки.
Мы можем сделать быстро, качественно, дешево — выбирайте два из трех. Как правило — лучше дешево и качественно. Выполнение программы в 10 раз быстрее — это часто экономия 9 миллисекунд раз в минуту.
Мы можем сделать быстро, качественно, дешево — выбирайте два из трех. Как правило — лучше дешево и качественно. Выполнение программы в 10 раз быстрее — это часто экономия 9 миллисекунд раз в минуту.
Спасибо огромное за статью — некоторые вещи делал не задумываясь, а теперь понял что к чему (учителя не объясняли — а говорили:«Так нужно делать и все»). Добавил в свою мини библиотеку полезных вещей. Очень жду следующую часть.
>Компилятору тяжело определить, имеет вызов функции побочные эффекты или нет.
Ой чёйто? Ему это довольно просто определить. Но в некоторых редких случаях, когда хотя бы часть f() линкуется динамически, ему это сделать вообще невозможно*.
Ой чёйто? Ему это довольно просто определить. Но в некоторых редких случаях, когда хотя бы часть f() линкуется динамически, ему это сделать вообще невозможно*.
Я верю профессорам Carnegie Mellon, которые написали книгу, которая вдохновила эту статью. Они в своей книге написали, что компилятору часто трудно это сделать (имеется вообще, а не в отношении моего примера).
Можно ссылку или хотя бы название?
В начале статьи книга упоминается. Computer Systems: A Programmer's Perspective. Пятая глава про оптимизацию.
Извините, читал вступление по диагонали :)
В книге, во всех трех изданиях написано:
>Most compilers do not try to determine whether a function is free of side effects and hence is a candidate for optimizations such as those attempted in func2. Instead, the compiler assumes the worst case and leaves all function calls intact.
Что переводится как «Большинство компиляторов НЕ ПЫТАЮТСЯ определить, имеет ли функция побочные эффекты...». Так что утверждение «тяжело определить» не имеет под собой оснований. Эта цитата кочует из издания к изданию с 2001 года, но разработчики компиляторов не даром свой хлеб едят и за 15 лет таки наверняка этот анализ добавили. Более того, в третьем издании таки сказано, что GCC встраивает f() и поэтому имеет все возможности для оптимизации (хотя вышеприведенный абзац все равно там остался).
В книге, во всех трех изданиях написано:
>Most compilers do not try to determine whether a function is free of side effects and hence is a candidate for optimizations such as those attempted in func2. Instead, the compiler assumes the worst case and leaves all function calls intact.
Что переводится как «Большинство компиляторов НЕ ПЫТАЮТСЯ определить, имеет ли функция побочные эффекты...». Так что утверждение «тяжело определить» не имеет под собой оснований. Эта цитата кочует из издания к изданию с 2001 года, но разработчики компиляторов не даром свой хлеб едят и за 15 лет таки наверняка этот анализ добавили. Более того, в третьем издании таки сказано, что GCC встраивает f() и поэтому имеет все возможности для оптимизации (хотя вышеприведенный абзац все равно там остался).
Вообще есть модификатор функции, прямо говорящий — функция не имеет побочных эффектов. Как называется — не помню, давно не пишу на C++.
>Считывание инструкций наперёд называется предвыборкой. Если во время предвыборки, процессор встречает ветвление (к примеру, конструкция if-else), он пытается угадать, какая ветвь будет взята и считывает инструкции оттуда.
Предвыборка — это считывание [в нашем случае] инструкций в кэш кода. Во время нее никакого анализа на ветвления не производится. А то, что вы назвали «предвыборкой» на самом деле просто «конвейерное исполнение».
А попытка исполнения предсказанной ветви называется спекулятивным исполнением.
Предвыборка — это считывание [в нашем случае] инструкций в кэш кода. Во время нее никакого анализа на ветвления не производится. А то, что вы назвали «предвыборкой» на самом деле просто «конвейерное исполнение».
А попытка исполнения предсказанной ветви называется спекулятивным исполнением.
>cmove
>тернарный оператор
Да что же у вас за конпелятор такой тупой?! У меня на простом примере обе версии транслировались в ИДЕНТИЧНЫЙ код. Для разных уровней оптимизации он был разный, либо с cmove, либо без, но всегда ОДИНАКОВЫЙ. Вот, смотрите: https://godbolt.org/g/n9kaSN
Более того, переписав кода как вы сказали, вы, скорее всего, заставите компилятор вычислять оба подвыражения ВСЕГДА, хотя это компилятор должен решать, когда ему выгодней вычислить одну ветку, но с условным переходом, а когда обе, но с cmove.
>тернарный оператор
Да что же у вас за конпелятор такой тупой?! У меня на простом примере обе версии транслировались в ИДЕНТИЧНЫЙ код. Для разных уровней оптимизации он был разный, либо с cmove, либо без, но всегда ОДИНАКОВЫЙ. Вот, смотрите: https://godbolt.org/g/n9kaSN
Более того, переписав кода как вы сказали, вы, скорее всего, заставите компилятор вычислять оба подвыражения ВСЕГДА, хотя это компилятор должен решать, когда ему выгодней вычислить одну ветку, но с условным переходом, а когда обе, но с cmove.
gcc (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4
Коммпилятор не всегда решает рравильно. Компилятор может решить не использовать cmov, хотя при использовании программа работала бы чуть быстрее.
Коммпилятор не всегда решает рравильно. Компилятор может решить не использовать cmov, хотя при использовании программа работала бы чуть быстрее.
Я ссылку привел на онлайн компилятор. Сейчас попробовал выставить там x86-64 gcc 4.8.4, но на нем результат такой же.
>чуть быстрее
Скорее всего только на вашем процессоре. А если ошибка существенная, то это просто недоработка/баг в компиляторе.
Это только Интеловский компилятор может точно* посчитать, что сколько на каком их процессоре будет выполняться. Остальные компиляторы могут только прикидывать. Так же как и вы.
>чуть быстрее
Скорее всего только на вашем процессоре. А если ошибка существенная, то это просто недоработка/баг в компиляторе.
Это только Интеловский компилятор может точно* посчитать, что сколько на каком их процессоре будет выполняться. Остальные компиляторы могут только прикидывать. Так же как и вы.
Спасибо за статью! На днях разбирал функцию преобразования картинки с камеры (YUYV -> YV12) и думал почему нельзя было выполнить всё в один проход for, а разбивать на 4 идентичных участка внутри одного цикла. Теперь всё встало на свои места.
Интересно что на моем AMD 8350 функция combine4 с четырьмя аккумуляторами работает значительно медленнее чем та которая все перемножает в один цикл. На интеле же все соответствует ожидаемому результату.
Кстати к слову про SSE у гольдштейна есть замечательный пример переписывания `String.Contains(...)` на SIMD (причем в подсчете учитывается еще и время на интероп между дотнетом и С):
Sign up to leave a comment.
Оптимизация кода: процессор