Какой самый быстрый способ конвертировать hex в integer в С++?

Я пытаюсь преобразовать hex char в integer как можно быстрее.

Это только одна строка: int x = atoi(hex.c_str);

Есть ли более быстрый способ?

Здесь я пробовал более динамичный подход, и он немного быстрее.

int hextoint(char number) {
    if (number == '0') {
        return 0;
    }
    if (number == '1') {
        return 1;
    }
    if (number == '2') {
        return 2;
    }
    /*
     *  3 through 8
     */
    if (number == '9') {
        return 9;
    }
    if (number == 'a') {
        return 10;
    }
    if (number == 'b') {
        return 11;
    }
    if (number == 'c') {
        return 12;
    }
    if (number == 'd') {
        return 13;
    }
    if (number == 'e') {
        return 14;
    }
    if (number == 'f') {
        return 15;
    }
    return -1;
}

Ответ 1

Предлагаемые решения, которые отображаются быстрее, чем OP if-else:

Таблица поиска неупорядоченных карт

Если ваши строки ввода всегда шестнадцатеричные, вы можете определить таблицу поиска как unordered_map:

std::unordered_map<char, int> table {
{'0', 0}, {'1', 1}, {'2', 2},
{'3', 3}, {'4', 4}, {'5', 5},
{'6', 6}, {'7', 7}, {'8', 8},
{'9', 9}, {'a', 10}, {'A', 10},
{'b', 11}, {'B', 11}, {'c', 12},
{'C', 12}, {'d', 13}, {'D', 13},
{'e', 14}, {'E', 14}, {'f', 15},
{'F', 15}, {'x', 0}, {'X', 0}};

int hextoint(char number) {
  return table[(std::size_t)number];
}

Таблица поиска в качестве пользователя constexpr literal (С++ 14)

Или, если вам нужно что-то более быстрое, а не unordered_map, вы можете использовать новые объекты С++ 14 с типом пользовательских литералов и определить таблицу как тип литерала во время компиляции:

struct Table {
  long long tab[128];
  constexpr Table() : tab {} {
    tab['1'] = 1;
    tab['2'] = 2;
    tab['3'] = 3;
    tab['4'] = 4;
    tab['5'] = 5;
    tab['6'] = 6;
    tab['7'] = 7;
    tab['8'] = 8;
    tab['9'] = 9;
    tab['a'] = 10;
    tab['A'] = 10;
    tab['b'] = 11;
    tab['B'] = 11;
    tab['c'] = 12;
    tab['C'] = 12;
    tab['d'] = 13;
    tab['D'] = 13;
    tab['e'] = 14;
    tab['E'] = 14;
    tab['f'] = 15;
    tab['F'] = 15;
  }
  constexpr long long operator[](char const idx) const { return tab[(std::size_t) idx]; } 
} constexpr table;

constexpr int hextoint(char number) {
  return table[(std::size_t)number];
}

Live Demo

Ориентиры:

Я провел тесты с кодом, написанным Nikos Athanasiou, который недавно был опубликован в isocpp.org в качестве предлагаемого метода для микро-бенчмаркинга на С++.

Алгоритмы, которые были сопоставлены:

1. OP original if-else:

long long hextoint3(char number) {
  if(number == '0') return 0;
  if(number == '1') return 1;
  if(number == '2') return 2;
  if(number == '3') return 3;
  if(number == '4') return 4;
  if(number == '5') return 5;
  if(number == '6') return 6;
  if(number == '7') return 7;
  if(number == '8') return 8;
  if(number == '9') return 9;
  if(number == 'a' || number == 'A') return 10;
  if(number == 'b' || number == 'B') return 11;
  if(number == 'c' || number == 'C') return 12;
  if(number == 'd' || number == 'D') return 13;
  if(number == 'e' || number == 'E') return 14;
  if(number == 'f' || number == 'F') return 15;
  return 0;
}

2. Компактный if-else, предложенный Кристофом:

long long hextoint(char number) {
  if (number >= '0' && number <= '9') return number - '0';
  else if (number >= 'a' && number <= 'f') return number - 'a' + 0x0a;
  else if (number >= 'A' && number <= 'F') return number - 'A' + 0X0a;
  else return 0;
}

3. Исправлена версия троичного оператора, которая обрабатывает также входы с большой буквы, предложенные g24l:

