从字符串中获取IPv4地址的最快方法

Question

从字符串中获取IPv4地址的最快方法

17

我有以下代码，比inet_addr快约7倍。我想知道是否有办法改进它，使其更快，或者是否存在更快的替代方案。

这段代码需要提供有效的无空格IPv4地址，并以null结尾，在我的情况下通常都是这样，所以我对此进行了优化。通常您会有更多的错误检查，但如果有方法可以使下面的代码更快，或者存在更快的替代方案，我将不胜感激。

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

- Harry

9

好的，我会尽力为您进行翻译。我认为这更适合于codereview.stackexchange.com。 - M.M

4

为什么？我想知道从字符串中获取IP地址的最快方法是什么。 - Harry

6

请注意，如果未调整大小端序（endianess）为网络字节顺序，UINT32 可能不适用于 IP 地址。 - πάντα ῥεῖ

9

@Harry CodeReview专注于审查“可运行的代码”（您的代码能够正常工作），他们可以提出算法改进的建议。这并不意味着速度优化无法在此讨论。 - Iwillnotexist Idonotexist

3

如果我的代码确实是目前世界上最快的，那么值得去代码审查看看它是否可以更快？我曾经看到过更快的整数转换问题被放在这里，我认为这与那些问题相关。我自己找不到其他关于这个主题的东西，如果没有其他选择的话，这可能会帮助未来的其他人。 - Harry

显示剩余12条评论

2个回答

1

关于替代方案：这个与你的类似，但有一些错误检查：

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

- slashmais

你的速度和我的原始速度相比如何？ - Harry

@Harry：我没有进行特定的批量速度测试（也没有数据）；即使与特定机器有关，但只是使用上述数据运行两者，速度大约相同（在这里毫无意义）。 - slashmais

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- stgatilov · Accepted Answer

既然我们在谈论最大化 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));
                    }
                }
}

完整的代码和测试在这里可用。在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获取所有字节的符号掩码。

根据此掩码的值，我们从查找表shuffleTable中获取一个非平凡的16字节洗牌掩码。表格相当大：总共1Mb。并且需要花费相当长的时间进行预计算。但是，它不会占据CPU缓存中的宝贵空间，因为实际上只使用了来自此表格的81个元素。这是因为IP地址的每个部分可以是一个、两个、三个数字长=> 因此总共有81个变量。请注意，字符串结束后的任意垃圾字节原则上可能会导致查找表中的内存占用增加。

编辑：您可以在评论中找到@IwillnotexistIdonotexist修改的版本，它使用4Kb大小的查找表（速度稍慢）。

巧妙的_mm_shuffle_epi8内部机制允许我们使用我们的洗牌掩码重新排序字节。结果，XMM寄存器包含四个4字节块，每个块包含小端顺序的数字。我们通过_mm_maddubs_epi16接着_mm_hadd_epi16将每个块转换为16位数字。然后，我们重新排列寄存器的字节，以便整个IP地址占用较低的4字节。

最后，我们从XMM寄存器中提取较低的4字节到GP寄存器。这是用SSE4.1内在机制实现的（_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

顺便提一下，如果你还在阅读，请务必查看评论 =）