Array Reverse - XOR медленнее, чем переключение с временным объектом - PullRequest
Новая
       10

Array Reverse - XOR медленнее, чем переключение с временным объектом

1 голос
/ 24 февраля 2012

Я читал вопрос о самом быстром способе обращения к массиву (который оказался менее захватывающим), и я наткнулся на интересный комментарий, расположенный по ссылке здесь:

https://stackoverflow.com/a/1129028/857994

В указанном решении показаны следующие две возможности: 

//Possibility #1
void reverse(char word[])
{
    int len=strlen(word);
    char temp;
    for (int i=0;i<len/2;i++)
    {
            temp=word[i];
            word[i]=word[len-i-1];
            word[len-i-1]=temp;
    }
}

//Possibility #2
void reverse(char word[])
{
    int len=strlen(word);
    for (int i=0;i<len/2;i++)
    {
        word[i]^=word[len-i-1];
        word[len-i-1]^=word[i];
        word[i]^=word[len-i-1];
    }
}

и комментарий гласит: «Использование XOR будет намного медленнее, чем обмен с использованием временного объекта».

Никто не оспаривал это,Итак, мои вопросы:

  1. Это правда?
  2. Почему это правда?
  3. Будет ли все еще верно, если бы это был массив невстроенный тип?

1 Ответ

5 голосов
/ 24 февраля 2012

Цикл xor содержит 2 чтения в память и 1 запись в память на строку, всего 6 операций чтения и 3 записи для каждой итерации цикла. Кроме того, существует сильная зависимость между первой строкой, записывающей слово [i], и следующей строкой, читающей слово [i]. Это предотвратит конвейерную обработку, или, если две строки будут выполняться параллельно, чтение второй строки из слова [i] будет остановлено до завершения записи первой строки. Существует еще одна такая зависимость между 2-й и 3-й строками.

В цикле temp var временная переменная почти наверняка будет сохранена в регистре процессора, а не в основной памяти. Таким образом, общее количество операций ввода-вывода в памяти для цикла temp var составляет 2 чтения и 2 записи. Между операторами есть слабые зависимости потока данных, но они читаются перед записью, что может быть передано по конвейеру. Зависимости потока данных в примере xor - чтение-после-записи, что намного сложнее сделать без остановки конвейера.

6 операций чтения + 3 записи по сравнению с 2 операциями чтения + 2 записи. 2 + 2 имеет явное преимущество.

...