Почему я пишу свои алгоритмы в 95% случаев, и буду и дальше разрабатывать кодовые велосипеды

Это ответ на публикацию «А нужно ли знать программисту алгоритмы?».

Так почему я пишу свои алгоритмы в 95% случаев и буду их и дальше писать?

Дабы быть кратким, сразу приведу конкретику в моем случае (весьма экзотическом), но отмечу что есть немало случаев-аналогов. Если в вашей практике нет случая-аналога — поздравляю, вам не нужно заморачиваться велосипедами. Возьмите с полки пирож... Возьмите готовый код, это реально отличный вариант для RAD, да и просто для потоковой разработки, где время — деньги, а специальные требования отсутствуют.

Я разработчик экспериментальной системы управления крылатым беспилотником.

1. В моем коде не должно быть никаких «черных ящиков»


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

2. У меня есть всего 160 мегагерц и 300 кб ОЗУ


Я не могу позволить себе в первую очередь тратить мегагерцы, а во вторую килобайты.

Современные разработчики под «большие машины» избалованы обилием ресурсов. Они не оптимизируют код и склонны делать избыточные конструкции в стиле «и так работает шустро/компилятор все оптимизирует». Это расслабляет, и зачастую делает боле-менее нормальный код для больших компьютеров, нежизнеспособным в чужой экосистеме (например, на микроконтроллерах (МК)).

Код для МК потому должен максимально полно раскрывать и рассчитывать все, что используется не раз в коде. Чтото вроде очень глобальной оптимизации. Потому даже если берется решение «из форумов и stackoverflow», оно проверяется и оптимизируется (простейший пример такой оптимизации — замена обычных тригонометрических функций на табличные, предрасчитанные).

Внутри моего кода используется очень много абсолютных переходов типа goto, и все лишние расчеты максимально срезаются. Хороший чужой код, как правило, медлителен и неповоротлив. Например, техзрение. Отличная библиотека OpenCV — но куда мне ее впихивать? Это же кодовый монстр! От всего богатства функций технического зрения мне надо всего лишь определять расстояние до движущихся объектов и их границы. Причем на высокой частоте. Изучайте чужой опыт, но пишите свое.

3. Мой код должен быть быстрым и безопасным с точки зрения ошибок в логике


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

И немножко к личному опыту по изучаемой теме.

4. Еще одна причина работы с велосипедами сугубо отраслевая


В моей индустрии нет готовых (открытых) решений, едва мы уходим от проторенной open source автопилотами дорожки. Например, проблема управления полетом на низком уровне (когда мы уже знаем, какая должна быть траектория и нужно всего лишь совместить положение борта с ней) описана в теоретических трудах как обычная PID цепочка. Все в целом просто, но el diablo скрывается в деталях. В сотнях мелких деталей. Что если отказал двигатель? Если у борта GPS ушел гулять на +-150м? Если инерциальный датчик горизонта из-за вибрации показывает направление на горизонт в районе полярной звезды? И так далее и тому подобное. Вы можете сказать: причем тут PID? Это выходит за его рамки! И будете правы, но задача-то итоговая — именно управление, потому вы смешиваете разные алгоритмы и их элементы в разных функциях. И потому все алгоритмы создаются с нуля, шлифуются и идеализируются именно под конкретную задачу в контексте автоматического управления БПЛА. Получается довольно ядреная спагетти-смесь из кодов, весьма сложная в изменениях, но крайне эффективно решающая задачу.

Известная истина, которую часто забывают (или ленятся вспомнить): эффективность/скорость — это противоположность универсализации. Не прямое противопоставление, но они не на одной чаше весов. Когда создается софт для очень экономичной экосистемы, образно говоря, каждый синус на счету. А уж тем более использование delay(), за которое надо некоторых авторов библиотек «расстреливать» (творческая аллегория) с этим самым delay(), чтобы растягивать процесс. Потому все быстрые функции пишутся in situ, с ограниченной универсальностью, а не берутся готовыми универсальными.

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

P.S.: Мнение автора может не совпадать с вашим.
Share post