long long hextoint(char in) {
  int const x = in;
  return (x <= 57)? x - 48 : (x <= 70)? (x - 65) + 0x0a : (x - 97) + 0x0a;
}

4. Таблица поиска (unordered_map):

long long hextoint(char number) {
  return table[(std::size_t)number];
}

где table - неупорядоченное отображение, показанное ранее.

5. Таблица поиска (пользователь constexpr литерал):

long long hextoint(char number) {
  return table[(std::size_t)number];
}

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

Экспериментальные настройки

Я определил функцию, которая преобразует входную шестнадцатеричную строку в целое число:

long long hexstrtoint(std::string const &str, long long(*f)(char)) {
  long long ret = 0;
  for(int j(1), i(str.size() - 1); i >= 0; --i, j *= 16) {
    ret += (j * f(str[i]));
  }
  return ret;
}

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

std::vector<std::string>
populate_vec(int const N) {
  random_device rd;
  mt19937 eng{ rd() };
  uniform_int_distribution<long long> distr(0, std::numeric_limits<long long>::max() - 1);
  std::vector<std::string> out(N);
  for(int i(0); i < N; ++i) {
    out[i] = int_to_hex(distr(eng));
  }
  return out;
}

Я создал векторы, заполненные случайными шестнадцатеричными строками 50000, 100000, 150000, 200000 и 250000 соответственно. Затем для каждого алгоритма выполняются 100 экспериментов и усредняются результаты времени.

Компилятор был GCC версии 5.2 с опцией оптимизации -O3.

Результаты:

Обсуждение

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

CODE

Изменить:

Результаты для метода, предложенного stgatilov, с побитовыми операциями:

long long hextoint(char x) {
    int b = uint8_t(x);
    int maskLetter = (('9' - b) >> 31);
    int maskSmall = (('Z' - b) >> 31);
    int offset = '0' + (maskLetter & int('A' - '0' - 10)) + (maskSmall & int('a' - 'A'));
    return b - offset;
}

Edit:

Я также проверил исходный код из g24l на метод таблицы:

long long hextoint(char in) {
  long long const x = in;
  return x < 58? x - 48 : x - 87;
}

Обратите внимание, что этот метод не обрабатывает заглавные буквы A, B, C, D, E и F.

Результаты:

Тем не менее метод таблицы отображается быстрее.

Ответ 2

Этот вопрос может, очевидно, иметь разные ответы на разные системы, и в этом смысле он некорректен с самого начала. Например, у i486 нет конвейера, а у pentium нет SSE.

Правильный вопрос: "какой самый быстрый способ преобразуйте одиночный char hex в dec в системе X, например. i686".

Среди подходов в данном случае ответ на этот вопрос на самом деле тот же или очень близкий к системе с многоступенчатым конвейером. Любая система без конвейера будет сгибаться к методу таблицы поиска (LUT), но если медленный доступ к памяти медленный, условный метод (CEV) или метод побитовой оценки (BEV) может получить прибыль в зависимости от скорости xor vs load для данный процессор.

(CEV) разлагается на 2 эффективных адреса загрузки, сравнение и условное перемещение из регистров которые не подвержены ошибочному прогнозированию. Все эти команды можно найти в конвейере pentium. Таким образом, они фактически идут в 1-цикл.

  8d 57 d0                lea    -0x30(%rdi),%edx
  83 ff 39                cmp    $0x39,%edi
  8d 47 a9                lea    -0x57(%rdi),%eax
  0f 4e c2                cmovle %edx,%eax

(LUT) разлагается в mov между регистрами и mov из зависимого от данных места памяти плюс некоторые nops для выравнивания и должен принимать минимум 1 цикл. Как и предыдущие, существуют только зависимости данных.

  48 63 ff                movslq %edi,%rdi
  8b 04 bd 00 1d 40 00    mov    0x401d00(,%rdi,4),%eax

(BEV) - это другой зверь, поскольку на самом деле ему требуется 2 movs + 2 xors + 1 и условное mov. Они также могут быть хорошо конвейерными.

  89 fa                   mov    %edi,%edx
  89 f8                   mov    %edi,%eax
  83 f2 57                xor    $0x57,%edx
  83 f0 30                xor    $0x30,%eax
  83 e7 40                and    $0x40,%edi
  0f 45 c2                cmovne %edx,%eax

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

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

