Когда я проверяю разницу во времени между сдвигом и умножением на C, нет никакой разницы. Зачем?

Мне научили, что смещение в двоичном коде намного эффективнее, чем умножение на 2 ^ k. Поэтому я хотел поэкспериментировать, и я использовал следующий код, чтобы проверить это:

#include <time.h>
#include <stdio.h>

int main() {
    clock_t launch = clock();
    int test = 0x01;
    int runs;

    //simple loop that oscillates between int 1 and int 2
    for (runs = 0; runs < 100000000; runs++) {


    // I first compiled + ran it a few times with this:
    test *= 2;

    // then I recompiled + ran it a few times with:
    test <<= 1;

    // set back to 1 each time
    test >>= 1;
    }

    clock_t done = clock();
    double diff = (done - launch);
    printf("%f\n",diff);
}

Для обеих версий распечатка была приблизительно 440000, дала или принимала 10000. Не было (по крайней мере, визуально, по крайней мере) существенного различия между выходами двух версий. Итак, мой вопрос: есть ли что-то не так с моей методологией? Должна ли быть визуальная разница? Связано ли это с архитектурой моего компьютера, компилятора или чего-то еще?

28 голосов | спросил NicholasFolk 21 J000000Monday14 2014, 23:31:05

11 ответов


44

Как сказано в другом ответе, большинство компиляторов автоматически оптимизируют умножения, которые должны выполняться с помощью бит-брейков.

Это очень общее правило при оптимизации: Большинство «оптимизаций» фактически ошибочно скомпилируют компиляцию о том, что вы на самом деле имеете в виду, и, возможно, даже уменьшите производительность.

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

Большой недостаток в оптимизации заключается в том, что «оптимизированный» код часто гораздо менее читабельен. Таким образом, в вашем случае всегда используйте умножение, когда вы пытаетесь размножаться. И переходите к смещению бит, когда хотите переместить бит.

ответил Thirler 21 J000000Monday14 2014, 23:39:19
25

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

ответил ddyer 21 J000000Monday14 2014, 23:33:14
21

Независимо от того, будет ли переход быстрее, чем умножение, зависит от архитектуры вашего процессора. Еще во времена Pentium и ранее смещение часто было быстрее, чем умножение, в зависимости от количества 1 бит в вашем мультипликаторе. Например, если ваш множитель был 320, это 101000000, два бита.

a *= 320;               // Slower
a = (a<<7) + (a<<9);    // Faster

Но если у вас было более двух бит ...

a *= 324;                        // About same speed
a = (a<<2) + (a<<7) + (a<<9);    // About same speed

a *= 340;                                 // Faster
a = (a<<2) + (a<<4) + (a<<7) + (a<<9);    // Slower

На небольшом микроконтроллере, как PIC18 с однократным умножением, но не barrel shifter , умножение происходит быстрее, если вы перемещаетесь более чем на 1 бит.

a  *= 2;   // Exactly the same speed
a <<= 1;   // Exactly the same speed

a  *= 4;   // Faster
a <<= 2;   // Slower

Обратите внимание, что это напротив того, что было на старых процессорах Intel.

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

a  *= 4;   // 
b  *= 4;   // 

a <<= 2;   // Both lines execute in a single cycle
b <<= 2;   // 
ответил Rocketmagnet 22 J000000Tuesday14 2014, 15:51:00
11

У вас есть несколько проблем с вашей тестовой программой.

Во-первых, вы фактически не используете значение test. В стандарте C нет способа, чтобы значение test имело значение. Оптимизатор полностью освобождает его. После его удаления ваш цикл фактически пуст. Единственным видимым эффектом было бы установить runs = 100000000, но runs также не используется. Поэтому оптимизатор может (и должен!) Удалять весь цикл. Простое исправление: также распечатайте вычисленное значение. Обратите внимание, что достаточно определенный оптимизатор все еще может оптимизировать цикл (он полностью опирается на константы, известные во время компиляции).