Comments 77

    +52
    Коллеги, не стесняйтесь создавать велосипеды.
    Если есть кто-то кто готов это оплачивать…
      0
      Вся суть подобных статей и споров в том, что доводы вырываются из контекста задач.

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

      Но если вам надо сделать страничку для вывода статистики, надо делать быстро и не заморачиваться (в пределах разумного конечно). А еще лучше время на красявости и рюшечки для пользователя потратить. Они это любят.
      +20
      Ну, автор под конец немного перепутал тёплое и мягкое. Конечно, причина "таких алгоритмов нет" — вполне себе повод написать "такой алгоритм". Изначальная статья-то была не о таких случаях, а о хорошо известных алгоритмах типа сортировки\поиска\структур данных\графов\матриц\конечных автоматов\деревьев\хэш-функций и т.д. Вот эти вещи спрашивалось писать ли и на этот вопрос автор как-раз и не ответил. Алгоритмы в стандартной библиотеке — это уже табу или ещё нет? А в опенсорсе уровня буста?
        +8
        В качестве ad absurdum, а проверяет ли автор сам предрассчитанные таблицы тригонометрический функций?
          0
          Там же БПЛА, всё по ходу дела итеративно и интерактивно корректируется, ошибки не накапливаются. Главное состоит не в том, чтоб "попасть" сразу в цель, а чтоб по итогам цикла приблизится к цели или уйти от неё не слишком далеко.
          –2
          Изначальная статья вообще была ни о чём.
          +13
          Почему я пишу свои алгоритмы в 95% случаев, и буду и дальше разрабатывать кодовые велосипеды

          Ответ: потому, что это требуется по условиям задачи.

          В оригинальной статье речь про то, что необходимости писать свои реализации нет почти никогда (даже не в 95% случаев), потому что влияния на решение бизнес-задачи это не оказывает.
            +4
            Пункт 3 я не понял. Если вы пишете тесты для кода — то внешние библиотеки проверять не составит труда. Если вы не тестируете код «на земле», то как вы можете утверждать, что выходит «очень эффективный и безопасный код»? Если в открытых библиотеках, над которыми долгое время работает куча людей, встречаются ошибки, то каков шанс, что у вас будет код эффективнее и безопаснее?
              –2
              Хм, согласен, формулировка неточна. Все коды конечно тестируются и проверяются на земле в первую очередь. Но если возникает некая проблема, и ее причина упирается в выбранный сторонний алгоритм (который для примера вы используете как готовое решение, не углубляясь и не вникая в него, только подключив к нему функции из своего кода), и вы раз за разом проходите по коду все больше убеждаясь что данный алгоритм не работает как надо — дальше есть два пути. Можно разбирать чужой код, как он работает, где делает "не так", или искать другие готовые алгоритмы. Или писать свой. Так вот, используя чужой код я не уверен на 100% что он во всех случаях отработает как надо. Если я его не разобрал построчно, и особенно все непонятные мне места. И часто с глубокой переработкой. Но не проще ли написать тогда свое?
                +8
                > Но если возникает некая проблема, и ее причина упирается в выбранный сторонний алгоритм (который для примера вы используете как готовое решение, не углубляясь и не вникая в него, только подключив к нему функции из своего кода), и вы раз за разом проходите по коду все больше убеждаясь что данный алгоритм не работает как надо — дальше есть два пути. Можно разбирать чужой код, как он работает, где делает «не так», или искать другие готовые алгоритмы. Или писать свой.

                Вот тут я не согласен. У нас есть два варианта: мы взяли открытый код, либо мы купили стороннюю закрытую библиотеку.

                1. Если код открыт, то мы легко можем помочь библиотеке, поправив проблему и сделав жизнь лучше сразу для всех. Мы же исходим из того, что у нас достаточно компетенции в вопросе.
                2. Если мы заплатили деньги — попросить починить код, не отвечающий требованиям.

                > Так вот, используя чужой код я не уверен на 100% что он во всех случаях отработает как надо.

                Вы никогда не можете быть уверены, что код отработает на 100% во всех случаях, если у вас нет тестов. Для своего кода вам придётся писать и код, и тесты. Для чужого — только тесты, и то не всегда. Для этого не обязательно его разбирать построчно, достаточно определить, что он делает ровно то, что должен.

                > Но не проще ли написать тогда свое?

                Если мы говорим «в принципе» — то нет, не проще. Над популярными библиотеками трудятся десятки людей, тратят на это кучу времени и сил, у каждого свои знания в разных областях — безопасности, читабельности, тестировании и т.д. Один разум не может переплюнуть множество, как ни крути.

                Разумеется, речь не о случаях, вроде того что вы описали с OpenCV, который у вас никуда не влезает. Это — случай, когда библиотека просто не подошла. И безусловно, есть ситуации, когда нет ни одной подходящей по всем параметрам (включая и скорость, и память). Тогда у вас просто нет выхода, конечно.
                  +2
                  Так вот, используя чужой код я не уверен на 100% что он во всех случаях отработает как надо. Если я его не разобрал построчно, и особенно все непонятные мне места

                  Вы же провели тестирование. Так, в принципе, 100% уверенности и в вашей реализации быть не может. Вы просто подсознательно к ней тяготеете — ведь она ваша.
                +12
                Простите, я, конечно, дилетант в таких вещах, но разве текст
                потому вы смешиваете разные алгоритмы и их элементы в разных функциях. <...> Получается довольно ядреная спагетти-смесь из кодов, весьма сложная в изменениях, но крайне эффективно решающая задачу.
                не следует читать как "Вы заботливо раскладываете вокруг себя грабли"?
                  +3
                  Если это делается осознанно и с полным пониманием последствий, то это не раскладывание граблей, а просто архитектурное решение.
                    +2
                    То есть, если вы понимаете и осознаёте, что пишете быдлокод, то он перестаёт быть таковым и становится «архитектурным решением»?
                      +3
                      Fisher's Fundamental Theorem states—in terms appropriate to the present context—that the better adapted a system is to a particular environment, the less adaptable it is to new environments.
                      Gerald M. Weinberg «The Psychology of Computer Programming»

                      Быдлокод — это если человек либо не понимает, что можно сделать лучше, либо ему просто наплевать.
                      Это же — оптимизация. Читаемость и модифицируемость кода и скорость его выполнения находятся на разных чашах весов и иногда приходится делать выбор в пользу того или иного исходя из ситуации.
                        0
                        | Software's Primary Technical Imperative: Managing Complexity

                        Steve McConnell «Code Complete»

                        Мы говорим о «довольно ядерной спагетти-смеси из кодов, весьма сложной в изменениях». И стоит понимать, что спагетти-код используется не как образное выражение, а в классическом понимании, с goto, невозможностью что-либо понять и т.д.

                        Не стоит смешивать читаемость и модифицируемость. Да, оптимизации и читаемость кода порой друг другу противоречат, поэтому оптимизации как элементы архитектуры должны быть задокументированы. Именно документирование позволяет сохранить модифицируемость даже при утрате читаемости. А ещё выделение «хитрого кода» в выделенные методы или модули, например.
                          0
                          Я, к сожалению, не знаю ограничений, накладываемых средой, в которой работает автор, поэтому не могу определить насколько ваши слова к ней применимы.
                          Если судить о коде по тому описанию, что дал автор, то то, что вы говорите, совершенно верно. Я просто даю ему некий кредит доверия и списываю слова про ядреную спагетти-смесь на счёт литературных оборотов.
                            0
                            Коллеги, среда разработки coocox (МК STM32) + версия для отработки это старенький Codegear CBuilder. Это один и тот же файл .c, просто на критических точках, где берется работа с реальными аппаратными датчиками и IO используются альтернативные ветки через #ifdef
                            Так что особых ограничений касаемо кода нет.

                            По спагетти-коду, совершенно верно прокомментировано что в данном случае функциональность и быстродействие ставится в некоторый ущерб портируемости.
                            Но не до степени граблей.
                            Код переписывался и рефакторился больше десятка раз.
                            Архитектура системы такова что некоторые функции "размазаны" по коду, что накладывает определенные ограничения. Опять таки, код насыщен комментариями буквально по всем строчкам. Почти каждая операция поясняется "зачем/почему", что получаем, и т.д. и при необходимости по каким меткам в коде искать относящиеся к ней элементы. Так что спагетти-код в моем случае это в меньшей степени техническое определение и в большей литературная аллегория.
                        –1
                        Думаю, слово "БПЛА" в статье показывает, что проблема "быдлокода" тут практически неактуальна.
                      +6
                      Раскладываете грабли и ОГРАЖДАЕТЕ их яркой лентой. Наступить можно, но только если закрыть глаза и идти напролом.
                      Вот собственно чем быдлокод и отличается — там грабли раскидывают и присыпают листьями всячески скрывая наличие этих граблей.
                      В полностью математически выверенном коде, где прописаны все ограничения использования того или иного кода и проработаны все возможные условия количество ошибок резко стремится к нулю. Разработка эта получается не быстрой но надёжной. Примерно так как поступают в авиа и космической промышленности.
                      +7
                      Я разработчик экспериментальной системы управления крылатым беспилотником.

                      Ваши доводы очевидны учитывая специфику работы, было бы странно если бы вам там не приходилось пилить кастомные алгоритмы, даже само слово "экспериментальной" указывает на необходимость этого. То есть доводы оторваны от реального мира, если за таковой брать основную нишу разработки — прикладная разработка.
                        +5
                        Во-первых, на мой взгляд должна быть какая-то грань, начиная с которой уже можно использовать готовые алгоритмы?
                        Например, существует оптимизированный вариант стандартной библиотеки С — MicroLIB — в котором многие функции написаны на ассемблере и оптимизированы по самое не балуйся.

                        Или вы брезгуете использовать даже memcpy и qsort?

                        Во-вторых:

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

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

                        Я лично не считаю себя достаточно квалифицированным специалистом, чтобы считать, что мой код безопаснее, чем код из стандартной библиотеки. И я знаю, что в стандартных реализациях тоже бывают ошибки, хотя их используют уже десятилетиями!

                        Так что вы, судя по всему, очень храбрый человек. Или очень самонадеянный.
                          +4
                          В программировании микроконтроллеров есть своя специфика:

                          1. Баги можно списать на сбой в питании или нестандартное поведение внешней среды
                          2. Код исполняется без ОС или со своей ОС, короче работает гораздо более строго детерминированной среде (внезапное обновление винды код не обрушит, обновлений библиотек тоже нет). И поэтому кажется что функция не глючит и качество нормальное.
                          3. Часто код пишут схематехники или прочие неспециалисты
                          4. А если и пишут программисты, то из за ограничений железа у них целый букет глупых само-ограничений "то нельзя, это нельзя, ЭТО ЖЕ МИКРОКОНТРОЛЛЕР!", и соответствующий стиль с кучей суеверий.
                          5. Код пишется очень редко, в перерывах между кучей разных дел, от заказа разводки плат до отладки технологии или согласования ТЗ с начальством. Реально многие разрабы мк пишут код в лучшем случае 10% рабочего времени. Остальное время они занимаются ЧЕМ УГОДНО (это сродни "тыжпрограмист", только в разы хуже — ты не чайники ремонтируешь, а производственный техпроцесс предприятия из сотен человек и извеняюсь но это полный ппц по выматыванию и нервов, и времени). И бывают длинные паузы когда код не пишут вообще, это от полугода, до года, а то и больше.

                          Поэтому часто код выглядит очень и очень страшно.
                          Да не спорю есть такая беда.
                          И она усугубляется что часто фирмы не берут даже схематехников в штат — сами нарисуете и пофиг что управлять опасным оборудованием типа лазеров 1кВатт. Про беттатестеров, контроль качества и банальный гит я вообще молчу — их обычно нет.
                            0
                            Я, собственно, сам под микроконтроллеры пишу и все, что вы перечислили, вижу регулярно. Хотя у нас все более-менее прилично, но периодически обращаются за помощью товарищи из других отделов и тогда мои глаза наполняются кровью.
                            Потому что самоограничения, и суеверия, и велосипеды, и goto, и чудовищно запутанная логика, и костыли, и костыли для костылей и банально отступы в коде стоят как попало, и компилируется все только компилятором десятилетней давности.

                            Очень надеюсь, что автор статьи — не из таких товарищей, но вероятность этого оценить не берусь.
                              0
                              Код исполняется без ОС или со своей ОС, короче работает гораздо более строго детерминированной среде

                              Извините за оффтопик, но у меня просто пониже спины взорвалось от этой фразы. То есть, индустрия IT на нашей планете дошла до того, что по своей природе недетерминированная реальная среда оказывается более детерминированной, чем прослойка для неё в виде ОС! Кхм. Извините.
                                +1
                                Внешние факторы, не спорю, да — они куда более изменчивы и мк взаимодействует с ними напрямую минуя ос.

                                Но я про внутренние факторы в виде самой ос. Например для десктопа, на которой:

                                1. Есть виртуальная память и она может быть перемещена или выкинута вообще в свап в любой момент (надеюсь мало кто лочит ВСЕ страницы приложения). В мк же вся память статичная, не выгружаемая и по быстродействию как кеш, она не разгоняется и не меняет своё быстродействие.
                                2. Левые процессы которые к приложению дела не имеют но любой из них может загрузить проц на полную или иным образом выжрать все ресурсы.
                                3. Планировщики задач и само ядро тоже могут внезапно сожрать чего нибудь или занять монопольно ресурс.
                                4. Обновления могут изменить поведение системы, а так же версии и подверсии ос разные.
                                5. Как переключаются задачи тоже сложно понять на фоне левых задач и задач самого ядра — их количество меняется
                                6. Жуткая бюрократия самой ос — так просто доступ к железу не получить
                                  и тд и тому подобное, короче вся та плата за удобство

                                а контекст был такой:
                                Если программист мк реализовал быдлокод который проц у мк грузит на 99.9% то это будет незаметно до первой неудачно правки, даже если он работает с реалтаймом. И это может быть незаметно очень долгое время порой годами всё работает нормально.

                                Но если программист для ПК реализовал код который грузит проц всего на 95% и так же работает с реалтаймом (ну например видеоплеер) то будет икать и слайдшоу он словит на ПК почти сразу же. Это хотя-бы заметно будет почти сразу ну или при первом же запуске крона/фонового процесса.
                              0
                              я не имел в виду стандартные библиотечные функции и уж тем более malloc/free — даже и не претендую их переписывать. Речь шла про те что выходят за пределы стандартной библиотеки
                                0
                                Странно, вот как раз malloc/free в контроллерах очень часто заменяют различными реализациями pool-ов.
                              +7
                              Каждому самолёту свой велосипед!
                                +12
                                Внутри моего кода используется очень много абсолютных переходов типа goto, и все лишние расчеты максимально срезаются.

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

                                Я 15 лет назад для МК писал c goto, но только потому:
                                а. стек фиксированный (до 8 вызовов) или его вообще нет,
                                б. флеша так мало что на стековые кадры и вызовы много кода тратится
                                ц. только когда были в тренде пик микро и i51 — там актуальны ограничения а и б

                                Сейчас же я умудряюсь загрузчики по GPRS впихнуть в 10кбайт (с 24-30кб) даже с полноценными драйверами, ДМА, HTML и FTP и иже с ними не используя: ни goto, ни ассемблер, ни куроча код, не превращая функции в чёртезнай чо, не злоупотребляя препроцессором и инлайнами и тд и тп. Благо компиляторы стали умными и я на них полагаюсь, а не на превращение кода в кашу из GOTO как это сделано например в uIP библиотеке или в FAT от elm-てゃん.
                                А использовать goto для STM32F4xx ну я не знаю, честно зачем?
                                Когда в голове порядок и в коде порядок, а не мокоронное месиво.

                                А в остальном согласен.
                                Причин не использовать в МК общие библиотеки много:

                                1. Строгий реалтайм или очень часто вызывать, например прерывание 512000 раз в секунду, бывает чаще.
                                2. Новомодные выкрутасы языка — не под все платформы они вообще заработают.
                                3. ОС нет, вообще нет.
                                4. Железо слабое — я например делал анализ нелинейных искажений на 512 байтах озу и проце 8мгц, какое там ФФТ и плавающие запятые? да без них хотя они на кортексы M3 есть. Более того это можно и нужно сделать налету с 10% загрузкой такого проца.
                                5. Флеша маловато 16-32к, если мегабайт и более то там и функционала много и на каждую либу останется те же 10-30к.
                                6. 95% задач настолько тривиальные, что реально проще написать самому прямо сейчас под конкретное ТЗ чем тащить стопятьсот зависимостей и раздувать время тестирования и компиляции до небес.
                                7. Библиотеки слишком общие, десятки параметров, громоздкие функции и структуры, очень сложный код использования когда вместо выходного вала тебе дают кусок стали с набором инструментов и говорят что из него можно выточить и ДВС и турбовинтовой двигатель и двигатель стерлинга.
                                8. Программисты МК часто не знают библиотеки для ПК/веба или не имеют опыта использования.
                                9. Часто "Программисты МК" и по факту, и по опыту, и по бумажкам — схемотехники или электронщики (незря же ардуина расцвела).

                                Если есть кто-то кто готов это оплачивать…

                                обычно с радостью оплачивают, т.к. есть такая штука как себестоимость изделия и она сильно зависит от типа МК, а микроконтроллеры по ценам очень сильно различаются в десятки раз порой и могут составлять до 50% от цены всех деталей. Поэтому экономический эффект очень оправдан. Особенно для массового производства.
                                  0
                                  Совершенно согласен и с вами и с автором. Хотя, как показывает практика, при дефиците ресурсов альтернатив для jmp — нет. :(
                                    0
                                    jmp может быть не только результатом goto, но также и результатом else, не считая более изысканных случаев.

                                    Кроме того, jmp вперёд и jmp назад — совершенно разные по степени запутывания кода.
                                      0
                                      А можно еще джамп с побитовым сдвигом делать. Но это совсем от бедности. В общем если надо играть на одной струне вместо четырех, тут не до читаемости кода. Хотя программирование сейчас больше на игру на пианино похоже. Для всего есть своя кнопка и нефиг лезть внутрь и разбираться как там оно внутри работает.
                                  +1
                                  Много библиотек, на том же Nuget изначально пишут для удовольствия/популярности, что иногда заставляет авторов очень долго разрабатывать и поддерживать свои работы. Иногда, автор разрабатывает на уровне «чем сложнее и запутаннее» + побольше абстракций, тем лучше.
                                  Все вокруг требуют больше функционала и авторы идут на поводу, иногда зря, а в итоге, мы получаем примитивные библиотеки, для validation, mapping, serialization, etc нереальных размеров с дебрями кода.
                                    0
                                    С самописными алгоритмами вероятность ошибки всё-таки больше, чем с библиотечными.
                                    Было такое: зависает вот софт раз в год/месяц/неделю у заказчика. В чем может быть проблема? Да 100500 причин! Оказалось, что человек ошибся в самописном
                                    std::nth_element<float*>
                                    Перепутал "меньше" и "меньше или равно". На float-ах раз в месяц и подвисало. Теперь каждый раз, когда думаю о самописном алгоритме вместо библиотечного задаюсь вопросом "Хочу ли я, чтобы к заказчику в **** поехал кто-то из моей команды разбираться с проблемой в этом алгоритме?.."
                                      +1
                                      Вы изобрели независимо открыли вот этот велосипед. Программирование — единство и борьба противоположностей:

                                      • Желание сократить избыточность (не повторяться)
                                      • Желание сократить зависимости

                                      Избыточность — плохо, но зависимости — ещё хуже.
                                        +8
                                        Пост мог ограничиться словами «у меня в проекте специфические нефункциональные требования, поэтому я предпочитаю использовать велосипеды». Проблема в том, что велосипедизм не является панацеей: автор совершенно забывает про баги в самописном коде, про сложности поддержки самописных решений и т.п.

                                        Может, главная причина вашего велосипедизма — банальное отсутствие решений под вашу платформу?
                                        Стоило ли ради этого писать пост и заканчивать его спорными и даже опасными выводами?
                                          +14
                                          Все эти причины будут работать до того момента, когда вы внезапно увольняетесь или уходите с фирмы.

                                          После этого — новый программист, скорее всего, будет переписывать всё с нуля, и постить на Хабр тексты типа "почему иногда проще написать программу заново".
                                            +2
                                            +1

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

                                              Более того, у армии есть требования к группам разработки, как раз касающиеся предотвращению возникновения ситуаций когда ведущего разработчика съела акула или он улетел на месяц на Алтай и все встало. Потому как кроме него никто не может разобраться в коде. Такие разработки не пройдут финансирования изначально.
                                              0
                                              Есть разница между алгоритмами и библиотеками, их реализующими. Одно дело — взять существующий алгоритм и самому реализовать его; другое дело — самому написать алгоритм. Первое — вполне понятно, и зачастую оправданно. Второе — нетривиально, и, скорее всего, не нужно (если хороший алгоритм уже есть, конечно).
                                                –4
                                                ' У меня есть всего 160 мегагерц и 300 кб ОЗУ'
                                                Т.е. вместо того чтобы добавить ресурсов которые сейчас достаточно дешевы, вы изобретаете целый зоопарк тяжело поддерживаемого в условия бизнеса ПО (люди приходят уходят, иногда нужно и студентов нанимать и.т.д.)
                                                Ох и не дальновидное у вас начальство я бы сказал. Не видящее всей картины. Такой подход вас доконает в долгосрочной перспективе.

                                                Но если вы в целом не пытаетесь бизнес построить, а работаете на оборонку, скажем, и там по сути конкурентов в целом нет. И год на то чтобы добавить новую функцию — не проблема, то тут совсем другая картина.
                                                  +7
                                                  вообще то "160 мегагерц и 300 кб ОЗУ" это одни из самых лучших и передовых условий на рынке МК, и увеличить максимум можно в 1.5 — 2 раза (кортекс М7). 300кб Это статическая память, они очень шустрая, но очень дорогая, такие МК порой стоят дороже Cortex Aх но без памяти и флеша. И их можно собрать на коленке. И поэтому мк нужны что их могут мелкие стартапы осилить и запуск в производство сразу не съест десятки лямов. И поэтому там далеко не бизнес условия разработки ПО
                                                    +1
                                                    Спасибо за комментарий. Не подумал об этом.

                                                    Ок, тогда на этом МК запускается сильно специализированная задача из серии что-то рассчитать по формуле из сигнала,
                                                    написали один раз — и забыли. Тут тогда поддержки как таковой нет вообще и не нужно. 'Велосипедить' можно сколько угодно.

                                                    Все равно если требования изменятся, то скорее всего новую плату разрабатывать будут с новым железом, частотами и временами отклика и.т.п.
                                                    Тут даже если код красиво написан — его менять дольше чем своять свою мелкую реализацию на коленке.

                                                    Забавно получается что программисты железа получают 'микросервисную архитектуру' из коробки. Этот МК — отвечает за сетевое взаимодействие, этот за управление двигателем и.т.п.

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

                                                    Это я все к чему, то о чем говорить автор в статье полностью имеет смысл в таких условиях. Но забава в том, что это очень редкий случай.
                                                      +2
                                                      Забавно получается что программисты железа получают 'микросервисную архитектуру' из коробки. Этот МК — отвечает за сетевое взаимодействие, этот за управление двигателем и.т.п.
                                                      нет, ради экономии денег на каждом экземпляре (это железо, а не софт) стараются всё простое типа аналоговых модемов, езернета, http сервера, файловой системы, адаптивной сигнальной обработки звука и тд спихать всё в один чип и подешевле а значит послабже. А у нас на фирме например маржа с каждой железяки делится между разработчиками от 25 до 30% между прочим например. Так что финансовый кнут ещё тот балансировать между грянями минимализма и запасом по флешу и памяти для будущего развития и патчей своих же факапов (которые из премии уже не 30 а 100% вычитаются включая транспортные расходы).

                                                      Более того — самое жирное поле для будущих багов и костылей — это как раз связь между несколькими мк. Протоколы связи это ОЧЕНЬ сложно, пожалуйста не делайте их, и делать свои костыли каждый раз это как парсить html при помощи regexp Тесты на протоколы связи мягко говоря задолбаешся писать — у них много степеней свобод и 2 в очень большой степени вариаций. А качественных либ очень мало, крайне мало. И даже с либами не всё быстро и просто, особенно при жёстком реалтайме и случайных внешних событиях.

                                                      И поэтому хочу опровергнуть высказывание:
                                                      Ок, тогда на этом МК запускается сильно специализированная задача из серии что-то рассчитать по формуле из сигнала,
                                                      написали один раз — и забыли. Тут тогда поддержки как таковой нет вообще и не нужно.
                                                      Микроконтроллеры это те же самые компы, они просто отличаются от обще-принятых персоналок / веб серверов. И развивать на них проекты порой нужно подольше чем для ПК. 10-20 лет норма. Тем более те же авр и даже i51 до сих пор актуальны и не устарели а i8051 архетектуре лет… ну в даже СССР клоны были.
                                                      Существует также советский клон данной микросхемы, КР1816ВЕ51.


                                                      Хотел бы подытожить: нормы бизнеса в IT по заменяемости специалистов достаточно далеки в области разработки для железа. В любом случае так просто заменить разработчика не выйдет. Сложность выше. Побочных знаний знать надо гораздо больше, и мат анализ с тригинометрией минимум на твёрдую институтскую четвёрку и сигнальная обработка и схематехника и физика и технология и тд и тп. Более того обязан быть опыт во всём этот. И опыт положительный а не из разряда «да я баловался этим что то вроде получилось». А опыт уровня «использовал, запустил в производство, отвечал за ошибки и правил. продавалось и окупилось». По так по каждому каждому пункту (к сожалению в идеальной параллельной вселенной).

                                                      Ну и собственно изделие — там своя история развития и порой в BOM листе (Bill of material перечень комплектации) бывает 100+ страниц. Где собственно сам перечень на одной странице, а все остальные это возможные аналоги, опыт и мотивация подбора, история косяков и тесты как их избежать и тд и тп. И каждая позиция этого чёртово бомлиста обязана быть покрыта в том числе и софтверными тестами. Да и кроме основного изделия часто бывает несколько технологических пультов с своими тестами, софтом тестирования основного изделия и самого пульта. со своей историе разработки и тд и тп.

                                                      Есть даже анекдот такой когда американцы украли ядерный реактор а вот журнал изменений на 1000 страниц не украли.

                                                      Но вот беда, чтоб содержать штат чтоб разделить по ролям да ещё и с запасом и поэтому иметь в штате в десятки высококлассных спецов в России есть деньги только у пары тройки предприятий (исключая гос… пока но скоро и включая гос сектор).
                                                        –1
                                                        Простите, не поверю что полноценную систему управления БПЛА можно впихнуть на один "160 мегагерц и 300 кб ОЗУ"
                                                        У вас видео поток с камер (которых ни одна)
                                                        Вам нужно образы распознавать, связываться с центром для уточнения маршрута(если есть динамическое управление)
                                                        Посылать или записывать какие то данные (ради которых он летает)
                                                        Контролировать другие параметры полета (ветер, температуру, заряд батареи)
                                                        Между этими задачами еще переключаться надо правильно и.т.п.

                                                        Если задача так изначально ставиться, а сделай ка мне БПЛА на одной слабенькой дешевой плате. Задача изначально провальная. И говорить нечего.

                                                        Если вы полноценный стек своими руками пишите, вплоть до шедуллеров, реализацию многопоточности самостоятельно и.т.п. — Это не правильно, это не место для велосипедов. Задачи стандартные. Если в чем то таком — лапша какая то и никто кроме одного Васи не понимает как это работает и от этого все зависит — это очень опасно для предприятия. А завтра Васю собьет автобус, и что?

                                                        То что вы рассказываете звучит как полное не понимание руководством тех. части — что плачевно. Если вся МК разработка такая, то я очень рад что я не там.

                                                        'Протоколы связи это ОЧЕНЬ сложно, пожалуйста не делайте их' — неужели нет стандартного протокола по типу http
                                                        Как вы ребят сложные системы из нескольких подсистем пишите то в обще.
                                                          +1
                                                          Я конечно не спец в этом, но ArduPilot (OpenSource автопилот для мелких беспилотников) вполне себе сносно бегает на Atmega2560 (256кб флеш, 8кб ОЗУ, 16МГц тактовая частота), при этом функций достаточно: полет по маршруту, поддержка кучи датчиков, телеметрия, и много других фишек. Запаса по производительности, правда, практически не остается.
                                                          Видеопоток с камер беспилотнику для полета анализировать особо не требуется (разве что оптические датчики горизонта, но я опять же не спец, мой опыт ограничивается полутораметровым беспилотником на ArduPilot), а остальные задачи не требуют чудовищной производительности.

                                                          БЦВМ "Бурана" по нынешним меркам до смешного слабая. Но тем не менее, ее хватило для того, чтобы полностью автономно совершить полет в космос, и мягко приземлиться на полосу (без двигателей, между прочим).
                                                            +2
                                                            Простите, не поверю что полноценную систему управления БПЛА можно впихнуть на один «160 мегагерц и 300 кб ОЗУ»

                                                            Между этими задачами еще переключаться надо правильно и.т.п.
                                                            это не моя разработка с БПЛА. об этом лучше спросить автора статьи. Могу сказать что автор статьи использует STM32F4xx, а эти чипы очень часто в БПЛА идут. В квадрики особенно. Они реально мощные, на уровне целеронов на которых Win98 и Win2000 шли без лагов и тормозов. Так же свой MMX есть правда урезанный но есть. И плавающая запятая есть.

                                                            Если вы полноценный стек своими руками пишите, вплоть до шедуллеров, реализацию многопоточности самостоятельно и.т.п. — Это не правильно, это не место для велосипедов. Задачи стандартные.
                                                            если переключаться нужно редко (менее 10к в сек), если не требуется строго реалтайма, если экономика не давит и не надо каждый килобайт экономить, если есть опыт и ещё много «если». То есть куча разных RTOS. и они отлично с задачами справляются. Есть rtos не пригодно то есть простые как валенок lockfree алгоритмы и приёмы типа очередей точка-точка. И тд. Это не проблема.

                                                            С протоколами сложнее но решаемо (требований больше, а библиотеки не всё покрывают — часто очень важна общая архитектура в целом). Вот только беда — многие пишут свои протоколы… а потом такие костыли и баги что ужас.

                                                            А завтра Васю собьет автобус, и что?
                                                            плохо. как минимум месяц-два в тему входить и изучать много тыщь строк документации, хех которую часто не ведут в полной мерее. Просто людям надо побольше платить, а потом Москвичи в шоке — за 80...120тр инженеры с опытом не хотят. да даже за 150тр вообще не едут в Москву из глубинки ну никак. В любом случае часто Вася один или два три не более. В любом случае программист Си для NXP для двигателей с опытом работы найти это из области фантастики и пол года отдача будет так себе если он вообще изучит матан двигательный или например модемный. Ну и пожжот до кучи несколько приводов за лям и запросит. В любом случае выход на полную отдачу пол года — это неплохо.

                                                            Ну нету у отечественного бизнеса денег на норм процесс разработки железа. В гос предприятиях работающих на оборонку в нашем регионе всё точно так же — есть несколько Васей, каждый незаменим, у каждого З/П такая что выше чем в Мск, но он рабоатет 24/7/365. А остальные сотни человек чаи гоняют и бумажки носят, оформляют и люто ненавидят этих чёртовых мажоров, т.к. им и 10 и 20тр зп. А ведь в каждом работает от 5т человек и более. Был я там, или работал сам или по командировке отвечать за своё оборудование.
                                                            Стартаперы тоже жгут: «а зачем схемотехник/беттатестер нам? он же будет в потолок плювать, сами разводите, сами рисуйте плату и схему, сами кодите и сами проверяете как нибудь», некоторые мелкие сколковские не исключения.

                                                            Важно: Всё выше сказанное только про наукоёмкую электронику, сделать что то тривиальное типа стопятьсот первый павер банк или простой логер открытия дверей на SD карту — тут всё шоколадно и за 40 — 80тр к тебе в очередь с наработками выстроится. Ну или студенты/хоббисты на постоянку запросто пойдут за те же 80тр в мес — тоже очередь и сразу. И особо к качеству кода нет претензий — такой стартап или разработка загнётся за год в лучшем случае или уйдёт на капитальную переделку уже нормальной сформированной командой.
                                                              0
                                                              Много нового узнал сегодня. Интересная область, спасибо за ответы.
                                                              0
                                                              Это многопроцессорная система.
                                                              Один STM32F4 на главный алгоритм, один на оптику (с одной камеры). Есть доп процессор (послабже) на IMU и совсем слабенький на IO. Это что касается только автопилота не входя в тонкие материи шифрования радиообмена.
                                                            0
                                                            Ок, тогда на этом МК запускается сильно специализированная задача из серии что-то рассчитать по формуле из сигнала,
                                                            написали один раз — и забыли. Тут тогда поддержки как таковой нет вообще и не нужно. 'Велосипедить' можно сколько угодно.

                                                            Это я все к чему, то о чем говорить автор в статье полностью имеет смысл в таких условиях. Но забава в том, что это очень редкий случай.
                                                            Просто другой из пяти миров имени Спольски.
                                                        +1
                                                        Очень тяжело проверять чужие коды на безопасность и устойчивость. И всякие cppcheck не помогут. Это хорошие инструменты, но они обнаруживают только технические, но не алгоритмические ошибки, которые в чужих кодах встречаются. Чаще проще написать с нуля, понимая идею и решение, чем адаптировать и переписывать к своим требованиям чужое. Да, это занимает время, но на выходе получаем очень эффективный и безопасный код. Заточенный именно под нужную задачу

                                                        А как на счёт model checking и symbolic execution? Если вы пишете свои алгоритмы с нуля, вы пробуете их верифицировать как-то?
                                                          +1
                                                          Я один слышу хохот зала?
                                                            +2
                                                            мужчина, опубликуйте какую нибудь статью — у меня патроны в кармамёте протухают.
                                                          –1
                                                          Ну, Вы прямо против всего мира решили пойти. Последние годы почти во всех популярных языках тренд — использовать пакеты (gems в Ruby, packages в PHP, cocoa pods в Xcode, components в bower/npm и так далее) для быстрой и эффективной разработки.

                                                          Есть даже термин, популярный сейчас в стартап-сфере — комбинаторная инновация. Не помню, кто первым теорию выдвинул, но суть ее в том, что сначала появляется базовая инновация, а затем на ее основе вырастает множество производных инноваций (в которых по-разному скомбинированы элементы, отсюда и название).

                                                          Примеры: электроника в 1920-ых, интегральные схемы в 1970-ых.

                                                          Сейчас происходит тоже самое. На одном GitHub находится более 2-ух миллионов репозиториев. Работа современного инноватора (за исключением действительно уникальных, новых функций) — собрать из этих готовых кусков новый продукт, сделать инновацию посредством комбинирования.

                                                          Если каждый раз сознательно изобретать велосипеды — об Agile/Lean разработке можно просто забыть. Это очень дорого и неэффективно.
                                                            +1
                                                            Так ведь у автора как раз ситуация, когда в ущерб стоимости и эффективности усиливается надёжность. Вернее, она в теории усиливается, выше написали несколько проблем такого подхода.
                                                              +1
                                                              Надежность собственных решений — это заблуждение. Все нормальные open source пакеты автоматически тестируются, показывают уровень покрытия код тестами и так далее.

                                                              Плюс всего один — гибкость, можно что-то изменить под себя, добавить. Но это как правило решается через fork или pull request.

                                                              У нас были как-то проблемы с библиотекой ZeroMQ, к примеру. Написали автору, заплатили как консультанту — он срочно исправил баг в библиотеке (который видимо больше никого не беспокоил). Даже так получилось быстрее и дешевле, чем свое решение.

                                                              У меня ощущение, что нежелание использовать чужое — берет истоки где-то в характере разработчика, это что-то эмоциональное. Тут рациональности нет вообще.
                                                                0
                                                                > Все нормальные open source пакеты автоматически тестируются,

                                                                Про «кровоточащее сердце» слышали? Или про дыры в Линкуксе, SQL и т.д.? И все тихо и спокойно жило себе годами.

                                                                Насчет «характера» — зря это. Равно как и другие право-руко-собранные комментаторы. Просто для военных целей использовать чужое а) нельзя, б) опасно. Для тех же БПЛ: при использовании старого и открытого софта их просто уводили. И из-за дыр в коде/безопасности тоже, но больше из-за «кабинетности» людей. Писать код, не тестируя его в реалиях — уже моветон.
                                                                Вы никогда не писали «в закрытую»? Поясню: есть чей-то алгоритм, доступный только в виде машкодов. Вы его восстанавливаете, что-то меняете, делаете 3-4 версии и отдаете их на тестирование. Самой железки не видите — допуск не тот. И Вам просто передают ответ — что и как отработало и в какой версии. Весело? — сейчас станет грустнее.
                                                                Большинство таких контроллеров напрямую работают с железом и данные им нужны «сейчас» и именно в том виде, в каком их отдает датчик, а не очередной программер, запихнувший ответ в уже существующую переменную, чтобы новую не плодить. И начхать, что в разных компиляторах точность разная. Или что ее потом кто-то где-то меняет. Пример? — датчик гироскопа, общение через старый-добрый COM.

                                                                Вдогонку.
                                                                Половина таких библиотек не работает в среде x64. Виртуалка? — ой, не всегда…
                                                              0
                                                              Против всего мира ходит куча отраслей техники. Давно и успешно ходит. Авионика для "пилотников", автомобильная промышленность, медицина, safety-critical systems. Почитав стандарты, вроде MISRA C, проницательный читатель может узреть легкую задебиленность во имя надежности и снижения эксплуатационных издержек, характерную для промышленной автоматики и систем управления реального времени, столь нелюбимых тру програмерами с их гитами, агилями и архитектурами. Да, и парадигма разработки в этих сферах несколько иная. Не быстро и эффективно разработать инновацию, чтобы денег поднять, а плавно и надежно сделать банальность, которая просто работает и не взрывается.
                                                              +6
                                                              Я во много согласен с автором статьи. Подобных примеров того, зачем изобретать велосипед можно привести ещё очень много. Ограничусь лишь тем, в чём являюсь специалистом.

                                                              Высокопроизводительные параллельные вычисления. Далеко не все алгоритмы, существующие в известных библиотеках, реализованы для кластеров. Мне нередко приходилось реализовывать какой-либо классический алгоритм для того, чтобы он эффективно работал, скажем, на 100 ядрах. Причём в разных вариантах, как с наличием общей памяти, так и с необходимость разбивать память по узлам кластера через "одно место". Но даже когда такие алгоритмы есть в библиотеках, ситуация всё равно печальна, потому что одно дело, когда они заточены под 20 ядер и работают, и совсем другое, когда на 200 они начинают дико тормозить, а для 1000 ядер вообще может быть нужен иной подход к распараллеливанию.

                                                              Научные задачи. Первое правило в тех задачах, чьё время расчётов могло запросто превышать 2-3 месяца — никаких сторонних библиотек. Научная задача (скажем, расчёт термодинамических характеристик материала) как правило не является совсем уж общей. Вот, понадобился мне алгоритм обхода графа, но граф не общий, а особого вида. Даже не прямоугольная решётка, а это может быть гибрид прямоугольной и гексагональной решётки. Ясень пень, что для ускорения работы программы нужно писать свой алгоритм обхода, заточенный специально под этот конкретный случай графа, ускорение получаем в сотни и тысячи раз. Не шучу. В моей научной практике никаких boost и stl никогда не было, именно поэтому я часто обгонял конкурентов по качеству результатов, мои программы работали на несколько порядков быстрее и, следовательно, больше успевали посчитать за отведённое время, всё именно потому что это был "самопал".

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

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

                                                              Ну и очень часто бывают случаи, когда реализация делается под конкретное железо на ассемблере. Есть только одна библиотека — GMP (или её ветка MPIR), в которой такая необходимость отпадает. Во всех остальных случаях всегда можно выиграть минимум на порядок (если, конечно, это не тривиальный алгоритм вроде сортировки).
                                                                0
                                                                Очень интересный комментарий, спасибо. Хотелось бы уточнить про примеры, когда выигрыш получался более чем на порядок.

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

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

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

                                                                На первый взгляд тут максимальный теоретический выигрыш ограничен тем, сколько процедур "слепливаем". Если две — выиграть можно максимум в два раза, три — в три… И то, это максимум, на практике будет меньше, с FLTO — может вообще смысла и не быть. Часто на таких вещах можно выиграть если упираемся в производительность памяти, и "слепливание" операций позволяет избежать повторного прохода по памяти, но тут есть предел выигрыша — пока не упрёмся в производительность вычислений, так что на практике тоже более 10 раз вряд ли можно выиграть.

                                                                Что касается кластеров — тут однозначно, поле ещё не пахано и доступных готовых реализаций почти нет. Однако, на практике часто оказывается, что эффективнее делать реализацию под GPU либо вообще под GRID-архитектуру, типа BOINC. В моей области так и произошло — Molecuar Dynamics.
                                                                  +1
                                                                  Для того, чтобы конкретизировать то, о чём я говорю, нужно достаточно детально разбираться в этих задачах, что потребует от меня и от Вас кучу времени. В примерах с обходом там сложная тема, в конечном итоге в ход пошли всякие битовые трюки и навороты, жёстко учитывающие вид графа. А вот простой пример у меня был в студенческие годы (10 лет назад). Алгоритм решения задачи о максимальном потоке методом Форда-Фалкерсона был ускорен в 13 раз простым переходом от списка stl::list для хранения графа через смежные вершины к собственному списку на основе голых массивов, упорядоченному особым образом в памяти. Я тогда радовался, что это я придумал так ловко граф хранить специально для задачи о потоке, но потом вычитал то же самое то ли у Голдберга, то ли у Тарьяна. Более сложные примеры, увы, я не в состоянии тут описать. Но примеры того, как задачи ускорялись с 5 лет счёта (теоретически, конечно) на 100 ядрах до нескольких секунд на обычной машине у меня были. И это именно "самопал", возникающий при отказе от чьих-то продуктов.

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

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

                                                                  Такой вот глупый пример для пояснения идеи: функция x=add(a,b,c) и последовательность функций t=a+b, x=t+c дадут разное время работы. В первом случае самопальная версия сложения трех длинных чисел, во втором мы порождаем 3 лишних объекта (само t и два временных), 3 лишних копирования памяти и 2 лишних прохода по массиву. В итоге тут на пустом месте можно получить ускорение более чем в 3 раза (хотя, зависит от реализации оператора "присвоить"). А если число переменных будет 10, то сами понимаете… Это лишь абстрактный пример.

                                                                  Поясню на ещё одном на абстрактном примере, чтобы была понятна суть того, откуда можно взять ускорение. Есть граф, с которым нужно сделать 10 обходов, и каждый обход делает одно действие (это может быть поиск компонент связности, мостов и т. д.), получаем 9 лишних обращений к элементам списка смежных вершин, который в общем случае работает плохо из-за плохой работы кэша, например. А мы вот берём и делаем всё за один обход. Причём ускорение может быть больше, чем в 10 раз потому, что каждый вызов процедуры обхода из библиотеки скорее всего будет возвращать лишнюю информацию (например, сами компоненты связности вместо их количества, которое нам только и нужно), поиск мостов будет возвращать сами мосты в виде каких-нибудь объектов типа TEdge, которые нам нафиг не нужны по сути. То есть вот эта лишняя передача данных из процедуры в процедуру тоже съедает время.
                                                                    0
                                                                    Алгоритм решения задачи о максимальном потоке методом Форда-Фалкерсона был ускорен в 13 раз простым переходом от списка stl::list для хранения графа через смежные вершины к собственному списку на основе голых массивов, упорядоченному особым образом в памяти.

                                                                    Не знаю, как дела обстояли 10 лет назад, но сейчас это можно сделать стандартными средствами boost, скорее всего даже с лучшими алгоритмами.

                                                                    По поводу тёплицевых систем ничего сказать не могу т.к. не знаю, существуют ли доступные реализации нужных алгоритмов на них, (Eigen, LAPACK, ATLAS, GSL,… "тысячи" их), может быть не существует и тогда это уже не велосипед, т.к. готового решения нет, ведь это уже по сути другой алгоритм.

                                                                    Что касается примеров, которые Вы приводите для слепливания, то FLTO в некоторых (многих ли?) случаях сведёт их на нет. Выкидывание неиспользуемых частей тоже может быть оптимизировано компилятором на O3. Опять же, более чем в 10 раз за счёт исключения повторных проходов выиграть не получится т.к. упрёмся в вычислительную мощность процессора, а не производительность памяти.
                                                                    То есть максимум можно выиграть в 10 раз, как мне кажется, и то редко, хотя и бывает.
                                                                      0
                                                                      Лишняя передача данных время съедать (почти) не будет, так как критический фрагмент в другом месте — доступ к памяти при проходе по графу. Все эти вещи можно выявить профайлером и выпилить из готовых решений, при необходимости и если компилятор этого сам не сделал.
                                                                        0
                                                                        Будет съедать, ещё как. Обычная замена c=a+b на add(c,a,b) на C++ ускоряет вычисление на 10% или около того. Даже при использовании r-value reference.

                                                                        Далее, то, о чём Вы говорите про выпиливания из кода и т. д. — это всё-таки тоже нужно знать, что делаешь. Я вот пишу код быстрее, чем буду выпиливать, по крайней мере, по классическим алгоритмам. Всякие там Atlas и т. д. я проверял, они часто хуже Maple (на нужных мне задачах). Один из моих учеников обыграл факторизацию полиномов в 50 раз по сравнению с какой-то из этих библиотек в своей дипломной работе (по-моему, это был Flint). Хотя я требовал выиграть в 50 000 раз, но у него не получилось, поэтому я ему 4 поставил: )

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

                                                                        Добавлю только одну мысль. На протяжении всего опыта моей работы я обнаружил только одну библиотеку, выиграть у которой я сейчас (пока) не могу. Это GMP (и её ветка MPIR). Всё остальное рвалось без каких-либо проблем, особенно научные библиотеки и научный софт (Maple, Mathematica, Maxima, PariGP ...). Слово "рвалось" означает, что разрыв был достаточным, чтобы предпочесть свою версию против библиотечной. Вот именно поэтому я уволился из вуза и взялся за разработку библиотек, и однажды кое-что напишу.

                                                                        По поводу склеивания функций в одну добавлю, что я согласен, что это весьма экзотический случай и обычно он порождает новый алгоритм, поэтому я и затрудняюсь с хорошим примером из жизни, там у меня всегда получалось, что это уже не велосипед. Разумеется, тупое склеивание мало что даст, а иногда навредит.
                                                                          0
                                                                          Я просто тоже сталкиваюсь с задачами стат. механики иногда. 10% — это не "более одного порядка", кроме того такие вещи компилятор элементарно оптимизирует. Сравнивать C++ библиотеки и Maple/Mathematica — не совсем корректно, первые, часто, сильно производительнее, так что лучше сравнивать свой код с библиотечным. В научной работе, по моим наблюдениям, обычно есть смысл заморачиваться с оптимизацией только когда выигрыш более одного порядка.

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

                                                                          Хотя я требовал выиграть в 50 000 раз, но у него не получилось, поэтому я ему 4 поставил: )

                                                                          А это было вообще теоретически возможно? Можно же посчитать минимальное теоретически необходимое число FLOPS для заданного алгоритма, сравнить с пиковым FLOPS CPU и получить верхнюю оценку производительности. В статьях по реализации алгоритмов так и делают, обычно, пишут что-то вроде "our implementation shows performance of 90% of theoretical limit for the algorithm".

                                                                          И еще пример по поводу кластеров из моей области. Я пользуюсь методом Molecular Dynamics — это когда программно численно интегриуют уравнения механики для каждого из миллионов атомов. Ранее эта задача решалась на кластерах, но в силу фундаментальных ограничений задачи, её невозможно эффективно масштабировать бесконечно, — есть некое пороговое соотношение между числом атомов и процессоров. На практике получалось что-то типа 64-128 ядер максимум. Затем появилось GP-GPU и софт переписали под них и вышло что один GPU даёт большую производительность, чем 128 CPU — и всё, все эти сложно с кластерами стали ни к чему. Про стоимость и говорить нечего. Я полагаю, что подобный эффект для многих задач мог бы наблюдаться, что кластеры процессоров со сложными дорогими интерконнектами и моделью памяти не эффективны — эффективней использовать GPGPU или вообще FPGA/ASIC. Кстати наиболее эффективная реализация MD (ANTON) как раз на ASIC — она на 2-3 порядка быстрее GPU, правда для разработки понадобились миллионы долларов, а для переработки софта по GPU — пара аспирантов. При этом большие "параллельные" мощности оказалось эффективней задействовать не через распараллеливание алгоритмов в классическом смысле, а через технологии типа GRID (BOINC). Иначе говоря, продуктивней разделить кластер на кучу слабосвязанных небольших ферм по 4 workstation в каждой, а чаще вообще по одной workstation. Я думаю, причина тому — закон Амдала и тот факт, что связь между потоками становится как раз "самым длинным фрагментом". Полагаю, что это один из факторов, почему готовых реализаций алгоритмов для (очень) большого числа потоков почти невозможно отыскать.
                                                                            0
                                                                            Нет, про 10% я говорил в другом контексте. В задачах статмеханики я ускорял алгоритмы в миллионы раз. Вычислить степень подобного ускорения, конечно, можно только в теории, то есть я смотрю на число состояний, которое успевает рассчитать моя программа против чужой за одно и то же время. Там разница не меньше 6 порядков. Последний пример я приводил выше, когда программа раньше должна была считать на 100 ядрах 5 лет, а затем стала считать несколько секунд на одном. Там была реализация авторегрессионного фильтра в одном особом случае.

                                                                            Что касается корректности сравнения Maple и C++, то разумеется, оно некорректно в общем случае. Но когда речь идёт о вызове глубинных функций Maple, которые чуть менее чем полностью вызывают бинарный код (например, арифметика там на GMP), то всё в порядке. Тормоза Maple проявляются в другом и это отдельная тема.

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

                                                                            Закон Амдала — это один из моих любимых законов, потому что его очень интересно нарушать. В теории да, он что-то важное говорит, а на практике ускорение в M>N раз можно добиться при распараллеливании на N ядер, например, за счёт того, что данные начали хорошо кэшироваться и плохо кэшировались на одном ядре. Как и все остальные абстрактные законы, он не имеет (лично для меня) прикладного смысла. Есть он или нет — мне без разницы. Я никогда не смогу сказать, что причиной чего-либо стал закон Амдала. Я могу сказать прямо: тупой маршрутизатор, кривой процессор, криворукий программист и т. д. Но закон тут ни при чём. Разумеется, связь между потоками имеет место быть, но в этом и состоит искусство распараллеливания — свести эту связь почти к нулю или к просто к минимуму.

                                                                            Прошу прощение за категоричность, сам понимаю, что она для многих не к месту, но именно в моём субъективном опыте все эти теоретические попытки что-то предсказать на практике обращаются в ноль, и лично мне только мешают сосредоточиться на задаче. Мне не важно, что об ускорении алгоритма говорит теория, я смотрю, что можно сделать на самом деле.

                                                                            Наверное, мы начинаем оффтоп, который стоило бы закончить: )

                                                                            В целом, Вы правы, можно использовать готовое решение, но вот у меня ни разу не получилось удовлетвориться ими (в сложных научных расчётах — речь только о них!), кроме случаев с прямым использованием GMP или тривиальных алгоритмов типа сортировки. Всё остальное приходилось переписывать. Даже когда победа была всего лишь на 10%. Согласитесь, считать 100 дней или 90 дней — есть разница? Да, есть, при условии, что написание своей версии занимает меньше 10 дней. Но обычно, как я говорил, ускорение в реализации сложных алгоритмов идёт на порядки. Там без вопросов даже пишется самопал.
                                                                              0
                                                                              Даже когда победа была всего лишь на 10%. Согласитесь, считать 100 дней или 90 дней — есть разница?
                                                                              По моему опыту, обычно нет разницы, потому что всё равно «ручной» анализ полученных расчётов занимает больше времени, да и эти 10 дней — они не мои, а компьютера/кластера, его время намного дешевле моего (для меня лично и с финансовой точки зрения — тоже). Если я могу подождать расчётов 90 дней — смогу и 100, а если нет — куплю получше компьютер. Разница между годом и месяцем — есть, а между годом и полгода — нет.
                                                                              в этом и состоит искусство распараллеливания — свести эту связь почти к нулю или к просто к минимуму.
                                                                              Согласен, это я и хотел сказать, говоря о BOINC. Мало смысла в классических суперкомпьютерах: часто там где они используются, можно заменить подход и перейти к GPGPU или BOINC-типа архитектуре выиграв по всем параметрам.
                                                                              Если я считаю, что что-то можно ускорить в N раз, значить N — это минимум, который я гарантирую по каким-то причинам.
                                                                              Я об этом и спрашивал, по вашим прикидкам на коленке, возможно было ускорить программу в 50000 раз?
                                                                              Понятие «теоретический предел алгоритма» — это тоже фикция, не имеющая ничего общего с реальностью.

                                                                              Этот предел имеет совершенно практический смысл, если у него (предела) есть контекст. Можно точно рассчитать предел конкретного программного алгоритма (не задачи), принимая допущение, что процессор выдаёт максимальный FLOPS/s независимо от того, какие операции выполняет и что кэш имеет нулевую задержку и безграничен по объему. То есть, подразумевая конкретную структуру программы, можно получить практически полезную верхнюю оценку производительности на доступном оборудовании. Эта оценка даёт понимание того, чего можно добиться «микро-оптимизациями», в т.ч. заменой библиотек на самописный код. Если эта оценка хуже чем 50000 — значит у студента не было шансов, кроме как изобрести совершенно другой подход к решению задачи. Такая оценка — это нечто вроде профайлера: если видишь, что программа 99% времени занята тем, что складывает а+б и избавиться от этого никак нельзя — нет смысла заменять одни библиотеки на другие.
                                                                                0
                                                                                Да, я Вас понимаю. Для меня разница одна, для Вас — другая. У нас же разные условия жизни.

                                                                                Бывают задачи, в которых нужно иметь около 1ТБ оперативной памяти, не уверен, что их можно считать на видеокарточке. Ещё бывают задачи, в которых много ветвлений, вот тут уж я лично проверял, видеокарты сливают. Опять же, всё зависит от задачи и я согласен, что мой опыт довольно специфичен и узок, чтобы наверняка рассуждать.

                                                                                Что касается студента, там ситуация сложнее, чем она представляется по моему поверхностному комментарию. Во-первых, ему нужно было создать свой алгоритм на основе комбинации разных приёмов. Во-вторых, задача сужалась для некоторого частного случая полиномов. Поэтому, во-первых, теоретический минимум рассчитать нельзя в принципе, а, во-вторых, если бы студент доказал, что он из кожи вон вылез и у него не получилось ничего, я бы поставил 5. Но там была иная ситуация, в том числе неорганизованность, чего я категорически не терплю. Да, там можно было ускорить где-то на 5 порядков для наших задач и даже была идея внедриться во Flint. Но сейчас это уже в прошлом.

                                                                                Далее, Вы не совсем правы, когда говорите, что если от a+b нельзя избавиться, что нет смысла менять одно на другое. В одном из примеров моего успеха была задача, где как раз нужно было считать что-то вроде a+b, но это были быстрорастущие несократимые дроби. Казалось бы, ничего не ускорить, а нет, переход в p-адическую арифметику дал вообще даже иную оценку сложности работы. Так что теория теорией, а если бить тяжёлой артиллерией по задаче, то всё может быть совершенно иначе. Теорию и практику нужно уметь гармонично сочетать. Вот я и стараюсь не делать бесполезных расчётов теоретических предсказаний попусту, предел всегда показывает практика. Она же порождает новые подходы, которые затем могут быть улучшены теоретически, что породит новые практические приёмы и т. д. В общем, это уже философия и она у каждого своя. Она обусловлена личным опытом.
                                                                                  0
                                                                                  Бывают задачи, в которых нужно иметь около 1ТБ оперативной памяти

                                                                                  Да, это один из случаев, когда суперкомпьютер может быть полезен, есть даже специальные решения, где упор на большие объемы ОЗУ идёт, у SGI такое есть. Но задач, где такие жесткие требования к памяти не так уж и много. Многие задачи, которые сейчас считаются на суперкомпьютерах, не требуют столь больших объемов ОЗУ. Например реализации иерархического кластерного анализа на сегодняшний день требуют N^2 памяти, но можно (я пробовал — работает) реализовать эту задачу через STXXL, с около-линейным потреблением ОЗУ и небольшим снижением скорости выполнения, и при этом не изобретать велосипедов, а скомбинировать готовые доступные решения.

                                                                                  Вы не совсем правы, когда говорите, что если от a+b нельзя избавиться, что нет смысла менять одно на другое

                                                                                  переход в p-адическую арифметику дал вообще даже иную оценку сложности работы.

                                                                                  Под "нельзя избавиться" я как раз подразумевал, в том числе, невозможность эффективного перехода в p-адическую арифметику.
                                                                                  И вот, кстати, оценить производительность алгоритма на p-адической арифметике может быть полезно, что бы знать, до каких пор есть смысл заниматься микро-оптимизациями, например. Или, что более важно, что бы знать, на какой прирост можно надеяться в сравнении с предыдущей реализацией, а то, может, и начинать смысла нет.
                                                                  0
                                                                  А меня тут в моей последней статье активно ругали за активный велосипедизм применительно к FPGA. Хотя на мой взгляд, уж где-где, а в ПЛИС, которые умеют реконфигурироваться под любую задачу, такое раздолье для велосипедов! Более того, они успешно приживаются в крупных проектах и десятки лет живут своей жизнью, никому не мешая, но при этом оптимальным образом решая требуемые задачи. Так или иначе, все мои доводы в доказательство преимущества велосипеда перед стандартным решением для ПЛИС не дали эффекта. Но тем не менее, велосипеды были, есть и будут разрабатываться. :)
                                                                    +1
                                                                    В моей личной практике есть ещё причина номер 5:

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

                                                                    Вот один из характернейших примеров из моей практики.
                                                                      +2
                                                                      я тоже склонен делать собственные реализации алгоритмов когда это уместно и возможно. Но всегда это выбор связанный с ограничениями по времени, вычислительным ресурсам, сложности и т.п.
                                                                      Когда находятся готовые и доступные реализации алгоритмов, которые вписываются в имеющиеся ресурсные ограничения — это называется счастье и грех ими не пользоваться!
                                                                      Также неплохо, когда разработаны сами алгоритмы для той или иной задачи и нужно лишь вписать их в ограниченные ресурсы. Даже когда есть теория как подступиться к решению той или иной задачи — уже неплохо.

                                                                      Зачастую возиться с оптимизацией и собственной реализацией алгоритмов начинаешь, когда чувствуешь, что есть возможность сократить общие издержки решения задачи (издержки собственной реализации алгоритма + альтернативные издержки + издержки работы алгоритма на имеющихся ресурсах), но тут бывает добавляется радость от решения сложной задачи и часто забываешь про альтернативные издержки (что это время ты или твой сотрудник мог бы заняться чем-то ещё полезным/прибыльным).
                                                                        +1
                                                                        Автор так сильно зациклен на чужих возможных ошибках, что мне показалось, будто он практически исключает ошибки в своём коде. Иными словами — где гарантия, что в Вашем коде в итоге ошибок будет меньше чем в сторонних библиотеках? Или того, что вы не допустите одну но фатальную ошибку?
                                                                        Я знаю человека, который написал заглушку для сайта. на 40 строк кода 12 ошибок. Но всё работало как надо. И это не мешает ему работать в профессии.
                                                                          0
                                                                          Позволю заметить, что оперативность внесения изменений выше. Алгоритмических ошибок бывает достаточно и в моем коде, но в отличии от чужого они решаются сразу, с ходу, без необходимости вникания в чужой код.
                                                                            +1
                                                                            Я с Вами солидарен. К тому же чужой код имеет много лишнего, потому, что у каждого задачи разные (например ему нужно вот, это, это и это, а мне только одно из них и еще что-то свое и лепить этот комбайн, бывает, не рационально).
                                                                            0
                                                                            Архитектура системы такова что единичные ошибки не могут сильно повлиять на поведение системы в целом. Но это выходит за рамки статьи. Серьезные фатальные ошибки засекаются еще на этапе проверки SoftwareInLoop через симулятор.

                                                                          Only users with full accounts can post comments. Log in, please.