April 26th, 2011

glider

Интересное за полгода

Всем привет! Последний раз мы виделись за обсуждением прогресса по Конфлаксу, а это весьма давно. Пришло время рассказать о самых интересных штуках, произошедших со мной за последнее время. Кое-какие вещи я писал в стол и сейчас их запостил в режиме "Date out of order" (кому интересно - пролистайте бложек вниз), а об остальном коротко расскажу прямо здесь.

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

Очень понравилось читать художественную литературу. Как я недавно упоминал в каментах, киндл не оправдал возложенного на него доверия (не помещается в руку, фиг достанешь в транспорте, нет подсветки, нет дропбокса), и вместо него я для чтения юзаю телефон (на удивление, 3.7" lcd экран не напрягает глаза даже при длительном чтении). Впрочем, я отвлекся как в том анекдоте про "какой у тебя компьютер". Наибольшее впечатление на меня произвела "Анна Каренина", а также последующее прочтение рецензии Натальи Воронцовой-Юрьевой (внимание! там очень много букав). Могу сказать, что чтение и обдумывание сабжевой книжки позволили мне свести воедино многие разрозненные куски знаний и опыта касательно отношений и семьи. С небольшим отрывом второе место занял "Шантарам". Не знаю, насколько эта книга биографична, но описанный взгляд на жизнь - это что-то новенькое. Особенно запомнилась сцена первой посадки главного героя в переполненный поезд в Бомбее вместе с последующей поездкой в этом поезде. Также хотел бы еще упомянуть Довлатова - когда было хреново, для меня было лучшим лекарством сидеть и читать его часами.

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

Также, я проникся идеей курсов - регулярного и детерминированного выделения небольших кусочков времени под какое-то полезное дело (например, по 2 часа пн/ср/пт). Родилась эта идея в результате посещения месячного курса подготовки к TOEFL (если кому интересно, я отпостился о впечатлениях сдачи тоефла и могу в каментах рассказать о том, как готовился - в целом, все просто и без шизы, но нужна системная подготовка). Смысл очень простой - даже если все неделя-две скатываются в полный трэш вследствие депрессняка, все равно в сухом остатке будет что-то полезное, ибо за 2 часа не успеваешь устать + маленькие кусочки новой инфы хорошо загружают подсознание. Сейчас разбираюсь с лямбда-исчислением по лекциям Дениса Москвина (deni_ok) - прогнал всего лишь четыре лекции, но узнал много концептуально нового + теперь неслабо тянет программировать на Хаскелле =)

Наконец, параллельно всему этому я искал точку приложения творческих порывов. Спасибо всем тем, кто дочитал досюда - продолжение будет в следующем посте.
glider

Телефонное собеседование с гуглом

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

В итоге поболтали в начале марта. она немножко повпаривала про то, что такое гугл и про то, что подготовить к собеседованию (по большей части это был рестейт известного блогпоста: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html), после чего по добазарились о телефонном интервью.

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

***

Чел позвонил минута в минуту, в 12:00. Минут 10-15 мы болтали о моем прошлом экспириенсе (это, кстати, большая проблема - связно и кратко рассказать о том, чем ты занимался. если бы я заранее не готовился и не получил неприятный опыт на одном из недавних интервью, то точно бы залажал), потом началось самое интересное - задачки на алгоритмы.

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

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

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

Четвертая задача заключалась в кодировании одной из операций из третьей задачи. Делать это надо было в режиме реального времени в google docs. Началось все хорошо - я набросал структуру данных, проверил в алгоритме краевые условия, упомянул про defensive программирование, различные стратегии работы с ошибками и все дела. И потом неправильно написал алгоритм. Нет, главную идею я выразил правильно, но ошибся в мелочи, причем смог найти ошибку только с третьего раза. Хорошо, что все-таки пофиксил баг, зато потом додумался, как упростить алгоритм, уменьшив количество строчек раза в 1.5-2. Надеюсь, хоть это произвело положительное впечатление.

На этом оказалось, что мы разговариваем уже больше 55 минут, поэтому чел стал закругляться (по регламенту полагается около 45 минут на собеседование). Последовало классическое DYHAQFM, на что я классически ответил, что вопросов нет, но зато собеседование было очень интересным. На этом и разошлись.

***

Выводы:

1) Все было совсем просто, только надо было подготовиться. Так как во время двух недель подготовки я неслабо времени посвятил сортировкам и деревьям, мне было относительно просто. Впрочем, по факту я подготовил и кучу ненужных вещей, например, изучал новинки C# (додумался же сказать Дженни, что я эксперт сишарпа =)), неслабо проштудировал графы и строки (было риальне интересно!), разбирался с map/reduce, вдавался в детали работы континюэйшнов, читал про техники сборки мусора и JIT-компиляции. Наверное, для телефонного интервью это был оверкилл, но зато я поимел кучу фана. Надеюсь, меня пригласят на on-site интервью, где я смогу про все это поговорить. upd. Пригласили, не поговорили (детали ниже).

2) Всю неделю я писал маленькие алгоритмики в LINQPad, т.е. без IDE, без решарпера, без подсветки и без интеллисенса. Это сильно помогло кодировать в гуглодоксах, но, как видите, не спасло от затупов (ну что делать, иногда на меня как нападет затуп, так хоть иди вешайся на 10-15 минут, пока он пройдет - блин, я даже не могу оправдаться, что волновался, ибо нихрена я не волновался). В любом случае, кодирование в блокноте оказалось крайне полезным.

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

upd. Так получилось, что, несмотря на фейл с кодированием задачки, я прошел телефонное интервью, и Дженни прислала приглашение поучаствовать в onsite интервью. На эту тему есть пост в трех частях: первая, вторая и третья.
glider

PoLite: polyhedral optimizations for Scala

A couple of hours ago I was accepted as a participant of this year's Google Summer of Code! My project involves implementing a polyhedral optimizer for parallel programming in Scala. If you fancy, you can take a look at the full text of the proposal. Below I'll cover the most essential ideas.

One of the important initiatives in Scala ecosystem is the creation of a commodity parallel programming platform. This initiative relies on language virtualization, a new principle that enables the construction of parallel domain-specific languages that are embedded in a common host language. The best introduction to language virtualization is Tiark Rompf's paper that describes the original idea. You can also take a look at slides for one of the lectures at Stanford for a practical point of view towards language virtualization. To keep it short, a special build of Scala compiler lets the programmer overload all constructs of the language: operators, method bindings and even syntactic constructs such as conditionals and loops. By leveraging this machinery, one can develop an embedded DSL and an accompanying optimizing compiler completely at library level.

Delite is a joint effort of researchers from EPFL and Stanford towards practical implementation of ideas described above. Most of the infrastructure is already in place (it's actually possible to clone the repo and play with some tests - see instructions on the main page of the project), and now it's about time to implement optimizations.

Polyhedral model is a theory of optimizing for parallelism and locality. Unlike its predecessors, it is capable of analyzing arbitrary superpositions of loop transformations (tiling, unrolling, fusion). This allows for deeper insight into optimization possibilities and provides noticeable performance improvements. I have always been fascinated by this framework, and even blogged about it back then (warning: linked post is in Russian). The best introduction to the polyhedral model is the second section of Pouchet's thesis (if you've got a spare hour, take a look - you won't regret it). To put it in a nutshell, polyhedral framework operates on algebraic representation of programs and their transformations. Its calculus features simple composition laws and enables reasoning about data dependences, code transformations and their validity.

The aim of the project is to implement polyhedral optimizations for Delite. By following the ideas of the researchers from Ohio University and adapting them for (quite extravagant) intermediate representation of Delite, I'm going to implement optimizers for CPU and GPU hardware targets. Subsequent posts will feature mentioned stuff in more detail - stay tuned for updates.
glider

Emacs + ENSIME, part 1

My GSoC 2011 project will involve coding in Scala. Since I've not yet got accustomed to any Scala IDE, I think it's a good chance for me to try out Emacs. As of such, I'd appreciate any feedback on developing with ENSIME. What are the pain points? Any setup tips? Any good screencasts? upd. As of now, ensime_2.8.1-0.5.0 provides the most essential functionality that can be expected from an IDE (integration with tools, error highlighting, navigation facilities), though I've found refactoring to be mostly broken. See a field report on that.

Moreover, it's my very first experience of using Emacs, that's why I've got several Emacs-related questions. How do I reproduce the following configuration of widgets: tree view for browsing file system (left) + tabs for quick access to recently opened files (top) + the editor itself (center) + pop-up compilation log and scala interactive (down)? upd. The tree view can be implemented with ECB, tabs can be replaced by ido, integration with tools is provided by ENSIME.