Команда WinterMUTE @ ICFPContest 2018 2018-07-24

20-23 июля 2018 года проходил очередной ICFPContest, где наша команда WinterMUTE снова принимала участие.

Disclaimer

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

Задача

Итак, на входе алгоритма дискретная 3D модель (матрица) размером до 250х250х250 вокселей (см. анимацию), представленная в виде вектора битов. Необходимо предоставить трассу из набора команд для управления наноботами, которые построят указанную модель.

Наноботы могут:

Симуляция системы осуществляется в дискретном времени. Всё начинается и заканчивается единственным наноботом, который стоит в начале координат. На каждом такте симуляции каждый нанобот выполняет ровно одну команду.

В lightning round (заканчивается через одни сутки с момента старта соревнований) Nanobot Matter Manipulation System поддерживала до 20 наноботов и требовалось строить модели, начиная с пустого пространства.

В full round Deluxe Nanobot Matter Manipulation System позволяла использовать до 40 наноботов и поддерживала операции групповой заливки/уничтожения вокселей. При этом появились два новых типа заданий:

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

High режим гораздо дороже с точки зрения энергии и между режимами можно переключаться (если выполняется условие groundedness).

Разумеется, на каждом такте работы системы проверяется отсутствие коллизий при перемещении наноботов (между собой и со стенами).

Участникам для каждой проблемы предоставляется пример решения, где один нанобот "змейкой" строит модель, находясь всё время в режиме High.

Модели и трассы (команды) упакованы в компактные битовые представления. Организаторы выдали client-side визуализацию моделей и симулятор трасс на WebGL.

Цель

Для каждой проблемы (сборка/разборка/пересборка модели) предложить наилучшее решение (трассу из набора команд для наноботов) с точки зрения потраченной энергии.

Команда

Мы собрались более-менее устоявшейся командой в офисе Одноклассников:

Решение

Ещё перед началом соревнований мы спонтанно приняли решение писать на связке Java и Python. В итоговом репе только Java и JavaScript.

Day 0

Contest начался 20 июля в 19:00 по Мск, поэтому мы посвятили несколько часов разбору задания, генерации идей по его решению и рассмотрению извращённых примеров 2D моделей на доске, а затем разошлись по домам думать.

Day 1

Собрались пораньше и начали писать код. Олег заинтересовался JS кодом симулятора/визуализатора от организаторов и занялся его изучением и деобфускацией (чем и продолжил заниматься оставшиеся дни). Остальные члены команды разбились по парам и отправились кодить обязательные части: наше внутреннее представление состояния системы наноботов в матрице, координаты, десериализаторы входных моделей и сериализаторы выходных трасс. При этом всё обильно покрывали тестами.

Решили пойти по пути создания детерминированных стратегий решения задач и реализовать следующую архитектуру (сверху вниз):

К концу дня Саша, Дима и Вадим дописали основную обвязку и реализовали SwitchVM. Тем временем Олег сократил код JS с 30К до 14К строк. Антон с Алексеем занимался кодом "парковки" в начале координат после построения модели, а затем начал пилить простейшую стратегию, которая собирает модель одним наноботом, но более эффективно, чем дефолтные трассы от организаторов.

Тем временем, lightning round закончился, мы ничего не отправили. Организаторы опубликовали условия Full Round, где были добавлены групповые команды заливки и уничтожения вокселей (к слову, Олег обнаружил их в коде JS загодя), увеличено максимальное количество наноботов, а также опубликованы новые проблемы сборки, разборки и пересборки моделей.

Day 2

Собрались пораньше, посокрушались, что не успели ничего доделать до окончания lightning round, и продолжили кодить. Нас осталось четверо.

Первым делом Дима поддержал групповые GFill/GVoid и переключился на создание стратегии послойной разборки моделей сверху-вниз. Вадим занялся автоматизацией прогона и отправки решений, а затем начал разрабатывать утильные примитивы горизонтальных плоскостей и проверки groundness с помощью BFS. Олег продолжил разбирать JS организаторов на части, чтобы переиспользовать в качестве валидатора и оценщика энергии. Антон существенно развил стратегию сборки моделей MothershipStrategy, использующую рой наноботов, и доотлаживал её. MothershipStrategy распределяла строки каждой горизонтальной плоскости между ботами, которые строили свою часть снизу вверх.

Мы начали сабмитить наши решения для набора задач по сборке моделей, используя MothershipStrategy, хотя и не поднимались выше 37 места в таблице. Нужно было научиться решать оставшиеся задачи (благодаря будущей DisassemblyStrategy), а также улучшать существующие стратегии.