Итак, я действительно создал несколько тестов в этом смысле, которые легко воспроизводимы в любой системе с компилятором С++ 11 и источником случайного устройства, например, любой системой * nix. Если не разрешить векторизацию -O2 CEV/LUT почти равны, но после установки -O3 преимущество написания кода, которое более разложимо, показывает разницу.

Подводя итог, , если у вас есть старый компилятор, используйте LUT, if ваша система является младшей или старой, считают BEV, иначе компилятор перехитрит вас, и вы должны использовать CEV.

Проблема: речь идет о преобразовании из набора символов {0,1,2,3,4,5,6,7,8,9, a, b, c, d, e, f} к набору {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}. Заглавные буквы не рассматриваются.

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

[Простой и легкий]: Условная оценка → CEV

int decfromhex(int const x)
{
return x<58?x-48:x-87;
}

[Грязный и сложный]: Побитовая оценка → BEV

int decfromhex(int const x)
{
return 9*(x&16)+( x & 0xf  );
}

[время компиляции]: условная оценка шаблона → TCV

template<char n> int decfromhex()
{
  int constexpr x = n;
  return x<58 ? x-48 : x -87;
}

[Таблица поиска]: Таблица поиска → LUT

int decfromhex(char n)
{
static int constexpr x[255]={
           // fill everything with invalid, e.g. -1 except places\
           // 48-57 and 97-102 where you place 0..15 
           };
return x[n];
}

Среди всех, последний, по-видимому, самый быстрый при первом просмотре. Второй - только во время компиляции и постоянного выражения.

[РЕЗУЛЬТАТ] (пожалуйста, проверьте): * BEV является самым быстрым среди всех и обрабатывает букву нижнего и верхнего регистра, но только маргинальный номер CEV, который не обрабатывает заглавные буквы. LUT становится медленнее, чем CEV и BEV по мере увеличения размера строки.

Примерный результат для str-размеров 16-12384 можно найти ниже (ниже лучше)

Среднее время (100 пробегов) вдоль показывается. Размер пузырька является нормальной ошибкой.

Доступен script для запуска тестов.

Тесты были выполнены для conditional CEV, bitwise BEV и lookup table LUT на множестве случайно сгенерированные строки. Тесты довольно просты и от:

Проверить исходный код

они поддаются проверке:

A локальная копия строки ввода помещается в локальный буфер каждый раз.
Сохраняется локальная копия результатов, которая затем копируется в кучу для каждого теста строки
Продолжительность только для времени, в течение которого работает строка.
единообразный подход, нет сложного механизма и кода обертки/вокруг, который подходит для других случаев.
нет выборки используется вся временная последовательность
Выполняется предварительный нагрев процессора
Сон между тестами происходит, чтобы разрешить маршал кода таким образом, чтобы один тест не воспользовался предыдущим тестом.
Компиляция выполняется с помощью g++ -std=c++11 -O3 -march=native dectohex.cpp -o d2h
Запустить с помощью taskset -c 0 d2h
Нет зависимостей нитей или многопоточности
Фактически используются результаты, чтобы избежать любой оптимизации цикла.

В качестве побочной заметки я видел на практике версию 3 намного быстрее с более старыми компиляторами С++ 98.

[НИЖНЯЯ ЛИНИЯ]: используйте CEV без страха, если вы не знаете свои переменные во время компиляции, где вы можете использовать версию TCV. LUTследует использовать только после значительных результатов в каждом случае использования оценки и, возможно, со старыми компиляторами. Другое дело, когда ваш набор больше, т.е. {0,1,2,3,4,5,6,7,8,9, a, b, c, d, e, f, A, B, C, D, E, F}, Это также может быть достигнуто. Наконец, если вы голодны, используйте BEV.

Результаты с unordered_map были удалены, так как они были слишком медленными для сравнения или в лучшем случае могут быть такими же быстрыми, как решение LUT.

Результаты моего личного ПК по строкам размером 12384/256 и для 100 строк:

 g++ -DS=2 -DSTR_SIZE=256 -DSET_SIZE=100 -DUNITS=nanoseconds -O3 -std=c++11 -march=native dectohex.cpp -o d2h && taskset -c 0 ./d2h
