Рубрика «оптимизация кода»

Быстрый двоичный поиск без ветвления - 1


Мои читатели — занятые люди, поэтому сразу перейду к делу. Вот она, самая быстрая обобщённая (и простая) реализация двоичного поиска на C++:

template <class ForwardIt, class T, class Compare>
constexpr ForwardIt sb_lower_bound(
      ForwardIt first, ForwardIt last, const T& value, Compare comp) {
   auto length = last - first;
   while (length > 0) {
      auto rem = length % 2;
      length /= 2;
      if (comp(first[length], value)) {
         first += length + rem;
      }
   }
   return first;
}

Тот же интерфейс функции, что и у std::lower_bound, но вдвое быстрее и короче. «Без ветвления», потому что if компилируется в команду условной передачи, а не в ветвление/условный переход. Ближе к концу статьи мы изучим опции компилятора и даже более быстрые версии полностью без ветвления. Для понимания этой статьи не нужны особые знания в C++. Достаточно понимать, что итераторы (first и last) по сути являются указателями на элементы массива, хотя могут указывать на один элемент дальше, чем последний элемент массива. Можете не обращать внимания на template, class, constexpr и &. Вот если бы существовал быстрый и чистый язык, работающий на уровне железа...1 2Читать полностью »

Содержание

  1. Общие сведения.

  2. Увеличиваем потребление памяти вдвое.

  3. Увеличиваем потребление памяти втрое.

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

  5. Заключение.

Общие сведения

Известно, что PHP активно использует механизм copy-on-write. Это означает, что при попытке внутри функции что-то записать в переданные ей параметры вначале будет сделана копия этой переменной, а уж затем в неё что-то запишется. Такая же ситуация наблюдается с итерацией массива с помощью foreachЧитать полностью »

Укрощение имен. Как нейминг помогает оптимизировать код - 1

Что такое имя? Имя — это ярлык, дескриптор, указатель в вашей памяти. Это краткое изложение сложной идеи. Оно позволяет ссылаться на «экономику» или «догфудингЧитать полностью »

Как оценить реальную производительность своего кода - 1


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

Как сделать программу на Go быстрее на 42%, изменив один символ - 1

Если вы прочитали заголовок и подумали «ну, ты, наверно, сделал сначала что-то глупое», то вы правы! Но что такое программирование, как не упражнения в глупых ошибках? Поиск глупых ошибок — это и есть самое большое удовольствие!

Также стоит заранее сделать оговорку о бенчмаркинге: ускорение на 42% было замерено при выполнении программы с моими данными и на моём компьютере, поэтому относитесь к этому результату с долей скепсиса.

Что делает программа?

codeowners — это программа на Go, выводящая владельцев каждого из файлов в репозитории согласно набору правил, указанному в файле GitHub CODEOWNERS. Правило может гласить, что всеми файлами с расширением .go владеет команда @gophers, или что всеми файлами в папке docs/ владеет команда @docs.
Читать полностью »

В этой статье я хочу поделиться несколькими нестандартными алгоритмами для быстрого возведения числа в степень, а также продемонстрировать их реализацию и сравнить их быстродействие в C++, C# и Java.

Ускоряем pow - 1

Сравнить точность алгоритмов можно прямо сейчас на этой странице.

Читать полностью »

Неожиданные причины торможения программ и систем - 1

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

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

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

Ускоряем на 70% игру на процессоре в 1 МГц - 1

Давным-давно, во времена студенчества в колледже я немного занимался разработкой компьютерных видеоигр. Это была эпоха 8-битных PC, когда игровое оборудование по современным стандартам было почти невозможно медленным.

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

Это история об одном из таких трюков.

Я постараюсь припомнить все важные подробности, однако в чём-то могу ошибиться. Если так случится, простите меня, это было очень давно.

Исходные данные

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

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

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

Я посмотрел. Но там нельзя было найти никакой простой оптимизации.Читать полностью »

Профессор Никлаус Вирт был прав. Создатель языка Pascal, соавтор технологии структурного программирования, лауреат премии Тьюринга в 1995 году заметил:

«Замедление программ происходит куда быстрее, чем ускорение компьютеров»

С тех пор это высказывание считается законом Вирта. Он фактически нивелирует закон Мура, согласно которому количество транзисторов в процессорах удваивается примерно с 1965 года. Вот что пишет Вирт в статье «Призыв к стройному софту»:

«Около 25 лет назад интерактивный текстовый редактор умещался всего в 8000 байт, а компилятор в 32 килобайта, тогда как их современные потомки требуют мегабайтов. Стало ли всё это раздутое программное обеспечение быстрее? Нет, совсем наоборот. Если бы не в тысячу раз более быстрое железо, то современное программное обеспечение было бы совершенно непригодным».

С этим трудно не согласиться.
Читать полностью »

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

Хостинг и выделенные серверы: отвечаем на вопросы. Часть 3 - 1
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js