char [] en hexagone

Question

Ci-dessous se trouve ma fonction char * to hex string actuelle. Je l'ai écrit comme un exercice de manipulation de bits. Il faut environ 7 ms sur un processeur AMD Athlon MP 2800+ pour hexifier un tableau de 10 millions d’octets. Y a-t-il un truc ou un autre moyen qui me manque?

Comment puis-je accélérer les choses?

Compilé avec -O3 en 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;
}

Mises à jour

Code de synchronisation ajouté

Brian R. Bondy : remplacez le std :: string par un tas alloué tampon et changement de * 16 en ofs < < 4 - Cependant, le tampon alloué par le tas semble le ralentir? - résultat ~ 11ms

Antti Syk & # 228; ri : remplacez la boucle interne par

.

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

résultat ~ 8ms

Robert : remplacez _hex2asciiU_value par une table complète de 256 entrées, en sacrifiant l'espace mémoire mais le résultat. ~ 7ms!

HoyHoy : remarque que les résultats obtenus étaient incorrects

.

Answer 1

Au prix de davantage de mémoire, vous pouvez créer un tableau complet de 256 codes hexadécimaux:

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

Ensuite, index direct dans la table, aucun bidouillage n'est requis.

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

Answer 2

Cette fonction d'assemblage (basée sur mon précédent article ici, mais j'ai dû modifier un peu le concept pour qu'il fonctionne réellement) traite 3,3 milliards de caractères en entrée par seconde (6,6 milliards en caractères de sortie) sur un cœur d'un Core 2. Conroe 3Ghz. Penryn est probablement plus rapide.

%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

Notez qu’il utilise la syntaxe d’assemblage x264, ce qui le rend plus portable (32 bits par rapport à 64 bits, etc.). Convertir cela en une syntaxe de votre choix est simple: r0, r1, r2 sont les trois arguments des fonctions dans les registres. C'est un peu comme un pseudocode. Vous pouvez également obtenir common / x86 / x86inc.asm à partir de l’arborescence x264 et l’inclure pour l’exécuter en mode natif.

P.S. Stack Overflow, ai-je tort de perdre du temps sur une chose aussi triviale? Ou est-ce génial?

Answer 3

Une implémentation plus rapide de C

Cela est presque 3 fois plus rapide que l’implémentation C ++. Je ne sais pas pourquoi car c'est assez similaire. Pour la dernière implémentation C ++ que j'ai publiée, il a fallu 6,8 secondes pour parcourir un tableau de 200 000 000 caractères. La mise en œuvre n'a pris que 2,2 secondes.

#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

Opère sur 32 bits à la fois (4 caractères), puis traite la queue si nécessaire. Lorsque j'ai fait cet exercice avec le codage en url, la recherche d'une table complète pour chaque caractère était légèrement plus rapide que les constructions logiques, vous pouvez donc le tester également dans son contexte pour prendre en compte les problèmes de mise en cache.

Answer 5

Cela fonctionne pour moi avec 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

Pour l'un, au lieu de multiplier par 16 faire un bitshift << 4

N'utilisez pas non plus le std::string, créez simplement un tampon sur le tas, puis delete le. Il sera plus efficace que la destruction d’objet requise par la chaîne.

Answer 7

ne fera pas beaucoup de différence ... * pChar- (ofs * 16) peut être fait avec [* pCHar & amp; 0x0F]

Answer 8

Ceci est ma version qui, contrairement à la version de l'OP, ne suppose pas que std::basic_string a ses données dans une région contiguë:

#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

Je suppose qu'il s'agit de Windows + IA32.
Essayez d’utiliser short int au lieu des deux lettres hexadécimales.

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

Changer

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

entraîne une accélération d'environ 5%.

L'écriture du résultat, deux octets à la fois, comme le suggère Robert environ 18% d'accélération. Le code devient:

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

Initialisation requise:

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