sign: -2709
-------------------------------------------------------------------
(CEV) Total: 185568 nanoseconds - mean: 323.98 nanoseconds  error: 88.2699 nanoseconds
(BEV) Total: 185568 nanoseconds - mean: 337.68 nanoseconds  error: 113.784 nanoseconds
(LUT) Total: 229612 nanoseconds - mean: 667.89 nanoseconds  error: 441.824 nanoseconds
-------------------------------------------------------------------


g++ -DS=2 -DSTR_SIZE=12384 -DSET_SIZE=100 -DUNITS=nanoseconds -O3 -std=c++11 -march=native hextodec.cpp -o d2h && taskset -c 0 ./h2d

-------------------------------------------------------------------
(CEV) Total: 5539902 nanoseconds - mean: 6229.1 nanoseconds error: 1052.45 nanoseconds
(BEV) Total: 5539902 nanoseconds - mean: 5911.64 nanoseconds    error: 1547.27 nanoseconds
(LUT) Total: 6346209 nanoseconds - mean: 14384.6 nanoseconds    error: 1795.71 nanoseconds
-------------------------------------------------------------------
Precision: 1 ns

Результаты системы с GCC 4.9.3, скомпилированные для металла без загрузки системы в строки размером 256/12384 и для 100 строк

g++ -DS=2 -DSTR_SIZE=256 -DSET_SIZE=100 -DUNITS=nanoseconds -O3 -std=c++11 -march=native dectohex.cpp -o d2h && taskset -c 0 ./d2h
sign: -2882
-------------------------------------------------------------------
(CEV) Total: 237449 nanoseconds - mean: 444.17 nanoseconds  error: 117.337 nanoseconds
(BEV) Total: 237449 nanoseconds - mean: 413.59 nanoseconds  error: 109.973 nanoseconds
(LUT) Total: 262469 nanoseconds - mean: 731.61 nanoseconds  error: 11.7507 nanoseconds
-------------------------------------------------------------------
Precision: 1 ns


g++ -DS=2 -DSTR_SIZE=12384 -DSET_SIZE=100 -DUNITS=nanoseconds -O3 -std=c++11 -march=native dectohex.cpp -o d2h && taskset -c 0 ./d2h
sign: -137532
-------------------------------------------------------------------
(CEV) Total: 6834796 nanoseconds - mean: 9138.93 nanoseconds    error: 144.134 nanoseconds
(BEV) Total: 6834796 nanoseconds - mean: 8588.37 nanoseconds    error: 4479.47 nanoseconds
(LUT) Total: 8395700 nanoseconds - mean: 24171.1 nanoseconds    error: 1600.46 nanoseconds
-------------------------------------------------------------------
Precision: 1 ns

[КАК ПРОЧИТАТЬ РЕЗУЛЬТАТЫ]

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

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

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

Код имеет уникальный макрос, определенный для запуска тестов, позволяет определять переменные времени компиляции для настройки тестов и печатает полную информацию, такую как:

g++ -DS=2 -DSTR_SIZE=64 -DSET_SIZE=1000 -DUNITS=nanoseconds -O3 -std=c++11 -march=native dectohex.cpp -o d2h && taskset -c 0 ./d2h
sign: -6935
-------------------------------------------------------------------
(CEV) Total: 947378 nanoseconds - mean: 300.871 nanoseconds error: 442.644 nanoseconds
(BEV) Total: 947378 nanoseconds - mean: 277.866 nanoseconds error: 43.7235 nanoseconds
(LUT) Total: 1040307 nanoseconds - mean: 375.877 nanoseconds    error: 14.5706 nanoseconds
-------------------------------------------------------------------

Например, чтобы запустить тест с паузой 2sec на странице размера 256 для общей суммы 10000 разных строк, выходных таймингов в double precision и подсчета в nanoseconds, следующая команда компилирует и запускает тест.

g++ -DS=2 -DSTR_SIZE=256 -DSET_SIZE=10000 -DUTYPE=double -DUNITS=nanoseconds -O3 -std=c++11 -march=native dectohex.cpp -o d2h && taskset -c 0 ./d2h

Ответ 3

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

Я буду принимать следующие вещи:

У нас есть современный процессор x86 (64).
Код входного символа ASCII хранится в регистре общего назначения, например. в eax.
Выходное целое число должно быть получено в регистре общего назначения.
Входной символ гарантируется как действительная шестнадцатеричная цифра (один из 16 случаев).