Тем не менее, к концу дня драйв нарастал, поскольку всё это уже работало.

Day 3

Олег запустил перепиленый JS-симулятор организаторов под Nashorn, научился подавать ему входные данные извне, а также перехватывать callbackи ошибок и успеха, и начал интегрировать его в наш CI. Дима продолжил возводить DisassemblyStrategy, а Антон -- улучшать MothershipStrategy. Вадим вылавливал баги, добавил поддержку решения оставшихся проблем, запилил простейшую статистику и занялся изучением моделей из новых проблем.

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

Итоги

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

Java

IMHO, Java не подходит для решения подобных задач в сжатые сроки -- слишком много boilerplate кода и невыразительная система типов. Не хватало функций высших порядков, data/case classes, pattern matching и т.д. (чего стоят постоянные преобразования (short) 1 и отладка перепутанных координат). Впрочем, код на Java предельно "тупой", что позволяло быстро разбираться в чужом коде. При этом написание нетривиальных стратегий вызывало боль и страдание.

В следующий раз мы предварительно договорились попробовать язык Rust.

Scoring

С одной стороны, фиксированный набор готовых вариантов проблем от организаторов упрощал разработку и CI. Client-side визуализаторы и симуляторы устраняли необходимость дёргать какой-либо API. С другой стороны, это теоретически позволяло отправить для каждой проблемы какое-то кастомное решение. Возможно, было бы "честнее", если бы окончательная оценка решений осуществлялась запуском бинарников участников на отдельном оценивающем наборе задач (как когда-то в ICFPC про Pacman).

Решение

В этом раз (как и в предыдущие) мы применили классический инженерный подход к решению задачи. Было бы интересно взглянуть на проблему с принципиально иной точки зрения, например, попытаться свести задачу к известной, попробовать SAT-солверы, генетические/рандомизированные подходы или что-нибудь ещё.

Команда

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

В целом, это было чертовски круто! Трудно объяснить, почему круто. Это можно только почувствовать на собственном примере. Лично у меня после каждого ICFPC возникает ощущение, что нет ничего невозможного и за 3 дня можно подобраться к какому-никакому решению любой задачи.

Огромное спасибо организаторам за проделанную работу! Мне трудно представить, сколько усилий было потрачено на разработку, отладку и тестирование всей этой машинерии.

В корне проекта лежит README для организаторов.

Если есть, что сказать, добро пожаловать в комменты!

Retweet

Comments

Actor Model, Futures and Promises, Reactive Streams 2018-05-23

В рамках магистерского курса "Параллельные вычисления" на кафедре КСПТ прочитал лекцию "Actor Model" (скачать слайды):

Retweet

Comments

NoSQL 03. Cassandra. Haystack. 2018-05-16

Третья лекция раздела NoSQL курса "Базы данных" в Технополисе.

Cassandra (слайды, видео):

Haystack (слайды, видео):

Retweet

Comments

NoSQL 02. CAP. Raft. 2018-04-25

Вторая лекция раздела NoSQL курса "Базы данных" в Технополисе (скачать слайды, видео 1, видео 2):

Индивидуальный курсовой проект лежит на GitHub.

Retweet

Comments

Технополис.NoSQL 01. Введение. Hash and Cache. 2018-04-04

Первая лекция раздела NoSQL курса "Базы данных" в Технополисе (скачать слайды):

Индивидуальный курсовой проект лежит на GitHub.

Retweet

Comments

Технополис. Курс HighLoad. 2018-02-01

В рамках курса "Проектирование высоконагруженных систем" для студентов 3-го семестра образовательного проекта Технополис прочитал лекцию "Введение" (скачать слайды):

Видео и слайды всех лекций курса собраны в блоге Одноклассников на Хабрахабр.

Мы ищем разработчиков и стажёров в команду.

Retweet

Comments

Actor Model, Futures and Promises, Reactive Streams 2017-05-25

В рамках магистерского курса "Параллельные вычисления" на кафедре КСПТ прочитал лекцию "Actor Model" (скачать слайды):

Retweet

Comments

NoSQL 03. Cassandra. Haystack. 2017-05-24

Третья лекция раздела NoSQL курса "Базы данных" в Технополисе.

Cassandra и Haystack:

Retweet

Comments

NoSQL 02. CAP. Raft. 2017-05-10

Вторая лекция раздела NoSQL курса "Базы данных" в Технополисе (скачать слайды):

Retweet

Comments

NoSQL 01. Введение. Hash and Cache. 2017-04-26

