В итоге я немного поковырялся в стандарте, доступных реализациях и вышло у меня следующее: Continue reading
Posts Tagged → Оптимизация
Выступления Майерса на NDC
Досмотрел лекции Майерса с NDC 2014 (WTF, в Норвегии проходят годные конференции, а у нас нет?!) Effective Modern C++ и CPU Caches and Why You care.
Послушать было достаточно интересно, Майерс просто ну очень хороший докладчик, хотя, надо признать, слушать про Auto достало. Одно радует, опытный докладчик даже из совершенно затертой темы сможет сделать интересный рассказ. В данном случае – это информация о разложенных посредствам auto граблей.
Во второй лекции первые 10 минут можно смело проматывать. Что довольно неожиданно, Майерс, в том числе, говорит и о Instruction Cache, чего я не замечал за другими докладчиками/статьями на эту тему. Ну и как всегда, лекцию пронизывает модная на данный момент мысль: массивы хорошо, все остальное так себе. Кстати, если кто-то не знает что такое False Sharing, то в этой лекции можно найти образцово показательное объяснение сего печального явления.
Разбитые надежды или просто непонимание?
В одной из лекций с PyCon US 2014 проскочила очень заинтересовавшая меня информация о том, что с Python 3.3 CPython поддерживает оптимизацию для классов, и старый вариант использования Python, когда класс могли просто заменить на Dict не верен в корне, т.к. Dict не поддерживает никакой типизации. Вроде все верно и логично: никак не ограничиваемый по данным ассоциативный массив против класса, в котором можно предсказать используемые типы и количество полей. Continue reading
Оптимизация кода Python
Решил прояснить для себя возможности оптимизации приложений написанных на Python. В интернете существует довольно много рекомендаций на этот счет, так что я просто пытаюсь свести всю информацию вместе и выяснить чем вызваны те или иные отличия.
Хотя, на первый взгляд кажется, что Python и быстрый код не совместимые понятия, это не совсем правда.
Все тесты проводились на Python 3.3.3 и, само собой, не обошлось без IPython, который ну просто killer-feature этого языка. Continue reading
Взаимодействие между задачами в Rust
Модель памяти Rust, в общем случае, не допускает совместного обращения к одной и той же памяти (shared model) предлагая вместо этого обмениваться сообщениями (mailbox model). При этом существует возможность работать с общей памятью в режимах “только для чтения” и “один писатель много читателей”. На данный момент в Rust существует несколько способов организации взаимодействия между задачами:
- Низкоуровневые каналы и порты из модуля core::comm;
- Высокоуровневая абстракция над каналами и портами std::comm;
- Каналы предназначенные для передачи бинарных данных из std::flatpipes;
- Новая инфраструктура для обмена сообщениями core::pipes.
Continue reading
Ускорение ветвления в C++
Немного поигрался с довольно редко испольуземой при разработке приложений дерективой компилятора __builtin_expect. Эта директива поддерживатеся как Clang, так и в GCC, а в случае с MSVC есть довольно похожая директива __assume, работающая только для switch, и которую, если верить MSDN, использовать не рекомендутся, так как она ведет к потенциальным проблемам. Сказать насколько может быть полезна директива __builtin_expect сложно, но мало ли, к примеру товарищу на моем любимом форуме это зачем-то понадобилось.
Немного о самой __builtin_expect. При генерировании ассемблерных инструкций, компилятор самостоятельно решает о том, какая из ветвей условия должна быть размещена в начале, а к какой необходимо перейти посредством условного перехода. Данное поведение никак не регламентируется стандартом и полностью зависит не только от компилятора, но и от выбранного уровня оптимизации, в чем можно легко убедится получив несколько ассемблерных листингов одного и того же кода. При помощи же __builtin_expect можно указать компилятору какую из ветвей в условии if-else или switch-case разместить первой, а на какую организовать условный переход. Continue reading
Тестовые задания в Яндексе. Часть 2.
Как и планировал, опробовал второй способ сортировки, а именно сортировку подсчетом. Кода в разы меньше, сам код куда проще, но… Крайне плохо масштабируемое решение с сильной зависимостью от количества доступной памяти. Так при использовании максимального количества доступной памяти в 256 Мб, приходится делать 64 прохода по файлу. Если же попытаться разнести чтение и запись (как я писал раньше, асинхронная запись дает ускорение приблизительно в 10-15%) то количество проходов вырастает до 128 и итоговая скорость оказывается даже меньше чем при последовательной обработке. Так же, мое решение не будет корректно работать в том случае, если количество одинаковых элементов превысит максимальное значение помещающееся в size_t.
Тем не менее, сортирует довольно быстро: 1 Гб, в среднем, обрабатывается за 108 секунд.
P.S. а вообще, я выдохся с данной задачкой (как делать ясно, побочные эффекты алгоритмов тоже очевидны), так что вернусь ней… через еще пару лет?
Тестовые задания в Яндексе
Когда-то, давным-давно, в разгар активного поиска работы я написал в Яндекс. Не то что бы я думал туда пройти, все же алгоритмы не моя сильная сторона, но мне подумалось “а почему бы не попробовать, особенно с учетом того, что на РСДНе ходят легенды о полнейшей невменяемости собеседующих там товарищей”. Вобщем решил сходить и чисто позырить. Позырить мне так и не удалось, т.к. яндексовцы дали тестовое задание на дом, а на такое я принципиально не соглашаюсь. Но, надо признать, задание было интересное, и я его прикопал с целью когда-нибудь, когда будет соответствующее настроение, решить. Соответствующего настроения не было у меня два года, и вдруг оно появилось! Continue reading
Классическая задача для собеседования в реальной жизни
Случилось странное – я столкнулся с буквально классической задачей с собеседования в реальной жизни. Задача состоит в том, что необходимо найти первый не нулевой бит в массиве. Поиск должен происходить максимально быстро, скорость поиска желательно получить приближённую к линейной. Никаких правил по распределению единиц в массиве нет. Массив не велик и должен не вылезать за пределы одной кэш-линии.
Родились 3 варианта алгоритма, одна часть которого общая во всех случаях, вторая специфическая.
Общая часть сводится к поиску первого 32 разрядного слова с хотя бы одним не нулевым битом. Дальше, в найденном 32 разрядном слове ищем первый не нулевой бит. Я не знаю как можно оптимизировать первую часть алгоритма, так что ищу простым перебором. Continue reading