Во-вторых, вы выполняете две операции, которые отменяют друг друга. Оптимизатору разрешено заметить это и отменить их . Снова выйдем из пустой петли и удалим. Это очень трудно исправить. Вы можете переключиться на unsigned int (поэтому переполнение не является неопределенным поведением), но это, конечно, просто приводит к 0. И простые вещи ( например, test += 1) достаточно легки, чтобы оптимизатор мог это выяснить, и он делает.

Наконец, вы предполагаете, что test *= 2 на самом деле собирается скомпилироваться для умножения. Это очень простая оптимизация; если битдвиг быстрее, оптимизатор будет использовать его вместо этого. Чтобы обойти это, вам нужно использовать что-то вроде встроенной в реализацию сборки.

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

Когда я проверил вывод сборки компиляции вашей программы с помощью gcc -S -O3, используя версию 4.9, оптимизатор действительно видел все простые варианты выше, и еще несколько. Во всех случаях он удалял цикл (назначая константу test), оставалось только обращение к clock(), преобразование /вычитание и printf.

ответил derobert 23 J000000Wednesday14 2014, 01:58:55
8

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

В результате относительное время выполнения сдвига и умножения не имеет ничего общего с C. Когда я говорю C, я не имею в виду экземпляр конкретной реализации, такой как ту или иную версию GCC, но язык. Я не хочу принимать это объявление абсурдом, но для использования крайнего примера для иллюстрации: вы можете реализовать полностью совместимый со стандартом компилятор C и умножить его на один час, а сдвиг займет миллисекунды - или наоборот. Я не знаю каких-либо ограничений производительности на C или C ++.

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

Здесь присутствуют комментарии, которые ставят под сомнение полезность замены этой эквивалентности в программном обеспечении реального мира. Вы можете увидеть некоторые из комментариев к вашему вопросу, например, от Эрика Липперта. Это соответствует реакции, которую вы обычно получаете от более опытных инженеров в ответ на такую ​​оптимизацию. Если вы используете двоичные сдвиги в производственном коде в качестве основного средства умножения и деления, люди, скорее всего, съедят ваш код и будут испытывать некоторую эмоциональную реакцию («Я слышал это бессмысленное утверждение, сделанное по поводу JavaScript на небесах».), Чтобы это может не иметь смысла для начинающих программистов, если они не понимают причины этих реакций.

Эти причины в первую очередь представляют собой комбинацию уменьшенной читаемости и тщетности такой оптимизации, поскольку вы, возможно, уже выяснили, сравнивая их относительную производительность. Однако я не думаю, что у людей была бы такая сильная реакция, если бы замена сдвига для умножения была единственным примером таких оптимизаций. Вопросы, подобные вашим, часто возникают в различных формах и в разных контекстах. Я думаю, что более старшие инженеры на самом деле реагируют так сильно, по крайней мере, иногда я имею в виду, что существует потенциал для гораздо более широкого диапазона вреда, когда люди используют такую ​​микро-оптимизацию на основе кодовой базы. Если вы работаете в такой компании, как Microsoft, на большой базе кода, вы потратите много времени на чтение исходного кода других инженеров или попытаетесь найти там определенный код. Это может быть даже ваш собственный код, который вы будете пытаться понять через несколько лет, особенно в некоторые из самых неподходящих времен, например, когда вам нужно исправить производственный отрыв после звонка, который вы получили на пейджере долг в пятницу вечером, собираюсь отправиться на ночь веселья с друзьями ... Если вы потратите столько времени на чтение кода, вы оцените его как можно более читабельное. Представьте себе, что читаете свой любимый роман, но издатель решил выпустить новую версию, где они используют abbrv. все ovr th plc bcs your thnk it svs spc. Это сродни реакциям, которые другие инженеры могут иметь для вашего кода, если вы покроете их такими оптимизациями. Как указывали другие ответы, лучше четко указать, что вы имеете в виду, что использует операцию в коде, семантически близкую к тому, что вы пытаетесь выразить в идее.

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

Почему вы не видели разницу в скорости в C? Наиболее вероятный ответ заключается в том, что он привел к одному и тому же ассемблеру:

int shift(int i) { return i << 2; }
int multiply(int i) { return i * 2; }

Можно ли скомпилировать в

shift(int):
    lea eax, [0+rdi*4]
    ret

В GCC без оптимизации, то есть с использованием флага «-O0», вы можете получить следующее:

shift(int):
    push    rbp
    mov rbp, rsp
    mov DWORD PTR [rbp-4], edi
    mov eax, DWORD PTR [rbp-4]
    sal eax, 2
    pop rbp
    ret
multiply(int):
    push    rbp
    mov rbp, rsp
    mov DWORD PTR [rbp-4], edi
    mov eax, DWORD PTR [rbp-4]
    add eax, eax
    pop rbp
    ret

Как вы можете видеть, передача «-O0» в GCC не означает, что он не будет немного сообразить, какой код он производит. В частности, обратите внимание, что даже в этом случае компилятор избегал использования команды умножения. Вы можете повторить тот же эксперимент со сдвигами по другим числам и даже умножениями по числам, которые не являются степенями двух. Скорее всего, на вашей платформе вы увидите комбинацию сдвигов и дополнений, но не умножений. Похоже, что компилятор, по-видимому, избегает использования умножений во всех этих случаях, если умножения и сдвиги действительно имеют одинаковую стоимость, не так ли? Но я не хочу предлагать доказательства для доказательства, поэтому давайте двигаться дальше.

Вы можете повторно запустить свой тест с приведенным выше кодом и посмотреть, заметили ли вы сейчас разницу в скорости. Даже тогда вы не тестируете сдвиг и умножение, как вы можете видеть из-за отсутствия умножения, но код, который был сгенерирован с определенным набором флагов GCC для операций C сдвига и умножения в конкретный экземпляр . Итак, в другом тесте вы можете отредактировать код сборки вручную и вместо этого использовать команду «imul» в коде для метода «multiply».

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

int shift(int i, int j) { return i << j; }
int multiply(int i, int j) { return i * j; }

Что может привести к следующему ассемблеру:

shift(int, int):
    mov eax, edi
    mov ecx, esi
    sal eax, cl
    ret
multiply(int, int):
    mov eax, edi
    imul    eax, esi
    ret

Здесь мы, наконец, имеем даже на самом высоком уровне оптимизации GCC 4.9 выражение в инструкциях по сборке, которое вы, возможно, ожидали, когда вы изначально указали на свой тест. Я думаю, что сам по себе может стать важным уроком в оптимизации производительности. Мы можем видеть разницу, которую он сделал для замены переменных для конкретных констант в нашем коде, с точки зрения умений, которые компилятор может применить. Микрооптимизации, такие как замена с заменой сдвига, - это некоторые очень низкоуровневые оптимизации, которые компилятор обычно легко делает сам по себе. Другие оптимизации, которые намного более влияют на производительность, требуют понимания намерения кода , который часто недоступен компилятору или может быть угадан только некоторой эвристикой. Именно здесь вы, как разработчик программного обеспечения, входят, и это, конечно, обычно не предполагает замены умножений на сдвиги. Он включает такие факторы, как отказ от избыточного вызова службы, которая производит ввод-вывод и может блокировать процесс. Если вы перейдете на свой жесткий диск или, боже упаси, в удаленную базу данных для некоторых дополнительных данных, которые вы могли бы получить из того, что у вас уже есть в памяти, время ожидания ожидания перевешивает выполнение миллиона инструкций. Теперь я думаю, что мы немного отклонились от вашего первоначального вопроса, но я думаю, что это указывает на вопросника, особенно если мы предполагаем, что кто-то, кто только начинает понимать перевод и выполнение кода, может быть чрезвычайно важным для решения не только самого вопроса, но и многих его(возможно) лежащих в основе предположений.