Первая лекция раздела NoSQL курса "Базы данных" в Технополисе (скачать слайды):

Retweet

Comments

The Art of JVM Profiling 2017-04-07

The Art of JVM Profiling talk by Andrei Pangin and me has been accepted by JPoint 2017 conference (slides).

No Java profiler is perfectly accurate, since JDK does not provide sufficient means to find where CPU time is exactly spent. Even "honest" profilers based on private HotSpot APIs will not tell the whole truth. Hardware counters and kernel functions could probably help, but unfortunately they are not aware of Java code at all. We will discuss several approaches to Java profiling: JVM TI, AsyncGetCallTrace, perf_events and Flame Graphs. Their principles and limitations will be considered. We will find a way to combine the advantages of all approaches together. Finally, we will see how Odnoklassniki performs full-stack profiling in production: from Java code down to Linux kernel.

Retweet

Comments

Streaming Matching of Events 2017-02-05

Dmitry Schitinin gave talk about Streaming matching of events at CEE-SEC(R) 2016 conference.

Our paper is published by ACM in the proceedings of the conference (backup PDF).

In Russian:

Retweet

Comments

YoctoDB @ Yandex.Classifieds 2016-08-31

YoctoDB @ Yandex.Classifieds talk has been accepted by CEE-SEC(R) 2016 conference (slides).

The paper is published by ACM in the proceedings of the conference (backup PDF).

In English:

In Russian:

Retweet

Comments

Actor Model, Futures and Promises, Reactive Streams 2016-05-11

В рамках магистерского курса "Параллельные вычисления" на кафедре КСПТ прочитал лекцию "Actor Model" (скачать слайды):

В отличие от лекции прошлого года расширены примеры систем на Actor Model и добавлен раздел про Reactive Streams.

Retweet

Comments

Unique Action Counting 2015-08-30

I will describe our approach to unique user action counting using Cassandra. An action is a click, a page view, a phone call or anything similar. Each action connects an object and a user.

A counter for a specific action provides the following methods:

Sets of users and objects are effectively infinite, but they increase gradually -- new ones appear and former ones don't appear any more. We don't want to run out of space because of storing connections forever, so we need some expiration policy. More about it later.

Data model

Cassandra schema looks like this:

CREATE TABLE IF NOT EXISTS $TABLE(
  id varchar,
  t varchar,
  PRIMARY KEY (id, t))
WITH
  compaction = {
    'class': 'LeveledCompactionStrategy'
  } AND
  default_time_to_live = $TTL

id is an object id. t is a token identifying user.

As it follows from the schema:

Requests

We have only two kinds of requests.

A request connecting the object and the token:

INSERT INTO $TABLE(id, t) VALUES (:id, :t)

A request counting unique tokens associated with the object:

SELECT COUNT(1) as counter FROM $TABLE WHERE id = :id LIMIT $LIMIT

We use explicit counter limit to bound the response time in case of extremely (or artificially) popular object.

Both requests are executed with LOCAL_ONE consistency level.

DAO

The DAO uses requests considered before and is based on the official Cassandra Java driver.

Cassandra driver is configured the following way:

Cluster.builder()
  .addContactPoints(clusterNodes: _*)
  .withCompression(ProtocolOptions.Compression.LZ4)
  .withLoadBalancingPolicy(
    new TokenAwarePolicy(
      new DCAwareRoundRobinPolicy(
        localDataCenter,
        remoteNodes)))

The implementation uses Session.executeAsync() and is fully asynchronous.

HTTP API

HTTP API is quite simple and delegates to the DAO. Let's HTTP requests.

Get count of tokens connected with object object_id:

$ curl http://myhost/api/v1/counter/object_id
42

Connect token token to object object_id and return count of tokens:

$ curl -X PUT -d token http://myhost/api/v1/counter/object_id
43

When implementing HTTP API we used Spray.

Benchmarks

We have a two node Cassandra cluster. Each node is a 16 core (with HT) 64 GB SSD machine.

Cassandra keyspace configuration is the following:

replication = {'class': 'NetworkTopologyStrategy', 'DC1': '2'} AND durable_writes = true

HTTP API runs on a 32 core machine.

Test load

The test load depends on two parameters:

Each test request can be expressed like this:

$ curl -X PUT -d token http://myhost/api/v1/counter/object_id

Where token is a random long value and object_id is an int value between 0 and total number of objects chosen using Gaussian distribution to model hot (popular) objects.

100 objects and 10M tokens

Cassandra nodes' CPUs get fully saturated at 700 rps load. The stable load area:

700 rps

Some numbers:

1K objects and 10M tokens

Cassandra nodes' CPUs get fully saturated at 2.5 Krps load. The stable load area:

2.5 Krps

Some numbers:

Conclusion

We considered unique action counters on top of Cassandra storage. This implementation (with some minor changes and caching added) is used in all the user facing counters in Yandex.Auto, Yandex.Realty and Yandex.Rabota.

Next time we might consider:

Retweet

Comments

Croudfunding на подарок 2015-03-16

Если решили, но не придумали, что мне подарить, то знайте, что я коплю на наушники с активным шумоподавлением для ментальной изоляции в условиях openspace-офиса:

Retweet

Comments

Actor Model 2014-11-21

В рамках магистерского курса "Параллельные вычисления" на кафедре КСПТ прочитал лекцию "Actor Model" (скачать слайды):

Темы "Dataflow Concurrency" и "Software Transactional Memory" не рассматривались, поскольку поддержка в Akka приостановлена. См. лекции прошлого года.

Retweet

Comments

Документация и бенчмарки YoctoDB 2014-08-24

Наконец, дошли руки и смог написать более подробную документацию по YoctoDB:

Retweet

Comments

YoctoDB 2014-07-04

Выложили в OpenSource встраиваемую СУБД YoctoDB, разработанную в Яндекс.

Ждите подробных постов про мотивацию и внутреннее устройство.

Retweet

Comments

Фреймворк Akka и его использование в Яндексе 2014-04-18

Выступил на JPoint 2014 с докладом "Фреймворк Akka и его использование в Яндексе" (скачать слайды):

Retweet

Comments

Principles of Reactive Programming 2014-01-21

Получил 100% в курсе Principles of Reactive Programming на Coursera. Рекомендую.

Retweet

Comments

Базы данных. STM 2013-12-09

Лекция "Software Transactional Memory" (скачать слайды):

Посмотреть видео на сайте Лекториума.

См. множество ссылок в презентации.

Retweet

Comments

Базы данных. Задание FR11 2013-12-09

FR11 сгорает 2013-12-09.

Retweet

Comments

Базы данных. Задание FR10 2013-12-02

FR10 сгорает 2013-12-02.

Retweet

Comments

Базы данных. Multidimensional indexing 2013-12-02

Гостевая лекция "Multidimensional indexing" (скачать слайды) Антона Волохова в курсе "Базы данных" в Computer Science Center.

Посмотреть видео на сайте Лекториума.

Retweet

Comments

Actor Model 2013-11-29

В рамках магистерского курса "Параллельные вычисления" на кафедре КСПТ прочитал лекцию "Actor Model" (скачать слайды):

Retweet

Comments

Базы данных. Graph DB 2013-11-25

Гостевая лекция "Graph DB" (смотреть слайды) Ильи Тетерина в курсе "Базы данных" в Computer Science Center.

Посмотреть видео на сайте Лекториума.

Retweet

Comments

Базы данных. Задание FR9 2013-11-25

FR9 сгорает 2013-11-25.

Retweet

Comments

Базы данных. Lucene 2013-11-18

Гостевая лекция "Lucene" (скачать слайды) Германа Андреева в курсе "Базы данных" в Computer Science Center:

Посмотреть видео на сайте Лекториума.

Retweet

Comments

Базы данных. Задание FR8 2013-11-18

FR8 сгорает 2013-11-18.

Retweet

Comments

Базы данных. ZooKeeper 2013-11-11

Гостевая лекция "ZooKeeper" (скачать слайды) Дмитрия Щитинина в курсе "Базы данных" в Computer Science Center:

Посмотреть видео на сайте Лекториума.

Retweet

Comments

Базы данных. Задание FR7 2013-11-11

FR7 сгорает 2013-11-11.

Retweet

Comments

Базы данных. Задание FR6 2013-11-04

FR6 сгорает 2013-11-04.

Зачтено

Retweet

Comments

Базы данных. Задание FR4 2013-10-28

Минимальная функциональность:

FR4 сгорает 2013-10-28.

Retweet

Comments

Базы данных. HBase 2013-10-28

Гостевая лекция "HBase" (скачать слайды) Леонида Налчаджи в курсе "Базы данных" в Computer Science Center:

Посмотреть видео на сайте Лекториума.

Retweet

Comments

Базы данных. Задание FR5 2013-10-28

FR5 сгорает 2013-10-28.

Зачтено

Retweet

Comments

Базы данных. HDFS 2013-10-21

