Действительно ли более эффективно перейти или умножиться?

Ответ должен, конечно, быть: попробуйте его на целевых аппаратных средствах и посмотрите. И обязательно последуйте совету множества micro-benchmark/stopwatch-benchmark вопросов, отправленных здесь на ТАК за последние несколько недель.

Свяжитесь с одним вопросом о сравнительном тестировании: секундомер сравнивает приемлемый?

Лично, я пошел бы с если, если не был действительно неопровержимый довод для использования "запутываемой" альтернативы.

почему бы не это (принятие я - 32 бита),

  for (i2 = i; i2; i2 = i3) {
    i3 = i2 & (i2-1);
    last_bit = i2-i3;
    a = last_bit & 0xffff;
    b = (last_bit << 16);
    j = place[a] + big_place[b];
    total += value[j];
  }

Где место является таблицей размера 2^15+1 таким образом, которые помещают [0] = 0, место [1] = 1, место [2] = 2, место [4] = 3, место [8] = 4... место [15] = 16 (отдых значений не имеют значения). и big_place почти идентичен: big_place [0] = 0, big_place[1] = 17.... big_place[15] = 32.

Единственный реальный способ определить истину оператора состоит в том, чтобы протестировать. С этим в памяти я согласился бы с предыдущими сообщениями который, поскольку, которые говорят, испытывают его!

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

Попробовать

total += (-((i & mask) != 0)) & value[j];

вместо

total += ((i & mask) != 0) * value[j];

Это избегает умножения. Будет ли ответвление или не составило, достаточно ли компилятор умен для нахождения кода без ответвлений для - (нечто! = 0). (Который возможен, но я был бы немного удивлен.)

(Конечно, это зависит от two's-дополнительного представления; стандарт C является агностиком на этом.)

Вы могли бы выручить компилятор как так, приняв 32-разрядный ints, и подписанный>> распространяет знаковый бит:

total += (((int)((i & mask) << (31 - j))) >> 31) & value[j];

Таким образом, сместите возможно установленный бит, оставленный старшему значащему положению, снимите в качестве интервала со знаком, затем право полностью назад на младшее значащее положение, уступив или ко всему 0 или к всем 1's, под вышеупомянутыми определенными реализацией предположениями. (Я не протестировал это.)

Другая возможность: полагайте, что блоки (говорят) 4 бита за один раз. Существует 16 различных дополнительных последовательностей; можно отправить развернутому коду для каждого из них без тестов вообще в рамках каждого блока кода. Надежда здесь состоит в том, чтобы один косвенный переход стоил меньше чем 4 тестов-и-ответвлений.

Обновление: Используя леса Jonathan Leffler, 4-bits-at-a-time метод является самым быстрым с большим отрывом на моем MacBook. Инвертируйте - и оказывается о том же, когда умножаются. Интересно, умножает ли процессор особые случаи как 0 и 1 быстрее (или не такой особый случай, если это быстрее для most-bits-clear или most-bits-set множимых в целом).

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

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

static int value[] =
{
    12, 36, 79, 21, 31, 93, 24, 15,
    56, 63, 20, 47, 62, 88,  9, 36,
};

static int test_1(int i)
{
    int total = 0;
    for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++)
    {
        if (i & mask)
            total += value[j];
    }
    return(total);
}

static int test_2(int i)
{
    int total = 0;
    for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++)
    {
        total += ((i & mask) != 0) * value[j];
    }
    return(total);
}

static int test_3(int i)
{
    int total = 0;
    for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++)
    {
        total += (mask & 0x0001) * value[j];
    }
    return(total);
}

static int test_4(int i)
{
    int total = 0;
    for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++)
    {
        total += -(mask & 0x0001) & value[j];
    }
    return(total);
}

static int test_5(int i)
{
    int total = 0;
    const int *p = value;
    for (unsigned mask = i & 0xFFFF; mask != 0; mask >>= 4, p += 4)
    {
        switch (mask & 0xF)
        {
        case 0x0: break;
        case 0x1: total += p[0]; break;
        case 0x2: total += p[1]; break;
        case 0x3: total += p[1] + p[0]; break;
        case 0x4: total += p[2]; break;
        case 0x5: total += p[2] + p[0]; break;
        case 0x6: total += p[2] + p[1]; break;
        case 0x7: total += p[2] + p[1] + p[0]; break;
        case 0x8: total += p[3]; break;
        case 0x9: total += p[3] + p[0]; break;
        case 0xA: total += p[3] + p[1]; break;
        case 0xB: total += p[3] + p[1] + p[0]; break;
        case 0xC: total += p[3] + p[2]; break;
        case 0xD: total += p[3] + p[2] + p[0]; break;
        case 0xE: total += p[3] + p[2] + p[1]; break;
        case 0xF: total += p[3] + p[2] + p[1] + p[0]; break;
        }
    }
    return(total);
}

typedef int(*func_pointer)(int);

static func_pointer test[] = { test_1, test_2, test_3, test_4, test_5 };

#define DIM(x)(sizeof(x)/sizeof(*(x)))

int main()
{
    int i, j, k;
    for (i = 0; i < DIM(test); i++)
    {
        long sum = 0;
        clock_t start = clock();
        for (j = 0; j <= 0xFFFF; j += 13)
        {
            int rv;

            for (k = 0; k < 1000; k++)
                rv = (*test[i])(j);
            sum += rv;
        }
        clock_t stop = clock();
        printf("(sum = %ld) Test %d: %8.6f s\n", sum, i + 1, 
               (stop - start) / (1.0 * CLOCKS_PER_SEC));
    }
}

Результаты (gcc -O4 -std=c99 branchmult2.c):

