Почему переработка отсортированного массива быстрее, чем неотсортированный массив? | VPROS.ru

Почему переработка отсортированного массива быстрее, чем неотсортированный массив?

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

#include <algorithm> #include <ctime> #include <iostream> int main()
{ // Generate data const unsigned arraySize = 32768; int data[arraySize];
for (unsigned c = 0; c < arraySize; ++c) data[c] = std::rand() % 256;
// !!! With this, the next loop runs faster std::sort(data, data + arraySize);
// Test clock_t start = clock(); long long sum = 0; for (unsigned i = 0; i < 100000; ++i)
{ // Primary loop for (unsigned c = 0; c < arraySize; ++c)
{ if (data[c] >= 128) sum += data[c]; } }
double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << std::endl; std::cout << "sum = " << sum << std::endl; }

 

  • Без std::sort(data, data + arraySize); код выполняется за 11.54 секунд.
  • С отсортированными данными, код выполняется за 1.93 секунд.

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

import java.util.Arrays; import java.util.Random; public class Main { public static void main(String[] args)
{ // Generate data int arraySize = 32768; int data[] = new int[arraySize];
Random rnd = new Random(0); for (int c = 0; c < arraySize; ++c) data[c] = rnd.nextInt() % 256;
// !!! With this, the next loop runs faster Arrays.sort(data);
// Test long start = System.nanoTime(); long sum = 0; for (int i = 0; i < 100000; ++i)
{ // Primary loop for (int c = 0; c < arraySize; ++c)
{ if (data[c] >= 128) sum += data[c]; } }
System.out.println((System.nanoTime() - start) / 1000000000.0); System.out.println("sum = " + sum); } }

 

С несколько похожими, но менее драматический результат.

Первое, что пришло в голову это то, что приносит сортировки данных в кэш, но потом я понял, как это глупо, потому что массив был просто сгенерирован.

  • Что происходит?
  • Почему отсортированный массив быстрее, чем неотсортированный массив?
  • Код подводя некоторые независимые условия, и порядок не имеет значения.

One Reply to “Почему переработка отсортированного массива быстрее, чем неотсортированный массив?”

  1. Вышеизложенное поведение происходит из-за предсказания ветвлений.

    Чтобы понять предсказания ветвлений нужно сначала понять инструкцию трубопровода:

    Любые инструкции разбивается на последовательность шагов так, что различные действия могут быть выполнены одновременно, параллельно. Этот метод известен как инструкция трубопровода и используется для увеличения пропускной способности в современных процессорах. Чтобы понять это, лучше обратитесь к примеру https://en.wikipedia.org/wiki/Pipeline_(computing)#Concept_and_motivation

    Как правило, современные процессоры имеют довольно длинные трубопроводы, но для простоты рассмотрим только эти 4 действия.

    1. Если-выборка инструкции из памяти
    2. Идентификатор — декодировать инструкции
    3. Экс-выполнение инструкции
    4. Р — записать обратно в регистр процессора

    4-этап трубопровода в целом за 2 инструкции. 4-stage pipeline in general

    Переезд обратно на поставленный выше вопрос рассмотрим следующие инструкции:

                            A) if (data[c] >= 128)                                 /                                /                                 /                             true /       false                             /                                    /                                     /                                      /                             B) sum += data[c];          C) for loop or print(). 

    Без предсказания ветвлений следующие произойдут:

    Для выполнения инструкция инструкция B или C, то процессор будет ждать до инструкции не доходят до экс стадии в конвейере, как решение начать инструкция инструкция B или C зависит от результата обучения А. поэтому газопровод будет выглядеть так.

    когда если условие возвращает значение True: enter image description here

    Когда если условие возвращает значение false: enter image description here

    В результате жду результат обучения, общая тактов процессора, затраченное в вышеописанном случае(без предсказания ветвлений;как True и false) составляет 7.

    Так что такое предсказание ветвлений?

    Филиал будет предиктор пытается угадать в какую сторону ветку ( если-тогда-иначе структура) будет идти перед это известно точно. Он не будет ждать инструкции для достижения экс стадии конвейера, но это будет угадать решение и пойти на эту инструкцию(B или C в случае нашего примера).

    В случае правильного догадаться, трубопровод выглядит примерно так: enter image description here

    Если впоследствии будет обнаружено, что догадка была неверной затем частично исполненных поручений отбрасываются и трубопровода начинается с правильного филиала, неся задержкой. Время, которое тратится впустую в случае филиала misprediction равно числу стадий в трубопроводе от выборки этапе, до выполнения этапа. Современные микропроцессоры имеют тенденцию иметь довольно длинные трубопроводы так, что misprediction задержка между 10 и 20 тактов. Чем длиннее трубопровод тем больше потребность в хорошей филиал предсказатель. (https://en.wikipedia.org/wiki/Branch_predictor)

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

    1. Все элементы являются менее 128
    2. Все элементы, которые больше 128
    3. Некоторые новые элементы, начиная с менее чем 128 и позже это стало больше чем 128

    Предположим, что предсказатель всегда будет считать истинной ветви при первом запуске.

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

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

    Но в случае случайных несортированный массив, предсказание нужно будет отменить частично исполненных поручений и начать заново с правильной ветке большую часть времени и в результате больше ресурсов процессора по сравнению со отсортированный массив.

Comments are closed.