Гостевая лекция "HDFS" (скачать слайды) Леонида Налчаджи в курсе "Базы данных" в Computer Science Center:

Посмотреть видео на сайте Лекториума.

Retweet

Comments

Базы данных. Задание FR3 2013-10-21

Минимальная функциональность:

FR3 сгорает 2013-10-21.

Зачтено

Retweet

Comments

Базы данных. Задание FR1 2013-10-14

Минимальная функциональность:

FR1 обязателен и не приносит баллов всем, кроме выполнивших в срок FR0.

Зачтено

Retweet

Comments

Базы данных. Задание FR2 2013-10-14

Минимальная функциональность:

FR2 сгорает 2013-10-14.

Зачтено

Retweet

Comments

Базы данных. Haystack 2013-10-14

Лекция "Haystack" (скачать слайды) про хранение фоток в Facebook по статье "Finding a Needle in Haystack: Facebook's Photo Storage" (скачать статью):

Посмотреть видео на сайте Лекториума.

Retweet

Comments

Базы данных. MongoDB 2013-10-07

Гостевая лекция "MongoDB is a web-scale" (скачать слайды) Антона Волохова в курсе "Базы данных" в Computer Science Center:

Посмотреть видео на сайте Лекториума.

См. множество ссылок в презентации.

Retweet

Comments

Базы данных. Cassandra 2013-09-30

Лекция "Cassandra" (скачать слайды):

Посмотреть видео на сайте Лекториума.

См. множество ссылок в презентации.

Retweet

Comments

Базы данных. Задание FR0 2013-09-30

Минимальная функциональность:

Зачтено

Retweet

Comments

Базы данных. Введение, Hash and Cache, CAP 2013-09-16

Прочитал 3 лекции на первом занятии курса "Базы данных" в Computer Science Center.

Введение

Скачать слайды.

Посмотреть видео на сайте Лекториума.

Hash and Cache

Скачать слайды.

Посмотреть видео на сайте Лекториума.

Consistency, Availability and Partition Tolerance

Скачать слайды.

Посмотреть видео на сайте Лекториума.

Retweet

Comments

Базы данных. Курсовой проект 2013-09-16

Для получения зачёта по курсу "Базы данных" необходимо выполнить курсовую работу. В рамках курсовой работы каждая команда (1-3 человека) должна разработать работоспособное Key-Value хранилище данных.

Требования

В первую очередь необходимо создать проект на BitBucket (DVCS Hg) или GitHub (DVCS Git). Если проект открытый, то нужно прислать мне на почту ссылку на проект, если проект закрытый -- дать пользователю incubos права администратора.

Язык программирования -- только Scala или Java.

Обязательны модульные тесты -- ScalaTest или JUnit.

Обязательна система автоматической сборки -- SBT или Maven.

Обязательна базовая документация: README (краткое описание устройства проекта) и INSTALL (краткое руководство по сборке и запуску проекта, а также его зависимостям).

Система оценивания

В течение курса будет выдано не менее 6 feature requests (FR). Для каждого FR установлен жёсткий срок, но не менее 2 недель. За каждый FR присуждается 0, 1 или 2 балла (2 балла за особое мастерство и креативность).

Кроме того, существует обязательный FR0. Для тех, кто не успел во время выполнить FR0, FR0 замещается обязательным FR1, а баллы за его выполнение не присуждаются.

Для получения зачёта в конце курса необходимо выполнить обязательные FR, заработать не менее 4 баллов на других FR и написать отчёт.

Проверка FR

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

Обратная связь по результатам проверки FR осуществляется в виде issues. Наличие незакрытых issues, относящихся к соответствующему FR, препятствует зачёту по FR.

Отчёт

Отчёт должен содержать 2-10 страниц, включая картинки и не включая титульный лист.

Retweet

Comments

Лекции по "Базам данных" в Computer Science Center 2013-09-04

В осеннем семестре 2013 года читаю курс "Базы данных" в Computer Science Center. Все материалы будут выкладываться в этот блог.

Мой курс во многом основывается на курсе "Базы данных" 2012 года Ильи Тетерина. Во второй половине курса планирую приглашать моих коллег из Яндекса прочитать по одной лекции про конкретные хранилища данных, экспертами в которых они являются.

Retweet

Comments

Дедуктивная верификация 2013-04-30

В рамках магистерского курса "Методы анализа и обеспечения качества ПО" на кафедре КСПТ прочитал лекцию "Дедуктивная верификация".

Retweet

Comments

Site launched 2013-04-22

This website uses:

Retweet

Comments

Copyright © 2013-2018 Vadim TSesko