...Но если это так, то почему бы компилятору самому не находить конфликтующие доступы к данным, и не расставлять бы самому в нужных местах упорядочивающие их барьеры? Да, мы потеряем возможность писать программы с гонками. Ну, проживем без эффективного
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-полная.
Мораль цитаты в том, что она отвечает на вопрос почему весь этот геморрой с синхронизацией вообще свалился на программиста — да просто компилятор с ним не справляется, вот и приходится привлекать могучий человеческий разум на помощь кремниевому арифмометру. Компилятор с программистом традиционно делят ответственность по-братски: компилятору что может, программисту все оставшееся.
То, что задача NP-полная не означает отсутствия приближенного алгоритма, который может быть достаточно эффективен, для практического применения. Человеческий разум скорее всего также не очень способен решать NP-полные задачи, вероятно мы находим какое-то приближенное решение.
ОтветитьУдалитьДа, человек, в отличие от компилятора, способен переформулировать задачу, оказавшуюся слишком сложной для решения. Правда, креативности на это хватает не у всех.
УдалитьТо, что она NP-полная и в самом деле не так важно -- задача эффективного распределения регистров тоже, кажется, NP-полная, что не мешает. Важнее, конечно, что она требует глобального анализа кода.
В базе данных с этим тоже немало проблем, хотя и побольше инструментов для разруливания все же
ОтветитьУдалитьМне кажется, в базах данных с этим проще потому что нет таких требований к скорости. Как правило, мы больше диском лимитированы, поэтому для чисто вычислительных задач простора больше.
Удалить