Подтвердить что ты не робот

Является ли разумная оптимизация для проверки того, сохраняет ли переменная определенное значение перед записью этого значения?

if (var != X)
  var = X;

Это разумно или нет? Будет ли компилятор всегда оптимизировать инструкцию if? Существуют ли какие-либо варианты использования, которые могли бы выиграть от оператора if?

Что делать, если var является изменчивой переменной?

Мне интересны как ответы на С++, так и Java, поскольку изменчивые переменные имеют разные семантики на обоих языках. Также JIT-компиляция Java может иметь значение.

Оператор if вводит разветвление и дополнительное чтение, которое не произошло бы, если бы мы всегда перезаписывали var с X, так что это плохо. С другой стороны, если var == X, то, используя эту оптимизацию, мы выполняем только чтение, и мы не выполняем запись, которая может иметь некоторые эффекты для кеша. Ясно, что здесь есть некоторые компромиссы. Я хотел бы знать, как это выглядит на практике. Кто-нибудь пробовал на этом тестирование?

EDIT:

Мне больше всего интересно, как это выглядит в многопроцессорной среде. В тривиальной ситуации, кажется, нет большого смысла в проверке переменной в первую очередь. Но когда согласованность кеша должна поддерживаться между процессорами/ядрами, дополнительная проверка может быть действительно полезной. Мне просто интересно, как это может повлиять на ситуацию? Также не должен ли процессор делать такую ​​оптимизацию? Если var == X присвоить его еще раз значение X не должно "загромождать" кеш. Но можем ли мы полагаться на это?

4b9b3361

ОТВЕТЫ

Ответ 1

Да, есть определенные случаи, когда это разумно, и, как вы полагаете, волатильные переменные являются одним из таких случаев - даже для однопоточного доступа!

Неустойчивые записи дороги, как с аппаратного, так и с точки зрения компилятора /JIT. На аппаратном уровне эти записи могут быть на 10x-100x дороже, чем обычная запись, так как буферы записи должны быть очищены (на x86 данные будут отличаться в зависимости от платформы). На уровне компилятора /JIT волатильная запись запрещает многие общие оптимизации.

Спекуляция, однако, может только получить вас до сих пор - доказательство всегда находится в бенчмаркинге. Вот микробиблиотека, которая пытается ваши две стратегии. Основная идея состоит в том, чтобы скопировать значения из одного массива в другой (в значительной степени System.arraycopy), с двумя вариантами, которые копируются безоговорочно, и проверяет, отличаются ли значения друг от друга.

Ниже приведены процедуры копирования для простого, энергонезависимого случая (полный источник здесь):

        // no check
        for (int i=0; i < ARRAY_LENGTH; i++) {
            target[i] = source[i];
        }

        // check, then set if unequal
        for (int i=0; i < ARRAY_LENGTH; i++) {
            int x = source[i];
            if (target[i] != x) {
                target[i] = x;
            }
        }

Результаты с использованием приведенного выше кода для копирования длины массива 1000 с использованием Caliper в качестве моей проводки для микрообнаружения:

    benchmark arrayType    ns linear runtime
  CopyNoCheck      SAME   470 =
  CopyNoCheck DIFFERENT   460 =
    CopyCheck      SAME  1378 ===
    CopyCheck DIFFERENT  1856 ====

Это также включает в себя около 150 нс накладных расходов за каждый запуск до reset целевого массива. Пропуск проверки выполняется намного быстрее - около 0,47 нс на элемент (или около 0,32 нс на элемент после того, как мы удалим накладные расходы на установку, так что почти точно 1 цикл на моем ящике).

Проверка примерно на 3 раза медленнее, когда массивы одинаковы, а в 4 раза медленнее, чем другие. Я удивлен тем, насколько плохо проверен, учитывая, что он отлично предсказан. Я подозреваю, что виновником является в значительной степени JIT - с гораздо более сложным телом цикла, его можно развернуть меньше раз, а другие оптимизации могут не применяться.

Перейдите в неустойчивый корпус. Здесь я использовал AtomicIntegerArray как мои массивы летучих элементов, так как Java не имеет типов собственных массивов с летучими элементами. Внутри этот класс просто пишет прямо к массиву с помощью sun.misc.Unsafe, что позволяет волатильную запись. Сгенерированная сборка по существу аналогична нормальному доступу к массиву, за исключением изменчивого аспекта (и, возможно, устранения пробега в диапазоне, что может быть неэффективным в случае AIA).

Здесь код:

        // no check
        for (int i=0; i < ARRAY_LENGTH; i++) {
            target.set(i, source[i]);
        }

        // check, then set if unequal
        for (int i=0; i < ARRAY_LENGTH; i++) {
            int x = source[i];
            if (target.get(i) != x) {
                target.set(i, x);
            }
        }

И вот результаты:

arrayType     benchmark    us linear runtime
     SAME   CopyCheckAI  2.85 =======
     SAME CopyNoCheckAI 10.21 ===========================
DIFFERENT   CopyCheckAI 11.33 ==============================
DIFFERENT CopyNoCheckAI 11.19 =============================

