インターネットに接続されたすべてのマシンには、IPアドレスと呼ばれるアドレスが割り当てられています。元々、これらのアドレスは32ビットの整数（IPv4）で、理論上は約40億の異なるアドレスが可能です。私たちはこれらのアドレス（例: 192.168.0.0）に馴染みがあります。アドレスが枯渇するという大騒ぎがありましたが、それは実際には起こりませんでした。なぜなら、すべてのデバイスが独自の一意なアドレスを持つ必要はないからです。ホームルーターはアドレスを必要としますが、家庭内のすべてのデバイスが世界的に一意なアドレスを持つ必要はありません。

それでも、アドレスの範囲は128ビット（IPv6）に拡張されました。IPv6アドレスは、通常、コロンで区切られた8つの4桁の16進数グループとして表記されます。例:

2001:0db8:85a3:0000:0000:8a2e:0370:7334

アドレスにはゼロの連続が含まれることが多いため、この形式では2つの省略形が許可されます:

  • グループ内の先頭ゼロは省略可能: 2001:db8:85a3:0:0:8a2e:370:7334。
  • すべてのゼロのグループの単一の連続は :: に置き換え可能: 2001:db8:85a3::8a2e:370:7334。

ダブルコロンのトリックはアドレス内で1回だけ使用でき、1つ以上のゼログループに一致します。したがって ::1 はループバックアドレス（最後のグループ以外はすべてゼロ）、:: は未指定アドレス（すべてゼロ）です。

IPv6は最後の32ビットに埋め込まれたIPv4アドレスも受け入れ、通常のドット区切り10進数形式で表記します。これは主に ::ffff:192.168.1.1 のようなIPv4マップIPv6アドレスに使用されます。最長のテキスト形式は45文字です:

0000:0000:0000:0000:0000:ffff:255.255.255.255

したがって、パーサーは16進数グループ、圧縮形式、およびオプションのIPv4末尾を受け入れる必要があります。IPv4のパースより複雑です。

この作業のための標準C関数は inet_pton で、ほぼすべてのシステムで利用可能です。

より良い方法はあるでしょうか？

数年前、私はIPv4アドレスを非常に高速にパースできることを示しました。IPv6でも同じことができるでしょうか？

その秘訣はデータ並列処理を使うことです。すべてのプロセッサがサポートするSIMD命令と呼ばれる命令を呼び出します。これらの命令は、潜在的に数十バイトを一度に処理できます。

Shreesh Adigaは、最近のIntelサーバープロセッサとすべての新しいAMD CPUがサポートする強力な命令セットであるAVX-512で試みました。アイデアは、文字列全体を512ビットレジスタにロードし、単一の比較でコロンを見つけ、それらの間の間隔を計算してバイトレベルの展開を駆動し、permuteで16進数桁を翻訳し、最後に乗算累算で16進数桁をバイトに結合することです。パーサーのほぼ全体が分岐なしで、つまり if 節がほとんどありません。

私は inet_ntop でランダムなIPv6アドレスを生成し（したがってアドレスは正規の圧縮形式で書かれます）、それぞれを inet_pton とAVX-512ルーチンの両方でパースする小さなベンチマークを用意しました。ベンチマークはIntel Xeon Gold 6548N CPU @ 2.8 GHz（Emerald Rapids）上でGCCを使用し、-march=native -O3 でコンパイルして実行します。

function ns/addr speed (Mv/s) instr/addr instr/cycle
inet_pton 175.3 5.7 954 1.56
AVX-512 14.0 71.3 120 2.45

AVX-512ルーチンは inet_pton より約12倍高速で、シングルコアで1秒あたり7000万以上のアドレスをパースします。使用する命令数は8分の1で、より高いスループット（1サイクルあたり2.45命令対1.56命令）で実行されます。

このベンチマークに使用したソースコードは私のブログリポジトリで入手可能です。

Update. Peter Forsは、ベンチマークでバイトを合計するステップが特にGCC下でオーバーヘッドを追加することを指摘しています。したがって私は速度をやや過小評価しています。

Published by

Post navigation