<p>Below is my current char* to hex string function. I wrote it as an exercise in bit manipulation. It takes ~7ms on a AMD Athlon MP 2800+ to hexify a 10 million byte array. Is there any trick or other way that I am missing?</p>

<p>How can I make this faster?</p>

<p>Compiled with -O3 in g++</p>

<pre><code>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 = &amp;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 &lt;&lt; "ticks to hexify " &lt;&lt; etick - stick &lt;&lt; std::endl;

    return str;
}
</code></pre>

<p><strong>Updates</strong></p>

<p>Added timing code</p>

<p><a href="https://stackoverflow.com/questions/69115/char-to-hex-string-exercise#69126">Brian R. Bondy</a>: replace the std::string with a heap alloc'd buffer and change ofs*16 to ofs &lt;&lt; 4 - however the heap allocated buffer seems to slow it down? - result ~11ms</p>

<p><a href="https://stackoverflow.com/questions/69115/#69305">Antti Sykäri</a>:replace inner loop with </p>

<pre><code> int upper = *pChar &gt;&gt; 4;
 int lower = *pChar &amp; 0x0f;
 pszHex[0] = pHex[upper];
 pszHex[1] = pHex[lower];
</code></pre>

<p>result ~8ms</p>

<p><a href="https://stackoverflow.com/questions/69115?sort=votes#69218">Robert</a>: replace <code>_hex2asciiU_value</code> with a full 256-entry table, sacrificing memory space but result ~7ms!</p>

<p><a href="https://stackoverflow.com/questions/69115/char-to-hex-string-exercise#70254">HoyHoy</a>: Noted it was producing incorrect results</p>

