Действительно ли умножение и деление с использованием операторов сдвига в C быстрее?

Question

Умножение и деление может быть достигнуто с помощью битовых операторов, например

i*2 = i<<1
i*3 = (i<<1) + i;
i*10 = (i<<3) + (i<<1)

и т. Д.

Действительно ли быстрее использовать, скажем, (i<<3)+(i<<1) для умножения на 10, чем при использованииi*10 напрямую?Есть ли какие-либо данные, которые не могут быть умножены или разделены таким образом?

Answer 1

Я согласен с помеченным ответом Дрю Холла. Ответ может использовать некоторые дополнительные примечания.

Для подавляющего большинства разработчиков программного обеспечения процессор и компилятор больше не имеют отношения к данному вопросу. Большинство из нас далеко за 8088 и MS-DOS. Возможно, это актуально только для тех, кто все еще разрабатывает для встроенных процессоров ...

В моей компании по разработке программного обеспечения Math (add / sub / mul / div) должен использоваться для всей математики. Хотя Shift следует использовать при преобразовании между типами данных, например. ushort к байту как n >> 8 и не n / 256.

Answer 2

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

Однако некоторые машины имеют математический процессор, который содержит специальные инструкции для умножения / деления.

Answer 3

Я думаю, что в одном случае, когда вы хотите умножить или разделить на степень два, вы не ошибетесь с использованием операторов битового сдвига, даже если компилятор преобразует их в MUL / DIV, потому что некоторые процессоры микрокодируют (на самом деле, макрос) их в любом случае, так что в этих случаях вы добьетесь улучшения, особенно если сдвиг больше 1. Или, если говорить точнее, если у ЦПУ нет операторов битового сдвига, это будет MUL / DIV в любом случае, но еслив процессоре есть операторы битового сдвига, вы избегаете ветви микрокода, а это на несколько инструкций меньше.

Я сейчас пишу некоторый код, который требует много операций удвоения / деления пополам, потому что он работает на плотном двоичном деревеи есть еще одна операция, которая, как я подозреваю, может быть более оптимальной, чем сложение, - сдвиг влево (умножение на две степени) с сложением.Это можно заменить на сдвиг влево и xor, если сдвиг шире, чем количество бит, которое вы хотите добавить, простой пример (i << 1) ^ 1, который добавляет единицу к удвоенному значению.Это, конечно, не относится к сдвигу вправо (степень деления двух), потому что только сдвиг влево (с прямым порядком байтов) заполняет пробел нулями. </p>

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

Кроме того, в алгоритмах, которые я пишу, они визуально представляют движения, которые происходят, так что в этом смысле онина самом деле более понятно.Левая часть бинарного дерева больше, а правая меньше.Кроме того, в моем коде нечетные и четные числа имеют особое значение, и все левые дочерние элементы в дереве являются нечетными, а все правые дочерние элементы и корень четными.В некоторых случаях, с которыми я еще не сталкивался, но, может, я даже и не думал об этом, x & 1 может быть более оптимальной операцией по сравнению с x% 2.x & 1 на четном числе будет давать ноль, но будет давать 1 для нечетного числа.

Пройдя немного дальше, чем просто нечетная / четная идентификация, если я получу ноль для x & 3, я знаю, что 4 является фактором нашегочисло, и то же самое для x% 7 для 8, и так далее.Я знаю, что эти случаи, вероятно, имеют ограниченную полезность, но приятно знать, что вы можете избежать операции модуля и использовать вместо этого побитовую логическую операцию, потому что побитовые операции почти всегда самые быстрые и наименее вероятно будут неоднозначными для компилятора.

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

Answer 4

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

Ниже приведен пример кода c ++, который может выполнить более быстрое деление, выполняя 64-битное «Умножение на обратную». Числитель и знаменатель должны быть ниже определенного порога. Обратите внимание, что он должен быть скомпилирован для использования 64-битных инструкций, чтобы на самом деле он выполнялся быстрее обычного деления.

#include <stdio.h>
#include <chrono>

static const unsigned s_bc = 32;
static const unsigned long long s_p = 1ULL << s_bc;
static const unsigned long long s_hp = s_p / 2;

static unsigned long long s_f;
static unsigned long long s_fr;

static void fastDivInitialize(const unsigned d)
{
    s_f = s_p / d;
    s_fr = s_f * (s_p - (s_f * d));
}

static unsigned fastDiv(const unsigned n)
{
    return (s_f * n + ((s_fr * n + s_hp) >> s_bc)) >> s_bc;
}

static bool fastDivCheck(const unsigned n, const unsigned d)
{
    // 32 to 64 cycles latency on modern cpus
    const unsigned expected = n / d;

    // At least 10 cycles latency on modern cpus
    const unsigned result = fastDiv(n);

    if (result != expected)
    {
        printf("Failed for: %u/%u != %u\n", n, d, expected);
        return false;
    }

    return true;
}

int main()
{
    unsigned result = 0;

    // Make sure to verify it works for your expected set of inputs
    const unsigned MAX_N = 65535;
    const unsigned MAX_D = 40000;

    const double ONE_SECOND_COUNT = 1000000000.0;

    auto t0 = std::chrono::steady_clock::now();
    unsigned count = 0;
    printf("Verifying...\n");
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        fastDivInitialize(d);
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            count += !fastDivCheck(n, d);
        }
    }
    auto t1 = std::chrono::steady_clock::now();
    printf("Errors: %u / %u (%.4fs)\n", count, MAX_D * (MAX_N + 1), (t1 - t0).count() / ONE_SECOND_COUNT);

    t0 = t1;
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        fastDivInitialize(d);
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            result += fastDiv(n);
        }
    }
    t1 = std::chrono::steady_clock::now();
    printf("Fast division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT);

    t0 = t1;
    count = 0;
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            result += n / d;
        }
    }
    t1 = std::chrono::steady_clock::now();
    printf("Normal division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT);

    getchar();
    return result;
}

Answer 5

Тест Python, выполняющий одинаковое умножение 100 миллионов раз против одинаковых случайных чисел.

>>> from timeit import timeit
>>> setup_str = 'import scipy; from scipy import random; scipy.random.seed(0)'
>>> N = 10*1000*1000
>>> timeit('x=random.randint(65536);', setup=setup_str, number=N)
1.894096851348877 # Time from generating the random #s and no opperati

>>> timeit('x=random.randint(65536); x*2', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); x << 1', setup=setup_str, number=N)
2.2616429328918457

>>> timeit('x=random.randint(65536); x*10', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); (x << 3) + (x<<1)', setup=setup_str, number=N)
2.9485139846801758

>>> timeit('x=random.randint(65536); x // 2', setup=setup_str, number=N)
2.490908145904541
>>> timeit('x=random.randint(65536); x / 2', setup=setup_str, number=N)
2.4757170677185059
>>> timeit('x=random.randint(65536); x >> 1', setup=setup_str, number=N)
2.2316000461578369

Таким образом, при выполнении сдвига вместо умножения / деления на степень два в питоне, есть небольшое улучшение (~10% для деления; ~ 1% для умножения).Если значение не равно двум, вероятно, будет существенное замедление.

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

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

Answer 6

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