Решение

Вот несколько способов решения проблемы: первая на основе поиска, две на основе тернарного оператора, последняя из которых основана на битовых операциях:

int hextoint_lut(char x) {
    static char lut[256] = {???};
    return lut[uint8_t(x)];
}

int hextoint_cond(char x) {
    uint32_t dig = x - '0';
    uint32_t alp = dig + ('0' - 'a' + 10);
    return dig <= 9U ? dig : alp;
}
int hextoint_cond2(char x) {
    uint32_t offset = (uint8_t(x) <= uint8_t('9') ? '0' : 'a' - 10);
    return uint8_t(x) - offset;
}

int hextoint_bit(char x) {
    int b = uint8_t(x);
    int mask = (('9' - b) >> 31);
    int offset = '0' + (mask & int('a' - '0' - 10));
    return b - offset;
}

Ниже приведены соответствующие списки агрегатов (показаны только соответствующие части):

;hextoint_lut;
movsx   eax, BYTE PTR [rax+rcx]   ; just load the byte =)

;hextoint_cond;
sub edx, 48                       ; subtract '0'
cmp edx, 9                        ; compare to '9'
lea eax, DWORD PTR [rdx-39]       ; add ('0' - 'a' + 10)
cmovbe  eax, edx                  ; choose between two cases in branchless way

;hextoint_cond2;                  ; (modified slightly)
mov eax, 48                       
mov edx, 87                       ; set two offsets to registers
cmp ecx, 57                       ; compare with '9'
cmovbe  edx, eax                  ; choose one offset
sub ecx, edx                      ; subtract the offset

;hextoint_bit;
mov ecx, 57                       ; load '9'
sub ecx, eax                      ; get '9' - x
sar ecx, 31                       ; convert to mask if negative
and ecx, 39                       ; set to 39 (for x > '9')
sub eax, ecx                      ; subtract 39 or 0
sub eax, 48                       ; subtract '0'

Анализ

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

Функция hextoint_lut состоит из одной нагрузки на память, которая занимает 1 мкп на порте 2 или 3. Оба этих порта предназначены для загрузки памяти, и они также имеют внутренний адрес, способный выполнять rax+rcx без дополнительных затрат. Есть два таких порта, каждый из которых может выполнять один цикл в цикле. Так что предположительно эта версия займет 0,5 часа. Если нам нужно загрузить номер ввода из памяти, для этого потребуется еще одна загрузка памяти за одно значение, поэтому общая стоимость будет равна 1 такту.

Версия hextoint_cond имеет 4 команды, но cmov разбивается на два отдельных типа. Таким образом, всего 5 штук, каждый из них может обрабатываться на любом из трех арифметических портов 0, 1 и 5. Таким образом, предположительно, это займет 5/3 цикла времени. Обратите внимание, что порты загрузки памяти свободны, поэтому время не увеличивается, даже если вам нужно загрузить входное значение из памяти.

Версия hextoint_cond2 имеет 5 инструкций. Но в замкнутом цикле константы могут быть предварительно загружены в регистры, поэтому будет только сравнение, cmov и вычитание. Они всего 4 мкп, что дает 4/3 цикла на одно значение (даже при чтении памяти).

Версия hextoint_bit - это решение, гарантированное отсутствие ветвей и поисков, что удобно, если вы не хотите всегда проверять, генерировал ли ваш компилятор команду cmov. Первый mov свободен, так как константа может быть предварительно загружена в узкой петле. Остальные - это 5 арифметических инструкций, в которых 5 портов в портах 0, 1, 5. Таким образом, это должно занимать 5/3 циклов (даже при чтении памяти).

Benchmark

Я выполнил тест для функций С++, описанных выше. В бенчмарке генерируется 64 КБ случайных данных, затем каждая функция выполняется много раз по этим данным. Все результаты добавляются в контрольную сумму, чтобы убедиться, что компилятор не удаляет код. Используется ручная разворачивание 8x. Я тестировал на ядре Ivy Bridge 3.4 Ghz, которое очень похоже на Sandy Bridge. Каждая строка вывода содержит: имя функции, общее время, отсчитываемое по эталону, количество циклов на входное значение, сумму всех выходов.

Контрольный код

