Comments 30
Я не очень понял суть статьи, немогли бы вы разяснить зачем вы сравниваете Fetch-And-Add с Compare-And-Swap? Это не равнозначные операции, они не решают одну задачу — какой толк от этого сравнения?
Кроме того, используемые архитектуры не ограничиваются одним только x86, и атомарные операции не ограничваются CAS и FAA, есть еще например LL/SC (которые по общности, в отличие от FAA, на равне с CAS).
Кроме того, используемые архитектуры не ограничиваются одним только x86, и атомарные операции не ограничваются CAS и FAA, есть еще например LL/SC (которые по общности, в отличие от FAA, на равне с CAS).
В рамках реализации Java они делают к примеру, атомарные операции инкрементирования. Причем в разных версиях 7 и 8 соответственно используется CAS и FAA. То есть один и тот же код на разных версиях будет иметь разную производительность.
Перечитав статью я осознал, что вы сравниваеие не Fetch-And-Add с Compare-And-Swap, а две разные реализации Fetch-And-Add — моя ошибка, прошу прощения. Но все равно вопросы о ценности вашего сравнения остаются.
Во-первых, производительность одной атомарной операции совсем не обязательно значительно влияет на производительность всего алгоритма в целом.
Во-вторых, сама операция, которую вы тут измеряете в зависимости от условий будет иметь разную производительность даже на одной версии Java, например, если алгоритм использующий FAA (не важно как он реализован) спроектирован так идеально, что к атомарной переменной мы почти всегда обращаемся с одного CPU, то ее стоимость будет меньше, чем если за доступ к переменной одновременно борются много CPU.
В-третьих, как я уже писал, используемые архитектуры не ограничваются x86.
Отсюда вопрос, в чем ценность сравнения? В каком контексте ваши результаты окажутся применимыми?
Во-первых, производительность одной атомарной операции совсем не обязательно значительно влияет на производительность всего алгоритма в целом.
Во-вторых, сама операция, которую вы тут измеряете в зависимости от условий будет иметь разную производительность даже на одной версии Java, например, если алгоритм использующий FAA (не важно как он реализован) спроектирован так идеально, что к атомарной переменной мы почти всегда обращаемся с одного CPU, то ее стоимость будет меньше, чем если за доступ к переменной одновременно борются много CPU.
В-третьих, как я уже писал, используемые архитектуры не ограничваются x86.
Отсюда вопрос, в чем ценность сравнения? В каком контексте ваши результаты окажутся применимыми?
В 7 версии у нас используется цикл для атомарной установки нового значения переменной. Исходя из этого — в случае большой нагрузки и высокой конкурентности потоков мы будем ловить branch mispredict — ошибочное предсказание ветвления, который приводит, например, к перезагрузке конвейера процессора и всяким дополнительным издержкам, вроде out-of-order. В 8 версии мы полностью лишены цикла и всех связанных с ним издержек во время работы, таким образом получаем профит от использования новой версии и в моем понимании, все операции (то есть уже написанный код или системы), которые имеют атомарные операции с данными будут работать быстрее в каком-то определенном числе сценариев использования. Например, потокобезопасные коллекции иметь более высокую производительность. В моем понимании я вижу это так)) Поправьте, если я не так Вас понял)
все операции (то есть уже написанный код или системы), которые имеют атомарные операции с данными будут работать быстрее в каком-то определенном числе сценариев использования
Какой-то неопределенный ответ. Вы знаете хоть один конкретный алгоритм, который использует FAA и измеримо выиграет в производительности от перехода к Java 8 по причине изменения реализации FAA?
Кроме того, FAA все еще атомарная операция, так что для ее выполнения в архитектурах с когерентными кешами все равно придется повозиться, так что при высокой конкуренции совсем не факт что branch misprediction будет оказывать влияние по сравнению с накладными расходами на коммуникацию между CPU и поддержку когерентности. И эти расходы тем больше чем больше у вас ядер, а ваш low-voltage CPU из тестов не тянет на мощный CPU с кучей ядер (я абсолютно безосновательно предполагаю, что у вашего всего 2 настоящих ядра, каждое с HT). Т. е. на другой машине, возможно, и результаты другие.
CounterMonitor или LinkedBlockingQueue, например, использует FAA в своей реализации. Это в исходниках самой Java. Затем, да, вы совершенно правы, физически у меня 2 ядра на машине)). Однако, на своем опыте замечал, что результат от перехода есть, когда тестил один и тот же код в в своей программе на разных версиях JDK, когда изменения счетчика происходили с частотой 100-200 раз за секунду и испытания проводились на серверном процессоре, результат был в целом хороший. Конечно, там было не так много потоков (2-3), соревнующихся между собой, однако профит все же был.
Во-первых, откуда вы знаете, что выигрышь именно от реализации FAA, а не от каких-то других изменений при переходе от Java 7 к Java 8.
Во-вторых, эти измерения и стоило привести, измерения отдельно взятой операции не наглядны.
Во-вторых, эти измерения и стоило привести, измерения отдельно взятой операции не наглядны.
В целом на тот момент у меня производительность кода зависела как раз от FAA реализации. Это была часть системы (которую я сам полностью и писал) и для этой части у меня как раз был написан простой тест, который тупо отправлял данные в большом количестве и потом же забирал одновременно. По поводу измерений, в целом, возможно Вы и правы, но картина будет схожей, только пиковые значений выше. Но как появится возможность, я все же гляну на результаты на серверной машине ради интереса
Вы все воду льете, а я прошу конкретики. Конкретный код, конкретный сопособ измерения, конкретные результаты измерения. На каком основании был сделан вывод, что именно FAA — узкое место, или, как это часто бывает, «это было очевидно»?
Я не поверю ни в жизнь, что измерения реализации любого конкурентного алогритма, которой не посчастливилось использовать FAA будет давать схожую картину с измерениями отдельно взятой FAA. Так что хотелось бы таки услышать конкретики про то, где и как вы используете FAA, что она вдруг стала узким местом.
Я не поверю ни в жизнь, что измерения реализации любого конкурентного алогритма, которой не посчастливилось использовать FAA будет давать схожую картину с измерениями отдельно взятой FAA. Так что хотелось бы таки услышать конкретики про то, где и как вы используете FAA, что она вдруг стала узким местом.
Я согласен с Вами в том, что алгоритм, который стоит на FAA и отдельно взятый FAA не будут давать ну очень схожие результаты. По поводу конкретики, ждите после праздников как доберусь до рабочего места и сообщу Вам о результатах, потому как когда я готовил эту статью, я старался делать больше упор на общих вопросах и целью было донести разницу реализаций 7 и 8 версии и пытаться показать на очень простых примерах.
Да, на 4-х ядерной машине (с физическими и 8 виртуальными) наблюдалась схожая картина
есть еще например LL/SC (которые по общности, в отличие от FAA, на равне с CAS).
LL/SC круче CAS, поскольку оно не страдает от проблемы ABA.
Зачем декомпилировать Unsafe, если сорцы есть в OpenJDK?
Тесты не пробовали в JMH делать? Снимает многие вопросы к методологии.
И, кстати, для полноты обзора может в LongAdder ещё поглядеть? Если надо много добавлять и редко считывать общую сумму (частый сценарий при наборе всякой статистики), то должно быть существенно быстрее.
И про MESI бы пару общих слов. Не все знают, что такое "состояние E", и гуглить по букве E трудно.
Если вы используете типичную нагрузку CAS идиомы, предполагая нормальный snoop-base когерентности кэша (подслушивание или snooping, это часто употребимая реализация когерентности в многоядерных системах), то нагрузка может вызывать read-to-share транзакцию, чтобы получить основную строку кэша в S или состояние E. CAS, который имеет эффективную память семантик в отношении протоколов когерентности кэшей, может вызвать другую транзакцию шины, чтобы обновить линию для M состояния. Таким образом, в самом худшем случае идиома может подвергнуть шину двум транзакциям, но реализация XADD будет стремиться провести передачу линии непосредственно в M состоянии. В процессе вы могли бы спекулировать значениями и получать короткий путь, который пытается получить «голый» CAS без предварительных загрузок. К тому же, это возможно для сложных реализаций процессора для выполнения согласованных спекуляций и целевого исследования линии в M состоянии. Наконец, в некоторых случаях можно успешно вставить инструкцию предвыборка-для-записи (PREFETCHW) до нагрузки, чтобы избежать транзакции обновления. Но этот подход должен быть применен с тщательностью, так как в некоторых случаях это может принести больше вреда, чем пользы. Учитывая все это, XADD, где это возможно, имеет преимущество.
Вы не могли бы перевести этот текст до конца на русский? Действительно ли сказанное здесь вытекает из вышесказанного?
Вы имеете введу внести больше ясности в терминологию — про snoop-base, про MESI и прочее?
Дело не в терминологии, ваш перевод просто некорректен грамматически. И вообще по хорошему стоит приводить ссылку на оригинал.
Придерживаюсь вашего мнения, к сожалению среди знакомых нет людей с хорошим опытом перевода, чтобы корректировать недочеты. Поэтому, если есть возможность, прошу оказать мне помощь в столь деликатном деле))
Во-первых, если вы не можете переводить, то зачем беретесь.
Во-вторых, не нужно быть знатоком языков, чтобы увидеть, что текст из цитаты выше выглядит очень странно, достаточно более или менее знать русский.
В-третьих, не нужно переводить, если вы понимаете смысл, достаточно этот смысл описать своим языком.
Во-вторых, не нужно быть знатоком языков, чтобы увидеть, что текст из цитаты выше выглядит очень странно, достаточно более или менее знать русский.
В-третьих, не нужно переводить, если вы понимаете смысл, достаточно этот смысл описать своим языком.
Я имею в виду вот что: над списком, второй пункт которого я процитировал, вы написали: «Из выше сказанного. В результате, что мы имеем:». Но до этого вы ни разу не упоминали детали реализации такого низкого уровня. Я не вижу, как этот пункт вытекает из сказанного вами выше.
Если вы хотели сказать, что для того, чтобы сделать CAS нужно загрузить старое значение из памяти, что даёт два обращения к памяти, а чтобы сделать xadd старое значение загружать не нужно, и обращение к памяти нужно только одно, то можно было так и сказать.
Ну и про грамматику уже вам сказали.
Если вы хотели сказать, что для того, чтобы сделать CAS нужно загрузить старое значение из памяти, что даёт два обращения к памяти, а чтобы сделать xadd старое значение загружать не нужно, и обращение к памяти нужно только одно, то можно было так и сказать.
Ну и про грамматику уже вам сказали.
Ага, подкорректировал) Насчет изменений, хотел по идее оставить по протоколу MESI изменения, которые происходят, но в целом Ваш вариант мне понравился. Спасибо
Compare-And-Swap имеет эффективную память семантик по отношению к протоколам когерентности кэшей, что может вызвать другую транзакцию шины, чтобы обновить линию до M состояния.Нет не подкорректировали, в оригинале это предложение имеет следующий смысл: CAS операция, по сути, переводит кеш линию в состояние Modified, для чего может потребоваться дополнительная транзакция. Никакой эффективной памяти семантик в оригинальном тексте нет.
Ну как я понимаю это предложение, то тут подразумевается SMR — safe memory reclamation (отложенное физическое удаление) для решения проблем ABA-проблем? Поэтому использование «эффективное хранение семантики» не уместно? Или я что-то не так до конца понял?
The CAS, which effectively has store semantics with respect to the cache coherence protocol, may induce another bus transaction to upgrade the line to M state.Это оргинальное предложение. В нем нет ни слова про SMR, ABA и прочее, так что вы, очевидно, совершенно не понимаете это предложение. Фраза «effectively has store semantics» дословно переводится как «по сути (effectively), имеет семантику (has semantics) сохранения (store)», никакого «эффективного хранения семантики» там нет.
x86 уже 20 лет, со времен Pentium Pro, не лочат шину, все делается в M состоянии строки кеша.
И x86 процессоров, которые поддерживают cmpxchg, но не умеют xadd, не бывает. Обе инструкции появились в 486.
И x86 процессоров, которые поддерживают cmpxchg, но не умеют xadd, не бывает. Обе инструкции появились в 486.
Sign up to leave a comment.
Сравнение Lock-free алгоритмов — CAS и FAA на примере JDK 7 и 8