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


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

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

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

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

Доброго всем времени суток, уважаемые посетители сайта Хабрахабр. В данной статье я бы хотел рассказать вам о том, что такое диаграмма Вороного (изображена на картинке ниже), о различных алгоритмах её построения (за , — пересечение полуплоскостей, — алгоритм Форчуна) и некоторых тонкостях реализации (на языке C++).



Также будет рассмотрено много интересных применений диаграммы и несколько любопытных фактов о ней. Будет интересно!

Тот факт, что в большинстве случаев URL-адреса хранятся в виде простого текста, либо ключ для их расшифровки располагается в самой функции расшифровки, позволяет нам извлекать эти URL-адреса автоматически из многих образцов CPL malware с использованием специального скрипта. В случае семпла, который хранит строки в виде открытого текста, строка с адресом может быть извлечена напрямую из CPL-файла. В противном случае, т. е. в случае, когда строка с адресом зашифрована, скрипт подвергает анализу функцию расшифровки, в которой хранится ключ. Исключение составили некоторые семплы вредоносного ПО, для которых скрипт не смог расшифровать зашифрованные строки. В таких семплах ключ расшифровки не был доступен в функции, а располагался в ресурсах CPL-файла. Для извлечения ключа оттуда вредоносный код использует стандартные API для работы с ресурсами: FindResource, LoadResource, SizeofResource and LockResource. Сам ресурс, в котором располагается ключ расшифровки, является зашифрованным.

Это последняя, на сегодняшний день, статья из цикла про внутреннее устройство конкурентных ассоциативных контейнеров. В предыдущих статьях рассматривались hash map, был построен алгоритм lock-free ordered list и контейнеры на его основе. За бортом остался один важный тип структур данных — деревья. Пришло время немного рассказать и о них.

Исследования, посвященные алгоритмам конкурентных деревьев, не требующих внешней синхронизации доступа к ним, начались довольно давно — в 70-х годах прошлого века, — и были инициированы развитием СУБД, поэтому касались в основном оптимизации страничных деревьев (B-tree и его модификации).

Развитие lock-free подхода в начале 2000-х не прошло мимо алгоритмов деревьев, но лишь недавно, в 2010-х годах, появилось множество действительно интересных работ по конкурентным деревьям. Алгоритмы деревьев довольно сложны, поэтому исследователям потребовалось время — порядка 10 лет — на их lock-free/non-blocking адаптацию. В данной статье мы рассмотрим самый простой случай — обычное бинарное дерево, даже не самобалансирующееся.

В предыдущих статьях (раз, два) мы рассматривали классический hash map с хеш-таблицей и списком коллизий. Был построен lock-free ordered list, который послужил нам основой для lock-free hash map.
К сожалению, списки характеризуются линейной сложностью поиска O(N), где N — число элементов в списке, так что наш алгоритм lock-free ordered list сам по себе представляет небольшой интерес при больших N.
Или все же представляет?..

Вступление

Давно хотел написать статью про образование в Computer Science, но руки не доходили. Решил все-таки это наконец сделать. Итак, о чем пойдет речь? Речь о том, что из себя представляет диплом MSc Computer Science топовых университетов США (во всех подробностях, включая основные курсы, книги и проекты) и как ему соответствовать.

Почему именно MSc? Это — некая развилка: с одной стороны после MSc — вы уже готовый к жизни инженер (да, речь идет о инженерной подготовке, как мне кажется это самое больное место в нашей системе образования), с другой — можно спокойно идти по пути PhD. Как известно, в PhD программу можно попасть и не особо умея программировать — особенно это касается теоретического Computer Science. С другой стороны найти работу программиста тоже дело не очень сложное, и часто не требует мощного образования. Но достигнув уровня MSc — вы получаете возможность разбираться как во всех новый идеях в Computer Science, так и возможность их воплотить в практику. То есть с одной стороны круто разобраться в каком-нибудь deep learning и сделать в нем что-то новое, а также взять и написать свою операционную систему (кто так сделал?). Причем вы не зажаты в рамки узкой специализации (если конечно продолжаете учиться). То есть вы теперь — универсальный солдат, готовый на все.

Надеюсь что эта статья будет полезна:
1. Студентам, которые хотят соответствовать высоким стандартам топ вузов США, или собирающиеся туда в аспирантуру по Computer Science
2. Профессионалам, которые хотят закрыть «дыры» и пробелы
3. Может кто-то из преподавателей возьмет на заметку для своих курсов.
4. Студентам, аспирантам американских вузов — хотелось бы тоже получить фидбэк, особенно касается последних трендов в образовании

Что же здесь будет написано? Минимум философии и общих мыслей: конкретная программа undergraduate и graduate курсов, конечно из дисциплин наиболее мне близких. Все курсы были лично прочувствованы на собственной шкуре, по этому и пишу. (Я пытался записаться на все интересные курсы, которые были, но мой основной упор — системное программирование, базы данных и искусственный интеллект. Отсюда конечно некий bias, но пытаюсь предложить более-менее универсальную программу).

Все мы знаем, что не следует самостоятельно реализовывать криптографические примитивы. Мы также в курсе, что даже если мы хитрым образом развернем порядок букв во всех словах сообщения, сдвинем каждую букву по алфавиту на 5 позиций и разбавим текст случайными фразами, чтобы сбить атакующих с пути, наш замечательный шифр скорее всего вскроет любой мало-мальски знакомый с криптографией человек (а в данном случае с задачей справится и в меру умный 12-летний подросток).

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

Мой посыл не в том, что убедить вас отказаться от самостоятельного использования криптографических средств или пойти и нанять консультанта с зарплатой от $1000 в час всякий раз когда вы задумываетесь о шифровании.
Частично я веду к тому, что вам никогда не следует расслабляться, всегда нужно быть начеку, изыскивая пути, которые злоумышленник может использовать для получения дополнительной информации о вашей системе, а частично к тому, что Padding Oracle Attack является крутой демонстрацией всего этого. Итак, начнем.

Биометрия набирает обороты

В России обсуждают вопросы о создании Национального биометрического Центра с объемом базы данных 100 – 150 млн. записей. В Госдуму уже внесен проект закона об обязательной биометрической регистрации. На Хабре пишут про результаты тестирования алгоритмов биометрических компаний и пытаются выяснить, кто круче: пароль или биометрия. Даже Mastercard выпускает платёжную карту со сканером отпечатков пальцев и VISA тоже.

Хакеры ехидно потирают ручки

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

Про то, как «хакнули по фотографии» первую женщину на посту министра обороны Германии, читайте под катом.

Пройдем по следам C++ 2015 Russia далее.
В предыдущей статье мы рассмотрели алгоритм для lock-free ordered list и на его основе сделали простейший lock-free hash map. У этого hash map есть недостаток: размер хеш-таблицы постоянен и не может быть изменен в процессе роста числа элементов в контейнере. Это не представляет проблемы, если мы заранее примерно представляем требуемый объем контейнера. А если нет?

Мне оказали честь — пригласили выступить на первой конференции C++ 2015 Russia 27-28 февраля. Я был насколько наглым, что запросил 2 часа на выступление вместо положенного одного и заявил тему, наиболее меня интересующую — конкурентные ассоциативные контейнеры. Это hash set/map и деревья. Организатор sermp пошел навстречу, за что ему большое спасибо.
Как подготовиться ко столь ответственному испытанию выступлению? Первое — нарисовать презентацию, то есть кучу картинок, желательно близко к теме. Но надо ещё и два часа озвучивать картинки, — как все это запомнить? Как избежать глубокомысленных «ээээмммм», «здесь мы видим», «на этом слайде показано», несвязных прыжков повествования и прочих вещей, характеризующих выступающего c не очень хорошей стороны в части владения родным языком (это я про русский, с C++ я разобрался быстро — никакого кода в презентации, только картинки)?
Конечно, надо записать свои мысли, глядя на слайды. А если что-то написано, то не худо бы и опубликовать. А если публиковать, — то на хабре.
Итак, по следам C++ 2015 Russia! Авторское изложение, надеюсь, без авторского косноязычия, без купюр и с отступлениями по теме, написанное до наступления события, в нескольких частях.

Пару месяцев назд Скотт Майерс (Scott Meyers) выпустил новую книгу Effective Modern C++. Последние годы он безусловно является писателем №1 «про это», кроме того он блестящий лектор и каждая его новая книга просто обречена быть прочитана пишущими на С++. Более того, именно такую книгу я ждал давно, вышел стандарт С++11, за ним С++14, уже виднеется впереди С++17, язык стремительно меняется, однако нигде так и не были описаны все изменения в целом, взаимосвязи между ними, опасные места и рекомендуемые паттерны.

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

Все началось с данного топика на сайте gamedev.ru. Топикстартер предложил найти сортировку, которая обладает следующими свойствами:

1. Время выполнения — гарантированные O(nlogn).
2. Использование O(1) дополнительной памяти.
3. Применимость для сортировки данных в односвязных списках (но не ограничиваясь ими).

Оговорки на все три ограничения:

1. Гарантированные O(nlogn) означают, что, например, среднее время быстрой сортировки не подходит — должно получаться O(nlogn) для любых, даже самых худших входных данных.
2. Рекурсию использовать нельзя, поскольку она подразумевает O(logn) памяти на хранение стека рекурсивных вызовов.
3. Произвольного доступа к элементам сортируемого массива нет, мы можем двигаться итератором от любого элемента только к соседнему (за O(1)), причем только в одном направлении (вперед по списку). Модифицировать сам список (перевешивать указатели на следующие элементы) нельзя.

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

