Различия в доступе / записи в массиве?

Question

Вероятно, это зависит от языка, но в целом, какова разница в производительности между доступом и записью в массив?

Например, если я пытаюсь написать простое сито и представляю простые числа как логический массив.

Найдя простое число, я могу сказать

for(int i = 2; n * i < end; i++)
{
    prime[n * i] = false;
}

или

for(int i = 2; n * i < end; i++)
{
    if(prime[n * i])
    {
        prime[n * i] = false;
    }
}

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

Answer 1

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

1. Во втором примере вы должны получить значение из ОЗУ в кэш-память L2 / L1 и прочитать его в регистр, получить значение и записать его обратно. В первом случае вы могли бы легко записать значение в кэш L1 / L2. Это может быть записано в RAM из кешей позже, пока ваша программа делает что-то еще.

2. Вторая форма имеет гораздо больше кода для выполнения за одну итерацию. При достаточно большом количестве итераций разница очень быстро увеличивается.

Answer 2

В целом это зависит гораздо больше от машины, чем от языка программирования. Зачастую для записи требуется несколько дополнительных тактов, поскольку в зависимости от машины в памяти необходимо обновить больше значений кэша.

Однако ваш второй сегмент кода будет ОЧЕНЬ медленнее, и не только потому, что «больше кода». Основная причина в том, что каждый раз, когда вы используете оператор if на большинстве машин, процессор использует предиктор ветвления. Процессор буквально предсказывает, каким образом оператор if будет выполняться раньше времени, и, если он не верен, он должен вернуться назад. См. http://en.wikipedia.org/wiki/Pipeline_%28computing%29 и http://en.wikipedia.org/wiki/Branch_predictor, чтобы понять, почему.

Если вы хотите провести оптимизацию, я бы порекомендовал следующее:

• Профиль! Посмотрите, что на самом деле занимает время.
• Умножение намного сложнее, чем сложение. Попробуйте переписать цикл так, чтобы i + = n, и используйте это для индекса массива.
• Условие цикла «следует» полностью переоценивать на каждой итерации, если компилятор не оптимизирует его. Поэтому постарайтесь избегать умножения там.
• Использовать -O2 или -O3 в качестве опции компилятора
• Вы можете обнаружить, что некоторые значения n быстрее других из-за локальности кэша. Вы можете подумать о некоторых умных способах переписать ваш код, чтобы воспользоваться этим.
• Разберите код и посмотрите, что он на самом деле делает на вашем процессоре

Answer 3

Это сложный вопрос, и он сильно зависит от вашего оборудования, ОС и компилятора.Но ради теории вы должны рассмотреть две вещи: ветвление и доступ к памяти.Поскольку ветвление обычно является злом, вы хотите избежать этого.Я даже не удивлюсь, если бы произошла некоторая оптимизация компилятора, а ваш второй фрагмент был бы сведен к первому (компиляторы любят избегать веток, они, вероятно, считают это хобби, но у них есть причина).Таким образом, в этих терминах первый пример намного чище и с ним легче иметь дело.

Существуют также кэши ЦП и другие проблемы, связанные с памятью.Я полагаю, что в обоих примерах вам необходимо загрузить память в кэш ЦП, чтобы вы могли либо прочитать ее, либо обновить.Хотя чтение не является проблемой, письмо должно распространять изменения вверх.Я не буду беспокоиться, если вы используете функцию в одном потоке (как указал @gby, ОС может внести изменения чуть позже).

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