упражнение с символом [] для преобразования в шестнадцатеричную строку
https://stackoverflow.com/questions/69115
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Ниже приведена моя текущая функция преобразования символа * в шестнадцатеричную строку.Я написал это как упражнение по манипулированию битами.На 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;
}
Обновления
Добавлен временной код
Брайан Р.Бонди:замените std::string буфером выделения кучи и измените ofs*16 на ofs << 4 - однако выделенный буфер кучи, похоже, замедляет его работу?- результат ~ 11 мс
Antti Sykäri: замените внутренний контур на
int upper = *pChar >> 4;
int lower = *pChar & 0x0f;
pszHex[0] = pHex[upper];
pszHex[1] = pHex[lower];
результат ~ 8 мс
Роберт:заменить _hex2asciiU_value с полной таблицей из 256 записей, жертвуя объемом памяти, но получая результат ~ 7 мс!
ХойХой:Отметил, что это приводило к неверным результатам
Решение
За счет увеличения объема памяти вы можете создать полную таблицу шестнадцатеричных кодов из 256 элементов:
static const char _hex2asciiU_value[256][2] =
{ {'0','0'}, {'0','1'}, /* ..., */ {'F','E'},{'F','F'} };
Затем направьте индекс в таблицу, никаких битовых манипуляций не требуется.
const char *pHexVal = pHex[*pChar];
pszHex[0] = pHexVal[0];
pszHex[1] = pHexVal[1];
Другие советы
Эта функция сборки (основана на моем предыдущем посте здесь, но мне пришлось немного изменить концепцию, чтобы заставить ее действительно работать) обрабатывает 3,3 миллиарда входных символов в секунду (6,6 миллиарда выходных символов) на одном ядре Core 2 Conroe 3GHz.Пенрин, вероятно, быстрее.
%include "x86inc.asm"
SECTION_RODATA
pb_f0: times 16 db 0xf0
pb_0f: times 16 db 0x0f
pb_hex: db 48,49,50,51,52,53,54,55,56,57,65,66,67,68,69,70
SECTION .text
; int convert_string_to_hex( char *input, char *output, int len )
cglobal _convert_string_to_hex,3,3
movdqa xmm6, [pb_f0 GLOBAL]
movdqa xmm7, [pb_0f GLOBAL]
.loop:
movdqa xmm5, [pb_hex GLOBAL]
movdqa xmm4, [pb_hex GLOBAL]
movq xmm0, [r0+r2-8]
movq xmm2, [r0+r2-16]
movq xmm1, xmm0
movq xmm3, xmm2
pand xmm0, xmm6 ;high bits
pand xmm2, xmm6
psrlq xmm0, 4
psrlq xmm2, 4
pand xmm1, xmm7 ;low bits
pand xmm3, xmm7
punpcklbw xmm0, xmm1
punpcklbw xmm2, xmm3
pshufb xmm4, xmm0
pshufb xmm5, xmm2
movdqa [r1+r2*2-16], xmm4
movdqa [r1+r2*2-32], xmm5
sub r2, 16
jg .loop
REP_RET
Обратите внимание, что он использует синтаксис сборки x264, что делает его более переносимым (для 32-разрядных версий по сравнению с 64-разрядными и т.д.).Преобразовать это в выбранный вами синтаксис тривиально:r0, r1, r2 - это три аргумента функций в регистрах.Это немного похоже на псевдокод.Или вы можете просто получить common/x86 / x86inc.asm из дерева x264 и включить это, чтобы запустить его изначально.
P.S.Переполнение стека, я не прав, что трачу время на такую тривиальную вещь?Или это действительно потрясающе?
Более быстрая имплантация C
Это выполняется почти в 3 раза быстрее, чем реализация на C ++.Не уверен, почему, потому что это очень похоже.Для последней реализации C ++, которую я опубликовал, потребовалось 6,8 секунды, чтобы просмотреть массив из 200 000 000 символов.Реализация заняла всего 2,2 секунды.
#include <stdio.h>
#include <stdlib.h>
char* char_to_hex(const unsigned char* p_array,
unsigned int p_array_len,
char** hex2ascii)
{
unsigned char* str = malloc(p_array_len*2+1);
const unsigned char* p_end = p_array + p_array_len;
size_t pos=0;
const unsigned char* p;
for( p = p_array; p != p_end; p++, pos+=2 ) {
str[pos] = hex2ascii[*p][0];
str[pos+1] = hex2ascii[*p][1];
}
return (char*)str;
}
int main()
{
size_t hex2ascii_len = 256;
char** hex2ascii;
int i;
hex2ascii = malloc(hex2ascii_len*sizeof(char*));
for(i=0; i<hex2ascii_len; i++) {
hex2ascii[i] = malloc(3*sizeof(char));
snprintf(hex2ascii[i], 3,"%02X", i);
}
size_t len = 8;
const unsigned char a[] = "DO NOT WANT";
printf("%s\n", char_to_hex((const unsigned char*)a, len, (char**)hex2ascii));
}
Работайте с 32 битами одновременно (4 символа), затем при необходимости разберитесь с хвостом.Когда я выполнял это упражнение с кодировкой URL, полный поиск по таблице для каждого символа выполнялся немного быстрее, чем логические конструкции, поэтому вы можете захотеть протестировать это и в контексте, чтобы учесть проблемы с кэшированием.
У меня это работает с unsigned char:
unsigned char c1 = byteVal >> 4;
unsigned char c2 = byteVal & 0x0f;
c1 += c1 <= 9 ? '0' : ('a' - 10);
c2 += c2 <= 9 ? '0' : ('a' - 10);
std::string sHex(" ");
sHex[0] = c1 ;
sHex[1] = c2 ;
//sHex - contain what we need. For example "0f"
Для единицы, вместо умножения на 16 сделайте bitshift << 4
Также не используйте std::string, вместо этого просто создайте буфер в куче , а затем delete IT.Это будет более эффективно, чем уничтожение объекта, которое требуется из строки.
это не будет иметь большого значения...*PChar-(ofs * 16) может быть выполнен с помощью [*PChar & 0x0F]
Это моя версия, которая, в отличие от версии OP, не предполагает, что std::basic_string имеет свои данные в смежном регионе:
#include <string>
using std::string;
static char const* digits("0123456789ABCDEF");
string
tohex(string const& data)
{
string result(data.size() * 2, 0);
string::iterator ptr(result.begin());
for (string::const_iterator cur(data.begin()), end(data.end()); cur != end; ++cur) {
unsigned char c(*cur);
*ptr++ = digits[c >> 4];
*ptr++ = digits[c & 15];
}
return result;
}
Я предполагаю, что это Windows + IA32.
Попробуйте использовать short int вместо двух шестнадцатеричных букв.
short int hex_table[256] = {'0'*256+'0', '1'*256+'0', '2'*256+'0', ..., 'E'*256+'F', 'F'*256+'F'};
unsigned short int* pszHex = &str[0];
stick = clock();
for (const unsigned char* pChar = _pArray; pChar != pEnd; pChar++)
*pszHex++ = hex_table[*pChar];
etick = clock();
Меняющийся
ofs = *pChar >> 4;
pszHex[0] = pHex[ofs];
pszHex[1] = pHex[*pChar-(ofs*16)];
Для
int upper = *pChar >> 4;
int lower = *pChar & 0x0f;
pszHex[0] = pHex[upper];
pszHex[1] = pHex[lower];
это приводит к ускорению примерно на 5%.
Записываем результат по два байта за раз, как предложено Роберт это приводит к ускорению примерно на 18%.Код меняется на:
_result.resize(_len*2);
short* pszHex = (short*) &_result[0];
const unsigned char* pEnd = _pArray + _len;
const char* pHex = _hex2asciiU_value;
for(const unsigned char* pChar = _pArray;
pChar != pEnd;
pChar++, ++pszHex )
{
*pszHex = bytes_to_chars[*pChar];
}
Требуемая инициализация:
short short_table[256];
for (int i = 0; i < 256; ++i)
{
char* pc = (char*) &short_table[i];
pc[0] = _hex2asciiU_value[i >> 4];
pc[1] = _hex2asciiU_value[i & 0x0f];
}
Выполнение этого по 2 байта за раз или по 4 байта за раз, вероятно, приведет к еще большему ускорению, как указано Аллан Уинд, но тогда это становится сложнее, когда вам приходится иметь дело со странными персонажами.
Если вам хочется приключений, вы можете попытаться адаптироваться Устройство Даффа чтобы сделать это.
Результаты получены на процессоре Intel Core Duo 2 и gcc -O3.
Всегда измеряйте что вы на самом деле получаете более быстрые результаты — пессимизация, притворяющаяся оптимизацией, более чем бесполезна.
Всегда проверяйте чтобы вы получили правильные результаты — ошибка, притворяющаяся оптимизацией, совершенно опасна.
И всегда имейте в виду компромисс между скоростью и удобочитаемостью — срок службы слишком короток, чтобы кто-либо мог поддерживать нечитаемый код.
(Обязательная ссылка к кодированию для жестокий психопат, который знает, где ты живешь.)
Убедитесь, что оптимизация вашего компилятора включена на самый высокий рабочий уровень.
Вы знаете, такие флаги, как от '-O1' до '-03' в gcc.
Я обнаружил, что использование индекса в массиве, а не указателя, может немного ускорить процесс.Все зависит от того, как ваш компилятор выберет оптимизацию.Ключ в том, что у процессора есть инструкции для выполнения сложных действий, таких как [i* 2+ 1], в одной инструкции.
Если вы здесь слишком одержимы скоростью, вы можете сделать следующее:
Каждый символ состоит из одного байта, представляющего два шестнадцатеричных значения.Таким образом, каждый символ на самом деле представляет собой два четырехбитовых значения.
Итак, вы можете сделать следующее:
- Распакуйте четырехразрядные значения в 8-разрядные, используя команду умножения или аналогичную инструкцию.
- Используйте pshufb, инструкцию SSSE3 (правда, только для Core2).Он принимает массив из 16 8-битных входных значений и перетасовывает их на основе 16 8-битных индексов во втором векторе.Поскольку у вас есть только 16 возможных символов, это подходит идеально;входной массив представляет собой вектор от 0 до F символов, а индексный массив - это ваш распакованный массив 4-битных значений.
Таким образом, в единая инструкция, вы будете выполнять 16 поиск по таблицам за меньшее количество часов, чем обычно требуется для выполнения только одного (pshufb - это задержка в 1 такт на Penryn).
Итак, в вычислительных шагах:
- 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-битных умножения.
- pshub [0123456789ABCDEF], Вектор B
Я не уверен, что делать это большим количеством байтов за раз будет лучше...вероятно, вы просто получите тонны промахов в кэше и значительно замедлите его работу.
Однако что вы могли бы попробовать, так это развернуть цикл, выполнять более крупные шаги и вводить больше символов каждый раз в цикле, чтобы убрать часть накладных расходов цикла.
Стабильно получаю ~ 4 мс на моем Athlon 64 4200+ (~ 7 мс с оригинальным кодом)
for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++) {
const char* pchars = _hex2asciiU_value[*pChar];
*pszHex++ = *pchars++;
*pszHex++ = *pchars;
}
Функция, как показано, когда я пишу это, выдает неверный вывод, даже если _hex2asciiU_value указано полностью.Следующий код работает, и на моем Macbook Pro с частотой 2,33 ГГц он выполняется примерно за 1,9 секунды для 200 000 000 миллионов символов.
#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";
}
