Русский
Русский
English
Статистика
Реклама

Arc

Введение в ARCORC в Nim

16.10.2020 08:10:13 | Автор: admin

Nim переходит к более эффективным моделям управления памятью: ARC и ORC. Давайте узнаем, как именно они изменят работу с памятью в нём.



Введение


Всем привет! В этой статье я постараюсь рассказать, что такое ARC и ORC и как они повлияют на производительность или другие части Nim'а. Я не буду глубоко погружаться в аспекты программной части, а постараюсь дать более или менее высокоуровневое объяснение.


Давайте начнём издалека: Nim всегда был языком со сборщиком мусора (GC). Конечно же GC можно выключить, но тогда при работе с большей частью стандартной библиотеки (а она немаленькая) память будет утекать.


Стандартным GC в Nim уже долгое время является refc (отложенный подсчёт ссылок с mark & sweep фазой для сборки циклов), хотя доступны и другие варианты, как markAndSweep, boehm, go, regions.


За последние несколько лет у разработчиков Nim'а появилось несколько разных идей, связанных с деструкторами, собственными ссылками (owned ref) и так далее:



Из симбиоза этих идей получилось то, что в Nim называется ARC


Что такое ARC?


По своей сути ARC это модель управления памятью, основанная на автоматическом подсчёте ссылок (Automatic Reference Counting) с деструкторами и семантикой перемещений (move semantics). Можно заметить то, что ARC в Nim называется так же, как ARC в Swift, но есть одно больше различие в Nim ARC не использует атомарный подсчёт ссылок.


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


Основным отличием ARC от остальных GC в Nim является то, что ARC полностью детерминированный компилятор автоматически вставляет деструкторы в программу для удаления переменных (строк, последовательностей, ссылок, и т.д), которые больше не нужны. В этом смысле ARC похож на C++ с его деструкторами (RAII)


Для того, чтобы продемонстрировать этот процесс, мы используем интроспекцию ARC expandArc, которая будет доступна в Nim 1.4.


Возьмём простой пример кода на Nim:


proc main =   let mystr = stdin.readLine()  case mystr  of "привет":    echo "Здравствуйте!"  of "пока":    echo "Удачи!"    quit()  else:    discardmain()

И используем эту интроспекцию командой nim c --gc:arc --expandArc:main example.nim.


--expandArc: mainvar mystrtry:  mystr = readLine(stdin)  case mystr  of "привет":    echo ["Здравствуйте!"]  of "пока":    echo ["Удачи!"]    quit(0)  else:    discardfinally:  `=destroy`(mystr)-- end of expandArc ------------------------

Результат этой интроспекции довольно интересен Nim завернул тело процедуры main в try: finally выражение (код в finally выполняется всегда, даже если внутри блока try было вызвано исключение) и вставил вызов =destroy для строки mystr, чтобы она уничтожилась после окончания её жизненного цикла.


Благодаря этому мы можем увидеть одну из главных возможностей ARC: управление памятью на основе областей видимости (scope-based MM). Область видимости это любой отдельный регион кода в программе. Такое управление памятью означает, что компилятор автоматически вставит вызовы деструкторов везде, где это необходимо, после выхода из области видимости. Многие части Nim'а вводят новые области видимости: процедуры, функции, конвертеры, методы, конструкции с block, циклы for и while и так далее.


У ARC к тому же имеются так называемые hooks специальные процедуры, которые можно привязывать к типам для того, чтобы перезаписать стандартное поведение компилятора при деструкции/перемещении/копировании переменной. Они являются очень полезными при создании нестандартных семантик для своих типов, работы с низкоуровневыми операциями, включающими сырые указателями, или для FFI.