Le faire 2 octets à la fois ou 4 octets à la fois entraînera probablement des accélérations encore plus rapides, comme le souligne Allan Wind , mais cela devient encore plus délicat lorsque vous devez gérer des caractères étranges.

Si vous vous sentez aventureux, essayez d’adapter le au périphérique de Duff . faites cela.

Les résultats concernent un processeur Intel Core Duo 2 et gcc -O3.

Mesurez toujours que vous obtenez des résultats plus rapides & # 8212; une pessimisation prétendant être une optimisation vaut bien moins que rien.

Vérifiez toujours que vous obtenez les bons résultats & # 8212; un bogue prétendant être une optimisation est carrément dangereux.

Et gardez toujours à l'esprit le compromis entre vitesse et lisibilité & # 8212; la vie est trop courte pour que quiconque puisse conserver du code illisible.

( référence obligatoire au codage du psychopathe violent qui sait où vous habitez .)

Answer 11

Assurez-vous que l'optimisation de votre compilateur est activée au niveau de travail le plus élevé.

Vous savez, des drapeaux tels que "-O1" à "-03" dans gcc.

Answer 12

J'ai constaté que l'utilisation d'un index dans un tableau, plutôt que d'un pointeur, peut accélérer les choses. Tout dépend de la manière dont votre compilateur choisit d'optimiser. La clé est que le processeur dispose d’instructions lui permettant de réaliser des opérations complexes telles que [i * 2 + 1] en une seule instruction.

Answer 13

Si vous êtes plutôt obsédé par la vitesse ici, vous pouvez procéder comme suit:

Chaque caractère est un octet, représentant deux valeurs hexadécimales. Ainsi, chaque caractère correspond en réalité à deux valeurs de quatre bits.

Vous pouvez donc effectuer les opérations suivantes:

1. Décompressez les valeurs de quatre bits en valeurs de 8 bits en utilisant une multiplication ou une instruction similaire.
2. Utilisez pshufb, l'instruction SSSE3 (si Core2 uniquement). Il prend un tableau de 16 valeurs d'entrée de 8 bits et les mélange en fonction des 16 indices de 8 bits d'un second vecteur. Comme vous n'avez que 16 caractères possibles, cela correspond parfaitement; le tableau d'entrée est un vecteur de 0 à F, et le tableau d'index est votre tableau non compressé de valeurs à 4 bits.

Ainsi, dans une instruction unique , vous aurez effectué 16 consultations de table dans moins d'horloges qu'il n'en faut normalement pour en faire une seule (pshufb correspond à une horloge de latence sur Penryn. ).

Donc, en étapes de calcul:

1. A B C D F G H I J K L M N O P (vecteur de valeurs d'entrée de 64 bits, " vecteur A ") - > 0A 0B 0C 0D 0E 0F 0G 0H 0I 0J 0K 0L 0M 0N 0O 0P (vecteur à 128 bits d'indices, & Quot; vecteur B & Quot;). La méthode la plus simple consiste probablement à utiliser deux multiplications 64 bits.
2. pshub [0123456789ABCDEF], vecteur B

Answer 14

Je ne suis pas sûr que le fait de multiplier les octets à la fois sera préférable ... vous obtiendrez probablement des tonnes de données manquantes dans la mémoire cache et le ralentirez considérablement.

Vous pouvez toutefois essayer de dérouler la boucle, franchir des étapes plus importantes et faire plus de caractères à chaque fois dans la boucle pour éliminer une partie de la surcharge de la boucle.

Answer 15

Toujours obtenir environ 4 ms sur mon Athlon 64 4200+ (~ 7 ms avec le code d'origine)

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

Answer 16

La fonction telle qu'elle est affichée lors de l'écriture produit des résultats incorrects, même si _hex2asciiU_value est complètement spécifié. Le code suivant fonctionne et sur mon Macbook Pro à 2,33 GHz, il s'exécute en environ 1,9 seconde pour 200 000 000 millions de caractères.

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