«Проще ответить, чем продолжать молчать» — большое интервью с отцом транзакционной памяти, Морисом Херлихи

wvk9sy10iyl7m9y2stnq7jd5f3e.jpeg

Морис Херлихи — обладатель целых двух премий Дейкстры. Первая — за работу по «Wait-Free Synchronization» (Brown University) и вторая, более свежая, — «Transactional Memory: Architectural Support for Lock-Free Data Structures» (Virginia Tech University). Премию Дейкстры дают за работы, значимость и влияние которых были заметны на протяжении не менее десяти лет и, очевидно, Морис — один из самых известных специалистов в области. На данный момент он работает профессором в Брауновском университете и имеет множество достижений на целый абзац длиной. Сейчас он занимается исследованиями блокчейна в контексте классических распределенных вычислений.

Ранее Морис уже приезжал в Россию на SPTCC (видеозапись) и cделал отличную встречу сообщества Java-разработчиков JUG.ru в Питере (видеозапись).

Этот хабрапост — большое интервью с Морисом Херлихи. В нем обсуждаются следующие темы:


  • Взаимодействие академической сферы и индустрии;
  • Фундамент для исследований блокчейна;
  • Откуда берутся прорывные идеи. Влияние популярности;
  • PhD под руководством Барбары Лисков;
  • Мир в ожидании многоядерности;
  • Новому миру — новые проблемы. NVM, NUMA и взлом архитектуры;
  • Компиляторы против процессоров, RISC vs CISC, shared memory vs message passing;
  • Искусство написания хрупкого многопоточного кода;
  • Как обучить студентов написанию сложного многопоточного кода;
  • Новое издание книги «The Art of Multiprocessor Programming»;
  • Как изобреталась транзакционная память;    
  • Почему стоит проводить исследования в области распределенных вычислений;
  • Остановилось ли развитие алгоритмов, и как жить дальше;
  • Работа в Брауновском Университете;
  • Разница между исследованиями в университете и внутри корпорации;
  • Hydra и SPTDC.

Виталий Аксенов — на данный момент, пост-док в IST Austria и сотрудник кафедры «Компьютерные Технологии» Университета ИТМО. Занимается исследованиями в области теории и практики конкурентных структур данных. До работы в IST, он получил PhD в Университете Париж Дидро и в Университете ИТМО под руководством профессора Петра Кузнецова.

Алексей Федоров — продюсер в JUG Ru Group, российской компании, которая занимается организацией конференций для разработчиков. Алексей участвовал в подготовке более чем 50 конференций, а в его резюме есть всё что угодно, начиная от позиции инженера-разработчика в Oracle (JCK, Java Platform Group), и заканчивая позицией деврела в компании Одноклассники.

Владимир Ситников — инженер в компании Netcracker. Десять лет работает над производительностью и масштабируемостью NetCracker OS — ПО, используемого операторами связи для автоматизации процессов управления сетью и сетевым оборудованием. Увлекается вопросами производительности Java и Oracle Database. Автор более десятка улучшений производительности в официальном PostgreSQL JDBC-драйвере.

Алексей: Морис, вы очень долго работали в академической среде и первый вопрос заключается во взаимодействии между академической и индустриальной сферами. Не могли бы вы рассказать, как изменились взаимодействия между ними за последнее время? Что было 20–30 лет назад и что происходит сейчас?  

Морис: Я всегда старался тесно сотрудничать с коммерческими компаниями, потому что у них есть интересные задачи. Они, как правило, не очень заинтересованы ни в публикации полученных результатах, ни в подробных объяснениях своих проблем мировой общественности. Они лишь заинтересованы в решении этих проблем. Я некоторое время работал в таких компаниях. Я провел пять лет, работая полный рабочий день в исследовательской лаборатории в Digital Equipment Corporation, которая раньше была крупной компьютерной компанией. Я работал один день в неделю в Sun, в Microsoft, в Oracle, немного работал в Facebook. Сейчас я собираюсь отправиться в творческий отпуск (sabbatical leave, профессору в американском университете разрешается где-то раз в шесть лет брать такой отпуск на год) и поработать в Algorand, это такая криптовалютная компания в Бостоне. Работать в тесной связи с компаниями всегда было приятно, потому что именно так вы узнаете о новых и интересных вещах. Вы можете быть вообще первым или вторым человеком, опубликовавшим статью на выбранную тему, вместо того, чтобы заниматься постепенным улучшением решений задач, над которыми и так работают все остальные.