Итак, какой из них будет быстрее? Я думаю, что это хороший подход, который вы выбрали для проверки разницы в производительности. В общем, легко удивляться быстродействию некоторых изменений кода. Существует много технологий, используемых современными процессорами, и взаимодействие между программным обеспечением также может быть сложным. Даже если вы должны получить полезные результаты для определенных изменений в одной ситуации, я думаю, что было бы опасно заключить, что такой тип изменений всегда будет давать преимущества в производительности. Я думаю, что один раз опасно запускать такие тесты, сказать: «Ладно, теперь я знаю, что быстрее!» и затем без разбора применяют эту же оптимизацию к производственному коду без повторения ваших измерений.

Итак, что, если сдвиг быстрее, чем умножение? Есть определенные указания, почему это было бы правдой. GCC, как вы можете видеть выше, кажется, думает (даже без оптимизации), что избежать прямого умножения в пользу других инструкций является хорошей идеей. Архитектуры Intel 64 и IA-32 Справочное руководство по оптимизации даст вам представление об относительной стоимости инструкций ЦП. Другой ресурс, более сфокусированный на латентности и пропускной способности команды, - это http://www.agner.org/оптимизировать /instruction_tables.pdf . Обратите внимание, что они не являются хорошим предикатором абсолютного времени исполнения, а выполняют инструкции относительно друг друга. В плотной петле, когда ваш тест моделируется, метрика «пропускная способность» должна быть наиболее актуальной. Это число циклов, в течение которого исполнительный блок обычно будет привязан для выполнения данной команды.

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

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

В данном случае объясняется Barrel Shifter . Документы, на которые я ссылался в предыдущем абзаце, дают другое представление об относительной стоимости операций, по доверенности инструкциям ЦП. У инженеров, работающих в Intel, часто возникают похожие вопросы: форумы форумов разработчиков Intel тактовые циклы для целочисленного умножения и добавления в процессор Core 2 Duo

Да, в большинстве реальных сценариев и, почти наверняка, в JavaScript, попытка использовать эту эквивалентность для производительности, вероятно, является бесполезной задачей. Однако, даже если мы вынудили использовать умножениеа затем не видел разницы во времени выполнения, что больше связано с характером используемой нами метрики затрат, а точнее, а не потому, что нет никакой разницы в стоимости. Сквозное время выполнения - это одна метрика, и если это единственный, о котором мы заботимся, все хорошо. Но это не означает, что все различия в стоимости между умножением и сдвигом просто исчезли. И я думаю, что это, конечно, не очень хорошая идея, чтобы передать эту идею допрашивающему, подразумевая или иначе, который, очевидно, только начинает задумываться о факторах, связанных с временем выполнения и стоимостью современного кода. Техника всегда связана с компромиссами. Запрос и объяснение того, что компромиссы современных процессоров заставили показать время выполнения, которое мы, как пользователи, видим, могут дать более дифференцированный ответ. И я думаю, что более дифференцированный ответ, чем «это просто неправда больше», оправдан, если мы хотим, чтобы меньше инженеров проверяли в микро-оптимизированном коде стирающую удобочитаемость, поскольку оно требует более общего понимания природы таких «оптимизаций» для выявить его различные, разнообразные воплощения, чем просто ссылаться на некоторые конкретные случаи как устаревшие.

ответил user2880576 23 J000000Wednesday14 2014, 01:49:50
6

То, что вы видите, - эффект оптимизатора.

Задача оптимизатора состоит в том, чтобы сделать полученный скомпилированный код либо меньшим, либо более быстрым (но редко оба одновременно), но, как и многие другие ... IT ЗАВИСИТ, что такое код).

В ПРИНЦИПЕ любой вызов библиотеки умножения или, часто, даже использование аппаратного множителя будет медленнее, чем просто побитовый сдвиг.

Итак ... если наивный компилятор сгенерировал вызов в библиотеку для операции * 2, то, конечно, он будет работать медленнее, чем бит-сдвиг *.

Однако оптимизаторы обнаруживают шаблоны и выясняют, как сделать код меньше /быстрее /независимо. И то, что вы видели, это компилятор, обнаруживающий, что * 2 совпадает с сдвигом.

