char [] для шестнадцатеричного упражнения

Question

Ниже моя текущая функция char * to hex. Я написал это как упражнение в манипуляциях с битами. На AMD Athlon MP 2800+ требуется около 7 мс, чтобы зашифровать массив из 10 миллионов байт. Есть какой-то трюк или другой способ, который я пропускаю?

Как я могу сделать это быстрее?

Скомпилировано с -O3 в g ++

static const char _hex2asciiU_value[256][2] =
     { {'0','0'}, {'0','1'}, /* snip..., */ {'F','E'},{'F','F'} };

std::string char_to_hex( const unsigned char* _pArray, unsigned int _len )
{
    std::string str;
    str.resize(_len*2);
    char* pszHex = &str[0];
    const unsigned char* pEnd = _pArray + _len;

    clock_t stick, etick;
    stick = clock();
    for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++, pszHex += 2 ) {
        pszHex[0] = _hex2asciiU_value[*pChar][0];
        pszHex[1] = _hex2asciiU_value[*pChar][1];
    }
    etick = clock();

    std::cout << "ticks to hexify " << etick - stick << std::endl;

    return str;
}

Обновление

Добавлен временный код

Brian R. Bondy : замените std :: string буфером кучи на распределении и измените с * 16 на of << 4 - однако выделенный из кучи буфер, кажется, замедляет его? - результат ~ 11мс </p>

Antti Sykäri : заменить внутренний цикл на

 int upper = *pChar >> 4;
 int lower = *pChar & 0x0f;
 pszHex[0] = pHex[upper];
 pszHex[1] = pHex[lower];

результат ~ 8мс

Роберт : замените _hex2asciiU_value на полную таблицу из 256 записей, пожертвовав памятью, но в результате получите ~ 7 мс!

HoyHoy : заметил, что он дает неправильные результаты

Answer 1

Постоянно получаю ~ 4 мс на моем Athlon 64 4200+ (~ 7 мс с оригинальным кодом)

for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++) {
    const char* pchars = _hex2asciiU_value[*pChar];
    *pszHex++ = *pchars++;
    *pszHex++ = *pchars;
}

Answer 2

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

Что вы можете попробовать, так это развернуть цикл, сделать более крупные шаги и делать больше символов каждый раз в цикле, чтобы удалить некоторые издержки цикла.

Answer 3

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

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

Итак, вы можете сделать следующее:

1. Распаковать четырехбитные значения в 8-битные, используя умножение или аналогичные инструкции.
2. Используйте pshufb, инструкцию SSSE3 (только для Core2). Он принимает массив из 16 8-битных входных значений и перемешивает их на основе 16 8-битных индексов во втором векторе. Поскольку у вас есть только 16 возможных символов, это подходит идеально; входной массив - это вектор от 0 до F символов, а индексный массив - это ваш распакованный массив 4-битных значений.

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

Итак, вычислительными шагами:

1. A B C D E F G H I J K L M N O P (64-битный вектор входных значений, «Вектор A») -> 0A 0B 0C 0D 0E 0F 0G 0H 0I 0J 0K 0L 0M 0N 0O 0P (128-битный вектор индексов, «Вектор B»). Самый простой способ - это, вероятно, два 64-битных умножения.
2. pshub [0123456789ABCDEF], вектор B

Answer 4

Функция, показанная при написании этого сообщения, выдает неправильный вывод, даже когда _hex2asciiU_value полностью указан. Следующий код работает, и на моем MacBook Pro с тактовой частотой 2,33 ГГц за 200 000 000 000 символов у меня уходит около 1,9 секунды.

#include <iostream>

using namespace std;

static const size_t _h2alen = 256;
static char _hex2asciiU_value[_h2alen][3];

string char_to_hex( const unsigned char* _pArray, unsigned int _len )
{
    string str;
    str.resize(_len*2);
    char* pszHex = &str[0];
    const unsigned char* pEnd = _pArray + _len;
    const char* pHex = _hex2asciiU_value[0];
    for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++, pszHex += 2 ) {
       pszHex[0] = _hex2asciiU_value[*pChar][0];
       pszHex[1] = _hex2asciiU_value[*pChar][1];
    }
    return str;
}


int main() {
  for(int i=0; i<_h2alen; i++) {
    snprintf(_hex2asciiU_value[i], 3,"%02X", i);
  }
  size_t len = 200000000;
  char* a = new char[len];
  string t1;
  string t2;
  clock_t start;
  srand(time(NULL));
  for(int i=0; i<len; i++) a[i] = rand()&0xFF;
  start = clock();
  t1=char_to_hex((const unsigned char*)a, len);
  cout << "char_to_hex conversion took ---> " << (clock() - start)/(double)CLOCKS_PER_SEC << " seconds\n";
}

Answer 5

Я обнаружил, что использование индекса в массиве, а не указателя, может ускорить процесс. Все зависит от того, как ваш компилятор решит оптимизировать. Ключевым моментом является то, что процессор имеет инструкции для выполнения сложных операций, таких как [i * 2 + 1], в одной инструкции.

Answer 6

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

Знаете, в gcc флаги от '-O1' до '-03'.