Под катом можно узнать, что в итоге получилось у нас.

Challenge. Прежде чем заглядывать под кат, предлагаю сначала самостоятельно подумать над алгоритмом. Если придумается что-то круче нашего варианта — напишите в комментариях.

Одним субботним декабрьским вечером сидел я над книгой The Blind Watchmaker (Слепой Часовщик), как на глаза мне попался невероятно интересный эксперимент: возьмём любое предложение, например Шекспировскую строку: Methinks it is like a weasel и случайную строку такой же длины: wdltmnlt dtjbkwirzrezlmqco p и начнем вносить в неё случайные изменения. Через сколько поколений эта случайная строка превратится в Шекспировскую строку, если выживать будут лишь потомки более похожие на Шекспировскую?

Сегодня мы повторим этот эксперимент, но в уже совершенно другом масштабе.



Структура статьи:

1. Что такое генетический алгоритм
2. Почему это работает
3. Формализуем задачу со случайной строкой
4. Пример работы алгоритма
5. Эксперименты с классикой
6. Код и данные
7. Выводы

Осторожно трафик!

Периодически, как правило во вторую среду месяца, можно услышать истории о том, что Windows после очередного обновления перестает загружаться, показывая синий экран смерти. В большинстве случаев причиной такой ситуации оказывается либо руткит, либо специфичное системное ПО, фривольно обращающееся со внутренними структурами ОС. Винят, конечно, все равно обновление, ведь «до него все работало». С таким отношением не удивительно, что «Майкрософт» не поощряет использование всего, что не документировано. В какой-то момент, а именно с релизом Windows Server 2003, MS заняла более активную позицию в вопросе борьбы с чудо-поделками сторонних разработчиков. Тогда появился механизм защиты целостности ядра — kernel patch protection, более известный как PatchGuard.

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

Потоки ввода-вывода в стандартной библиотеке C++ просты в использовании, типобезопасны, устойчивы к утечке ресурсов, и позволяют простую обработку ошибок. Однако, за ними закрепилась репутация «медленных». Этому есть несколько причин, таких как широкое использование динамической аллокации и виртуальных функций. Вообще, потоки — одна из самых древних частей стандартной библиотеки (они начали использоваться примерно в 1988 году), и многие решения в них сейчас воспринимаются как «спорные». Тем не менее, они широко используются, особенно когда надо написать какую-то простую программу, работающую с текстовыми данными.

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

Сегодня в комментариях у посту возникло обсуждение о медленности iostreams. В частности, freopen пишет

Забавно смотреть на ваши оптимизации, расположенные по соседству со считыванием через cin :)

а aesamson даёт такую рекомендацию

Можно заменить на getchar_unlocked() для *nix или getchar() для всех остальных.
getchar_unlocked > getchar > scanf > cin, где ">" означает быстрее.

В этом посте я развею и подтвержу некоторые мифы и дам пару рекомендаций.

Здесь было много статей об универсальных Lock-free объектах, однако, для некоторых частных случаев они излишне громоздки. Мой случай как раз таким и являлся: требовалось организовать одностороннюю передачу информации от одного потока другому. Главный поток запускает рабочий, после чего он может только запросить его остановку и никак больше управлять он им не может. В свою очередь рабочий поток может уведомлять главный о своем текущем состоянии (прогрессе выполнения), а также отсылать промежуточные результаты выполнения. Получается, что требуется только передача данных от рабочего к главному потоку.

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

Со времени предыдущего поста из жизни lock-free контейнеров прошло немало времени. Я рассчитывал быстро написать продолжение трактата об очередях, но вышла заминка: о чем писать, я знал, но реализации на C++ этих подходов у меня не было. «Не годится писать о том, что сам не попробовал», — подумал я, и в результате я попытался реализовать в libcds новые алгоритмы очередей.
Сейчас настал момент, когда я могу аргументированно продолжить свой цикл. В данной статье закончим с очередями.

Кратко напомню, на чем я остановился. Были рассмотрены несколько интересных алгоритмов lock-free очередей, а под занавес приведены результаты их работы на некоторых синтетических тестах. Главный вывод — всё плохо! Надежды на то, что lock-free подход на магическом compare-and-swap (CAS) даст нам пусть не линейный, но хотя бы какой-то рост производительности с увеличением числа потоков, не оправдались. Очереди не масштабируются. В чем причина?..

Здравствуйте! Вы забыли заплатить за интернет, провайдер заблокировал TCP и UDP, а про ICMP забыл, и любой ресурс пингуется? Тогда этот топик для вас!