Алексей: Можете подробнее рассказать, как это происходит?

Морис: Конечно. Знаете, когда я работал в корпорации Digital Equipment Corporation, я и Эллиот Мосс, мы изобрели транзакционную память. Это был очень плодотворный период, когда все начали интересоваться информационными технологиями. Параллелизмом в том числе, хотя многоядерные системы еще не существовали. Во времена Sun и Oracle я много работал над параллельными структурами данных. В Facebook я занимался их блокчейн-проектом, о котором я не могу говорить, но надеюсь, он скоро станет публичным. В следующем году, в Algorand, я буду работать в исследовательской группе, изучая смарт-контракты.

Алексей: В последние несколько лет блокчейн стал очень популярной темой. Поможет ли это вашим исследованиям? Возможно, облегчит получение грантов или даст доступ к ресурсам компаний, работающим в индустрии?

Морис: Я уже получил небольшой грант от Ethereum Foundation. Популярность блокчейна очень полезна для того, чтобы вдохновлять студентов на работу в этой области. Они очень интересуются этим и рады принять участие, но иногда не понимают, что исследования, заманчиво звучащие снаружи, оказывается, включают действительно тяжелую работу. Тем не менее, я очень рад использовать всю эту мистику вокруг блокчейна, это помогает привлекать студентов. 

Но это еще не всё. Я нахожусь в консультативном совете нескольких блокчейн-стартапов. Некоторые из них могут преуспеть, некоторые из них, возможно, нет, но всегда очень интересно видеть их идеи, изучать их и консультировать людей. Самое захватывающее — когда вы предупреждаете людей не делать что-то. Многое вначале кажется хорошей идеей, но так ли это на самом деле?

Виталий: Кое-кто думает, что за блокчейном и его алгоритмами будущее. А другие люди говорят, что это просто очередной пузырь. Можете поделиться своим мнением на этот счёт?

Морис: Многое из того, что происходит в мире блокчейнов работает неправильно, что-то просто мошенничество, многое переоценено. Тем не менее, я думаю, что для этих исследований есть солидная научная база. Тот факт, что мир блокчейнов полон идеологических разногласий, показывает уровень волнения и преданности делу. С другой стороны, это не особо выгодно для научных исследований. Сейчас, если вы публикуете статью в которой говорится про недостатки конкретного алгоритма, полученная реакция не всегда является в полной мере научной. Зачастую люди выплескивают свои эмоции. Думаю, что подобный ажиотаж в этой области кое-кому может показаться привлекательным, но в конце концов, тут есть и реальные научные и инженерные вопросы, которыми только предстоит заняться. Здесь много Computer Science.

Виталий: То есть, вы пытаетесь заложить фундамент для исследований блокчейна, верно?

Морис: Я пытаюсь заложить фундамент для твердой, научно и математически обоснованной дисциплины. И отчасти проблема в том, что приходится иногда противоречить некоторым излишне резким позициям других людей, игнорировать их. Иногда люди спрашивают, почему я работаю в области, в которой заинтересованы только террористы и наркоторговцы. Такая реакция столь же бессмысленна, как и поведение последователей, слепо повторяющих твои слова. Думаю, что истина где-то посередине. Блокчейн ещё окажет глубокое влияние на общество и мировую экономику. Но, вероятно, это произойдет не благодаря современным технологиям. Современные технологии будут развиваться и то, что в будущем будет называться блокчейном, станет очень важным. Может быть, оно даже не будет выглядеть как современные блокчейны, это открытый вопрос.

Если люди будут изобретать новые технологии, они будут продолжать называть это блокчейном. Я имею в виду, точно так же, как сегодняшний Fortran не имеет никакого отношения к языку Fortran их 1960-х годов, но все продолжают называть это Fortran. То же самое для UNIX. То, что называется «блокчейн», ещё сделает свою революцию. Но я сомневаюсь, что этот новый блокчейн станет похож на то, что всем так нравится использовать сегодня.

Алексей: Привела ли популярность блокчейна к новым результатам с научной точки зрения? Больше взаимодействия, больше студентов, больше компаний в области. Есть ли уже какие-то результаты этого роста популярности?

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

Алексей: Это очень интересно, потому что несколько лет назад у нас была другая тенденция. Это немного похоже на фронтенд-разработку, когда разработчики браузерных интерфейсов переизобретали целые технологии, которые к тому времени уже были популярны в бэкенде: системы сборки, непрерывную интеграцию и всё в таком духе. 

Морис: Согласен. Но это неудивительно, ведь по-настоящему прорывные идеи всегда приходят извне сложившегося сообщества. Признанные исследователи, особенно авторитеты в академической среде, вряд ли сделают что-то действительно прорывное. Легко написать для следующей конференции доклад про то, как вы немного улучшили результаты своих прошлых работ. Сходите на конференцию, соберитесь с друзьями, поговорите о всём том же самом. А люди, врывающиеся с прорывными идеями, почти всегда приходят извне. Они не знают правил, не знают языка, но тем не менее… Если же вы внутри сложившегося сообщества, советую обращать внимание на новые вещи, на что-то, что не укладывается в общую картину. В некотором смысле, можно предпринять попытку объединить внешние, более подвижные разработки с методами, которые мы уже понимаем. В качестве первого шага, попробуйте создать научную базу, а потом измените ее так, чтобы ее можно было применять к новым прорывным идеям. Думаю, что блокчейн отлично подходит на роль свежей прорывной идеи.

Алексей: Как думаете, почему так происходит? Потому что у людей «снаружи» нет каких-то специфических барьеров, присущих сообществу?

Морис: Тут прослеживается какая-то схема. Если почитаете историю импрессионистов в живописи и искусстве вообще, то в своё время известные художники отвергали импрессионизм. Они говорили, что это какое-то ребячество. Поколение спустя, этот ранее отвергнутый вид искусства стал стандартом. Что я вижу в своей области: изобретатели блокчейна не были заинтересованы во власти, в накручивании публикаций и индекса цитируемости, они просто хотели сделать что-то хорошее. И вот, они сели и начали это делать. Им не хватало определенной технической глубины, но это поправимо. Куда сложнее придумать новые творческие идеи, чем исправлять и усиливать недостаточно зрелые. Благодаря этим изобретателям мне теперь есть чем заняться!

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

Морис: Хорошая аналогия — распределенные вычисления. Подумайте о блокчейне как если бы он был стартапом, а распределенные вычисления — крупной устоявшейся компанией. Распределенные вычисления находятся в процессе покупки и слияния с блокчейном.

Виталий: У нас ещё множество вопросов! Мы изучали вашу биографию и наткнулись на любопытный факт о вашей докторской степени. Да, это было давным-давно, но тема, кажется, важная. Вы получили PhD под руководством самой Барбары Лисков! Барбара очень известна в сообществе разработчиков языков программирования, и вообще очень известная личность. Логично, что ваши исследования были в области языков программирования. Как же вы перешли на параллельные вычисления? Почему вы решили сменить тему?

Морис: В то время Барбара и ее группа как раз посматривали на распределенные вычисления, это было очень новой идеей. Были и те, кто говорил, что распределенные вычисления — чепуха, общение компьютеров между собой бессмысленно. Один из вопросов, рассматриваемых в распределенных вычислениях, отличающий их от централизованных вычислений, — отказоустойчивость. После длительных исследований мы решили, что в языке программирования для распределенных вычислений нужно иметь что-то вроде атомарных транзакций, потому что никогда нельзя быть уверенным в успешности удаленного вызова. Как только у вас появились транзакции, возникает проблема управления параллелизмом. Потом было много работы по получению высокопараллельных транзакционных структур данных. Затем, когда я получил высшее образование, я пошел в Карнеги-Меллон и начал искать тему для работы. Мне пришло в голову, что вычисления перешли от отдельных компьютеров к сетям компьютеров. Естественным продолжением прогресса стали бы мультипроцессоры — слово «многоядерный» тогда ещё не существовало. Я подумал: каков эквивалент атомарным транзакциям для многоядерной системы? Точно не обычные транзакции, потому что они слишком большие и тяжелые. И вот так я пришел к идее линеаризуемости и именно так я придумал всю wait-free синхронизацию. Это была попытка ответить на вопрос, что же является аналогом атомарных транзакций для многопроцессорной системы с общей памятью. На первый взгляд, эта работа может выглядеть совсем по-другому, но на самом деле это продолжение всё той же темы.

Виталий: Вы упомянули, что в то время было совсем немного многоядерных компьютеров, так?

Морис: Их просто не было. Было несколько так называемых симметричных мультипроцессоров, которые в основном были подключены к одной и той же шине. Это не очень хорошо работало, потому что каждый раз, когда новая компания создавала нечто подобное, Intel выпускала один-единственный процессор, который превосходил мультипроцессор.

Алексей: Не значит ли это, что в те давние времена, это было скорее теоретическое исследование?

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

Алексей: Как вы думаете, почему многоядерные процессоры появились только в двухтысячных? Так почему так поздно?

Морис: Это связано с аппаратными ограничениями. Intel, AMD и другие компании очень хороши в повышении скорости процессора. Когда в какой-то момент процессоры стали достаточно маленькими и они больше не могли увеличивать тактовую частоту, потому что процессоры начали бы сгорать. Можно сделать их меньше, но никак не быстрее. Что в их силах — вместо очень маленького процессора, уместить восемь, шестнадцать или тридцать два процессора в тот же объем корпуса, где раньше помещался только один. Теперь у вас многопоточность и быстрая коммуникация между ними, потому что они совместно используют кэши. Но вы не можете заставить их работать быстрее — есть вполне конкретное ограничение скорости. Их продолжают понемногу улучшать, но уже не настолько сильно. На пути улучшений встали законы физики.

Алексей: Звучит очень разумно. С новыми многоядерными процессорами пришли новые проблемы. Ожидали ли вы и ваши коллеги этих проблем? Быть может, вы изучали их заранее? В теоретических исследованиях зачастую не очень легко предсказывать такие вещи. Когда проблемы всё же случились — насколько они соответствовали вашим ожиданиям и ожиданиям ваших коллег? Или же они были совершенно новыми, и вы с коллегами должны были тратить много времени на решение проблем по мере их появления?

Виталий: Добавлю к вопросу Алексея: правильно ли вы спрогнозировали архитектуру процессоров, пока занимались теорией?

Морис: Не все 100%. Но я думаю, что мы с коллегами хорошо поработали, прогнозируя многоядерность с общей памятью. Думаю, мы правильно предсказали сложности в разработке параллельных структуры данных, работающих без блокировок. Такие структуры данных были важны для многих приложений, хоть и не для всех, но зачастую вам действительно нужна структура данных без блокировки. Когда мы изобретали их, многие утверждали, что это чепуха, что и с блокировками все отлично работает. Мы достаточно хорошо предвидели, что появятся готовые решения для многих проблем программирования и проблем структур данных. Существовали и более сложные проблемы, такие как NUMA — неравномерный доступ к памяти. На самом деле, они даже не рассматривались до изобретения многоядерных процессоров, поскольку были слишком специфичны. Исследовательское сообщество работало над вопросами, которые были в целом предсказуемы. Некоторым аппаратным проблемам, связанным с конкретными архитектурами, пришлось подождать своего часа — собственно, появления этих архитектур. Например, никто особо не работал над структурами данных, специфичными для GPU, потому что GPU тогда не существовало. Несмотря на то, большая работа была проделана над SIMD, эти алгоритмы были готовы к применению сразу же, как появилось подходящее железо. Тем не менее, предвидеть всё невозможно.

Алексей: Если я правильно понимаю, NUMA является своего рода компромиссом между стоимостью, производительностью и некоторыми другими вещами. Есть идеи, почему NUMA появилась так поздно?

Морис: Думаю, что NUMA существует благодаря проблемам с железом, использующимся для производства памяти: чем дальше находятся компоненты, тем медленнее к ним доступ. С другой стороны, вторая ценность этой абстракции — равномерность памяти. Поэтому одной из характеристик параллельных вычислений является то, что все абстракции слегка сломаны. Если бы доступ был идеально равномерным, вся память была бы равноудалённой, но это экономически, а может даже и физически невозможно. Поэтому возникает этот конфликт. Если вы пишете свою программу так, как если бы память была равномерной, то скорее всего, она будет корректной. В том смысле, что она не будет выдавать неправильных ответов. Но и производительность у неё звёзд с неба не схватит. Точно так же, если вы пишете спинлоки без понимания иерархии кэшей, сама-то блокировка будет корректной, но о производительности можно забыть. В каком-то смысле, вы должны писать программы, живущие поверх очень простой абстракции, но вы должны перехитрить людей, которые эту абстракцию вам предоставили: вы обязаны знать, что под абстракцией лежит некая иерархия памяти, что есть шина между вами и этой памятью, и так далее. Таким образом, существует некий конфликт между полезными поодиночке абстракциями, что приводит нас к очень конкретным и прагматичным проблемам.

Виталий: Что насчёт будущего? Можно ли вы предсказать, как процессоры будут развиваться дальше? Есть идея, что одним из ответов является транзакционная память является одним из ответов. Вероятно, у вас есть что-то ещё в запасе.

Морис: Впереди есть пара основных проблем. Одна из них заключается в том, что когерентная память — замечательная абстракция, но она начинает ломаться в специальных случаях. Так, например, NUMA является живым примером чего-то, где можно продолжать притворяться, что существует равномерная память. На самом деле — нет, производительность заставит вас заплакать. В какой-то момент архитекторам придется отказаться от идеи об единой архитектуре памяти, нельзя притворяться вечно. Понадобятся новые модели программирования, достаточно простые в использовании и достаточно мощные, чтобы нижележащее оборудование было эффективным. Это очень сложный компромисс, ведь если вы покажите программистам ту архитектуру, которая на самом деле используется в железе, они сойдут ума. Это слишком сложно и не переносимо. Если же вы представите слишком простой интерфейс, то производительность будет плохой. Таким образом, потребуется достигнуть множество очень непростых компромиссов, необходимых для обеспечения полезных моделей программирования, применимых к действительно большим многоядерным процессорам. Я не уверен, что кто-то кроме узкого специалиста способен программировать на 2000-ядерном компьютере. И если вы не делаете очень специализированные или научные вычисления, криптографию или что-то такое — все еще совершенно не ясно, как это правильно делать. 

Другим подобным направлением являются специализированные архитектуры. Графические ускорители существуют уже давно, но уже стали своего рода классическим примером того, как можно взять специализированный тип вычислений и запустить их на выделенном чипе. Это добавляет свои собственные проблемы: как вы общаетесь с таким устройством, как вы его программируете. Я недавно работал над задачами в области near memory computing. Вы берете небольшой процессор и приклеиваете его к огромному куску памяти, так что память работает на скорости L1-кэша, а затем происходит связь с устройством вроде TPU — процессор занимается загрузкой новых задач в ваше ядро памяти. Разработка структур данных и протоколов связи для такого рода вещей — еще один интересный пример. Таким образом, специализированные процессоры и аппаратное обеспечение будут подвергаться улучшениям в течение достаточно долгого времени.

Алексей: Что насчет энергонезависимой памяти (non-volatile memory)?

Морис: О, это еще один отличный пример! NVM очень сильно изменит наш взгляд на такие вещи, как, например, структуры данных. Энергонезависимая память, в некотором смысле, обещает действительно всё ускорить. Но она не сделает жизнь проще, потому что большинство процессоров, кэши и регистры все еще энергозависимы. Когда вы начинаете работу после сбоя, ваше состояние и состояние вашей памяти не будет в точности теми же, что были до сбоя. Я очень благодарен людям, занимающимся NVM — долгое время исследователям будет чем заняться, пытаясь выяснить условия корректности. Вычисления корректны, если они могут пережить сбой, в котором потерялось содержимое кэшей и регистров, но основная память осталась неизменной.

Владимир: Что вы думаете о дилемме «компиляторы против процессоров» с точки зрения набора команд? Объясню для тех, кто не в теме: если мы перейдем к неравномерной памяти или чему-то подобному, мы могли бы применить очень простой набор команд и попросить компилятор сгенерировать сложный код, способный использовать открывшиеся преимущества. Или мы можем пойти другим путем: реализовать сложные инструкции и попросить процессор переупорядочить инструкции и проводить с ними другие манипуляции. Что вы думаете об этом?

Морис: У меня действительно нет ответа на этот вопрос. Эта дискуссия продолжается в течение четырех десятилетий. Было время, когда между сокращенным набором команд и сложным набором команд велись гражданские войны. Какое-то время выигрывали RISC-овые люди, но потом Intel перестроили свои движки так, чтобы внутри использовался сокращенный набор инструкций, а наружу экспортировался полный. Наверное, это та тема, в которой каждое новое поколение должно найти собственные компромиссы и принять собственные решения. Очень трудно предсказать, какая из этих вещей окажется лучше. Поэтому любое предсказание, которое я сделаю, будет верным в течение определенного времени, а потом какое-то время снова станет ложным, а затем снова верным.

Алексей: Насколько вообще для отрасли обычной является такая ситуация, что некоторые идеи выигрывают в течение нескольких десятилетий и проигрывают в следующих? Есть ли другие примеры таких периодических перемен?

Морис: В теме распределенных вычислений есть люди, которые верят в разделяемую память и люди, которые верят в обмен сообщениями. Изначально в распределенных вычислениях параллельные вычисления означают передачу сообщений. Потом кто-то обнаружил, что с разделяемой памятью программировать куда проще. Противоположная сторона заявила, что разделяемая память — штука слишком сложная, потому что там нужны блокировки и тому подобное, потому стоит перейти на языки, где ничего кроме передачи сообщений просто не существует. Кто-то посмотрел, что из этого вышло и говорит: «ого, эта реализация обмена сообщениями выглядят очень похоже на разделяемую память, потому что вы создаете много-много этих маленьких модулей, они отправляют сообщения друг другу, и все они взаимоблокируются, — давайте лучше сделаем базу данных с разделяемой памятью!». Всё это повторяется снова и снова, и невозможно сказать, что одна из сторон однозначно права. Одна из сторон всегда будет доминировать, потому что, как только одна из них почти побеждает, люди снова и снова изобретают способы улучшить противоположную.

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

Морис: Абсолютно верно, что разделяемая память построена на передаче сообщений — шины, кэши и так далее. Но с использованием передачи сообщений трудно писать программы, поэтому железо намеренно лжёт, притворяясь, что у вас есть какая-то равномерная память. Так вам будет проще писать простые корректные программы, пока производительность не начнет падать. Тогда вы скажете: похоже, настала пора подружиться с кэшем. И вот тогда вы начинаете беспокоиться о местонахождении кэша, и дальше пошло-поехало. В некотором смысле вы взламываете абстракцию: вы знаете, это не просто плоская равномерная память и собираетесь воспользоваться этими знаниями для написания программ, дружественных к кэшу. Это то, что придётся делать в реальных задачах. Этот конфликт между милой простой приятной абстракцией, которую вам выдали, и ужасающе сложной реализацией нижележащего железа — это то, где каждый пойдет на собственный компромисс. У меня есть книга о мультипроцессорах и синхронизации, и в один прекрасный момент я собирался написать главу о структурах данных в java.util.concurrent. Если вы посмотрите на них, на вещи вроде списков с пропусками — это изумительные произведения искусства. (Примечание редакции: тем, кто знаком с языком Java, стоит хоть раз взглянуть на реализацию ConcurrentSkipListMap, по ссылкам можно посмотреть на API и иcходный код). Но с моей точки зрения, было бы безответственно показывать их студентам, ведь такая структура данных своего рода парень в цирке, бегущий по канату над медвежьей ямой. Если вы измените хоть одну маленькую деталь, рухнет вся конструкция. Этот код очень быстрый и элегантный лишь потому, что он идеально написан, но малейшее изменение приведет к полному провалу. Если я поставлю этот код в пример студентам, они сразу скажут: я тоже могу так делать! И тогда какой-нибудь самолет упадет или ядерный реактор взорвется, и я буду виноват в том, что не вовремя предоставил им слишком много информации.

Алексей: Когда я был чуть моложе, то много раз я пытался изучать исходный код Дага Ли, например, java.util.concurrent, ведь это открытый исходный код, его очень легко найти и попытаться понять, что там происходит. Выходило не очень: зачастую, совершенно неясно, почему Даг решил что-то сделать именно таким образом, когда все остальные делают по-другому. Как вы объясняете своим студентам такие вещи? Если ли особый правильный способ описывать конкретные детали хардкорного алгоритма, например? Как вам это удается?

Морис: У преподавателей рисунка есть клише, которое они вспоминают первым делом: если вы хотите рисовать, как Пикассо, нужно сперва научиться рисовать простые реалистичные картинки, и лишь когда вы знаете правила можно начинать их нарушать. Если сразу начать с нарушения правил, получится беспорядок. Сперва я учу студентов как писать простой корректный код, не беспокоясь о производительности. Я говорю: тут прячутся сложные проблемы синхронизации, поэтому не беспокойтесь о кэшах, не беспокойтесь о моделях памяти, просто убедитесь, что всё правильно работает. Это уже достаточно сложно: современное программирование непросто само по себе, особенно для новых студентов. И вот когда у них появляется интуиция о том, как писать правильные программы, я говорю: посмотрите на эти две реализации спинлока: одна очень медленная, а вторая — тоже не очень, но уже получше. Тем не менее, математически эти два алгоритма совпадают. На самом деле, один из них использует локальность кэша. Один из них крутится на локально кэшированных данных, а другой многократно совершает операции, идущие через шину. Нельзя написать эффективный код, если вы не понимаете его сути, не знаете, как нарушить абстракцию и посмотреть на нижележащую структуру. Но вы не сможете сразу начать так делать. Есть люди, которые начинают делать так сразу и верят в собственную гениальность, обычно это плохо заканчивается, потому что они не понимают принципов. Никто не рисует как Пикассо и не пишет программы как Даг Ли, только что поступив в университет, в первую же неделю. Требуются годы, чтобы достичь такого уровня знаний.

Алексей: Получается, вы разделяете проблему на две части: первая — корректность, вторая — производительность?

Морис: Именно. Причём, именно в таком порядке. Часть проблемы заключается в том, что новые студенты не понимают, что достичь корректности сложно. Они с первого взгляда говорят: это, очевидно, корректно, осталось только ускорить. Поэтому иногда я рассказываю им об изначально некорректном алгоритме, как если бы он был корректным.

Алексей: Чтобы просто проверить, смогут ли они почувствовать подвох?

Морис: Я всегда предупреждаю заранее, что иногда буду предлагать неправильные алгоритмы. Не стоит обманывать людей. Я предлагаю им скептически относиться к информации. Если я что-то рассказываю и говорю: «смотрите, это очевидно правильно» — это сигнал, что где-то тебя пытаются обмануть, и следует начать задавать вопросы. Далее я стараюсь поддержать студентов, чтобы они не переставали задавать вопросы, и затем подсказываю: «что произойдет, если мы оставим все как есть?». И они сразу видят ошибку. Но убедить студентов, что им нужно побеспокоиться о корректности, куда сложнее, чем кажется на первый взгляд. Многие из этих студентов приходят с опытом программирования в старших классах, кто-то успел устроиться на работу и занимался программированием там, и все они полны уверенности в себе. Это что-то армейское: приходится вначале переломить их настрой, чтобы убедить терпеливо подходить к решению возникающих проблем. Или может это как у буддистских монахов: вначале они учатся рассуждать о корректности и как только они осознают способы рассуждений о корректности, им разрешается перейти на следующий уровень и начать беспокоиться о производительности.

Алексей: То есть, иногда вы показываете студентам нерабочие примеры, благодаря чему получаете обратную связь, показывающую, понимают ли они суть проблемы, могут ли найти неправильный код и неправильный результат. Ну и как, студенты обычно радуют или огорчают?

Морис: Почти всегда студенты в конце концов находят ошибку. Если они ищут слишком медленно, я задаю наводящие вопросы, и тут важно понять, что если их никогда не обманывать — они начнут бездумно воспринимать твои слова как истину в конечной инстанции. Потом им станет скучно и они начнут засыпать, читая Facebook на ноутбуке прямо во время занятия. Но когда вы заранее сообщаете, что их попытаются обмануть, и они будут выглядеть глупо, если не почувствуют подвоха, они становятся куда более бдительными. Это хорошо в разных смыслах. Хочется, чтобы студенты не только ставили под сомнение свое понимание вопроса, но ещё и ставили под сомнение авторитет преподавателя. Идея в том, чтобы студент мог в любое время поднять руку и сказать: думаю, то, что вы сейчас сказали — неверно. Это важный инструмент обучения. Я не хочу, чтобы кто-то из студентов сидел и молча про себя думал: всё это кажется полным бредом, но поднять руку слишком страшно, да и вообще, он же профессор, значит всё, что он говорит — истина. Поэтому, если заранее предупредить, что не всё рассказанное обязательно является правдой, у них появляется стимул уделять больше внимания материалу. Я явным образом проговариваю, что поднимать руку и задавать вопросы — это нормально. Ваш вопрос м

© Habrahabr.ru