27 февраля 2013 г.

А почему компилятор не синхронизирует код за меня?

Основная гарантия, которую дает программисту JMM, это что программы без гонок (data race free) выполняются так, как будто они sequentially consistent. Гонки (data race), напомню, это пара чтение/запись или запись/запись одной переменной, когда операции в этой паре не упорядочены через happens-before. И чтобы их упорядочить, если они еще не, нужно добавить каких-то действий синхронизации.

...Но если это так, то почему бы компилятору самому не находить конфликтующие доступы к данным, и не расставлять бы самому в нужных местах упорядочивающие их барьеры? Да, мы потеряем возможность писать программы с гонками. Ну, проживем без эффективного String.hashCode(), да ленивых кэшей, уж перетопчимся как-нибудь. Зато сколько геммороя сразу пропадет! Большинство разработчиков рассуждают о своем коде исключительно в рамках неявно предполагаемой sequential consistency, хотя вообще-то чтобы так рассуждать, нужно сначала сделать программу корректно синхронизированной. Какое счастье и благолепие настало бы, если бы за этой магией следил бы компилятор, а?

Я давно об этом думал, а вот сегодня прямо явно наткнулся (выделение мое):

In fact, Shasha and Snir show that non-sequentially consistent results can only occur when there is a cycle in the graph of happens-before and conflict edges (if two accesses conflict, there is a conflict edge between them). Therefore, detecting where to place memory barriers is a matter of detecting these cycles, and placing memory barriers accordingly.
...Lee and Padua developed a similar compiler analysis, and showed that minimizing the number of memory barriers using their technique was NP-complete.
[Manson, Pugh, Adve]

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

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

4 комментария:

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

    ОтветитьУдалить
    Ответы
    1. Да, человек, в отличие от компилятора, способен переформулировать задачу, оказавшуюся слишком сложной для решения. Правда, креативности на это хватает не у всех.

      То, что она NP-полная и в самом деле не так важно -- задача эффективного распределения регистров тоже, кажется, NP-полная, что не мешает. Важнее, конечно, что она требует глобального анализа кода.

      Удалить
  2. В базе данных с этим тоже немало проблем, хотя и побольше инструментов для разруливания все же

    ОтветитьУдалить
    Ответы
    1. Мне кажется, в базах данных с этим проще потому что нет таких требований к скорости. Как правило, мы больше диском лимитированы, поэтому для чисто вычислительных задач простора больше.

      Удалить