char []十六进制字符串练习
下面是我当前的char *到十六进制字符串的函数。我将其写为位操纵的练习。在AMD Athlon MP 2800+上花费约7毫秒来十六进制一千万个字节的阵列。有没有我想念的花招或者其他方式？
我怎样才能使它更快？
在g ++中与-O3一起编译
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;
}
更新
添加了计时码
Brian R. Bondy：用堆分配的缓冲区替换std :: string并将ofs * 16更改为ofs << 4，但是堆分配的缓冲区似乎减慢了速度？结果〜11ms
Antti Syk？ri：替换内部循环
int upper = *pChar >> 4; int lower = *pChar & 0x0f; pszHex[0] = pHex[upper]; pszHex[1] = pHex[lower];
结果〜8ms
罗伯特：将_hex2asciiU_value替换为完整的256项表，这会牺牲内存空间，但会导致〜7ms！
HoyHoy：注意到它产生了不正确的结果
解决方案
回答
对于一个，而不是乘以" 16"，而是进行" bitshift << 4"。
同样不要使用std :: string，而是在堆上创建一个缓冲区，然后删除它。它比字符串所需的对象销毁效率更高。
回答
一次操作32位(4个字符)，然后根据需要处理尾部。当我使用url编码进行此练习时，对每个字符进行全表查找比逻辑结构快一点，因此我们可能还想在上下文中进行测试以考虑缓存问题。
回答
不会有太大的不同... * 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;
}
回答
确保编译器优化已打开到最高工作级别。
我们知道，gcc中的标志如'-O1'到'-03'。
回答
我们可以花费更多的内存来创建一个完整的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];
回答
改变中
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];
}
正如艾伦·温德(Allan Wind)指出的那样，一次执行2个字节或者一次执行4个字节可能会导致更大的加速，但是当我们必须处理奇数字符时，它会变得更加棘手。
如果我们喜欢冒险，可以尝试改用Duff的设备来执行此操作。
结果显示在Intel Core Duo 2处理器和" gcc -O3"上。
始终衡量自己实际上获得了更快的结果，假装为优化的悲观并非一文不值。
始终测试我们是否能获得正确的结果，假装是优化的bug绝对是危险的。
始终牢记，速度与可读性寿命之间的权衡对于任何人都无法维护不可读的代码而言太短了。
(必须参考为知道我们所住地的暴力性精神病患者编码。)
回答
我发现使用数组索引而不是指针可以加快速度。这完全取决于编译器选择如何进行优化。关键在于处理器具有在单个指令中执行诸如[i * 2 + 1]之类的复杂任务的指令。
回答
即使完全指定了_hex2asciiU_value，在编写此函数时显示的功能也会产生不正确的输出。以下代码有效，并且在我的2.33GHz Macbook Pro上，运行2000亿亿个字符大约需要1.9秒。
#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";
}
回答
如果我们对速度不太满意，可以执行以下操作：
每个字符是一个字节，代表两个十六进制值。因此，每个字符实际上是两个四个位的值。
因此，我们可以执行以下操作：
- 使用乘法或者类似指令将4位值解压缩为8位值。
- 使用pshufb(SSSE3指令)(尽管仅适用于Core2)。它采用16个8位输入值的数组，并根据第二个向量中的16个8位索引对它们进行混洗。由于我们只有16个可能的字符，因此非常适合。输入数组是0到F个字符的向量，而索引数组是4位值的解压缩数组。
因此，在一条指令中，我们将以比通常只执行一个时钟要少的时钟执行16次表查找(pshufb是Penryn上的1个时钟延迟)。
因此，在计算步骤中：
- 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 0I 0J 0K 0L 0M 0N 0O 0P(索引的128位向量，"向量B")。最简单的方法可能是两个64位乘法。
- pshub [0123456789ABCDEF]，向量B
回答
我不确定一次执行更多的字节会更好...我们可能只会遇到大量的高速缓存未命中并显着降低其速度。
不过，我们可以尝试展开循环，采取更大的步骤，并在每次循环中执行更多字符，以消除一些循环开销。
回答
在我的Athlon 64 4200+上持续获得约4毫秒(原始代码约7毫秒)
for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++) {
const char* pchars = _hex2asciiU_value[*pChar];
*pszHex++ = *pchars++;
*pszHex++ = *pchars;
}
回答
更快的C放大
它的运行速度比C ++实现快3倍。不知道为什么，因为它非常相似。对于我发布的最后一个C ++实现，运行200,000,000个字符数组需要6.8秒。实施仅花费了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));
}
回答
这个组装功能(基于我之前的文章，但是我不得不对其进行一些修改才能使其真正起作用)在Core 2 Conroe 3Ghz的一个内核上每秒处理33亿个输入字符(66亿个输出字符)。 Penryn可能更快。
%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是寄存器中函数的三个参数。它有点像伪代码。或者，我们可以从x264树中获取common / x86 / x86inc.asm并将其包括在内以在本地运行它。
P.S.堆栈溢出，我为浪费时间在这样一件琐碎的事情上做错了吗？还是很棒？
回答
我认为这是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();
