char[] para exercício de string hexadecimal
https://stackoverflow.com/questions/69115
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Abaixo está minha função atual de char* para hexadecimal.Eu escrevi isso como um exercício de manipulação de bits.São necessários cerca de 7 ms em um AMD Athlon MP 2800+ para hexificar uma matriz de 10 milhões de bytes.Existe algum truque ou outra maneira que estou perdendo?
Como posso tornar isso mais rápido?
Compilado com -O3 em 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;
}
Atualizações
Adicionado código de tempo
Brian R.Bondy:substitua o std::string por um buffer alocado para heap e altere ofs*16 para ofs << 4 - no entanto, o buffer alocado para heap parece desacelerá-lo?- resultado ~11ms
Antti Sykäri:substitua o loop interno por
int upper = *pChar >> 4;
int lower = *pChar & 0x0f;
pszHex[0] = pHex[upper];
pszHex[1] = pHex[lower];
resultado ~8ms
Roberto:substituir _hex2asciiU_value com uma tabela completa de 256 entradas, sacrificando espaço de memória, mas resultando em aproximadamente 7ms!
Ei, ei:Observou que estava produzindo resultados incorretos
Solução
Ao custo de mais memória, você pode criar uma tabela completa de 256 entradas de códigos hexadecimais:
static const char _hex2asciiU_value[256][2] =
{ {'0','0'}, {'0','1'}, /* ..., */ {'F','E'},{'F','F'} };
Em seguida, direcione o índice para a tabela, sem necessidade de mexer um pouco.
const char *pHexVal = pHex[*pChar];
pszHex[0] = pHexVal[0];
pszHex[1] = pHexVal[1];
Outras dicas
Esta função de montagem (baseada em meu post anterior aqui, mas tive que modificar um pouco o conceito para que realmente funcionasse) processa 3,3 bilhões de caracteres de entrada por segundo (6,6 bilhões de caracteres de saída) em um núcleo de um Core 2 Conroe 3Ghz.Penryn provavelmente é mais rápido.
%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
Observe que ele usa sintaxe assembly x264, o que o torna mais portátil (para 32 bits versus 64 bits, etc.).Converter isso na sintaxe de sua escolha é trivial:r0, r1, r2 são os três argumentos para as funções nos registradores.É um pouco como pseudocódigo.Ou você pode simplesmente obter common/x86/x86inc.asm da árvore x264 e incluí-lo para executá-lo nativamente.
P.S.Stack Overflow, estou errado em perder tempo com uma coisa tão trivial?Ou isso é incrível?
Implementação C mais rápida
Isso é executado quase 3x mais rápido que a implementação C++.Não sei por que, pois é muito semelhante.Para a última implementação de C++ que publiquei, foram necessários 6,8 segundos para percorrer uma matriz de 200.000.000 caracteres.A implementação levou apenas 2,2 segundos.
#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));
}
Opere em 32 bits por vez (4 caracteres) e, em seguida, lide com a cauda, se necessário.Quando fiz este exercício com a codificação de URL, uma pesquisa de tabela completa para cada caractere foi um pouco mais rápida do que as construções lógicas, portanto, você também pode querer testar isso no contexto para levar em consideração os problemas de cache.
Funciona para mim com 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"
Por um lado, em vez de multiplicar por 16 faça um bitshift << 4
Também não use o std::string, em vez disso, basta criar um buffer no heap e depois delete isto.Será mais eficiente do que a destruição de objetos necessária na string.
não vai fazer muita diferença...*pChar-(ofs*16) pode ser feito com [*pCHar & 0x0F]
Esta é a minha versão, que, ao contrário da versão do OP, não pressupõe que std::basic_string tem seus dados em região contígua:
#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;
}
Presumo que seja Windows + IA32.
Tente usar short int em vez das duas letras hexadecimais.
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();
Mudando
ofs = *pChar >> 4;
pszHex[0] = pHex[ofs];
pszHex[1] = pHex[*pChar-(ofs*16)];
para
int upper = *pChar >> 4;
int lower = *pChar & 0x0f;
pszHex[0] = pHex[upper];
pszHex[1] = pHex[lower];
resulta em aproximadamente 5% de aceleração.
Escrevendo o resultado dois bytes por vez, conforme sugerido por Roberto resulta em cerca de 18% de aceleração.O código muda para:
_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];
}
Inicialização necessária:
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];
}
Fazer isso 2 bytes por vez ou 4 bytes por vez provavelmente resultará em acelerações ainda maiores, conforme apontado por Allan Vento, mas fica mais complicado quando você tem que lidar com personagens estranhos.
Se você estiver se sentindo aventureiro, você pode tentar se adaptar Dispositivo de Duff para fazer isso.
Os resultados estão em um processador Intel Core Duo 2 e gcc -O3.
Sempre meça que você realmente obtém resultados mais rápidos - uma pessimização fingindo ser uma otimização não vale nada.
Sempre teste que você obtenha os resultados corretos - um bug que finge ser uma otimização é totalmente perigoso.
E tenha sempre em mente a compensação entre velocidade e legibilidade – a vida é muito curta para alguém manter um código ilegível.
(Referência obrigatória para a codificação do psicopata violento que sabe onde você mora.)
Certifique-se de que a otimização do seu compilador esteja ativada no nível de trabalho mais alto.
Você sabe, sinalizadores como '-O1' a '-03' no gcc.
Descobri que usar um índice em uma matriz, em vez de um ponteiro, pode acelerar as coisas.Tudo depende de como o seu compilador escolhe otimizar.A chave é que o processador possui instruções para fazer coisas complexas como [i*2+1] em uma única instrução.
Se você é bastante obsessivo com velocidade aqui, você pode fazer o seguinte:
Cada caractere é um byte, representando dois valores hexadecimais.Assim, cada caractere é na verdade dois valores de quatro bits.
Então, você pode fazer o seguinte:
- Descompacte os valores de quatro bits em valores de 8 bits usando uma multiplicação ou instrução semelhante.
- Use pshufb, a instrução SSSE3 (embora apenas Core2).Ele pega uma matriz de 16 valores de entrada de 8 bits e os embaralha com base nos 16 índices de 8 bits em um segundo vetor.Como você tem apenas 16 caracteres possíveis, isso se encaixa perfeitamente;a matriz de entrada é um vetor de caracteres de 0 a F e a matriz de índice é sua matriz descompactada de valores de 4 bits.
Assim, em um instrução única, você terá realizado 16 pesquisas de tabela em menos clocks do que normalmente leva para fazer apenas um (pshufb tem latência de 1 clock em Penryn).
Então, em etapas computacionais:
- A B C D E F G H I J K L M N O P (vetor de valores de entrada de 64 bits, "Vetor A") -> 0A 0B 0C 0D 0E 0F 0G 0H 0I 0J 0K 0L 0M 0N 0O 0P (vetor de índices de 128 bits, "Vetor B").A maneira mais fácil são provavelmente duas multiplicações de 64 bits.
- pshub [0123456789ABCDEF], Vetor B
Não tenho certeza se fazer mais bytes por vez será melhor ...você provavelmente terá toneladas de falhas de cache e o reduzirá significativamente.
O que você pode tentar é desenrolar o loop, dar passos maiores e executar mais caracteres a cada vez que passa pelo loop, para remover parte da sobrecarga do loop.
Obtendo consistentemente ~ 4 ms no meu Athlon 64 4200+ (~ 7 ms com o código original)
for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++) {
const char* pchars = _hex2asciiU_value[*pChar];
*pszHex++ = *pchars++;
*pszHex++ = *pchars;
}
A função mostrada quando escrevo isso produz uma saída incorreta mesmo quando _hex2asciiU_value está totalmente especificado.O código a seguir funciona e, no meu Macbook Pro de 2,33 GHz, é executado em cerca de 1,9 segundos para 200 milhões de caracteres.
#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";
}