По сравнению с refc ARC обладает немалым количеством преимуществ (включая упомянутые выше):


  • Управление памятью на основе областей видимости (деструкторы вставляются после областей видимости) уменьшает потребление памяти программой и улучшает производительность.


  • Семантики перемещений возможность компилятора статически анализировать программу и переводить копии в перемещения там, где это возможно.


  • Общая куча в отличие от refc, у которого куча отдельная для каждого потока (thread-local heap), в ARC потоки имеют доступ к одной и той же памяти. Благодаря этому не нужно копировать переменные между потоками вместо этого их можно перемещать. Так же стоит обратить внимание на RFC об изоляции и отправке данных между потоками, которое строится на основе ARC.


  • Упрощение работы с FFI к примеру, с refc необходимо явно инициализировать его в каждом "чужом" (т.е. не созданным в самой программе) потоке, что не нужно для ARC. Это так же означает, что ARC является намного лучшим выбором для создания общих библиотек, которые будут использоваться из других языков (.dll, .so, нативные модули для Python'а и так далее)


  • Подходит для программирования в системах реального времени hard realtime


  • Избавление от копий (copy elision), в Nim так же называется как вывод курсоров (cursor inference) позволяет компилятору заменять копии простыми курсорами (алиасами) в большом количестве случаев



В целом, ARC для программ на Nim является отличным шагом вперёд, делающим их быстрее, уменьшающим потребление памяти, и давая им предсказуемое поведение.


Для того, чтобы включить ARC для вашей программы, всё, что нужно сделать, это скомпилировать её с ключом --gc:arc, или добавить его в конфигурационный файл вашего проекта (.nims или .cfg).


Проблема с циклами


Но подождите! Разве мы что-то не забыли? ARC проводит подсчёт ссылок, и, как известно, подсчёт ссылок не может освобождать циклы. Цикл это отношение нескольких объектов, когда они все зависят друг от друга, и эта зависимость замкнута. Возьмём простой пример цикла: 3 объекта (A, B, C), у каждого их которых есть ссылка на другой объект, создают такую зависимость:



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


В Nim'е сборка циклов совершалась mark & sweep фазой refc GC, но лучше использовать ARC как основу для создания чего-то лучшего. Это приводит нас к:


ORC сборщик циклов для Nim


ORC является совершенно новым сборщиком циклов, основанным на ARC.
Его можно считать полноценным GC, так как он включает в себя фазу локального отслеживания (local tracing phase) в отличие от большинства других отслеживающих GC, которые проводят глобальное отслеживание (global tracing).
Для работы с async в Nim необходимо использовать ORC, потому что асинхронность в Nim'е образует циклы, которые необходимо собрать.


ORC сохраняет большую часть преимуществ ARC кроме детерминированности (частично) по умолчанию у ORC есть адаптивный лимит для сборки циклов, и hard realtime (тоже частично) по той же самой причине.
Для включения ORC вам нужно компилировать вашу программу с --gc:orc, но планируется, что в будущем ORC станет стандартным GC в Nim'е


Я заинтересовался! Как мне можно их протестировать?


ARC уже доступен в релизах Nim 1.2.x, но из-за большого количества недоработок лучше дождаться релиза Nim 1.4, в котором ARC и ORC будут доступны для широкого тестирования. Однако, если вам хочется протестировать их уже сейчас, то вы можете попробовать релиз-кандидат версии 1.4.


Это всё! Спасибо за чтение данной статьи я надеюсь, что она вам понравилась!


Источники / дополнительная информация:


Подробнее..

Почему меня разочаровали результаты Kaggle ARC Challenge

23.06.2020 14:06:23 | Автор: admin
Кто-то с ужасом, а кто-то с нетерпением ждет ИИ как в произведениях фантастов. С личностью, эмоциями, энциклопедическими знаниями и главное с интеллектом, то есть способностями к логическим выводам, оперированию абстрактными понятиями, выделению закономерностей в окружающем мире и превращению их в правила. Как мы знаем, именно такой ИИ теоретики называют сильным или ещё AGI. Пока это далеко не мейнстримное направление в машинном обучении, но руководители многих больших компаний уже считают, что сложность их бизнеса превысила когнитивные способности менеджеров и без настоящего ИИ двигаться вперёд станет невозможно. Идут дискуссии, что же это такое, каким он должен быть, как сделать тест чтобы уж точно понять, что перед нами AGI, а не очередной blackbox, который лучше человека решает локальную задачу например, распознавание лица на фотографии.

Три недели назад на каггле прошло первое в истории платформы соревнование по сильному ИИ Abstraction and Reasoning Challenge. Чтобы проверить способность моделей к обобщению и решению абстрактных задач, все участники суммарно решили только чуть менее половины задач. Решение-победитель справляется приблизительно с 20% из них и то девятичасовым перебором вручную захардкоженных правил (ограничение в девять часов установили организаторы).

В посте я хочу напомнить о сложностях работы с AGI, рассказать о самых интересных идеях участников, топовых решениях и поделиться мнением, что не так с текущими попытками создать AGI.

Вызов


В ноябре 2019 года создатель Keras Франсуа Шолле написал статью Об оценке интеллекта. На хабре краткий пересказ уже выложила Rybolos. Ключевой практический элемент статьи датасет для проверки способности алгоритмов к абстрактному мышлению в человеческом смысле. Просто поглядеть на него можно здесь.

Примеры задач из датасета; наверху вход, внизу ответ





Для человека эти задачи легко решаемы и напоминают блок из теста на IQ они сводятся к набору трансформаций над картинками от 30x30 до 1x1: продолжить узор, восстановить удаленный кусок, обрезать, закрасить замкнутые области, найти лишний объект и т.д.

Соревнование


Не заставило себя долго ждать и само соревнование на Kaggle на основе этого датасета, призы в котором были не самые большие в зависимости от скора $5K-8K за первое место. Для сравнения в проходившем параллельно соревновании DFDC победивший Селим Сефербеков получил полмиллиона долларов.

Тем не менее, соревнование привлекло несколько грандмастеров Kaggle: rohanrao (H20), kazanova (H20, кстати третье место в глобальном рейтинге Kaggle), boliu0 (NVIDIA), titericz (NVIDIA), tarunpaparaju, много очень сильных ребят из ODS, в том числе Влада Голубева и Илью Ларченко, которые взяли третье место. Всего до LeaderBoard дошли 914 команд.

Участникам предлагалось обучить модель на 400 задачах, в каждой из которых есть train (три-пять картинок), ответ и тест (одна-две картинки и соответственно один-два ответа). Этот датасет вручную разметил Davide Bonin на комбинации из 192 элементарных трансформаций.

Такой же по объему датасет (400 задач) предлагался для валидации (eval), впрочем, на нем можно было и обучаться особенно с учетом того, что задачи на нем отличались от обучающего. То есть сочетание трансформаций на тесте могли не встречаться на трейне, например вместо операции crop crop + resize. В лидерборде было 100 задач, при этом на каждое задание можно было выдавать три варианта ответа, достаточно чтобы хотя бы один был верным.

Интересные идеи


CNN c TensorFlow Lattice


Не попали в лидерборд.TensorFlow Lattice позволяет накладывать достаточно жесткие ограничения на фичи при обучении сеток: монотонность, взаимную важность, выпуклость, взаимное доверие, унимодальность. Это существенно увеличивает способности сеток к экстраполяции и сглаживает разделяющие поверхности. Для привлечения внимания картинка про сравнение разделяющих поверхностей разных моделей на одной задаче из блога TensorFlow Core.



В решении предлагалось взять сверточную сеть, так как CNN широко применяется для решения задач на картинках вроде выделения объектов. Идея была любопытная, но решение сработало на тесте ровно никак:



Вариационные автоэнкодеры


Заняли 131 место из 914 в лидерборде. Похожая идея наложить ограничения, но не на пространство признаков как в TF Lattice, а на пространство скрытых переменных, то есть использовать вариационные автоэнкодеры. О них на хабре есть отличная статья.

Это решение было доработано и дошло до LeaderBoard.На картинке в первой строке входное изображение, во второй правильный ответ, в третьей результат работы модели.



Генетический алгоритм



Занял 631 место из 914 в лидерборде. В этом кейсе в качестве генов реализовано одиннадцать трансформаций DSL генетического алгоритма. В ходе селекции по стратегии элитизма отбираются наиболее сильные гены:


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

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

Графовый подход


Занял 165 место из 914 на лидерборде. Одна из наиболее человекообразных идей
выделить на исходных изображениях объекты и далее работать с их трансформациями. Для выделения объектов применялся алгоритм k-clique-communities algorithm графовой библиотеки networkx, и справился он на отлично:







К сожалению, ноутбук с трансформациями автор не оставил, есть только выделение объектов, однако автор вошел в топ-19 на лидерборде.

Языковая модель


Заняла 592 место из 914 на лидерборде. На начало 2019 года BERT state-of-the-art языковая модель. За последние месяцы было множество её усовершенствований: RoBERTa, DistilBERT, ALBERT и другие. Здесь идея решения основывается на двух фактах:
  • Способности BERT работать с последовательностями.
  • Механизме attention, который можно научить вычленять связи даже между достаточно удаленными элементами последовательности в противовес идее о влиянии на элемент только нескольких соседних.

В некоторых задачах идея сработала, пример ниже.
Обучающие примеры: слева входная картинка, справа правильный ответ.





А вот результат работы обученной модели (справа):

Жаль, что на других задачах результаты не были такими хорошими.

Работающие решения


Эх, а как хотелось верить в способность моделей вытаскивать простые логические правила. Да и еще в интрепретируемом виде. В итоге поиск решения участниками свелся к написанию правил (трансформаций) для решения конкретных кейсов, поиску по форуму и объединению в свой ноутбук таких решений.

Например, задание про изменение цветов при сохранении размера изображения: ноутбук Zoltan, занявшего в итоге шестое место, вошел в решение Влада Голубева и Ильи Ларченко, которые заняли третье место. Решение по сути представляет объединение нескольких, в том числе публичных. Так, идеи Ильи описаны в его репозитории, он декомпозировал задачи на абстракции (цвета, блоки, маски), в терминах которых для которых реализовал трансформации, решающие 32 задания. К этому добавляются решения Влада как с похожим подходом на правилах и трансформациях, так и модель xgboost.

Пример работы решения


Обучающие примеры; слева входная картинка, справа правильный ответ.



А вот результат работы решения:

Достаточно похожим выглядит решение , взявшее второе место:
  1. Определить на входе тип задания (из шести по классификации автора) и параметры входных изображений.
  2. Иногда упростить задание например, поменять один цвет или повернуть объекты.
  3. Перебирать в цикле различные трансформации (реализовано 51) и их комбинации чтобы выбрать три максимально близкие к ответу картинки.
  4. Выполнить преобразования, обратные тем, что были на шаге 2, к трем кандидатам.
  5. Иногда имеет смысл сделать аугментацию например, из исходных примеров сделать задачи монохромными или только с одной формой.

Чемпион и 10 000 строк кода


Первое место занял icecuber, который захардкодил 100 правил из обучающего датасета и 100 правил из теста, выделил 42 основных трансформации, добавил аугментацию данных и жадный перебор вариантов с кучей технических трюков для ускорения (например, часть комбинаций трансформаций приводит к одинаковому результату, здесь можно сэкономить) с остановкой при достижении четырех трансформаций на задачу. Cамо решение и его описание.



Что в итоге?


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

В ноябре 2019 мне посчастливилось посетить ICCV2019 в высокотехнологичном Сеуле, где каждый второй доклад был посвящен задаче ZSL. Были ожидания, что в соревновании ARC достаточно применить одну из раскрученных в научном сообществе техник. Может, я был невнимателен, но, к своему разочарованию, не увидел среди решений участников такого подхода.

Так как уже в процессе соревнований участники делятся идеями и наработками, участие в челлендже казалось отличным способом узнать, какие подходы сейчас на переднем крае в области создания сложных моделей с минимальной обучающей выборкой или без таковой: zero-shot learning (ZSL), one-shot learning, few-shot learning, prototype learning и domain shift. Конечно, перечисленные проблемы подразумевают изменение доменной области, а не самой задачи классификация остается классификацией. Но это самое проработанное направление в части обобщения моделей.

Сами мы решили попробовать GAN-архитектуру поверх feature extractor, которая у нас так и не зашла. Однако, примерно за три-четыре недели до конца соревнования стало понятно, что выигрывают решения на правилах. Обсудив внутри, мы пришли к выводу что, потратив кучу времени на написание, мы вряд ли повысим свои компетенции в современных методах, поэтому направили энергию на другие задачи.

В тысячный раз подтвердился тезис о прикладном характере машинного обучения это набор инструментов, который надо уметь применять четко понимая задачу. В то же время бессмысленно применять даже самые крутые инструменты к непонятной задаче. Можно провести аналогию со станком, ЧПУ и 3D-принтером: несмотря на то, что область применения на каждом этапе растет, пока даже близко нет волшебной палочки, способной создать абсолютно любой предмет.

Чтобы обучить машину, мало придумать ей абстрактный язык (DSL или набор трансформаций), придумать функцию потерь и показать пару примеров. Челлендж прошёл, но осталось разочарование: то, что маркетологи до сих пор продают как AI, на поверку оказывается набором инженерных хитростей. Флёр волшебства окончательно растаял.
Подробнее..

Memory Management ARC vs MRC в iOS

05.01.2021 16:09:52 | Автор: admin

Как работает Automatic Reference Counter в iOS? На самом деле эту тему мне было легче понять после того, как я познакомился с Manual Reference Counter. Это очень простая статья, которая помогает базово понять как работает управление памятью в iOS.

Для управления памятью в iOS есть несколько инструментов:

MRC - Manual Reference Counter

MRC - это ручное управление ссылками через код. В самом начале и в доисторические времена разработчики сами управляли подсчетом ссылок через команды. Было это, мягко говоря, жестко:

  • alloc - создание объекта (создаем ссылку)

  • retain - обращение к нему (+1 к ссылке)

  • release - уменьшаем счетчик ссылок (-1)

  • dealloc - если счетчик ссылок равен 0 = выгрузка из памяти

По сути, вы выделяете объект, сохраняете его в какой-то момент, а затем отправляете один выпуск для каждого отправленного вами выделения / сохранения. Метод dealloc вызывается для объекта, когда он удаляется из памяти.

Проблемы:

  • Нужно постоянно считать retain, release

  • крэш при обращении из выгруженного из памяти

  • забыли поставить релиз - утечка памяти

ARC - Automatic reference counter

После того, как умные программисты поняли, что можно придумать механизм, который сам за программиста считает ссылки - мир в iOS поменял. Больше не нужно было считать ссылки и следить за ними. За нас это делает ARC автоматически. Он сам понимает куда и зачем что вставлять и когда удалять. Стоит понять, ЧТО ARC РАБОТАЕТ ПРИ КОМПИЛЯЦИИ, А ПОДСЧЕТ ССЛОК В РАНТАЙМЕ.

Что изменилось?

  • (release/retain - нельзя вызывать) dealloc - работает частично

  • properties change - weak/strong

У property появились модификаторы:

  • strong - аналог retain

  • weak - аналог assign. в проперти при освобождении ставится нил и не крэшит приложение при обращении

Но есть и минусы, с которыми не справляется ARC:

  • Retain cycle - это когда объем выделенного пространства в памяти не может быть освобожден из-за циклов сохранения. Поскольку Swift использует автоматический подсчет ссылок (ARC), цикл сохранения происходит, когда два или более объекта содержат сильные ссылки друг на друга. В результате эти объекты сохраняют друг друга в памяти, потому что их счетчик сохранения никогда не уменьшится до 0, что предотвратит вызов функции deinit и освобождение памяти

Решение банальное - сделать одну из ссылок слабой.

Эта статья является больше базовой и ознакомительной с основами memory management в iOS, для легкого концептуального понимания.

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru