Майкл Скотт — уже 34 года как профессор Computer Science в Рочестерском университетe, а в родном универститете Wisconsin–Madison был деканом в течение пяти лет. Он занимается исследованиям в области параллельного и распределённого программирования и дизайна языков и обучает этому студентов.

Мир знает Майкла по учебнику «Programming Language Pragmatics», а работа «Algorithms for scalable synchronization on shared-memory multiprocessors» получила премию Дейкстры как одна из наиболее известных в области распределённых вычислений. Также вы можете знать его как автора того самого алгоритма Майкла-Скотта.

Вместе с Дагом Ли разработал те неблокирующие алгоритмы и синхронные очереди, на которых работают библиотеки Java. Внедрение «dual data structures» в JavaSE 6 позволило в 10 раз улучшить производительность ThreadPoolExecutor.

Содержание:

• Начало карьеры, Рочестерский университет. Проект Charlotte, язык Lynx;
• IEEE Scalable Coherent Interface, блокировка MCS;
• Выживание в постоянно меняющемся мире;
• Становятся ли студенты глупее? Глобальные тренды, интернационализация;
• Эффективная работа со студентами;
• Как не отстать при подготовке новых курсов и книг;
• Связь между бизнесом и академией;
• Практическая реализация идей. MCS, MS, CLH, JSR 166, работа с Дагом Ли и многое другое;
• Транзакционная память;
• Новые архитектуры. Близкая победа транзакционной памяти;
• Энергонезависимая память, Optane DIMM, сверхбыстрые устройства;
• Следующий большой тренд. Dual data structures. Hydra.

Интервью ведут:

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

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

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

Начало карьеры, Рочестерский университет. Проект Charlotte, язык Lynx.

Алексей: Для начала я хотел рассказать вам, что мы в России все очень любим Сomputer Science, Data Science и алгоритмы. Прямо до неприличия. Мы все читали книгу Cormen, Leiserson и Rivest. Поэтому предстоящая конференция, школа и само это интервью должны пользоваться большой популярностью. Нам поступило множество вопросов для этого интервью от студентов, программистов и членов сообщества, поэтому мы очень благодарны вам за эту возможность. Пользуется ли Computer Science такой же любовью в США?

Майкл: Наша область настолько разносторонняя, в ней так много направлений, и она влияет на общество такими различными способами, что мне сложно ответить вам однозначно. Но факт в том, что благодаря ей за последние 30 лет произошли колоссальные изменения в бизнесе, промышленности, искусстве и обществе в целом.

Виталий: Давайте начнём с чего-нибудь отдаленного. Во многих университетах наблюдается нечто вроде специализации на одном определённом направлении. Для университета Карнеги-Меллона это параллельные вычисления, для MIT — криптография, роботы и многопоточность. А есть ли подобного рода специализация в Рочестерском университете?

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

Виталий: Вы начали заниматься Computer Science, когда область многопоточного программирования только зарождалась. По списку ваших публикаций видно, что первые работы касались достаточно широкого спектра вопросов: управление памятью в многопоточных системах, распределенные файловые системы, операционные системы. Почему такая разносторонность? Вы пытались найти своё место в исследовательском сообществе?

Майкл: Будучи студентом, я участвовал в проекте Charlotte в университете Висконсина, в рамках которого разрабатывалась одна из первых распределенных операционных систем. Там я работал вместе с Рафаэлем Финкелем (Raphael Finkel) и Марвином Соломоном (Marvin Solomon). Моя диссертация была посвящена разработке языка для системного софта для распределенных систем — сейчас про нее все уже забыли, и слава богу. Я создал язык программирования Lynx, который должен был упростить создание серверов для распределенной операционной системы со слабым связыванием. Поскольку на тот момент я в основном занимался операционными системами, то предполагал, что и моя карьера будет в основном связана с ними. Но в Рочестере университет был очень маленький, и из-за этого разные группы там очень тесно общались друг с другом. Там не было десятка других специалистов по операционным системам, с которыми я мог бы общаться, так что все контакты были с людьми, которые работали в совершенно других областях. Мне это очень нравилось, быть универсалом — большое преимущество для меня. Если же говорить конкретно о многопоточных структурах данных и алгоритмах синхронизации, то ими я начал заниматься совершенно случайно.

IEEE Scalable Coherent Interface, блокировка MCS.

Виталий: Можно немного подробней об этом?

Майкл: Это забавная история, которую я не устаю всем рассказывать. Она произошла на конференции ASPLOS в Бостоне — это было в конце 80-х или в начале 90-х. На конференции присутствовал Джон Меллор-Крамми (John Mellor-Crummey), выпускник нашего факультета. Я был с ним знаком, но мы до этого не вели совместных исследований. Мэри Вернон (Mary Vernon) из Висконсина выступала с докладом о многопроцессорной системе, которую они разрабатывали в Висконсине: Wisconsin Multicube. В этом Multicube на уровне железа был механизм синхронизации, который назывался Q on Sync Bit, а позднее он был переименован в Q on Lock Bit, потому что так его можно было произносить как название сыра Colby, то есть это был такой каламбур. Если вы интересуетесь механизмами многопоточности, вы, наверное, знаете, что Colby в конченом итоге стал механизмом синхронизации стандарта Scalable Coherent Interface от IEEE. Это был механизм блокировки, который создавал указатели из одного кэша на другой на уровне железа, чтобы каждый держатель блокировки знал, чья за ним очередь. Когда Джон и я об этом услышали, мы переглянулись и сказали: а зачем это делать на уровне железа? Разве нельзя того же самого добиться при помощи compare-and-swap? Мы взяли один из блокнотов, лежавших в аудитории, и набросали на нём блокировку MCS, пока Мэри продолжала свой доклад. В последствии мы её реализовали, поэкспериментировали, идея оказалась удачной, и мы опубликовали статью. Тогда для меня эта тема казалась лишь забавным отвлечением, после которого я планировал вернуться к операционным системам. Но затем возникла другая проблема в том же направлении, и в конечном итоге синхронизация, многопоточность и структуры данных стали моей основной специальностью. Как видите, произошло это всё по случайности.

Виталий: Я давно знаком с блокировкой MCS, но до текущего момента я не знал, что это Ваша работа, и не понимал, что это акроним от Ваших фамилий.

Как выживать в постоянно меняющемся мире?

Алексей: У меня есть вопрос по связанной теме. 30 или 40 лет назад было больше свободы в разных специальностях. Хочешь начать карьеру в многопоточности или распределенных системах — пожалуйста, хочешь заняться операционными системами — никаких проблем. В каждой области было очень много открытых вопросов и мало экспертов. Сейчас появились узкие специализации: нет просто экспертов по операционным системам в целом, есть специалисты по отдельным системам. То же самое с многопоточностью и распределенными системами. Но проблема в том, что наши жизни не бесконечные, каждый может посвятить исследованиям лишь несколько десятилетий. Как выжить в этом новом мире?

Майкл: Мы в этом плане не особенные, всё то же самое происходило когда-то и в других областях. Мне повезло, что я начал работать в Computer Science, когда эта сфера была в «подростковом» возрасте. Некоторые основы уже были заложены, но все было еще очень незрелое. Такая возможность появляется нечасто. Электротехника существует уже очень давно, физика — еще дольше, математика — чуть ли не с начала времён. Но это не значит, что в математике никто больше не делает интересных открытий. Открытых проблем по-прежнему множество, но в то же время и учиться нужно больше. Вы верно заметили, что сейчас значительно больше специализаций, чем было раньше, но это лишь значит, что мы оказались в той же ситуации, что и большинство остальных областей человеческой деятельности.

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

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

Виталий: А вы не могли бы намекнуть, о чём была эта лекция?

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

Становятся ли студенты глупее? Глобальные тренды, интернационализация.

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

Майкл: От нас, стариков, действительно можно услышать много негатива. Подсознательно у нас есть склонность ожидать, что студенты освоят весь тот 30-летний опыт, который уже есть у нас. Если у меня есть более глубокое понимание, чем в 1985 году, то почему его нет у студентов? Наверное, потому что им 20 лет, как вам такое? Думаю, наиболее существенные изменения в последние десятилетия касаются демографического состава: у нас сейчас значительно больше международных студентов, за исключением канадцев. Раньше канадцев было много, поскольку мы находимся очень близко к границе с Канадой, и студенты оттуда могут ездить домой на выходных. Но сейчас в Канаде много хороших университетов, и канадцы предпочитают учиться у себя, в США их стало ездить значительно меньше.

Алексей: Как вы думаете, это местный тренд или глобальный?

Майкл: Не помню точно кто, но кто-то сказал, что мир плоский. Наша область стала значительно более интернациональной. Конференции ACM раньше проходили исключительно внутри США, потом решили раз в 4 года проводить их в других странах, а сейчас они проходят по всему миру. Ещё в большей степени эти изменения коснулись IEEE, поскольку она всегда была более интернациональной организацией, чем ACM. А руководители программ (program chairs) есть из Китая, Индии, России, Германии и многих других стран, потому что везде сейчас очень много чего происходит.

Алексей: Но, вероятно, есть какие-то негативные стороны такой интернационализации?

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

Алексей: То есть барьеры и тому подобные вещи. Понятно.

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

Эффективная работа со студентами

Алексей: И как найти чёртов баланс между первым и вторым?

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

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

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

Виталий: И если ты ответил неверно, вылетаешь из класса 🙂

Майкл: Если ты не ответил ничего, то должен задать вопрос. Я должен понять, что именно студенту нужно знать, чтобы ответить на вопрос, который я только что задал. Нужно, чтобы они помогли мне помочь им. Я готов подстроиться под них, чтобы они разобрались в проблеме. Но если я не знаю, что происходит у них в голове, я не могу этого сделать. И если достаточно долго не давать студентам покоя, то в итоге иногда они задают правильные вопросы, то есть такие, благодаря которым я вижу, что именно происходит в головах у студентов. 

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

Майкл: Бывают вопросы, благодаря которым открывается новый способ подачи материала. Часто бывают вопросы, которые приводят к интересным проблемам, о которых я не планировал говорить. Студенты мне часто говорят, что у меня есть склонность уходить от темы занятия, когда такое происходит. И, согласно им, очень часто это бывает наиболее интересная часть занятия. Совсем редко, буквально несколько раз, студенты задавали вопросы, которые наталкивали на новое направление в исследовании и вырастали в статью. Это значительно чаще происходит в беседах со студентами, а не во время занятий, но изредка было и во время занятий. 

Алексей: То есть студенты задавали вам вопросы, на основе которых потом можно было опубликовать статью?

Майкл: Да. 

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

Майкл: С моими аспирантами — постоянно. У меня их где-то 5 или 6 человек, и мы всё время с ними что-то обсуждаем. А разговоры такого рода со студентами, которые просто посещают мои занятия — не слишком часто. Хотя хотелось бы, чтобы это происходило чаще. Подозреваю, что они просто боятся приходить на факультет в часы приёма. Каждый семестр некоторым студентам удаётся преодолеть этот психологический барьер, и с ними всегда очень интересно говорить после занятий. Правда, если бы все студенты были настолько же смелыми, у меня просто не хватило бы времени. Так что, возможно, всё работает так, как надо. 

Виталий: Как вам удаётся находить время для общения со студентами? Насколько я знаю, в США у преподавателей очень много работы — заявки на гранты и тому подобное. 

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

Как не отстать при подготовке новых курсов и книг.

Алексей: Продолжаете ли вы сейчас читать какие-либо курсы, которые вы читаете на протяжении длительного времени? Что-нибудь вроде введения в Computer Science.

Майкл: Первое, что здесь приходит в голову — курс языков программирования. 

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

Майкл: Мой курс языков программирования был несколько необычен в то время, когда я его создал. Я стал читать его в конце 1980-х, заменив моего коллегу, Дага Болдуина (Doug Baldwin). Тема курса лишь косвенно относилась к моей специализации, но когда он ушёл, я оказался лучшим кандидатом для проведения этого курса. Мне не нравился ни один из существовавших тогда учебников, поэтому я в конечном итоге сам написал учебник для этого курса. (Примечание редакции: речь идёт о книге «Programming Language Pragmatics») Сейчас он используется в более чем 200 университетах по всему миру. Мой подход необычен в том плане, что в нём сознательно смешиваются проблемы проектирования языка и его реализации, и большое внимание уделяется взаимодействию между этими аспектами во всех возможных областях. Основной подход остался неизменным, как и многие базовые понятия: абстракции, пространство имён, модульность, типы. А вот набор языков, при помощи которого эти понятия демонстрируются, поменялся целиком. Когда курс был только создан, в нём было множество примеров на Pascal, а сегодня многие мои студенты о таком языке даже не слышали. Зато они знают Swift, Go, Rust, поэтому я должен говорить о языках, которые в ходу сегодня. Кроме того, сейчас студенты хорошо разбираются в скриптовых языках, а когда я начинал преподавать этот курс, он целиком был посвящен компилируемым языкам. Сейчас же нужно много материала о Python, Ruby и даже Perl, потому что это то, на чём в наши дни пишут код, в этих языках происходит множество интересных вещей, в том числе в области проектирования языков. 

Виталий: Тогда мой следующий вопрос будет связан с предыдущим. Как не отстать в этой области? Я подозреваю, что обновлять такой курс требует большого объема работы — нужно разбираться в новых языках, понимать основные идеи. Как вам это удаётся?

Майкл: Я не могу похвастаться, что у меня это всегда на 100% получается. Но чаще всего я просто делаю то, что делают все остальные — читаю интернет. Если я хочу разобраться в Rust, я вбиваю его в Google, иду на страницу Mozilla и читаю выложенное там руководство. Это по части вещей, происходящих в коммерческой разработке. Если же говорить о науке, то здесь нужно следить за докладами на главных конференциях. 

Связь между бизнесом и академией

Виталий: Давайте поговорим о связи между бизнесом и научными исследованиями. В списке ваших работ я нашел несколько статей о согласованности кэша (cache coherence). Насколько я понимаю, во время их публикации алгоритмы согласованности кэша были нестабильными? Или недостаточно распространёнными. Насколько общепринятыми были ваши идеи на практике?

Майкл: Я точно не уверен, о каких именно публикациях вы говорите. Я довольно много работы проделал с моими студентами Биллом Болоски (William Bolosky) и Леонидасом Контотанассисом (Leonidas Kontothanassis) в начале 1990-х над управлением памятью машин Неймана. В то время в бизнесе ещё не было понимания того, как правильно сделать многопроцессорную систему: стоит ли создавать поддержку доступа к удалённой памяти на уровне железа, стоит ли делать память распределённой, можно ли выполнять загрузку кэша из удалённой памяти, или необходимо перемещать страницы в операционной системе. Билл и Леонидас оба работали в этой области и исследовали подходы без удалённой загрузки кэша. Это напрямую не относилось к согласованности кэша, но всё же это была работа над управлением памятью NUMA, и впоследствии из этого выросли современные подходы к page placement в современных операционных системах. В общем, Билл и Леонидас проделали важную работу, хотя и не наиболее влиятельную в это области — в то время над этим же трудилось много других людей. Позднее я занимался темой, связанной с согласованностью кэша в контексте аппаратной транзакционной памяти (hardware transactional memory). Группа, вместе с которой я работал над этой проблемой, получила в итоге несколько патентов. За ними стоят довольно интересные идеи, но я не думаю, что они в итоге получат практическую реализацию. Так или иначе, мне сложно судить об их прибыльности. 

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

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

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

Майкл: Практика всегда вращается вокруг того, что может иметь коммерческий успех, то есть создавать прибыль, и об этом вам лучше спросить кого-нибудь другого. Моя работа в основном заканчивается публикациями, а в области операционных систем они оцениваются по показателям производительности: скорость, потребление энергии, размер кода. Но мне всегда казалось, что эти эмпирические результаты добавляются в статьи только для того, чтобы их можно было опубликовать, а реальные мотивы для работы у людей эстетические. Исследователи оценивают решения с художественной стороны, им важно, насколько идеи элегантны, и они стараются создать нечто лучше, чем уже существующие подходы. Исследователями движут личные, субъективные, эстетические мотивы. Но в самой статье об этом не напишешь, для программного комитета эти вещи не являются аргументами. К счастью, элегантные решения чаще всего также оказываются быстрыми и дешёвыми. Мы вместе с десятком моих коллег обсуждали эту тему где-то 15 лет назад и в итоге написали написали об этом статью. Думаю, сейчас её ещё можно найти, она называется «How to evaluate systems research» или что-то в таком роде, у неё больше десятка авторов. Это единственная статья, в которой я автор вместе с Сашей Фёдоровой, так что если вы сделаете поиск её имени в моём списке публикаций, то найдёте то, что нужно. Там говорится об оценке исследований систем и о том, насколько важна элегантность. 

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

Майкл: Да, у нашей кафедры очень много разных интересных машин. Чаще всего они маленькие, у нас есть небольшой кластер и много многопроцессорных систем с разными ускорителями. Кроме того, на кампусе есть огромный вычислительный центр, который обслуживает учёных из нескольких десятков различных дисциплин. В нём около тысячи узлов и двадцати тысяч ядер, всё на Linux. Если возникает потребность, то всегда можно купить немного AWS. Так что с железом у нас существенных ограничений нет. 

Алексей: А как обстояло дело тридцать лет назад? Тогда проблемы были?

Майкл: Тогда было несколько иначе. В середине-конце 1980-х считалось, что науке не хватает вычислительных ресурсов. Чтобы исправить эту ситуацию, Национальный научный фонд (National Science Foundation) создал программу координированных экспериментальных исследований (Coordinated Experimental Research, CER). Задачей этой программы было предоставить вычислительную инфраструктуру для кафедр Computer Science, и она добилась существенных изменений. На предоставленные ею деньги мы в Рочестерском университете купили в 1984 году 128-узловый BBN Butterfly, это было за год до моего появления там. На тот момент это был самая большая в мире многопроцессорная система с общей памятью. У неё было 128 процессоров, каждый на отдельной материнской плате, она занимала четыре стойки. Каждый процессор имел мегабайт памяти, 128 мегабайт оперативной памяти в то время было невообразимым количеством. На этой машине мы впервые реализовали блокировку MCS. 

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

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

Практическая реализация идей. MCS, MS, CLH, JSR 166, работа с Дагом Ли и многое другое.

Виталий: Вы уже рассказали о том, как начали работать над алгоритмами синхронизации. У вас есть две очень известных статьи о блокировке MCS и очереди Майкла-Скотта (MS), которые в определённом смысле были реализованы в Java. (Примечание редакции: все публикации можно посмотреть по ссылке). Там эта блокировка была реализована с некоторыми изменениями и получилась блокировка CLH, а очередь была реализована как и задумывалась. Но между публикацией ваших статей и их практическим применением прошло много лет. 

Алексей: Кажется, около 10 лет в случае с очередью.

Майкл: Прежде чем эти фичи появились в стандартной библиотеке Java?

Виталий: Да. Что вы сделали для того, чтобы это произошло? Или ничего не делали?

Майкл: Я могу рассказать вам, как очередь MS попала в Java 5. За несколько лет до её появления я работал с группой Марка Мойерса (Mark Moyers) из Sun Microsystems в их лаборатории под Бостоном. Он организовал семинар для своих знакомых, занимавшихся интересными проблемами в многопоточности, поскольку он хотел найти темы, которые можно было бы продать их компании. Там я впервые встретил Дага Ли (Doug Lea). Даг, я и ещё где-то 25 других людей из Sun вместе обсуждали презентацию Дага о JSR 166, который впоследствие стал java.util.concurrent. По ходу дела Даг сказал, что он хотел бы использовать очередь MS, но для этого ему был необходим счётчик количества элементов в очереди для интерфейса. То есть это должен был делать отдельный метод, атомарный, точный и быстрый. Я предложил просто добавить серийные номера к узлам, взять номер первого узла и последнего и отнять один от другого. Даг почесал голову, сказал «почему бы и нет», и в итоге так и поступил. Мы обсуждали с ним реализацию этого подхода в библиотеке, но большую часть работы Даг сделал сам. В итоге ему удалось наладить отличную поддержку многопоточности в Java. 

Алексей: То есть если я правильно понимаю, метод .size() должен был входить в стандартный интерфейс очереди, и у него должна была быть алгоритмическая сложность O(1)?

Майкл: Да, и помимо этого необходим отдельный счётчик.

Алексей: Потому что если вызвать метод .size() в Java, ожидается, что результат будет доступен сразу же, а не в зависимости от реального размера коллекции. Понятно, спасибо.

Майкл: Несколькими годами позже я работал над двойными структурами данных (dual data structures) с моим студентом Биллом Шерером (Bill Scherer) — собственно, о них будет мой доклад на Hydra. Даг подошёл к нам и сказал, что они пригодились бы ему в Java Executor Framework. Вместе с Биллом они создали две реализации, так называемые честные и нечестные очереди (fair and unfair queues). Я консультировал их по этому проекту, хоть и не участвовал в написании собственно кода. В итоге скорость executors существенно увеличилась. 

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

Майкл: Единственный пример, в котором ко мне подошли и спросили «как реализовать» — это вопрос Дага, о котором я уже рассказывал. Но было несколько случаев, когда в соответствии с практическими нуждами вносились интересные изменения. Например, команда K42 из IBM конвертировала блокировку MCS и сделала стандартный интерфейс, благодаря которому не было необходимости передавать туда и обратно узел очереди подпрограммам acquire и release. Благодаря этому стандартному интерфейсу идея, красивая в теории, стала работать на практике. Удивительно, что они так и не опубликовали об этом статью, а патент хоть и получили, но потом от него отказались. Замысел был прекрасным, и я при возможности стараюсь о нём рассказывать. 

Были и другие случаи, когда люди вносили улучшения в опубликованные мной алгоритмы. Например, в очереди MS есть двухэтапный механизм установки, а это значило, что на критическом пути очереди было два CAS. На старых машинах CAS были довольно дорогими. В последнее время Intel и другие производители неплохо их оптимизировали, но когда-то это были инструкции с 30 циклами, поэтому больше одной на критическом пути иметь было нежелательно. В результате была разработана отличная очередь, которая была похожа на очередь MS, но у которой была только одна атомарная операция на критическом пути. Это достигалось благодаря тому, что в течение определённого промежутка времени операция могла занять O(n) времени, а не O(1). Это было маловероятно, но возможно. Происходило это из-за того, что в определённые моменты алгоритм совершал обход очереди с начала и до текущего положения в этой очереди. В целом, алгоритм получился очень удачный. Насколько я знаю, он не очень широко используется, отчасти потому, что атомарные операции требуют значительно меньше ресурсов, чем раньше. Но идея была отличная. Мне также очень нравится работа Дейва Дайса (Dave Dice) из Oracle. Всё, что он делает, очень практично, и он очень ловко использует железо. Он приложил руку к значительной части NUMA-aware алгоритмов синхронизации и многопоточных структур данных. 

Владимир: Когда вы пишете алгоритмы или учите студентов, результат работы виден не сразу. Сообществу нужно какое-то время, чтобы ознакомиться, скажем, с новой статьей. Новый алгоритм далеко не сразу находит себе применение. 

Майкл: Далеко на сразу понятно, окажется ли статья значимой или нет. Думаю, было бы интересно провести исследование статей, завоевавших награды на конференциях. То есть посмотреть на статьи, которые люди в программных комитетах в своё время сочли самыми лучшими. Нужно попробовать посчитать по количеству ссылок и по влиянию на бизнес, насколько эти статьи действительно оказалась влиятельными через 10, 20, 25 лет. Я сомневаюсь, что между этими двумя параметрами была бы сильная корреляция. Она не будет нулевая, но, скорее всего, она будет значительно слабее, чем хотелось бы. Многие идеи в течение долгого времени остаются невостребованными, прежде чем получают распространение. Например, возьмём транзакционную память. С момента публикации изначальной статьи до того времени, когда люди действительно стали создавать машины с ней, прошло больше 10 лет. А до появления этой памяти в коммерческих продуктах — и все 20. Очень долго на статью никто не обращал внимания, а потом резко выросло количество ссылок на неё. Заранее это предсказать было бы сложно. С другой стороны, иногда идеи находят реализацию сразу же. Несколько лет назад я написал статью вместе с Джо Израелевичем (Joe Izraelevitz) для DISC, в которой было предложено новое формальное определение правильности для персистентных структур данных, которые могли бы использоваться после сбоя работающего с ними компьютера. Статья мне нравилась с самого начала, но она оказалась значительно более популярной, чем я ожидал. Ей воспользовалось несколько различных групп, и в итоге она стала стандартным определением персистентных структур. Что, конечно, приятно.

Владимир: А есть ли какие-то приёмы, которые вы используете для оценки? Пытаетесь ли вы вообще оценивать свои статьи, своих студентов? В плане того, идёт ли человек, которого вы учили, в правильном направлении.

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

Транзакционная память

Виталий: Может, немного поговорим о транзакционной памяти?

Майкл: Думаю, стоит сказать хотя бы немного, потому что я вложил в это очень много усилий. Это тема, по которой у меня больше публикаций, чем по любой другой. Но при этом, как это ни странно, я всё время был весьма скептично настроен по отношению к транзакционной памяти. На мой взгляд, статья Херлихи и Мосса (M. Herlihy, J. E. B. Moss) была опубликована раньше своего времени. В начале 1990-х они предположили, что транзакционная память могла бы помочь талантливым программистам, работающим над многопоточными структурами данных, чтобы эти структуры затем в качестве библиотек могли бы использоваться обычными программистами. То есть это было бы подспорье для Дагов Ли, занимающихся своими JSR 166. Но транзакционная память не предназначалась для того, чтобы сделать многопоточное программирование простым. А ведь её именно так стали воспринимать в начале 2000-х, когда она получила распространение. Её рекламировали как способ решить проблему параллельного программирования. Этот подход мне всегда казался безнадежным. Транзакционная память могла только упростить написание параллельных структур данных. Этого она, как мне кажется, и достигла. 

О сложности написания многопоточного кода

Алексей: Очень интересно. Кажется, есть определённый барьер между обычными программистами и теми, кто может писать многопоточный код. В прошлом году я несколько раз общался с людьми, которые занимались реализацией некоторого алгоритмического фреймворка. Например, с Мартином Томсоном, а также с программистами, работающими над многопоточными библиотеками.  (Примечание редакции: Мартин Томпсон — очень известный разработчик, он написал Disruptor и Aeron. А ещё у него есть доклад на нашей конференции Joker 2015, видеозапись доступна на YouTube. Он же открывал эту конференцию, запись кейноута тоже достуна). По их словам, главная трудность в том, чтобы алгоритмы были одновременно быстрыми и простыми в использовании. То есть они пытаются как раз преодолеть этот барьер и привлечь как можно больше людей в эту область. Что вы об этом думаете?

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

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

Майкл: Здесь главное — правильно спроектированные абстракции. Мне кажется, что это вообще главное для компьютерных систем как области. Этот термин любит употреблять Батлер Лэмпсон (Butler Lampson), и нас он называет «торговцами абстракциями». Простых технологий сегодня не существует. В процессорах, которые мы используем, по 10 миллиардов транзисторов — о простоте тут речи быть не может. При этом ISA значительно проще процессора, поскольку мы очень долго работали над тем, чтобы обеспечить для неё высокую производительность и относительно простой интерфейс. Но и с ней не всё гладко. Та же проблема с ускорителями, которые сейчас появляются на рынке. Возникают вопросы — как сделать правильный интерфейс для GPU, механизм шифрования, сжатие, механизм перекодирования, механизм линейной алгебры или даже более гибкую FPGA. Как сделать интерфейс, который обеспечит простоту использования инструмента и скроет сложность? Не избавится от неё, а именно скроет от простого программиста. 

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

Майкл: Это хороший вопрос — действительно ли кто-либо из нас понимает модель памяти.

Виталий: В особенности в C++.

Майкл: Поговорите как-нибудь с Хансом Бёмом (Hans Boehm). Это один из самых умных людей, которых я знаю, ведущий эксперт по моделям памяти. Он вам сразу же скажет, что он очень многого там не понимает. Но если возвращаться к вопросу абстракций, то, на мой взгляд, самая важная мысль в области моделей памяти за последние 30 лет была высказана в диссертации Сарита Адве. (Примечание редакции: полный список публикаций есть по ссылке).

Алексей: Мой вопрос такой: происходит ли этот барьер из самой природы понятия? 

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

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

Майкл: Сходу ничего подобного не вспоминается. Бывало, когда мне казалось, что в некоторой сфере делать уже нечего, а потом там происходило что-то новое и интересное. Например, я думал, что в области неограниченных очередей уже достигнута зрелость. После нескольких улучшений для очереди MNS ничего особенного уже не происходило. А потом Моррисон (Adam Morrison) и Афек (Yehuda Afek) изобрели очередь LCRQ. Стало ясно, что возможна неограниченная многопоточная очередь, у которых большую часть времени на критическом пути была только инструкция fetch-and-increment. И это позволяло добиться на порядок лучшей производительности. Не то что бы мы не знали, что fetch-and-increment очень полезная вещь. Эрик Фрейдентал (Eric Freudenthal) писал об этом в своей работе об Ultracomputer c Аланом Готтлибом (Allan Gottlieb) в конце 1980-х, но там речь шла об ограниченных очередях. Моррисон и Афек смогли использовать fetch-and-increment в неограниченной очереди.

Новые архитектуры. Близка ли победа транзакционной памяти?

Владимир: Следите ли вы за новыми архитектурными решениями, которые могли бы быть полезны для алгоритмов? 

Майкл: Конечно, есть множество вещей, которые мне хотелось бы, чтобы были реализованы. 

Владимир: А какие, например?

Майкл: В первую очередь — несколько простых расширений для нашей транзакционной памяти аппаратного уровня в процессорах Intel и IBM. В особенности мне хотелось бы, чтобы не-транзакционные только что произошедшие load и store были сразу же доступны внутри транзакций. Они сразу же приводят к циклам в последовательности happens-before, так что с ними могут быть сложности. Но если поддерживать уровни абстракции, существует множество очень интересных вещей, которые можно сделать за пределами транзакции, пока она происходит. Я не знаю, насколько трудно это было бы реализовать, но это было бы очень полезно. 

Другая полезная вещь — загрузка кэша из удалённой памяти. Думаю, рано или поздно это будет сделано. Эта технология позволит создавать системы с дезагрегированной памятью. Можно будет держать, скажем, 100 терабайт энергонезависимой памяти в стойке, и операционная система сама будет динамически решать, какие разделы этой памяти должны соответствовать физическому адресному пространству процессоров. Это было бы крайне полезно для облачных вычислений, поскольку позволило бы предоставлять большие объемы памяти тем задачам, которые в ней нуждаются. Думаю, кто-нибудь это да сделает.

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

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

Энергонезависимая память, Optane DIMM, сверхбыстрые устройства.

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

Майкл: Я не эксперт по железу, я знаю только то, что читаю в новостях и что мне рассказывают коллеги. Все уже слышали, что Intel продаёт Optane DIMM, у которых где-то в 3 раза больше задержка чтения и в 10 раз больше задержка записи, чем у динамических RAM. В скором времени они будут доступны в версиях с очень большим объемом. Забавно думать о том, что можно будет иметь ноутбук с несколькими терабайтами адресуемой в байтах RAM. Вполне вероятно, что через 10 лет мы решим использовать эту новую технологию, так как мы используем DRAM — просто наращивать объёмы. Но благодаря энергонезависимости у нас открываются совершенно новые возможности. Мы можем в корне изменить стек хранения данных, чтобы не было разделения между адресуемой в байтах рабочей памятью и блочно-структурированной персистентной памятью. Таким образом, нам не нужно будет сериализовать в блочно-структурированные файлы всё, что нужно — перенести из одного запуска программы в другой. Из этого можно вывести множество важных принципов, влияющих на операционные системы, среды выполнения и распределенные хранилища данных. В этой области очень интересно работать. Лично мне сложно предсказать, во что это всё выльется, но проблемы здесь крайне занимательные. Возможно, здесь произойдут революционные изменения, и они очень естественным образом следуют из работы над многопоточностью, поскольку восстановление после сбоя является «многопоточным» процессом рядом с обычной работой системы. 

Вторая главная тема, над которой я сейчас работаю — это управление сверхбыстрыми устройствами и безопасный доступ к устройствам из юзерспейса с системным контролем над политикой. В последние годы наблюдается тренд перемещать доступ к устройству в юзерспейс. Это делается из-за того, что поверх сетевого интерфейса, которому нужен новый пакет каждые 5 микросекунд, не может функционировать TCP-IP стек ядра, он просто не будет успевать. Поэтому производители предоставляют прямой доступ к устройствам. Но это значит, что операционная система теряет контроль над процессом, и она не может обеспечить правильный доступ к устройству для соревнующихся приложений. Наша исследовательская группа считает, что этого недостатка можно избежать. На USENIX ATC в этом месяце будет наша статья об этом. Она связана с работой над персистентностью, поскольку долговечная адресуемая в байтах персистентная память является, в сущности, устройством со сверхбыстрым I/O, к которому нужно предоставить доступ в юзерспейсе. Эти исследования делают возможными новые подходы к микроядрам, экзоядрам и прочим другим традиционным попыткам безопасно перенести функциональность из ядра ОС в юзерспейс. 

Владимир: Адресуемая в байтах память — это прекрасно, но есть ведь физическое ограничение — скорость света. А это значит, что неизбежно будет задержка при взаимодействии с устройством. 

Майкл: Совершенно верно.

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

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

Владимир: Есть ещё одна проблема. Новые, значительно большие объемы RAM будет невозможно разместить в CPU. Поэтому из-за физических ограничений эта RAM должна быть изолированной. 

Майкл: Здесь всё зависит от количества дефектов при производстве интегральных схем. Если бы можно было создавать полупроводниковые пластины целиком без дефектов, то из неё можно было бы целиком сделать микросхему. Но сейчас мы не умеем делать микросхемы больше почтовых марок. 

Владимир: Но речь всё равно идёт об огромных размерах, о сантиметрах. Это неизбежно оказывает влияние на задержку. 

Майкл: Да. Со скоростью света ничего не поделаешь. 

Владимир: К сожалению. 

Следующий большой тренд. Dual data structures. Hydra.

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

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

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

Майкл: Отчасти мы уже затрагивали эти темы с вами в этом интервью. Речь пойдёт о работе, которую я вел с моим студентом Биллом Шерером. Он написал на основе неё диссертацию, и в ней также участвовал Даг Ли, а в конечном итоге она стала частью многопоточных синхронных очередей в библиотеке Java. Предположим, происходит чтение и запись в структуру данных без блокировки, то есть у каждой операции есть ограниченное число инструкций на критическом пути. Если попытаться изъять данные из пустого контейнера, или попытаться изъять определённые данные, которых в этом контейнере нет, то тут же сообщается, что это сделать невозможно. Но такое поведение может быть недопустимо, если эти данные очень нужны треду. Тогда первое, что приходит в голову — это создать цикл, который будет постоянно спрашивать, не появились ли необходимые данные. Но тогда возникают помехи для всех остальных. Кроме того, при таком подходе можно ждать 10 минут, а потом придёт какой-то другой тред, и он случайно получит необходимые данные первым. В двойных структурах данных по-прежнему нет блокировок, но они позволяют правильно организовать ожидание тредов. Термин «двойная» означает, что структура содержит либо данные, либо запросы на данные, назовём их анти-данные. Так что если попытаться извлечь что-то из пустого контейнера, то вместо этого в контейнер будет положен запрос. Теперь тред может ожидать запроса и при этом никого другого не беспокоить. Кроме того, структура данных назначает запросам приоритеты, так что при получении она передаёт их тому, кому следует. Получается механизм без блокировки, который при этом имеет формальную спецификацию и хорошую производительность на практике. 

Алексей: Какие ваши ожидания от этой структуры данных? Позволит ли она улучшить производительность во всех типичных случаях, или она лучше подходит для определённых ситуаций? 

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

Виталий: Позвольте уточнить: вы будете говорить об одном и том же и в школе, и на конференции?

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

Алексей: Планируете ли вы рассказать о двойных структурах данных в конце вашего занятия в школе?

Майкл: Я их упомяну, но много времени уделять им не буду. Им будет посвящен доклад на Hydra. Там будет рассказано о проекте, который в итоге вошёл в Java, а также о работе с Джо Израелевичем над созданием двойного варианта очереди LCRQ, и о создании почти универсальной конструкции для двойных структур данных.

Алексей: То есть лекцию в школе можно порекомендовать для новичков, а лекцию о двойных структурах данных на Hydra — для людей, уже имеющих какой-то опыт?

Майкл: Поправьте меня, если я не прав, но аудитория на Hydra будет довольно разноплановой, в том числе там будет много экспертов по Java, и вообще людей, которые специально многопоточным программированием не занимаются. 

Виталий: Да, это верно.

Алексей: По крайней мере, мы на это надеемся.

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

Виталий: Будете ли вы вести доклад так, как ведете лекции? То есть разговаривать с аудиторией и адаптироваться по ситуации?

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

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

Виталий: Спасибо. 

Майкл: Я буду рад встретиться с вами в Санкт-Петербурге. 

Алексей: Мы тоже, у нас красивый город. Вы здесь когда-нибудь были?

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

Алексей: Кстати, у нас будет программа экскурсий для докладчиков. Спасибо большое за интервью, и удачного вам дня!

Продолжить общение с Майклом можно будет на конференции Hydra 2019, которая пройдёт 11-12 июля 2019 года в Санкт-Петербурге. Он приедет с докладом «Dual data structures». Билеты можно приобрести на официальном сайте.

Источник: habr.com