char[] a stringa esadecimale esercizio

Question

Qui di seguito la mia attuale char* a stringa esadecimale funzione.L'ho scritto come un esercizio di manipolazione dei bit.Si prende ~7ms su un AMD Athlon MP 2800+ a hexify 10 milioni di array di byte.C'è qualche trucco o altro modo che mi manca?

Come posso rendere questo più veloce?

Compilato con -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;
}

Aggiornamenti

Aggiunto codice dei tempi

Brian R.Bondy:sostituire le std::string con un mucchio alloc piacerebbe buffer e cambiare ofs*16 ofs << 4 - tuttavia l'heap buffer allocato sembra rallentare un po'?- risultato ~11ms

Antti Sykäri:sostituire ciclo interno con

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

risultato ~8ms

Robert:sostituire _hex2asciiU_value con un pieno di voce di 256 tabella, sacrificare spazio di memoria ma il risultato ~7ms!

HoyHoy:Notato che stava producendo risultati non corretti

Answer 1

A costo di più la memoria, è possibile creare una voce di 256 tabella dei codici esadecimali:

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

Quindi diretto indice nella tabella, nessun bit di giocherellare richiesto.

const char *pHexVal = pHex[*pChar];
pszHex[0] = pHexVal[0];
pszHex[1] = pHexVal[1];

Answer 2

Questa assemblea funzione (in base al largo il mio precedente post qui, ma ho dovuto modificare il concetto un po ' per farlo funzionare realmente) i processi di 3,3 miliardi di ingresso caratteri al secondo (6,6 miliardi di caratteri di uscita) su un core di un Core 2 Conroe 3Ghz.Penryn è probabilmente più veloce.

%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

Nota se si utilizza x264 assemblea sintassi, che lo rende più portabile (a 32 bit vs 64 bit, ecc).Per convertire questo in sintassi della vostra scelta è banale:r0, r1, r2 sono i tre argomenti alle funzioni in registri.Un po ' come pseudocodice.O si può solo ottenere common/x86/x86inc.asm dal x264 albero e comprendono che per eseguire in modo nativo.

P. S.Stack Overflow, ho sbagliato per perdere tempo su una cosa banale?O è questo impressionante?

Answer 3

Più Veloce Di Un'Implementazione C

Questo corre quasi 3 volte più veloce l'implementazione di C++.Non so perché, come è abbastanza simile.Per l'ultima implementazione di C++ che ho postato è preso 6,8 secondi per eseguire attraverso un 200,000,000 array di caratteri.L'attuazione preso solo il 2,2 secondi.

#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));
}

Answer 4

Operare su 32 bit alla volta (4 caratteri), per poi affrontare la coda, se necessario.Quando ho fatto questo esercizio con codifica url, un tavolo pieno di ricerca per ogni char era leggermente più veloce di logica costrutti, quindi si consiglia di fare una prova in un contesto di prendere problemi di memorizzazione nella cache in considerazione.

Answer 5

A me funziona con 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"

Answer 6

Per una volta, invece di moltiplicare per 16 fare un bitshift << 4

Inoltre, non usare il std::string, invece basta creare un buffer di heap e poi delete si.Sarà più efficiente, più che l'oggetto di distruzione che è necessario partire dalla stringa.

Answer 7

non andando a fare un sacco di differenza...*pChar-(ofs*16) può essere fatto con [*pCHar & 0x0F]

Answer 8

Questa è la mia versione, che, a differenza dell'OP versione, non si assume che std::basic_string i dati nella contigua regione:

#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;
}

Answer 9

Presumo che ciò è Windows+IA32.
Provare a utilizzare short int invece di due esadecimale lettere.

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();

Answer 10

Modifica

    ofs = *pChar >> 4;
    pszHex[0] = pHex[ofs];
    pszHex[1] = pHex[*pChar-(ofs*16)];

per

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

risultati in circa il 5% di aumento della velocità.

