Есть ли способ сделать эту функцию быстрее? (C)

Question

У меня есть код в C, который выполняет добавления так же, как это делает человек, поэтому, если, например, у меня есть два массива A[0..n-1] и B[0..n-1], метод будет выполнять C[0]=A[0]+B[0], C[1]=A[1]+B[1] ...

Мне нужна помощь в ускорении этой функции, даже если решение использует встроенные функции.

Моя главная проблема заключается в том, что у меня действительно большая проблема с зависимостями, как итерация i+1 зависит от переноса итерации i, пока я использую базу 10. Так что если A[0]=6 и B[0]=5, C[0] должно быть 1 и у меня будет перенос 1 для следующего добавление.

Более быстрый код, который я мог сделать, был такой:

void LongNumAddition1(unsigned char *Vin1, unsigned char *Vin2,
                      unsigned char *Vout, unsigned N) {
    for (int i = 0; i < N; i++) {
        Vout[i] = Vin1[i] + Vin2[i];
    } 

    unsigned char carry = 0;

    for (int i = 0; i < N; i++) {
        Vout[i] += carry;
        carry = Vout[i] / 10;
        Vout[i] = Vout[i] % 10;
    }
}

Но я также попробовал эти подходы, которые оказались медленнее:

void LongNumAddition1(unsigned char *Vin1, unsigned char *Vin2,
                      unsigned char *Vout, unsigned N) {
    unsigned char CARRY = 0;
    for (int i = 0; i < N; i++) {
        unsigned char R = Vin1[i] + Vin2[i] + CARRY;
        Vout[i] = R % 10; CARRY = R / 10;
    }
}

void LongNumAddition1(char *Vin1, char *Vin2, char *Vout, unsigned N) {
    char CARRY = 0;
    for (int i = 0; i < N; i++) {
        char R = Vin1[i] + Vin2[i] + CARRY;
        if (R <= 9) {
            Vout[i] = R;
            CARRY = 0;
        } else {
            Vout[i] = R - 10;
            CARRY = 1;
        }
    }
}

I ' Мы исследовали в Google и обнаружили некоторые псевдокоды, которые были похожи на то, что я реализовал, также в GeeksforGeeks есть другая реализация этой проблемы, но она также медленнее.

Не могли бы вы мне помочь?

Answer 1

Если вы не хотите менять формат данных, вы можете попробовать SIMD.

typedef uint8_t u8x16 __attribute__((vector_size(16)));

void add_digits(uint8_t *const lhs, uint8_t *const rhs, uint8_t *out, size_t n) {
    uint8_t carry = 0;
    for (size_t i = 0; i + 15 < n; i += 16) {
        u8x16 digits = *(u8x16 *)&lhs[i] + *(u8x16 *)&rhs[i] + (u8x16){carry};

        // Get carries and almost-carries
        u8x16 carries = digits >= 10; // true is -1
        u8x16 full = digits == 9;

        // Shift carries
        carry = carries[15] & 1;
        __uint128_t carries_i = ((__uint128_t)carries) << 8;
        carry |= __builtin_add_overflow((__uint128_t)full, carries_i, &carries_i);

        // Add to carry chains and wrap
        digits += (((u8x16)carries_i) ^ full) & 1;
        // faster: digits = (u8x16)_mm_min_epu8((__m128i)digits, (__m128i)(digits - 10));
        digits -= (digits >= 10) & 10;

        *(u8x16 *)&out[i] = digits;
    }
}

Это ~ 2 инструкции на ди git. Вам нужно будет добавить код для обработки хвоста.

---

Вот краткий обзор алгоритма.

Сначала мы добавляем наши цифры с переносом из последнего итерация:

lhs           7   3   5   9   9   2
rhs           2   4   4   9   9   7
carry                             1
         + -------------------------
digits        9   7   9  18  18  10

Мы вычисляем, какие цифры будут производить переносы (≥10), а какие будут их распространять (= 9). По любой причине true равен -1 с SIMD.

carries       0   0   0  -1  -1  -1
full         -1   0  -1   0   0   0

Мы конвертируем carries в целое число и сдвигаем его, а также конвертируем full в целое число.

              _   _   _   _   _   _
carries_i  000000001111111111110000
full       111100001111000000000000

Теперь мы можем сложить их вместе для распространения переносов. Обратите внимание, что только самый младший бит является правильным.

              _   _   _   _   _   _
carries_i  111100011110111111110000
(relevant) ___1___1___0___1___1___0