[{'answer_id': 69126, 'author': 'Brian R. Bondy', 'author_id': 3153, 'author_profile': 'https://Stackoverflow.com/users/3153', 'pm_score': 2, 'selected': False, 'text': "<p>For one, instead of multiplying by <code>16</code> do a <code>bitshift &lt;&lt; 4</code></p>\n\n<p>Also don't use the <code>std::string</code>, instead just create a buffer on the heap and then <code>delete</code> it. It will be more efficient than the object destruction that is needed from the string.</p>\n"}, {'answer_id': 69132, 'author': 'Allan Wind', 'author_id': 9706, 'author_profile': 'https://Stackoverflow.com/users/9706', 'pm_score': 2, 'selected': False, 'text': '<p>Operate on 32 bits at a time (4 chars), then deal with the tail if needed.  When I did this exercise with url encoding a full table lookup for each char was slightly faster than logic constructs, so you may want to test this in context as well to take caching issues into account.</p>\n'}, {'answer_id': 69139, 'author': 'Keith Nicholas', 'author_id': 10431, 'author_profile': 'https://Stackoverflow.com/users/10431', 'pm_score': 1, 'selected': False, 'text': '<p>not going to make a lot of difference...   *pChar-(ofs*16)   can be done with [*pCHar &amp; 0x0F]</p>\n'}, {'answer_id': 69197, 'author': 'C. K. Young', 'author_id': 13, 'author_profile': 'https://Stackoverflow.com/users/13', 'pm_score': 1, 'selected': False, 'text': '<p>This is my version, which, unlike the OP\'s version, doesn\'t assume that <code>std::basic_string</code> has its data in contiguous region:</p>\n\n<pre><code>#include &lt;string&gt;\n\nusing std::string;\n\nstatic char const* digits("0123456789ABCDEF");\n\nstring\ntohex(string const&amp; data)\n{\n    string result(data.size() * 2, 0);\n    string::iterator ptr(result.begin());\n    for (string::const_iterator cur(data.begin()), end(data.end()); cur != end; ++cur) {\n        unsigned char c(*cur);\n        *ptr++ = digits[c &gt;&gt; 4];\n        *ptr++ = digits[c &amp; 15];\n    }\n    return result;\n}\n</code></pre>\n'}, {'answer_id': 69213, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': "<p>Make sure your compiler optimization is turned on to the highest working level.</p>\n\n<p>You know, flags like '-O1' to '-03' in gcc.</p>\n"}, {'answer_id': 69218, 'author': 'Robert Groves', 'author_id': 3534, 'author_profile': 'https://Stackoverflow.com/users/3534', 'pm_score': 3, 'selected': True, 'text': "<p>At the cost of more memory you can create a full 256-entry table of the hex codes:</p>\n\n<pre><code>static const char _hex2asciiU_value[256][2] =\n    { {'0','0'}, {'0','1'}, /* ..., */ {'F','E'},{'F','F'} };\n</code></pre>\n\n<p>Then direct index into the table, no bit fiddling required.</p>\n\n<pre><code>const char *pHexVal = pHex[*pChar];\npszHex[0] = pHexVal[0];\npszHex[1] = pHexVal[1];\n</code></pre>\n"}, {'answer_id': 69305, 'author': 'Antti Kissaniemi', 'author_id': 2948, 'author_profile': 'https://Stackoverflow.com/users/2948', 'pm_score': 1, 'selected': False, 'text': '<p>Changing</p>\n\n<pre><code>    ofs = *pChar &gt;&gt; 4;\n    pszHex[0] = pHex[ofs];\n    pszHex[1] = pHex[*pChar-(ofs*16)];\n</code></pre>\n\n<p>to</p>\n\n<pre><code>    int upper = *pChar &gt;&gt; 4;\n    int lower = *pChar &amp; 0x0f;\n    pszHex[0] = pHex[upper];\n    pszHex[1] = pHex[lower];\n</code></pre>\n\n<p>results in roughly 5% speedup.</p>\n\n<p>Writing the result two bytes at time as suggested by <a href="https://stackoverflow.com/questions/69115/char-to-hex-string-exercise#69218">Robert</a> results in about 18% speedup. The code changes to:</p>\n\n<pre><code>_result.resize(_len*2);\nshort* pszHex = (short*) &amp;_result[0];\nconst unsigned char* pEnd = _pArray + _len;\n\nconst char* pHex = _hex2asciiU_value;\nfor(const unsigned char* pChar = _pArray;\n    pChar != pEnd;\n    pChar++, ++pszHex )\n{\n    *pszHex = bytes_to_chars[*pChar];\n}\n</code></pre>\n\n<p>Required initialization:</p>\n\n<pre><code>short short_table[256];\n\nfor (int i = 0; i &lt; 256; ++i)\n{\n    char* pc = (char*) &amp;short_table[i];\n    pc[0] = _hex2asciiU_value[i &gt;&gt; 4];\n    pc[1] = _hex2asciiU_value[i &amp; 0x0f];\n}\n</code></pre>\n\n<p>Doing it 2 bytes at a time or 4 bytes at a time will probably result in even greater speedups, as pointed out by <a href="https://stackoverflow.com/questions/69115/char-to-hex-string-exercise#69132">Allan Wind</a>, but then it gets trickier when you have to deal with the odd characters.</p>\n\n<p>If you\'re feeling adventurous, you might try to adapt <a href="http://en.wikipedia.org/wiki/Duff&#39;s_device" rel="nofollow noreferrer">Duff\'s device</a> to do this.</p>\n\n<p>Results are on an Intel Core Duo 2 processor and <code>gcc -O3</code>.</p>\n\n<p><strong>Always measure</strong> that you actually get faster results &mdash; a pessimization pretending to be an optimization is less than worthless.</p>\n\n<p><strong>Always test</strong> that you get the correct results &mdash; a bug pretending to be an optimization is downright dangerous.</p>\n\n<p>And <strong>always keep in mind</strong> the tradeoff between speed and readability &mdash; life is too short for anyone to maintain unreadable code.</p>\n\n<p>(<a href="http://c2.com/cgi/wiki?CodeForTheMaintainer" rel="nofollow noreferrer">Obligatory reference</a> to coding for the <a href="https://blog.codinghorror.com/coding-for-violent-psychopaths/" rel="nofollow noreferrer">violent psychopath who knows where you live</a>.)</p>\n'}, {'answer_id': 69499, 'author': 'Mark Ransom', 'author_id': 5987, 'author_profile': 'https://Stackoverflow.com/users/5987', 'pm_score': 0, 'selected': False, 'text': '<p>I have found that using an index into an array, rather than a pointer, can speed things up a tick.  It all depends on how your compiler chooses to optimize.  The key is that the processor has instructions to do complex things like [i*2+1] in a single instruction.</p>\n'}, {'answer_id': 70254, 'author': 'hoyhoy', 'author_id': 3499, 'author_profile': 'https://Stackoverflow.com/users/3499', 'pm_score': 0, 'selected': False, 'text': '<p>The function as it is shown when I\'m writing this produces incorrect output even when _hex2asciiU_value is fully specified. The following code works, and on my 2.33GHz Macbook Pro runs in about 1.9 seconds for 200,000,000 million characters. </p>\n\n<pre><code>#include &lt;iostream&gt;\n\nusing namespace std;\n\nstatic const size_t _h2alen = 256;\nstatic char _hex2asciiU_value[_h2alen][3];\n\nstring char_to_hex( const unsigned char* _pArray, unsigned int _len )\n{\n    string str;\n    str.resize(_len*2);\n    char* pszHex = &amp;str[0];\n    const unsigned char* pEnd = _pArray + _len;\n    const char* pHex = _hex2asciiU_value[0];\n    for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++, pszHex += 2 ) {\n       pszHex[0] = _hex2asciiU_value[*pChar][0];\n       pszHex[1] = _hex2asciiU_value[*pChar][1];\n    }\n    return str;\n}\n\n\nint main() {\n  for(int i=0; i&lt;_h2alen; i++) {\n    snprintf(_hex2asciiU_value[i], 3,"%02X", i);\n  }\n  size_t len = 200000000;\n  char* a = new char[len];\n  string t1;\n  string t2;\n  clock_t start;\n  srand(time(NULL));\n  for(int i=0; i&lt;len; i++) a[i] = rand()&amp;0xFF;\n  start = clock();\n  t1=char_to_hex((const unsigned char*)a, len);\n  cout &lt;&lt; "char_to_hex conversion took ---&gt; " &lt;&lt; (clock() - start)/(double)CLOCKS_PER_SEC &lt;&lt; " seconds\\n";\n}\n</code></pre>\n'}, {'answer_id': 70275, 'author': 'Dark Shikari', 'author_id': 11206, 'author_profile': 'https://Stackoverflow.com/users/11206', 'pm_score': 0, 'selected': False, 'text': '<p>If you\'re rather obsessive about speed here, you can do the following:</p>\n\n<p>Each character is one byte, representing two hex values.  Thus, each character is really two four-bit values.</p>\n\n<p>So, you can do the following:</p>\n\n<ol>\n<li>Unpack the four-bit values to 8-bit values using a multiplication or similar instruction.</li>\n<li>Use pshufb, the SSSE3 instruction (Core2-only though).  It takes an array of 16 8-bit input values and shuffles them based on the 16 8-bit indices in a second vector.  Since you have only 16 possible characters, this fits perfectly; the input array is a vector of 0 through F characters, and the index array is your unpacked array of 4-bit values.</li>\n</ol>\n\n<p>Thus, in a <em>single instruction</em>, you will have performed <strong>16 table lookups</strong> in fewer clocks than it normally takes to do just one (pshufb is 1 clock latency on Penryn).</p>\n\n<p>So, in computational steps:</p>\n\n<ol>\n<li>A B C D E F G H I J K L M N O P (64-bit vector of input values, "Vector A") -> 0A 0B 0C 0D 0E 0F 0G 0H 0I 0J 0K 0L 0M 0N 0O 0P (128-bit vector of indices, "Vector B").  The easiest way is probably two 64-bit multiplies.</li>\n<li>pshub [0123456789ABCDEF], Vector B</li>\n</ol>\n'}, {'answer_id': 70348, 'author': 'slicedlime', 'author_id': 11230, 'author_profile': 'https://Stackoverflow.com/users/11230', 'pm_score': 0, 'selected': False, 'text': "<p>I'm not sure doing it more bytes at a time will be better... you'll probably just get tons of cache misses and slow it down significantly.</p>\n\n<p>What you might try is to unroll the loop though, take larger steps and do more characters each time through the loop, to remove some of the loop overhead.</p>\n"}, {'answer_id': 72055, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': '<p>Consistently getting ~4ms on my Athlon 64 4200+ (~7ms with original code)</p>\n\n<pre><code>for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++) {\n    const char* pchars = _hex2asciiU_value[*pChar];\n    *pszHex++ = *pchars++;\n    *pszHex++ = *pchars;\n}\n</code></pre>\n'}, {'answer_id': 78611, 'author': 'hoyhoy', 'author_id': 3499, 'author_profile': 'https://Stackoverflow.com/users/3499', 'pm_score': 2, 'selected': False, 'text': '<p><strong>Faster C Implmentation</strong></p>\n\n<p>This runs nearly 3x faster than the C++ implementation.  Not sure why as it\'s pretty similar.  For the last C++ implementation that I posted it took 6.8 seconds to run through a 200,000,000 character array.  The implementation took only 2.2 seconds. </p>\n\n<pre><code>#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n\nchar* char_to_hex(const unsigned char* p_array, \n                  unsigned int p_array_len,\n                  char** hex2ascii)\n{\n    unsigned char* str = malloc(p_array_len*2+1);\n    const unsigned char* p_end = p_array + p_array_len;\n    size_t pos=0;\n    const unsigned char* p;\n    for( p = p_array; p != p_end; p++, pos+=2 ) {\n       str[pos] = hex2ascii[*p][0];\n       str[pos+1] = hex2ascii[*p][1];\n    }\n    return (char*)str;\n}\n\nint main()\n{\n  size_t hex2ascii_len = 256;\n  char** hex2ascii;\n  int i;\n  hex2ascii = malloc(hex2ascii_len*sizeof(char*));\n  for(i=0; i&lt;hex2ascii_len; i++) {\n    hex2ascii[i] = malloc(3*sizeof(char));    \n    snprintf(hex2ascii[i], 3,"%02X", i);\n  }\n  size_t len = 8;\n  const unsigned char a[] = "DO NOT WANT";\n  printf("%s\\n", char_to_hex((const unsigned char*)a, len, (char**)hex2ascii));\n}\n</code></pre>\n\n<p><img src="https://i.stack.imgur.com/3m8Hb.png" alt="enter image description here"></p>\n'}, {'answer_id': 78892, 'author': 'Dark Shikari', 'author_id': 11206, 'author_profile': 'https://Stackoverflow.com/users/11206', 'pm_score': 3, 'selected': False, 'text': '<p>This assembly function (based off my previous post here, but I had to modify the concept a bit to get it to actually work) processes 3.3 billion input characters per second (6.6 billion output characters) on one core of a Core 2 Conroe 3Ghz.  Penryn is probably faster.</p>\n\n<pre><code>%include "x86inc.asm"\n\nSECTION_RODATA\npb_f0: times 16 db 0xf0\npb_0f: times 16 db 0x0f\npb_hex: db 48,49,50,51,52,53,54,55,56,57,65,66,67,68,69,70\n\nSECTION .text\n\n; int convert_string_to_hex( char *input, char *output, int len )\n\ncglobal _convert_string_to_hex,3,3\n    movdqa xmm6, [pb_f0 GLOBAL]\n    movdqa xmm7, [pb_0f GLOBAL]\n.loop:\n    movdqa xmm5, [pb_hex GLOBAL]\n    movdqa xmm4, [pb_hex GLOBAL]\n    movq   xmm0, [r0+r2-8]\n    movq   xmm2, [r0+r2-16]\n    movq   xmm1, xmm0\n    movq   xmm3, xmm2\n    pand   xmm0, xmm6 ;high bits\n    pand   xmm2, xmm6\n    psrlq  xmm0, 4\n    psrlq  xmm2, 4\n    pand   xmm1, xmm7 ;low bits\n    pand   xmm3, xmm7\n    punpcklbw xmm0, xmm1\n    punpcklbw xmm2, xmm3\n    pshufb xmm4, xmm0\n    pshufb xmm5, xmm2\n    movdqa [r1+r2*2-16], xmm4\n    movdqa [r1+r2*2-32], xmm5\n    sub r2, 16\n    jg .loop\n    REP_RET\n</code></pre>\n\n<p>Note it uses x264 assembly syntax, which makes it more portable (to 32-bit vs 64-bit, etc).  To convert this into the syntax of your choice is trivial: r0, r1, r2 are the three arguments to the functions in registers.  Its a bit like pseudocode.  Or you can just get common/x86/x86inc.asm from the x264 tree and include that to run it natively.</p>\n\n<p>P.S. Stack Overflow, am I wrong for wasting time on such a trivial thing?  Or is this awesome?</p>\n'}, {'answer_id': 4431837, 'author': 'Mihai Vrinceanu', 'author_id': 540864, 'author_profile': 'https://Stackoverflow.com/users/540864', 'pm_score': 1, 'selected': False, 'text': "<p>I assume this is Windows+IA32.<br>\nTry to use short int instead of the two hexadecimal letters.</p>\n\n<pre><code>short int hex_table[256] = {'0'*256+'0', '1'*256+'0', '2'*256+'0', ..., 'E'*256+'F', 'F'*256+'F'};\nunsigned short int* pszHex = &amp;str[0];\n\nstick = clock();\n\nfor (const unsigned char* pChar = _pArray; pChar != pEnd; pChar++) \n    *pszHex++ = hex_table[*pChar];\n\netick = clock();\n</code></pre>\n"}, {'answer_id': 8838619, 'author': 'Sergey Zhukov', 'author_id': 1145960, 'author_profile': 'https://Stackoverflow.com/users/1145960', 'pm_score': 2, 'selected': False, 'text': '<p>It works for me with <code>unsigned char</code>:</p>\n\n<pre><code>unsigned char  c1 =  byteVal &gt;&gt; 4;\nunsigned char  c2 =  byteVal &amp; 0x0f;\n\nc1 +=  c1 &lt;= 9 ? \'0\' : (\'a\' - 10);\nc2 +=  c2 &lt;= 9 ? \'0\' : (\'a\' - 10);\n\nstd::string sHex("  ");\nsHex[0] = c1 ;\nsHex[1] = c2 ;\n\n\n//sHex - contain what we need. For example "0f"\n</code></pre>\n'}]
['https://Stackoverflow.com/questions/69115', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/716/']