Scrivere il risultato di due byte alla volta, come suggerito da Robert risultati in circa il 18% di aumento della velocità.Le modifiche al codice:

_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];
}

Richiesta di inizializzazione:

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];
}

Facendo 2 byte alla volta o 4 byte alla volta comporterà, probabilmente, anche una maggiore speedups, come sottolineato da Allan Vento, ma dopo diventa più difficile quando hai a che fare con i caratteri dispari.

Se vi sentite avventurosi, si potrebbe provare ad adattare Duff dispositivo per fare questo.

I risultati sono su un processore Intel Core 2 Duo processore e gcc -O3.

Misurare sempre che effettivamente ottenere più velocemente i risultati — un pessimization fingendo di essere un'ottimizzazione è meno che inutile.

Sempre test che si ottiene il risultato corretto un bug che finge di essere un programma di ottimizzazione è addirittura pericoloso.

E tenete sempre a mente il compromesso tra velocità e leggibilità — la vita è troppo breve per chiunque di mantenere un codice illeggibile.

(Di riferimento obbligatorio per la codifica per la violento psicopatico che sa dove si vive.)

Answer 11

Assicuratevi che il vostro ottimizzazione del compilatore è attivata al più alto livello di lavoro.

Si sa, le bandiere come '-O1' a '-03' di gcc.

Answer 12

Ho trovato che l'uso di un indice in un array, piuttosto che un puntatore, può accelerare le cose un segno di spunta.Tutto dipende da come il compilatore sceglie di ottimizzare.La chiave è che il processore ha le istruzioni per fare cose complesse come [i*2+1] in una singola istruzione.

Answer 13

Se sei piuttosto ossessiva di velocità, qui, è possibile effettuare le seguenti operazioni:

Ogni personaggio è un byte, che rappresentano due valori esadecimali.Così, ogni personaggio è davvero a due o quattro valori di bit.

Così, è possibile effettuare le seguenti operazioni:

1. Decomprimere i quattro bit valori a 8 bit valori utilizzando una moltiplicazione o simili istruzione.
2. Utilizzare pshufb, le SSSE3 istruzione (Core2-solo però).Si accetta un array di 16 a 8 bit valori di input e di mischia, basate sul 16 a 8 bit, gli indici di un secondo vettore.Dal momento che hai solo 16 caratteri possibili, questo si adatta perfettamente;l'array di input un vettore di 0 e F di caratteri, e l'indice dell'array è il tuo scompattato array di 4 bit valori.

Così, in una singola istruzione, si avrà eseguito 16 tabella ricerche in un minor numero di orologi che normalmente serve per fare un solo (pshufb è 1 orologio di latenza su Penryn).

Così, in computazionale seguente procedura:

1. A B C D E F G H I J K L M N O P (64-bit vettore di valori di input, "Vector") -> 0A 0B 0C 0D 0E 0F 0 G 0 H 0I 0J 0K 0L 0M 0N 0O 0P (128-bit vettore di indici, "Vector"B").Il modo più semplice è probabilmente due a 64 bit moltiplica.
2. pshub [0123456789ABCDEF], Vettore B

Answer 14

Io non sono sicuro di farlo più byte alla volta sarà migliore...probabilmente solo ottenere tonnellate di cache miss e rallentare in modo significativo.

Quello che si potrebbe provare è quello di srotolare il ciclo, però, prendere grandi passi e fare di più caratteri per ogni iterazione del ciclo, per rimuovere alcuni dei loop.

Answer 15

Ottenere sempre ~4ms sul mio Athlon 64 4200+ (~7ms con il codice originale)

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

Answer 16

La funzione come mostrato quando sto scrivendo questo produce output non corretto anche quando _hex2asciiU_value è completamente specificata.Il codice seguente funziona, e sul mio 2.33 GHz Macbook Pro viene eseguito in circa 1,9 secondi per n. 200.000.000 milioni di caratteri.

#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";
}