(sum = 1744366) Test 1: 0.225497 s
(sum = 1744366) Test 2: 0.221127 s
(sum = 1744366) Test 3: 0.126301 s
(sum = 1744366) Test 4: 0.124750 s
(sum = 1744366) Test 5: 0.064877 s

Редактирование 2: Я решил, что тест будет более реалистичным без volatile спецификатор.

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

switch (i) {
    case 0: break;
    case 1: total = value[0]; break;
    case 2: total = value[1]; break;
    case 3: total = value[1] + value[0]; break;
    case 4: total = value[2]; break;
    case 5: total = value[2] + value[0]; break;
    ...
}

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

Я записал бы маленький сценарий Perl, который сгенерирует этот код для меня - только для предотвращения опечаток.

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

Что относительно этого пересмотра?

int total = 0;
for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++){
    total += (mask & 0x0001) * value[j];
}

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

Это демонстрирует, почему измерение важно. Я использую устаревший Sun SPARC. Я записал тестовую программу как показано с этими двумя соперниками от вопроса как тест 0 и тест 1, и мой собственный ответ как тест 2. И затем запустил тесты синхронизации. 'Сумма' печатается как проверка работоспособности - чтобы гарантировать, чтобы алгоритмы все дали тот же ответ.

64-разрядный неоптимизированный:

gcc -m64 -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib/sparcv9 -ljl -lposix4

Test 0: (sum = 1744366)  7.973411 us
Test 1: (sum = 1744366) 10.269095 us
Test 2: (sum = 1744366)  7.475852 us

Шахта Мило: немного быстрее, чем оригинал, и souped, версия медленнее.

64-разрядный оптимизированный:

gcc -O4 -m64 -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib/sparcv9 -ljl -lposix4

Test 0: (sum = 1744366)  1.101703 us
Test 1: (sum = 1744366)  1.915972 us
Test 2: (sum = 1744366)  2.575318 us

Штопка - моя версия является теперь существенно самой медленной. Оптимизатор хорош!

32-разрядный оптимизированный:

gcc -O4 -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib -ljl -lposix4

Test 0: (sum = 1744366)  0.839278 us
Test 1: (sum = 1744366)  1.905009 us
Test 2: (sum = 1744366)  2.448998 us

32-разрядный неоптимизированный:

gcc -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib -ljl -lposix4

Test 0: (sum = 1744366)  7.493672 us
Test 1: (sum = 1744366)  9.610240 us
Test 2: (sum = 1744366)  6.838929 us

Тот же код (32-разрядного) Cygwin и не так гериатрический ноутбук (32-разрядный, оптимизированный)

Test 0: (sum = 1744366)  0.557000 us
Test 1: (sum = 1744366)  0.553000 us
Test 2: (sum = 1744366)  0.403000 us

Теперь мой код является самым быстрым. Вот почему Вы имеете размеры! Это также показывает, почему люди, которые выполняют сравнительные тесты для жизни, становятся обезумевшими.

Тестовая обвязка (кричат, если Вы хотите timer.h и timer.c код):

#include <stdio.h>
#include "timer.h"

static volatile int value[] =
{
    12, 36, 79, 21, 31, 93, 24, 15,
    56, 63, 20, 47, 62, 88,  9, 36,
};

static int test_1(int i)
{
    int total = 0;
    for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++)
    {
        if (i & mask)
            total += value[j];
    }
    return(total);
}

static int test_2(int i)
{
    int total = 0;
    for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++)
    {
        total += ((i & mask) != 0) * value[j];
    }
    return(total);
}

static int test_3(int i)
{
    int total = 0;
    for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++)
    {
        total += (mask & 0x0001) * value[j];
    }
    return(total);
}

typedef int(*func_pointer)(int);

static func_pointer test[] = { test_1, test_2, test_3 };

#define DIM(x)(sizeof(x)/sizeof(*(x)))

int main()
{
    int i, j, k;
    char buffer[32];
    for (i = 0; i < DIM(test); i++)
    {
        Clock t;
        long sum = 0;
        clk_init(&t);
        clk_start(&t);
        for (j = 0; j < 0xFFFF; j += 13)
        {
            int rv;

            for (k = 0; k < 1000; k++)
                rv = (*test[i])(j);
            sum += rv;
        }
        clk_stop(&t);
        printf("Test %d: (sum = %ld) %9s us\n", i, sum,
               clk_elapsed_us(&t, buffer, sizeof(buffer)));
    }
}

Я не провел время, работая, почему мой код медленнее при оптимизации.

Это зависит полностью от компилятора, набора машинной команды и, вероятно, фаза луны.

Нет никакого определенного корректного ответа из-за этого. Если Вы действительно хотите знать, проверьте вывод блока из компилятора.

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

Таким образом, корректный ответ: это зависит.

Какой код будет работать быстрее?

Протестируйте его для обнаружения.

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

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

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

Любой мог быть быстрее. Для некоторых процессоров фактические входные данные могут изменить ответ. Необходимо будет представить оба подхода с реальными данными. Вот некоторые вещи, которые могут влиять на фактическую производительность на x86 аппаратных средствах.

Давайте предположим в настоящий момент использование последней модели Pentium 4. Тот процессор имеет два уровня предикторов ответвления, испеченных в ЦП. Если предикторы ответвления могут предположить правильно направление ответвления, я подозреваю, что первое будет самым быстрым. Это, скорее всего, произойдет, если флаги будут почти всеми одинаковыми значение или если они чередуются в очень простом шаблоне большую часть времени. Если флаги будут действительно случайны, то предиктор ответвления будет неправильной половиной времени. Для нашего гипотетического 32-этапного Pentium 4 это уничтожит производительность. Для Pentium 3 микросхем, микросхемы Core 2, Core i7 и большинство микропроцессоров AMD, конвейеры короче, таким образом, стоимость плохого предсказания ветвлений намного ниже.

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