MSVC2013 x64 /O2:
hextoint_lut: 0.741 sec, 1.2 cycles  (check: -1022918656)
hextoint_cond: 1.925 sec, 3.0 cycles  (check: -1022918656)
hextoint_cond2: 1.660 sec, 2.6 cycles  (check: -1022918656)
hextoint_bit: 1.400 sec, 2.2 cycles  (check: -1022918656)

GCC 4.8.3 x64 -O3 -fno-tree-vectorize
hextoint_lut: 0.702 sec, 1.1 cycles  (check: -1114112000)
hextoint_cond: 1.513 sec, 2.4 cycles  (check: -1114112000)
hextoint_cond2: 2.543 sec, 4.0 cycles  (check: -1114112000)
hextoint_bit: 1.544 sec, 2.4 cycles  (check: -1114112000)

GCC 4.8.3 x64 -O3
hextoint_lut: 0.702 sec, 1.1 cycles  (check: -1114112000)
hextoint_cond: 0.717 sec, 1.1 cycles  (check: -1114112000)
hextoint_cond2: 0.468 sec, 0.7 cycles  (check: -1114112000)
hextoint_bit: 0.577 sec, 0.9 cycles  (check: -1114112000)

Очевидно, что подход LUT принимает один цикл за каждое значение (как и прогнозировалось). Другие подходы обычно занимают от 2,2 до 2,6 циклов на одно значение. В случае GCC hextoint_cond2 медленный, потому что компилятор использует cmp + sbb + и magic вместо желаемых команд cmov. Также обратите внимание, что по умолчанию GCC векторизовывает большинство подходов (последний абзац), что обеспечивает ожидаемые более быстрые результаты, чем неперерабатываемый подход LUT. Обратите внимание, что ручная векторизация даст значительно больший импульс.

Обсуждение

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

Я проанализировал производительность пропускной способности. Но если нам нужно обрабатывать тонны входных значений, то мы должны определенно векторизовать преобразование, чтобы получить лучшую скорость. hextoint_cond может быть векторизован с помощью SSE довольно простым способом. Он позволяет обрабатывать 16 байт до 16 байтов, используя только 4 команды, беря приблизительно 2 цикла, я полагаю.

Обратите внимание, что для того, чтобы увидеть разницу в производительности, вы должны убедиться, что все входные значения вписываются в кеш (L1 - лучший вариант). Если вы прочитаете входные данные из основной памяти, даже std::atoi будет одинаково быстро с рассмотренными методами =)

Кроме того, вы должны развернуть основной цикл 4x или даже 8x для максимальной производительности (для удаления служебных данных цикла). Как вы уже могли заметить, скорость обоих методов сильно зависит от того, какие операции окружают код. Например. добавление нагрузки на память удваивает время, затрачиваемое первым подходом, но не влияет на другие подходы.

P.S. Скорее всего, вам не нужно оптимизировать это.

Ответ 4

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

Альтернативой будет более компактный:

if (number >= '0' && number<='9') 
    return number-'0';
else if (number >= 'a' && number <='f') 
    return number-'a'+0x0a; 
else return -1;

Еще одна альтернатива - использовать таблицу поиска (торговое пространство против скорости), которое вы инициализируете только один раз, а затем напрямую:

if (number>=0) 
   return mytable[number]; 
else return -1;

Если вы хотите конвертировать более одной цифры за раз, вы можете посмотреть этот вопрос)

Изменить: эталон

После Ike я написал небольшой неофициальный ориентир (доступно онлайн), который вы можете запустить в своем любимом компиляторе.

Выводы:

Таблица поиска всегда является победителем.
Переключатель лучше, чем if-цепь.
С msvc2015 (выпуск) вторая лучшая версия - моя компактная версия, на удивление внимательно следящая за картой 101010.
С gcc на ideone вторая версия коммутатора, за которой следует компактная версия.

Ответ 5

Это мой любимый код hex-to-int:

inline int htoi(int x) {
    return 9 * (x >> 6) + (x & 017);
}

Это не зависит от регистра для буквы, т.е. вернет правильный результат для "a" и "A".

Ответ 6

Если вы (или кто-то еще) на самом деле конвертируете массив значений, я создал кодировщик и декодер AVX2 SIMD, который сравнивает ~ 12 раз быстрее, чем самая быстрая скалярная реализация: https://github.com/zbjornson/fast-hex

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