Есть два индикатора, на которые следует обратить внимание:

1. carries_i имеет самый низкий установленный бит, и digit ≠ 9. В этом квадрате произошел перенос.

2. carries_i имеет младший бит un и digit = 9. Здесь был перенос через этого квадрата, сбрасывающий бит.

Мы вычисляем это с (((u8x16)carries_i) ^ full) & 1 и добавляем к digits.

(c^f) & 1     0   1   1   1   1   0
digits        9   7   9  18  18  10
         + -------------------------
digits        9   8  10  19  19  10

Затем мы удаляем 10 с, которые уже были перенесены.

digits        9   8  10  19  19  10
(d≥10)&10     0   0  10  10  10  10
         - -------------------------
digits        9   8   0   9   9   0

Мы также отслеживаем выполнение, которое может произойти в двух местах.

Answer 2

Кандидаты на повышение скорости:

Оптимизации

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

restrict

Компилятор не знает, что изменение Vout[] не влияет на Vin1[], Vin2[] и поэтому ограничено в некоторых оптимизациях.

Используйте restrict для обозначения Vin1[], Vin2[] не влияет на запись в Vout[].

// void LongNumAddition1(unsigned char  *Vin1, unsigned char *Vin2, unsigned char *Vout, unsigned N)
void LongNumAddition1(unsigned char * restrict Vin1, unsigned char * restrict Vin2,
   unsigned char * restrict Vout, unsigned N)

Примечание: это ограничивает вызывающего абонента от вызова функции с Vout, который перекрывается Vin1, Vin2.

const

Также используйте const для оптимизации. const также позволяет const массивам передаваться как Vin1, Vin2.

// void LongNumAddition1(unsigned char * restrict Vin1, unsigned char * restrict Vin2,
   unsigned char * restrict Vout, unsigned N)
void LongNumAddition1(const unsigned char * restrict Vin1, 
   const unsigned char * restrict Vin2, 
   unsigned char * restrict Vout, 
   unsigned N)

unsigned

unsigned/int - это "goto" типы, чтобы использовать для целочисленной математики. Вместо unsigned char CARRY или char CARRY используйте unsigned или uint_fast8_t из <inttypes.h>.

% альтернатива

sum = a+b+carry; if (sum >= 10) { sum -= 10; carry = 1; } else carry = 0; @ pmg или тому подобное.

---

Примечание: я ожидаю, что LongNumAddition1() вернет окончательный перенос.

Answer 3

Первый l oop

for (int i = 0; i < N; i++) {
    Vout[i] = Vin1[i] + Vin2[i];
} 

автоматически векторизируется компилятором. Но следующая l oop

for (int i = 0; i < N; i++) {
    Vout[i] += carry;
    carry = Vout[i] / 10;
    Vout[i] = Vout[i] % 10;
}

содержит l oop -зависимую , которая по существу сериализует весь l oop (рассмотрите возможность добавления 1 к 99999999999999999 - это может рассчитывается только последовательно, 1 ди git за один раз). Зависимость от L oop является одной из самых больших головных болей в современной компьютерной науке.

Поэтому первая версия быстрее - она ​​частично векторизована. Это не относится к любой другой версии.

Как можно избежать зависимости от l oop?

Компьютеры, являющиеся устройствами base-2, как известно, плохо работают с base-10 arithmeti c. Он не только тратит пространство, но и создает искусственные переносимые зависимости между каждым di git.

Если вы можете превратить ваши данные из представления base-10 в base-2, то для машины это станет легче добавить два массива, потому что машина может легко выполнить двоичное добавление нескольких битов за одну итерацию. Хорошо работающее представление может быть, например, uint64_t для 64-битной машины. Обратите внимание, что потоковое добавление с переносом по-прежнему проблематично c для SSE , но там также есть некоторые варианты.

К сожалению, компиляторам C трудно создавать эффективные циклы с переносом распространение. По этой причине, например, libgmp реализует добавление bignum не в C, а на языке ассемблера, используя инструкцию AD C (add with carry). Кстати, libgmp может быть прямой заменой множества функций bignum arithmeti c в вашем проекте.

Answer 4

Обсуждать ручную оптимизацию всегда бессмысленно, если не учитывать конкретную c систему. Если мы предположим, что у вас есть какой-то основной 32-битный процессор с кешем данных, кешем команд и предсказанием переходов, то:

• Избегайте множественных циклов. Вы должны быть в состоянии объединить их в один и тем самым значительно повысить производительность. Таким образом, вам не придется касаться одной и той же области памяти несколько раз, и вы уменьшите общее количество ветвей. Каждое i < N должно проверяться программой, поэтому уменьшение количества проверок должно повысить производительность. Кроме того, это может улучшить возможности кэширования данных.

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

• Уточните параметры правильно. Вы действительно должны быть знакомы с термином const правильность . Vin1 и Vin2 не изменены, поэтому они должны быть const, и не только для повышения производительности, но и для обеспечения безопасности и удобочитаемости программы.

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

• Деление - это дорогостоящая операция на многих процессорах, поэтому, если есть возможность изменить алгоритм, чтобы избавиться от / и %, сделайте это. Если алгоритм выполняется на байтовой основе, то вы можете пожертвовать 256 байтами памяти для хранения справочной таблицы.

  (Это при условии, что вы можете выделить такую ​​справочную таблицу в ПЗУ без введения зависимостей состояния ожидания и т. Д. c).

• Изменение переноса на 32-разрядный Тип может дать лучший код в некоторых системах, хуже в других. Когда я попробовал это на x86_64, он дал немного худший код одной инструкцией (очень незначительная разница).

Answer 5

Чтобы повысить скорость добавления bignum, вы должны упаковать больше десятичных цифр в элементы массива. Например: вы можете использовать uint32_t вместо unsigned char и хранить 9 цифр за раз.

Еще один прием для повышения производительности - избегать ветвлений.

Вот измененный версия вашего кода без тестов:

void LongNumAddition1(const char *Vin1, const char *Vin2, char *Vout, unsigned N) {
    char carry = 0;
    for (int i = 0; i < N; i++) {
        char r = Vin1[i] + Vin2[i] + CARRY;
        carry = (r >= 10);
        Vout[i] = r - carry * 10;
    }
}

Вот модифицированная версия, имеющая дело с 9 цифрами одновременно:

#include <stdint.h>

void LongNumAddition1(const uint32_t *Vin1, const uint32_t *Vin2, uint32_t *Vout, unsigned N) {
    uint32_t carry = 0;
    for (int i = 0; i < N; i++) {
        uint32_t r = Vin1[i] + Vin2[i] + CARRY;
        carry = (r >= 1000000000);
        Vout[i] = r - carry * 1000000000;
    }
}

Вы можете посмотреть код, сгенерированный g cc и включите компилятор GodBolt .

Вот небольшая тестовая программа:

#include <inttypes.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>

int LongNumConvert(const char *s, uint32_t *Vout, unsigned N) {
    unsigned i, len = strlen(s);
    uint32_t num = 0;
    if (len > N * 9)
        return -1;
    while (N * 9 > len + 8)
        Vout[--N] = 0;
    for (i = 0; i < len; i++) {
        num = num * 10 + (s[i] - '0');
        if ((len - i) % 9 == 1) {
            Vout[--N] = num;
            num = 0;
        }
    }
    return 0;
}

int LongNumPrint(FILE *fp, const uint32_t *Vout, unsigned N, const char *suff) {
    int len;
    while (N > 1 && Vout[N - 1] == 0)
        N--;
    len = fprintf(fp, "%"PRIu32"", Vout[--N]);
    while (N > 0)
        len += fprintf(fp, "%09"PRIu32"", Vout[--N]);
    if (suff)
        len += fprintf(fp, "%s", suff);
    return len;
}

void LongNumAddition(const uint32_t *Vin1, const uint32_t *Vin2,
                     uint32_t *Vout, unsigned N) {
    uint32_t carry = 0;
    for (unsigned i = 0; i < N; i++) {
        uint32_t r = Vin1[i] + Vin2[i] + carry;
        carry = (r >= 1000000000);
        Vout[i] = r - carry * 1000000000;
    }
}

int main(int argc, char *argv[]) {
    const char *sa = argc > 1 ? argv[1] : "123456890123456890123456890";
    const char *sb = argc > 2 ? argv[2] : "2035864230956204598237409822324";
#define NUMSIZE  111  // handle up to 999 digits
    uint32_t a[NUMSIZE], b[NUMSIZE], c[NUMSIZE];
    LongNumConvert(sa, a, NUMSIZE);
    LongNumConvert(sb, b, NUMSIZE);
    LongNumAddition(a, b, c, NUMSIZE);
    LongNumPrint(stdout, a, NUMSIZE, " + ");
    LongNumPrint(stdout, b, NUMSIZE, " = ");
    LongNumPrint(stdout, c, NUMSIZE, "\n");
    return 0;
}