Заклиная техническое интервью
Перевод (возможно лучшей) статьи Aphyr.
Давным-давно, на Шпицбергене, когда ты была юной ведьмочкой всего сорока трех лет, мама взяла в свои ладони твои еще не покрытые шрамами руки, и сказала:
Видрун, зачатая от морских ветров в верхушках елей,
Видрун, зелень моих ветвей, радость и ноша моих дней,
Видрун, всех вдохновенней и умней, да станет мудрость нашего клана твоей:Никогда не читай Hacker News
Но Hacker News читали о тебе, и по их таинственным гнёздам, наполненным непременным хихиканьем, поползли слухи. А потому молодой человек, предлагающий тебе дары шведского стола с микро-кухни уже выглядит слегка сомневающимся. Он быстро увлекает тебя в стеклянную коробочку конференц-зала. Тот почему-то вызывает клаустрофобию, несмотря на полную прозрачность. Ты мысленно отмечаешь впредь избегать этой комнаты, но уверена, что в приглашении тебя именно сюда не было ничего личного.
«Итак, меня зовут Тим, и я буду вашим первым собеседующим…» — изо всех сил старается казаться радостным Тим. Его уши слегка торчат, а из-за темно-коричневой кофты и кремовой футболки, он, тревожно наклонившись над столом, несколько напоминает куницу. Тебе нравятся куницы, а потому нравится и Тим.
«Прежде чем мы начнем, могу я… ответить на ваши вопросы о компании?»
Тебе хотелось бы спросить, где Тим станет прятать от других куниц свою заначку из орехов и птичьих яиц —, но взамен ты лишь хихикаешь про себя, прислоняешь похожий на деревце стан к стене и удобно устраиваешься на полу. Тим выгибается, чтобы яснее видеть куда же ты делась. «Определенно», думаешь ты про себя.
«Так, эм… Не могли бы вы, скажем, рассказать немого о себе?»
Он не читал твое резюме. Никто этого не может.
«Зимой, над закованными льдами фьордами», начинаешь ты, «стоит скала, как пепельной шапкой покрытая призраками ледников--»
«Знаете!». Он тебя прерывает. Это прекрасная история, но может удастся рассказать ее позже. «Как насчет немножко попрограммировать вместе? Просто несколько основных упражнений, чтобы я понял как вы думаете?!»
«Милое предложение, Тим».
«Окей, отлично». Тим вроде уверен в том, что удалось вернулся в колею интервью. «Давайте откроем редактор. Эм… не хотите ли присесть?»
«Присаживайся!» — хлопаешь ты по полу рядом с собой, «Так гораздо безопасней». Тим с недоверием пялится на скобки просыпавшейся соли, трясет головой, но осторожно присаживается рядом.
Тим пересказывает древнюю загадку, он не знает ее происхождения, а потому путает слова. Несколько путешественников заблудились в лесу, на извилистой горной тропке, и беспокоятся о том, что они, возможно, ходят кругами. Им нужно узнать — ведет ли путь к свободе? Или заставит их вечно бродить по лесу?
Как гласит традиция, группа должна разделиться: самый быстроногий мчится вперед, а остальные идут не спеша. Если бегун их догоняет, то тропинка идет петлей.
«Начнем с linked list?» — улыбаешься ты уверяюще.
«Да», говорит Тим, «но… эм… просто обычный linked list, пожалуйста. Я в курсе, что ты, ну, занимаешься функциональным программированием, но у нас тут более прагматичная контора. Создаем настоящий софт. Нам нужно что-нибудь попрактичней».
«Да, конечно», соглашаешься ты, «Практичное. Поняла». Один из твоих паучков — тебе не видно который именно — осторожно пробирается по кофте Тима, и ты собираешь паучка в ладошку, прежде чем начать.
(ns cycle-detector.core
(:require [clojure.java.io :as io])
(:import (java.io DataOutputStream
ByteArrayOutputStream)))«Нам, э, не нужен тут IO. Просто список в памяти».
Вежливо соглашаешься, но ничего не удаляешь. Никогда не извиняйся за то, кто ты есть.
; A simple mutable linked list
(deftype MutableLinkedList [value next]
clojure.lang.Seqable
(seq [_]
(lazy-seq (cons value (seq @next)))))
(defn node [value]
(MutableLinkedList. value (atom nil)))
(defn link! [node next]
(reset! (.next node) next)
next)«Это… немного не то, чего я ожидал» — говорит Тим. «Нет, нет, хорошо! Прямолинейно и просто. Я просто, ну знаете, в интернете говорят что вы…». Он стихает, и извиняющеся глядит на тебя.
Ты обезоруживаюеще улыбаешься и вытряхиваешь на свободу кисти рук из своих шерстяных рукавов. Затем хлопаешь ладонями, твердо ставишь их поверх диска и открываешь портал в Нижний мир.
(gen-class
:name cycle_detector.core.ArbClassLoader
:extends ClassLoader
:state state
:init class-loader-init
:constructors {[ClassLoader String bytes]
[ClassLoader]}
:exposes-methods {defineClass superDefineClass
resolveClass superResolveClass}
:prefix "-"
:main false)«Простите,» говорит Тим из-за плеча, «я не эксперт в Clojure. Зачем это?»
«Просто бойлерплейт. Не беспокойтесь». Тим выглядит еще более обеспокоенным. «Мы все время так делаем».
(defn -class-loader-init
[^ClassLoader class-loader ^String class-name ^bytes bytecode]
[[class-loader] {:class-name class-name
:bytecode bytecode}])
(defn -loadClass
([this ^String class-name]
(-loadClass this class-name true))
([this ^String class-name resolve?]
(if (= class-name (:class-name (.state this)))
(let [bytecode (:bytecode (.state this))
c (.superDefineClass this
class-name
bytecode
(int 0)
(int (alength bytecode)))]
(when resolve? (.superResolveClass this c))
c)
(.loadClass (.getParent this) class-name))))
(defn class-loader
[^String class-name ^bytes bytecode]
(cycle_detector.core.ArbClassLoader. (.getClassLoader MutableLinkedList)
class-name
bytecode))Цвета начинают убегать с лица Тима. Видать пришла зима и он решил полинять.
(defn run-bytecode
[bytecode class-name method-name signature & args]
(-> class-name
(class-loader bytecode)
(.loadClass class-name)
(.getMethod method-name (into-array Class signature))
(.invoke nil (object-array args))))«Clojure — динамический язык», охотно объясняешь ты, «Так что когда мы гоняем туда и сюда классы Java, обычно происходит некоторая рефлексия».
«Похоже на то, что ты… написала classloader исключительно для того, чтобы вернуть массив одиночных байт для определенного класса? Это… это нормально?»
«Да» — настаиваешь ты, грозно сверкая глазами.
«А почему просто не написать алгоритм на Clojure?»
«Производительность» — совершенно честно объясняешь ты. «Так как постоянные проверки будут проводиться в тесном внутреннем цикле, то мы совершенно не хотим писать их на столь высокоуровневом языке».
«Х-хорошо» — заикается Тим «Так ны напишешь проверку на цикличность на Java? И будешь вызывать ее из Clojure?»
«Что-то типа того».
(def racer
(->> [0xca 0xfe 0xba 0xbe«А это что такое?»
«Магические числа». Ты же ведьма, в конце концов. «Каждый класс начинается с девушки в кафе»
[ в оригинале — babe in a cafe, см 0xca 0xfe 0xba 0xbe ]
«Чего?!»
«Знаешь, красивый мужчина — вроде тех, что бывают в кино — расслабляется в послеобеденное время после прогулки. В руках чашка кофе, оранжевые очки сверкают на солнце, а мимо него совершают пробежку красивые девушки. Если одной повезет, то его взгляд, возможно, встретится с ее глазами, и они улыбнутся друг другу, и вместе найдут отделанный кирпичом переулок. Ее губы встретятся с его кожей, и она почувствует жар солнца под ней…»
«Прости, что?»
Если честно, ты никогда не понимала замысел Sun в этой истории, или почему спецификация Java Virtual Machine, обычно столь прозаичная, низвергается в чувственную рапсодию на многие строфы в секции 4.1
0x00 0x00 ; Minor
0x00 0x31 ; Major«Мы используем версию 49, поскольку она не требует stack maps, что упрощает задачу. Теперь нам нужно число констант»
Вспомни будущее. Это обычный трюк для заклинателей протоколов, многие из которых жили как Мерлин, записывая константы и размеры буферов еще до (после) того как они написали (не написали) сами буферы.
Вспомни, что 22 хватит. Запиши.
0x00 0x17 ; 22 constants«Извиняюсь» — моргает Тим «Но ведь 0×17 это в десятичной системе 23, а не 22?»
«Og én,» — декламируешь ты напевно — «Til javanissen!»
«Прошу прощения?»
«Джаваниски. Ты наверняка о них слышал! Они мелкий волшебный народ — навроде гномов — который живет в каждой JVM. Если не выделишь им одну дополнительную константу, они пакостят сегфолтами. Но обрадуй джаваниска, и твои мьютексы будут работать как по маслу».
Это история из детства. Ты вспоминаешь маму, бубнящую офсеты и помешивающую варево в котле. «To byter for bufferen anvise / og ekstra én til javanisse.» Это радостное воспоминание, и ты в нем несколько забываешься, пока Тим не напоминает о себе покашливанием.
«Ах да. Константы. Нам понадобится наш суперкласс. Объект, конечно. Обычно я б использовала существующий класс, чтобы уменьшить размер, но тут мы работаем только с интерфейсами, так что будет Объект. И, полагаю, нужен класс для нас самих».
0x01 0x00 0x10 ; 1: A UTF-8 string of 16 bytes
(.getBytes "java/lang/Object")
0x07 0x00 0x01 ; 2: The Object class
0x01 0x00 0x19 ; 3: UTF-8 string of 25 bytes
(.getBytes "cycle_detector/core/Racer")
0x07 0x00 0x03 ; 4: Our classМы возьмем Iterable и вызовем .iterator (), а значит нам понадобится:
0x01 0x00 0x12 ; 5: UTF-8 string of 18 bytes
(.getBytes "java/lang/Iterable")
0x07 0x00 0x05 ; 6: Iterable
0x01 0x00 0x08 ; 7: UTF-8 string of 8 bytes
(.getBytes "iterator")
0x01 0x00 0x16 ; 8: UTF-8 string of 22 bytes
(.getBytes "()Ljava/util/Iterator;")
0x0c 0x00 0x07 0x00 0x08 ; 9: Name and type info (7, 8)
0x0b 0x00 0x06 0x00 0x09 ; 10: Interface methodref for Iterable.iterator()«И для этого итератора нам понадобятся hasNext и Next ()…». Теперь байты пойдут быстрее. Это намного лучше, чем древнескандинавская гексография, где четные и нечетные цифры имели в составе одну и ту же руну.
0x01 0x00 0x12 ; 11: UTF-8 string of 18 bytes
(.getBytes "java/util/Iterator")
0x07 0x00 0x0b ; 12: Iterator
0x01 0x00 0x07 ; 13: UTF-8 string of 7 bytes
(.getBytes "hasNext")
0x01 0x00 0x03 ; 14: UTF-8 string of 3 bytes
(.getBytes "()Z")
0x0c 0x00 0x0d 0x00 0x0e ; 15: Name and type info for .hasNext()
0x0b 0x00 0x0c 0x00 0x0f ; 16: Interface methodref: Iterator.hasNext()
0x01 0x00 0x04 ; 17: UTF-8 string of 4 bytes
(.getBytes "next")
0x01 0x00 0x14 ; 18: UTF-8 string of 20 bytes
(.getBytes "()Ljava/lang/Object;")
0x0c 0x00 0x11 0x00 0x12 ; 19: Name and type info for .next()
0x0b 0x00 0x0c 0x00 0x13 ; 20: Iterator.next()Тим онемел.
«Теперь можно подумать», — бормочешь ты, «что обычно код прячут в класс, а потому надо бы присвоить ему отдельную байтовую метку —, но вместо того нам хорошо бы засунуть слово «Code» в каждый класс и использовать его для идентификации наших атрибутов кода».
0x01 0x00 0x04 ; 21: UTF-8 string of 4 bytes
(.getBytes "Code") ; String for code attributesНаконец, наша сигнатура. Берем Iterable и возвращаем булево значение.
0x01 0x00 0x17 ; 22: UTF-8 string of 23 bytes
(.getBytes "(Ljava/lang/Iterable;)Z") ; Our arg signature«Ну что ж». Надо хрустнуть костяшками и нанести древние печати.
0x00 0x21 ; Flags: public & super
0x00 0x04 ; Our class
0x00 0x02 ; Our superclass (Object)
0x00 0x00 ; No interfaces
0x00 0x00 ; No fields
0x00 0x01 ; One methodКаждая юная ведьмочка вашего клана была должна вызубрить эти байты. Какую гордость ты испытывала, когда впервые сколдовала класс без учебных подпорок javac! Итак, начало метода:
0x00 0x09 ; Flags: public & static
0x00 0x15 ; Method name (21, "Code")«Имена методов должны начинаться в нижнем регистре», — утверждает Тим. Но голос его звучит так, как будто это был вопрос.
«Только по соглашению. Подойдет почти любая строка, а у нас уже есть одна в пуле констант».
0x00 0x16 ; Method signature (22)
0x00 0x01 ; One attribute
; Method attributes
0x00 0x15 ; Attribute name (21, "Code")
0x00 0x00 0x00 0x48 ; + 2 2 4 bytecode-length 2 0 2 attribute-len
0x00 0x02 ; Maximum stack
0x00 0x04 ; Number of local variables«Стой, стой, подожди» — Тим хватается за щепку во время шторма. «Всего четыре слота для переменных? Для аргументов плюс локальных?»
«Og to til javanissen!» — напоминаешь ты ему. Тим ловит ртом воздух, пока ты вспоминаешь, сколько именно инструкций написала.
0x00 0x00 0x00 0x3c ; Size of bytecodeТвой метод начинается с создания пары итераторов из единственного аргумента Iterable.
0x2a ; aload_0 (take arg)
0xb9 ; invokeinterface
0x00
0x0a ; .iterator()
0x01 ; 1 arg
0x00 ; unused
0x4d ; astore_1 (store iterator)
0x2a ; aload_0 (take arg)
0xb9 ; invokeinterface
0x00
0x0a ; .iterator()
0x01 ; 1 arg
0x00 ; unused
0x4e ; astore_0 (store iterator)«Наверное тут нужен astore_2?» — спрашивает Тим, стараясь помочь. «Нулевая переменная содержит наш первый аргумент, ведь так?»
«Так было», соглашаешься ты, «Но больше он нам не понадобится».
«Но… они ведь даже не одного типа. Это… это нелегально».
«Если бы это было нелегальным» — терпеливо напоминаешь ты ему, «то Sun Microsystems сделала бы это невозможным».
Первая будет быстрым итератором. Ее имя будет Йорунн, ее ноги будут сильными от многих лет катания на лыжах. Она летит вперед мощными толчками.
0x2d ; aload_1 take fast iterator
0xb9 ; invokeinterface
0x00
0x10 ; hasnext
0x01 ; 1 arg
0x00 ; unused
0x9a ; ifne
0x00
0x05 ; jump ahead 3 if we have a next element
0x03 ; iconst_0
0xac ; ireturn (return false)
; Move fast iterator forward by 1
0x2d ; aload_1 (take fast iterator)
0xb9 ; invokeinterface
0x00
0x14 ; .next()
0x01 ; 1 arg
0x00 ; unused
0x57 ; discard element
; Ensure fast iterator has next
0x2d ; aload_1 (take fast iterator)
0xb9 ; invokeinterface
0x00
0x10 ; hasNext()
0x01
0x00
0x9a ; ifne
0x00
0x05 ; jump forward by 3 if we have a next element
0x03 ; iconst_0
0xac ; ireturnБьёрн в нулевом регистре будет толстым и ленивым. Он не спеша топочет вперед, как его тезка. [Bjørn — медведь].
0x2c ; aload_0 (take slow iterator)
0xb9 ; invokeinterface
0x00
0x14 ; .next()
0x01
0x00Йорунн, чтоб ее не догнали, делает еще рывок. Ее поступь тверда.
0x2d ; aload_1 (take fast iterator)
0xb9 ; invokeinterface
0x00
0x14 ; .next()
0x01
0x00Зная их положение на тропинке, ты проверяешь, не столкнутся ли они друг с другом; и если нет, то повторяешь процесс еще раз:
0xa6 ; if_acmpne
0xff
0xd7 ; 0xffff + 1 - 41 instructions
; Return true
0x04 ; iconst_1
0xac ; ireturnТвои шестьдесят байт окончены, ты довольно вздыхаешь и наносишь запечатывающие руны на свое заклинание, прежде чем преобразовать каждое число в единственный хитрый байт.
; End of bytecode
0x00 0x00 ; No exceptions
0x00 0x00 ; No attributes
; End of method
0x00 0x00 ; No class attributes
]
(map (fn [x]
(if (instance? Long x)
(unchecked-byte x)
x)))))Тим вежливо пытается вернуть интервью в обычное русло. Благословляешь его, но не слишком сильно, а не то он годами будет тащиться за тобой в Твиттере, клянча заклинания против каждого вычислительного недуга, который его поразит. Заговор против мелких повреждений файловой системы подойдет.
Теперь стряхиваешь иней в пальцев, вводишь тор глубоко в виртуальную машину и раскручиваешь крепкую петлю сериализации.
(defn write-class!
[^DataOutputStream ds class-data]
(doseq [x class-data]
(condp = (class x)
nil nil
Long (.writeLong ds x)
Integer (.writeInt ds x)
Short (.writeShort ds x)
Byte (.writeByte ds x)
(.write ds ^bytes x))))
(defn class-bytes
[class-data]
(let [baos (ByteArrayOutputStream.)]
(with-open [ds (DataOutputStream. baos)]
(write-class! ds class-data))
(.toByteArray baos)))«Baos рифмуется с хаосом» — вежливо информируешь ты Тима. Тот сконфуженно спрашивает про юнит-тесты. В приготовлениях ты сплетаешь историю про тропинку в лесу, которая смыкается сама с собой.
(deftest cycle-test
(let [nodes (mapv node (range 5))
list (first nodes)]
(reduce link! nodes)
(link! (nth nodes 3) (nth nodes 1))Прежде чем бросить заклятье, ты обращаешься к сторонам света, обозначенным шрамами на твоем запятье: H, J, K, L. Только J дает ответы таким как ты, но быть вежливой никогда не повредит.
(deftest cycle-test
(let [cycle? (partial run-bytecode
(class-bytes racer)
"cycle_detector.core.Racer"
"Code"
[Iterable])]
(is (boolean (cycle? (seq list))))
(is (not (boolean (cycle? []))))
(is (not (boolean (cycle? [1 2 3]))))))))
Ran 1 tests containing 3 assertions.
0 failures, 0 errors.«Триста пятьдесят шесть байт» — заявляешь ты, и с удовольствием потягиваешься. «У Javac получилось бы примерно пятьсот восемьдесят. Мы конечно порядком сэкономили, пропустив stackmap и line mapping, но дополнительно мы сократили число переменных, и еще выбросили четыре лишних операции astore/aload. И естественно, поскольку класс никогда не инстанциируется, нам не надо генерировать метод , или вызывать суперкласс».
Тим пялится на тебя с молчаливым интересом. Его кофта блестит от быстро тающего инея. Скорей всего ты нанята.
Тянешься в карман своей мантии, и нежно, медленными движениями, чтобы не спугнуть его обратно в норку, протягиваешь руку, разжимаешь пальцы, и предлагаешь ему жёлудь.
