从字符串中获取 IPv4 地址的最快方法
Fastest way to get IPv4 address from string
我有以下代码，它比 inet_addr 快 7 倍。我想知道是否有办法改进它以使其更快，或者是否存在更快的替代方案。
此代码要求提供有效的空终止 IPv4 地址且不包含空格，在我的情况下始终如此，因此我针对这种情况进行了优化。通常你会有更多的错误检查，但如果有一种方法可以使以下操作更快或存在更快的替代方法，我将非常感激。
UINT32 GetIP(const char *p)
{
UINT32 dwIP=0,dwIP_Part=0;
while(true)
{
if(p[0] == 0)
{
dwIP = (dwIP << 8) | dwIP_Part;
break;
}
if(p[0]=='.')
{
dwIP = (dwIP << 8) | dwIP_Part;
dwIP_Part = 0;
p++;
}
dwIP_Part = (dwIP_Part*10)+(p[0]-'0');
p++;
}
return dwIP;
}
既然我们谈论的是最大化 IP 地址解析的吞吐量，我建议使用矢量化解决方案。
这里是 x86 特定的快速解决方案（需要 SSE4.1，或者至少需要 SSSE3）：
__m128i shuffleTable[65536]; //can be reduced 256x times, see @IwillnotexistIdonotexist
UINT32 MyGetIP(const char *str) {
__m128i input = _mm_lddqu_si128((const __m128i*)str); //"192.167.1.3"
input = _mm_sub_epi8(input, _mm_set1_epi8('0')); //1 9 2 254 1 6 7 254 1 254 3 208 245 0 8 40
__m128i cmp = input; //...X...X.X.XX... (signs)
UINT32 mask = _mm_movemask_epi8(cmp); //6792 - magic index
__m128i shuf = shuffleTable[mask]; //10 -1 -1 -1 8 -1 -1 -1 6 5 4 -1 2 1 0 -1
__m128i arr = _mm_shuffle_epi8(input, shuf); //3 0 0 0 | 1 0 0 0 | 7 6 1 0 | 2 9 1 0
__m128i coeffs = _mm_set_epi8(0, 100, 10, 1, 0, 100, 10, 1, 0, 100, 10, 1, 0, 100, 10, 1);
__m128i prod = _mm_maddubs_epi16(coeffs, arr); //3 0 | 1 0 | 67 100 | 92 100
prod = _mm_hadd_epi16(prod, prod); //3 | 1 | 167 | 192 | ? | ? | ? | ?
__m128i imm = _mm_set_epi8(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 6, 4, 2, 0);
prod = _mm_shuffle_epi8(prod, imm); //3 1 167 192 0 0 0 0 0 0 0 0 0 0 0 0
return _mm_extract_epi32(prod, 0);
// return (UINT32(_mm_extract_epi16(prod, 1)) << 16) + UINT32(_mm_extract_epi16(prod, 0)); //no SSE 4.1
}
这里是 shuffleTable 所需的预先计算：
void MyInit() {
memset(shuffleTable, -1, sizeof(shuffleTable));
int len[4];
for (len[0] = 1; len[0] <= 3; len[0]++)
for (len[1] = 1; len[1] <= 3; len[1]++)
for (len[2] = 1; len[2] <= 3; len[2]++)
for (len[3] = 1; len[3] <= 3; len[3]++) {
int slen = len[0] + len[1] + len[2] + len[3] + 4;
int rem = 16 - slen;
for (int rmask = 0; rmask < 1<<rem; rmask++) {
// { int rmask = (1<<rem)-1; //note: only maximal rmask is possible if strings are zero-padded
int mask = 0;
char shuf[16] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
int pos = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < len[i]; j++) {
shuf[(3-i) * 4 + (len[i]-1-j)] = pos;
pos++;
}
mask ^= (1<<pos);
pos++;
}
mask ^= (rmask<<slen);
_mm_store_si128(&shuffleTable[mask], _mm_loadu_si128((__m128i*)shuf));
}
}
}
带有测试的完整代码可用here。在 Ivy Bridge 处理器上它打印：
C0A70103
Time = 0.406 (1556701184)
Time = 3.133 (1556701184)
这意味着建议的解决方案在吞吐量方面比 OP 的代码快 7.8 倍。它每秒处理 3.36 亿个地址（单核 3.4 Ghz）。
现在我将尝试解释它是如何工作的。请注意，在清单的每一行上，您都可以看到刚刚计算的值的内容。所有数组都以小端顺序打印（尽管 set 内在函数使用大端）。
首先，我们通过lddqu指令从未对齐的地址加载16个字节。请注意，在 64 位模式下，内存是由 16 字节的块分配的，因此这会自动运行良好。在 32 位上，理论上它可能会导致超出范围访问的问题。虽然我不相信它真的可以。无论尾后字节中的值如何，后续代码都可以正常工作。不管怎样，你最好确保每个IP地址至少占用16字节的存储空间。
然后我们从所有字符中减去'0'。在那之后 '。'变成-2，零变成-48，所有数字都保持非负数。现在我们使用 _mm_movemask_epi8.
对所有字节的符号进行位掩码
根据此掩码的值，我们从查找 table shuffleTable 中获取一个非平凡的 16 字节改组掩码。 table 相当大：总共 1Mb。预计算需要相当长的时间。但是，它不会在 CPU 缓存中占用宝贵的 space，因为真正使用此 table 的只有 81 个元素。这是因为 IP 地址的每一部分都可以是一位、两位或三位数字长 => 因此总共有 81 个变体。
请注意，字符串末尾后的随机无用字节原则上可能会导致查找中的内存占用增加 table.
EDIT：你可以在评论中找到@IwillnotexistIdonotexist 修改的版本，它使用了只有 4Kb 大小的查找 table（虽然有点慢） .
巧妙的 _mm_shuffle_epi8 内在允许我们使用我们的洗牌掩码重新排序字节。结果 XMM 寄存器包含四个 4 字节块，每个块包含小端顺序的数字。我们通过 _mm_maddubs_epi16 后跟 _mm_hadd_epi16 将每个块转换为 16 位数字。然后我们重新排序寄存器的字节，使整个IP地址占据低4字节。
最后，我们将XMM寄存器的低4字节提取到GP寄存器中。它是通过 SSE4.1 intrinsic (_mm_extract_epi32) 完成的。如果没有，请使用 _mm_extract_epi16 将其替换为其他行，但它会 运行 有点慢。
最后，这是生成的程序集 (MSVC2013)，这样您就可以检查您的编译器是否生成了任何可疑的东西：
lddqu xmm1, XMMWORD PTR [rcx]
psubb xmm1, xmm6
pmovmskb ecx, xmm1
mov ecx, ecx //useless, see @PeterCordes and @IwillnotexistIdonotexist
add rcx, rcx //can be removed, see @EvgenyKluev
pshufb xmm1, XMMWORD PTR [r13+rcx*8]
movdqa xmm0, xmm8
pmaddubsw xmm0, xmm1
phaddw xmm0, xmm0
pshufb xmm0, xmm7
pextrd eax, xmm0, 0
P.S。如果您还在阅读它，请务必查看评论 =)
至于替代方案：这与您的相似，但有一些错误检查：
#include <iostream>
#include <string>
#include <cstdint>
uint32_t getip(const std::string &sip)
{
uint32_t r=0, b, p=0, c=0;
const char *s;
s = sip.c_str();
while (*s)
{
r<<=8;
b=0;
while (*s&&((*s==' ')||(*s=='\t'))) s++;
while (*s)
{
if ((*s==' ')||(*s=='\t')) { while (*s&&((*s==' ')||(*s=='\t'))) s++; if (*s!='.') break; }
if (*s=='.') { p++; s++; break; }
if ((*s>='0')&&(*s<='9'))
{
b*=10;
b+=(*s-'0');
s++;
}
}
if ((b>255)||(*s=='.')) return 0;
r+=b;
c++;
}
return ((c==4)&&(p==3))?r:0;
}
void testip(const std::string &sip)
{
uint32_t nIP=0;
nIP = getip(sip);
std::cout << "\nsIP = " << sip << " --> " << std::hex << nIP << "\n";
}
int main()
{
testip("192.167.1.3");
testip("292.167.1.3");
testip("192.267.1.3");
testip("192.167.1000.3");
testip("192.167.1.300");
testip("192.167.1.");
testip("192.167.1");
testip("192.167..1");
testip("192.167.1.3.");
testip("192.1 67.1.3.");
testip("192 . 167 . 1 . 3");
testip(" 192 . 167 . 1 . 3 ");
return 0;
}
我有以下代码，它比 inet_addr 快 7 倍。我想知道是否有办法改进它以使其更快，或者是否存在更快的替代方案。
此代码要求提供有效的空终止 IPv4 地址且不包含空格，在我的情况下始终如此，因此我针对这种情况进行了优化。通常你会有更多的错误检查，但如果有一种方法可以使以下操作更快或存在更快的替代方法，我将非常感激。
UINT32 GetIP(const char *p)
{
UINT32 dwIP=0,dwIP_Part=0;
while(true)
{
if(p[0] == 0)
{
dwIP = (dwIP << 8) | dwIP_Part;
break;
}
if(p[0]=='.')
{
dwIP = (dwIP << 8) | dwIP_Part;
dwIP_Part = 0;
p++;
}
dwIP_Part = (dwIP_Part*10)+(p[0]-'0');
p++;
}
return dwIP;
}
既然我们谈论的是最大化 IP 地址解析的吞吐量，我建议使用矢量化解决方案。
这里是 x86 特定的快速解决方案（需要 SSE4.1，或者至少需要 SSSE3）：
__m128i shuffleTable[65536]; //can be reduced 256x times, see @IwillnotexistIdonotexist
UINT32 MyGetIP(const char *str) {
__m128i input = _mm_lddqu_si128((const __m128i*)str); //"192.167.1.3"
input = _mm_sub_epi8(input, _mm_set1_epi8('0')); //1 9 2 254 1 6 7 254 1 254 3 208 245 0 8 40
__m128i cmp = input; //...X...X.X.XX... (signs)
UINT32 mask = _mm_movemask_epi8(cmp); //6792 - magic index
__m128i shuf = shuffleTable[mask]; //10 -1 -1 -1 8 -1 -1 -1 6 5 4 -1 2 1 0 -1
__m128i arr = _mm_shuffle_epi8(input, shuf); //3 0 0 0 | 1 0 0 0 | 7 6 1 0 | 2 9 1 0
__m128i coeffs = _mm_set_epi8(0, 100, 10, 1, 0, 100, 10, 1, 0, 100, 10, 1, 0, 100, 10, 1);
__m128i prod = _mm_maddubs_epi16(coeffs, arr); //3 0 | 1 0 | 67 100 | 92 100
prod = _mm_hadd_epi16(prod, prod); //3 | 1 | 167 | 192 | ? | ? | ? | ?
__m128i imm = _mm_set_epi8(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 6, 4, 2, 0);
prod = _mm_shuffle_epi8(prod, imm); //3 1 167 192 0 0 0 0 0 0 0 0 0 0 0 0
return _mm_extract_epi32(prod, 0);
// return (UINT32(_mm_extract_epi16(prod, 1)) << 16) + UINT32(_mm_extract_epi16(prod, 0)); //no SSE 4.1
}
这里是 shuffleTable 所需的预先计算：
void MyInit() {
memset(shuffleTable, -1, sizeof(shuffleTable));
int len[4];
for (len[0] = 1; len[0] <= 3; len[0]++)
for (len[1] = 1; len[1] <= 3; len[1]++)
for (len[2] = 1; len[2] <= 3; len[2]++)
for (len[3] = 1; len[3] <= 3; len[3]++) {
int slen = len[0] + len[1] + len[2] + len[3] + 4;
int rem = 16 - slen;
for (int rmask = 0; rmask < 1<<rem; rmask++) {
// { int rmask = (1<<rem)-1; //note: only maximal rmask is possible if strings are zero-padded
int mask = 0;
char shuf[16] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
int pos = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < len[i]; j++) {
shuf[(3-i) * 4 + (len[i]-1-j)] = pos;
pos++;
}
mask ^= (1<<pos);
pos++;
}
mask ^= (rmask<<slen);
_mm_store_si128(&shuffleTable[mask], _mm_loadu_si128((__m128i*)shuf));
}
}
}
带有测试的完整代码可用here。在 Ivy Bridge 处理器上它打印：
C0A70103
Time = 0.406 (1556701184)
Time = 3.133 (1556701184)
这意味着建议的解决方案在吞吐量方面比 OP 的代码快 7.8 倍。它每秒处理 3.36 亿个地址（单核 3.4 Ghz）。
现在我将尝试解释它是如何工作的。请注意，在清单的每一行上，您都可以看到刚刚计算的值的内容。所有数组都以小端顺序打印（尽管 set 内在函数使用大端）。
首先，我们通过lddqu指令从未对齐的地址加载16个字节。请注意，在 64 位模式下，内存是由 16 字节的块分配的，因此这会自动运行良好。在 32 位上，理论上它可能会导致超出范围访问的问题。虽然我不相信它真的可以。无论尾后字节中的值如何，后续代码都可以正常工作。不管怎样，你最好确保每个IP地址至少占用16字节的存储空间。
然后我们从所有字符中减去'0'。在那之后 '。'变成-2，零变成-48，所有数字都保持非负数。现在我们使用 _mm_movemask_epi8.
根据此掩码的值，我们从查找 table shuffleTable 中获取一个非平凡的 16 字节改组掩码。 table 相当大：总共 1Mb。预计算需要相当长的时间。但是，它不会在 CPU 缓存中占用宝贵的 space，因为真正使用此 table 的只有 81 个元素。这是因为 IP 地址的每一部分都可以是一位、两位或三位数字长 => 因此总共有 81 个变体。
请注意，字符串末尾后的随机无用字节原则上可能会导致查找中的内存占用增加 table.
EDIT：你可以在评论中找到@IwillnotexistIdonotexist 修改的版本，它使用了只有 4Kb 大小的查找 table（虽然有点慢） .
巧妙的 _mm_shuffle_epi8 内在允许我们使用我们的洗牌掩码重新排序字节。结果 XMM 寄存器包含四个 4 字节块，每个块包含小端顺序的数字。我们通过 _mm_maddubs_epi16 后跟 _mm_hadd_epi16 将每个块转换为 16 位数字。然后我们重新排序寄存器的字节，使整个IP地址占据低4字节。
最后，我们将XMM寄存器的低4字节提取到GP寄存器中。它是通过 SSE4.1 intrinsic (_mm_extract_epi32) 完成的。如果没有，请使用 _mm_extract_epi16 将其替换为其他行，但它会 运行 有点慢。
最后，这是生成的程序集 (MSVC2013)，这样您就可以检查您的编译器是否生成了任何可疑的东西：
lddqu xmm1, XMMWORD PTR [rcx]
psubb xmm1, xmm6
pmovmskb ecx, xmm1
mov ecx, ecx //useless, see @PeterCordes and @IwillnotexistIdonotexist
add rcx, rcx //can be removed, see @EvgenyKluev
pshufb xmm1, XMMWORD PTR [r13+rcx*8]
movdqa xmm0, xmm8
pmaddubsw xmm0, xmm1
phaddw xmm0, xmm0
pshufb xmm0, xmm7
pextrd eax, xmm0, 0
P.S。如果您还在阅读它，请务必查看评论 =)
至于替代方案：这与您的相似，但有一些错误检查：
#include <iostream>
#include <string>
#include <cstdint>
uint32_t getip(const std::string &sip)
{
uint32_t r=0, b, p=0, c=0;
const char *s;
s = sip.c_str();
while (*s)
{
r<<=8;
b=0;
while (*s&&((*s==' ')||(*s=='\t'))) s++;
while (*s)
{
if ((*s==' ')||(*s=='\t')) { while (*s&&((*s==' ')||(*s=='\t'))) s++; if (*s!='.') break; }
if (*s=='.') { p++; s++; break; }
if ((*s>='0')&&(*s<='9'))
{
b*=10;
b+=(*s-'0');
s++;
}
}
if ((b>255)||(*s=='.')) return 0;
r+=b;
c++;
}
return ((c==4)&&(p==3))?r:0;
}
void testip(const std::string &sip)
{
uint32_t nIP=0;
nIP = getip(sip);
std::cout << "\nsIP = " << sip << " --> " << std::hex << nIP << "\n";
}
int main()
{
testip("192.167.1.3");
testip("292.167.1.3");
testip("192.267.1.3");
testip("192.167.1000.3");
testip("192.167.1.300");
testip("192.167.1.");
testip("192.167.1");
testip("192.167..1");
testip("192.167.1.3.");
testip("192.1 67.1.3.");
testip("192 . 167 . 1 . 3");
testip(" 192 . 167 . 1 . 3 ");
return 0;
}