Столы повернулись. Сначала проверка выполняется на 3,5 раза быстрее обычного метода. Все происходит намного медленнее - в чеке мы платим ~ 3 нс за цикл, а в худших случаях ~ 10 нс (время выше в нас и покрывает копию всего массива элементов 1000). Волатильные записи действительно дороже. В разделе DIFFERENT содержится около 1 нс надкласса, в reset массива на каждой итерации (поэтому даже простой является немного медленнее для DIFFERENT). Я подозреваю, что большая часть накладных расходов в случае "проверки" фактически проверяется на границах.

Это все однопоточное. Если у вас на самом деле было многопользовательское противоречие по поводу летучих, результаты были бы намного хуже для простого метода и были бы примерно такими же хорошими, как выше для проверки (линия кэша просто сидела в общем состоянии - no необходим когерентный трафик).

Я также тестировал только экстремумы "каждый элемент равен" и "каждый элемент разный". Это означает, что ветвь в "контрольном" алгоритме всегда отлично предсказана. Если бы у вас было сочетание одинаковых и разных, вы бы не получили просто взвешенную комбинацию времени для ОДНОГО И РАЗЛИЧНЫХ случаев - вы делаете хуже, из-за неверного предсказания (как на аппаратном уровне, так и, возможно, на уровне JIT, который больше не может оптимизировать для всегда взятой ветки).

Так ли это разумно, даже для volatile, зависит от конкретного контекста - сочетание равных и неравных значений, окружающего кода и т.д. Обычно я не делал этого для волатильности в одиночном сценарии, если не подозревал, что большое количество наборов является избыточным. Однако в сильно многопоточных структурах чтение, а затем выполнение изменчивой записи (или другой дорогостоящей операции, такой как CAS), является лучшей практикой, и вы увидите его качественный код, например java.util.concurrent.

Ответ 2

Является ли разумная оптимизация проверкой, сохраняет ли переменная определенное значение перед записью этого значения?

Есть ли какие-либо варианты использования, которые могли бы выиграть от оператора if?

Это когда назначение значительно дороже, чем сравнение неравенства, возвращающее false.

Примером может быть большой * std::set, который может потребовать дублирования двух кучей.

** для некоторого определения "большого" * ​​

Будет ли компилятор всегда оптимизировать инструкцию if?

Это довольно безопасное "нет", как и большинство вопросов, которые содержат как "оптимизацию", так и "всегда".

Стандарт С++ редко упоминает об оптимизации, но никогда не требует этого.

Что делать, если var является изменчивой переменной?

Затем он может выполнить if, хотя volatile не достигает того, что большинство людей предполагает.

Ответ 3

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

Ответ 4

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

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

Если ветвь довольно непредсказуема, хотя она, вероятно, еще медленнее.

Ответ 5

В С++ назначение переменной SIMPLE (т.е. нормальное целое число или переменная float) определенно и всегда быстрее, чем проверка того, имеет ли оно это значение, а затем устанавливает его, если оно не имеет значения. Я был бы очень удивлен, если бы это было неверно и в Java, но я не знаю, насколько сложны или простые вещи в Java - я написал несколько сотен строк и на самом деле не изучал, как байт-код и JITed байт-код фактически работает.

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

if (current_process != new_process_to_run)
     current_process == new_process_to_run;

Потому что здесь "процесс" представляет собой сложный объект для изменения, но != может быть выполнен по идентификатору процесса.

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

volatile должен всегда заставлять компилятор считывать и записывать значения в переменную, независимо от того, "она" думает "нужно" или нет, поэтому она обязательно ПРОЧИТАЕТ переменную и НАПРАВЛЯЕТ эту переменную. Конечно, если переменная volatile, это, вероятно, означает, что она может меняться или представлять какое-то оборудование, поэтому вы должны быть ДОПОЛНИТЕЛЬНЫ осторожны с тем, как вы тоже относитесь к этому... Дополнительное чтение карты PCI-X может привести к нескольким (циклы шины на порядок медленнее, чем скорость процессора!), что, скорее всего, повлияет на производительность. Но тогда запись в аппаратный регистр может (например) заставить аппаратное обеспечение сделать что-то неожиданное и проверить, что у нас это значение сначала МОЖЕТ сделать это быстрее, потому что "какая-то операция начинается" или что-то в этом роде.

Ответ 6

Было бы разумно, если бы у вас была семантика блокировки чтения и записи, когда чтение обычно было менее разрушительным, чем запись.

Ответ 7

В Objective-C у вас возникает ситуация, когда присвоение адреса объекта переменной-указателю может потребовать, чтобы объект был "сохранен" (количество отсчетов увеличивалось). В этом случае имеет смысл увидеть, является ли назначенное значение таким же, как значение, находящееся в настоящее время в переменной указателя, чтобы избежать необходимости относительно дорогостоящих операций приращения/уменьшения.

Другие языки, которые используют подсчет ссылок, вероятно, имеют похожие сценарии.

Но при назначении, например, int или boolean простой переменной (вне сценария многопроцессорного кеша, упомянутой в другом месте), тест редко заслуживает внимания. Скорость хранения в большинстве процессоров по крайней мере такая же быстрая, как и load/test/branch.

Ответ 8

В java ответ всегда нет. Все назначения, которые вы можете выполнять на Java, являются примитивными. В С++ ответ по-прежнему почти всегда нет - если копирование намного дороже, чем проверка равенства, рассматриваемый класс должен выполнить эту проверку равенства.