Эксперименты с malloc и нейронными сетями

Автор: admin от 26-05-2017, 12:30, посмотрело: 348

Эксперименты с malloc и нейронными сетями

Больше года назад, когда я работал антиспамщиком в Mail.Ru Group, на меня накатило, и я написал про эксперименты с malloc. В то время я в свое удовольствие помогал проводить семинары по АКОСу на ФИВТе МФТИ, и шла тема про аллокацию памяти. Тема большая и очень интересная, при этом охватывает как низкий уровень ядра, так и вполне себе алгоритмоемкие структуры. Во всех учебниках написано, что одна из основных проблем динамического распределения памяти — это ее непредсказуемость. Как говорится, знал бы прикуп — жил бы в Сочи. Если бы оракул заранее рассказал весь план по которому будет выделяться и освобождаться память, то можно было составить оптимальную стратегию, минимизирующую фрагментацию кучи, пиковое потребление памяти и т.д. Отсюда пошла возня с ручными аллокаторами. В процессе раздумий я натолкнулся на отсутствие инструментов логирования malloc() и free(). Пришлось их написать! Как раз про это была статья (а ещe я изучал macOS). Были запланированы две части, однако жизнь круто повернулась и стало не до malloc(). Итак, пора восстановить справедливость и реализовать обещанное: ударить глубоким обучением по предсказанию работы с кучей.


Внутри:



  • Совершенствуем libtracemalloc, перехватчик malloc().

  • Строим LSTM на Keras — глубокую рекуррентную сеть.

  • Обучаем модель на примере работы реального приложения (vcmi/vcmi — а вы думали, причем здесь Heroes III?).

  • Удивляемся неожиданно хорошим результатам.

  • Фантазируем про практическое применение технологии.

  • Исходники.


Интересно? Добро пожаловать под кат.

Категория: Программирование / Системное администрирование

 

Эксперименты с malloc

Автор: admin от 13-04-2016, 14:40, посмотрело: 532

Эксперименты с malloc

Как известно, в современных архитектурах x86(_64) и ARM виртуальная память процесса линейна и непрерывна, ибо, к счастью, прошли времена char near* и int huge*. Виртуальная память поделена на страницы, типичный размер которых 4 KiB, и по умолчанию они не отображены на физическую память (mapping), так что работать с ними не получится. Чтобы посмотреть текущие отображённые интервалы адресов у процесса, в Linux смотрим /proc//maps, в OS X vmmap . У каждого интервала адресов есть три вида защиты: от исполнения, от записи и от чтения. Как видно, самый первый интервал, начинающийся с load address (соответствующий сегменту .text у ELF в Linux, __TEXT у Mach-O в OS X), доступен на чтение и исполнение — очень логично. Ещё можно увидеть, что стек по сути ничем не отличается от других интервалов, и можно быстро вычислить его размер, вычтя из конечного адреса начальный. Отображение страниц выполняется с помощью mmap/munmap, а защита меняется с помощью mprotect. Ещё существуют brk/sbrk, deprecated древние пережитки прошлого, которые изменяют размер одного-единственного интервала «данных» и в современных системах эмулируются mmap’ом.

Все POSIX-реализации malloc так или иначе упираются в перечисленные выше функции. По сравнению с наивным выделением и освобождением страниц, округляя необходимый размер в большую сторону, malloc имеет много преимуществ:


  • оптимально управляет уже выделенной памятью;

  • значительно уменьшает количество обращений к ядру (ведь mmap — это syscall);

  • вообще абстрагирует программиста от виртуальной памяти, так что многие пользуются malloc’ом, вообще не подозревая о существовании страниц, таблиц трансляции и т. п.


Довольно теории! Будем щупать malloc на практике. Проведём три эксперимента. Работа будет возможна на POSIX-совместимых операционках, в частности была проверена работа на Linux и на OS X.

Категория: Программирование / Веб-разработка

 

Структура данных 2-3-4 дерево

Автор: admin от 22-12-2015, 13:00, посмотрело: 843

Когда я первый раз столкнулся с темой бинарных деревьев в программировании, то сразу нашел на Хабре ответы почти на все возникшие у меня вопросы, но время шло, вопросов становилось больше и совсем недавно я нашел тему, которую еще не осветили на данном ресурсе — это 2-3-4 деревья. Есть отличная статья на тему 2-3 деревьев, в которой можно найти ответы на вопросы «Что такое куча?», «Что такое 2-3 деревья», а также информацию про основные операции со структурой, поэтому я не буду повторяться и сразу перейду к главной теме.

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

Структура данных 2-3-4 дерево

Категория: Программирование

 

Ограничение памяти, доступной программе

Автор: admin от 4-09-2015, 00:26, посмотрело: 584

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

Виртуальная память процесса


Перед тем, как окунуться в разные методы ограничения памяти, необходимо знать, как устроена виртуальная память процесса. Лучшая статья на эту тему – "Анатомия программы в памяти"

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

Первое: уменьшение объёма адресного пространства. Это довольно просто, но не совсем корректно. Мы не можем уменьшить всё пространство до 1 Мб – не хватит места для ядра и библиотек.

Второе: уменьшение объёма кучи. Это не так-то просто сделать, и обычно так никто не делает, поскольку это доступно только через возню с компоновщиком. Но для нашей задачи это был бы более корректный вариант.

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

Для тестирования будем использовать небольшую программу по имени big_alloc, размещающую, и затем освобождающую 100 MiB.

Категория: Программирование / Системное администрирование / Linux

 

Структуры данных. Неформальный гайд

Автор: admin от 29-07-2015, 08:41, посмотрело: 639

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

Категория: Программирование

 

J-сортировка

Автор: admin от 28-04-2014, 06:20, посмотрело: 856

J-сортировка

Пирамидальная сортировка (она же сортировка кучей) – классический алгоритм который, пожалуй, должен знать любой программист. Старая добрая «пирамидка» примечательна тем, что в независимости от набора данных у неё одна и та же сложность по времени (причём, очень пристойная) – O(n log n). Лучших и вырожденных случаев для неё нет.

С момента изобретения метода (а в этом году алгоритм празднует свой полувековой юбилей) было немало охочих кардинально оптимизировать процесс накладывания сортирующих куч. Тернарная пирамидальная сортировка, плавная сортировка, сортировка декартовым деревом – вот неполный список инноваций. Перечисленные алгоритмы хотя при тестировании и опережают оригинал по абсолютной скорости кто на 12, а кто и на 25%, в оценке временной сложности всё равно крутятся вокруг O(n log n). При этом данные методы весьма изощрённо реализованы.

Своё видение пирамидальной сортировки предложил и скромный труженик Университета Манитобы Джейсон Моррисон. При этом способ в некоторых случаях по скорости приближается к O(n).

Так ещё метод и прост до безобразия

Категория: Программирование