Так же, как интересно, я просто смотрел на сгенерированный ассемблер для некоторых операций вроде * 5 ... на самом деле не глядя на это, но на другие вещи, и по пути я замечаю, что компилятор превратил * 5 в

    сдвиг сдвиг
  • добавить оригинальный номер

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

Искусство оптимизаторов компилятора - это целый отдельный предмет, наполненный магией и действительно правильно понятый примерно 6 людьми на всей планете:)

ответил quickly_now 22 J000000Tuesday14 2014, 14:06:48
3

Попробуйте синхронизировать его с:

for (runs = 0; runs < 100000000; runs++) {
      ;
}

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

ответил Russell Borogove 22 J000000Tuesday14 2014, 19:58:27
2

Умножение представляет собой комбинацию сдвигов и добавлений.

В случае, о котором вы упоминали, я не считаю, что важно, оптимизирует ли его компилятор или нет - «multiply x двумя "может быть реализовано как:

  • Сдвинуть биты x на одно место слева.
  • Добавить x в x.

Это все основные атомные операции; один не быстрее, чем другой.

Измените его на "multiply x на четыре", (или любой 2^k, k>1), и это немного другое:

  • Сдвиг бит x два места влево.
  • Добавить x в x и назовите его y, добавьте y в ---- +: = 11 =:. + ---- литий>

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

Попробуйте последний (или любой y), с соответствующими параметрами, чтобы вы не могли оптимизировать их, чтобы быть тем же самым в реализации. Вы должны найти сдвиг быстрее, взяв 2^k, k>1 по сравнению с повторным добавлением в O(1).

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

ответил OJFord 22 J000000Tuesday14 2014, 01:47:06
1

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

Следует отметить, однако, что разделение потенциально-отрицательных знаковых значений not эквивалентно правым сдвигам. Выражение типа (x+8)>>4 не эквивалентно (x+8)/16. Первый, в 99% компиляторов, будет отображать значения от -24 до -9 до -1, от -8 до +7 до 0 и от +8 до +23 к 1 [числа округления почти симметрично относительно нуля]. Последние будут отображать от -39 до -24 до -1, от -23 до +7 до 0 и от +8 до +23 к +1 [сильно асимметричный, и, скорее всего, не тот, который был предназначен). Обратите внимание, что даже если значения не будут отрицательными, использование >>4, скорее всего, даст более быстрый код, чем /16, если компилятор не может доказать, что значения не могут быть отрицательными.

ответил supercat 22 J000000Tuesday14 2014, 20:49:40
0

Дополнительная информация, которую я только что проверил.

В x86_64 код операции MUL имеет задержку в 10 циклов и пропускную способность 1/2 цикла. MOV, ADD и SHL имеют задержку в 1 цикл с пропускной способностью 2,5, 2,5 и 1,7.

Умножение на 15 потребовало бы 3 SHL и 3 ADD ops минимум и, вероятно, пару MOV.

https://gmplib.org/~tege/x86-timing.pdf

ответил Rich Remer 22 J000000Tuesday14 2014, 22:58:50
0

Ваша методология ошибочна. Ваш инкремент цикла и проверка состояния сами занимают много времени.

  • Попробуйте запустить пустой цикл и измерьте время (назовите его base).
  • Теперь добавьте 1 операцию переключения и измерьте время (назовите это s1).
  • Затем добавьте 10 операций сдвига и измерьте время (назовите его s2)

Если все идет правильно base-s2 должно быть в 10 раз больше, чем base-s1. В противном случае здесь придет что-то другое.

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

int main(){

    int test = 2;
    clock_t launch = clock();

    test << 6;
    test << 6;
    test << 6;
    test << 6;
    //.... 1 million times
    test << 6;

    clock_t done = clock();
    printf("Time taken : %d\n", done - launch);
    return 0;
}

И у вас есть свой результат

1 миллион операций смены менее чем за 1 миллисекунду? .

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

 Результат оператора Shiftwise

ответил Akshay L Aradhya 2 Maypm18 2018, 18:08:21

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132