IPアドレスの高速解析（ポータブルに、SIMDマジックなしで）

ほとんどのプログラマはIPアドレスに馴染みがあります。0から255までの4つの数字をドットで区切った形式、たとえば192.168.0.1です。
ある意味では、32ビット整数を表す複雑な方法です。
IPアドレスの現代版であるIPv6は通常角括弧で囲まれます。私の経験ではあまり一般的ではありません。

凝った手法を使うと、IPアドレスをわずか50命令程度で解析できます。これは少し複雑で、必ずしもポータブルではありません。

あまり手間をかけず、専門のライブラリも使わずに高速化したい場合は、自分で実装してみることもできます。しかし、私は礼儀正しいプログラマなので、お気に入りのAIに書いてもらいました。

// Parse an IPv4 address starting at 'p'.
// p : start pointer, pend: end of the string
std::expected<uint32_t, parse_error> parse_manual(const char *p, const char *pend) {
uint32_t ip = 0;
    int octets = 0;
    while (p < pend && octets < 4) {
        uint32_t val = 0;
        const char *start = p;
        while (p < pend && *p >= '0' && *p <= '9') {
            val = val * 10 + (*p - '0');
            if (val > 255) {
                return std::unexpected(invalid_format);
            }
            p++;
        }
        if (p == start || (p - start > 1 && *start == '0')) {
            return std::unexpected(invalid_format);
        }
        ip = (ip << 8) | val;
        octets++;

        if (octets < 4) {
            if (p == pend || *p != '.') {
                return std::unexpected(invalid_format);
            }
            p++; // Skip dot
        }
    }
    if (octets == 4 && p == pend) {
        return ip;
    } else {
        return std::unexpected(invalid_format);
    }
}

この関数は十分に高速ではないことがすぐにわかりました。そこで、各数値が1〜3桁であることを利用してAIに改善を依頼したところ、以下のような妥当な関数が得られました。

std::expected<uint32_t, parse_error> parse_manual_unrolled(const char *p, const char *pend) {
    uint32_t ip = 0;
    int octets = 0;
    while (p < pend && octets < 4) {
        uint32_t val = 0;
        if (p < pend && *p >= '0' && *p <= '9') {
            val = (*p++ - '0');
            if (p < pend && *p >= '0' && *p <= '9') {
                if (val == 0) { 
                  return std::unexpected(invalid_format);
                }
                val = val * 10 + (*p++ - '0');
                if (p < pend && *p >= '0' && *p <= '9') {
                    val = val * 10 + (*p++ - '0');
                    if (val > 255) { 
                      return std::unexpected(invalid_format);
                    }
                }
            }
        } else {
            return std::unexpected(parse_error::invalid_format);
        }
        ip = (ip << 8) | val;
        octets++;
        if (octets < 4) {
            if (p == pend || *p != '.') {
              return std::unexpected(invalid_format);
            }
            p++; // Skip the dot
        }
    }
    if (octets == 4 && p == pend) {
        return ip;
    } else {
        return std::unexpected(invalid_format);
    }
}

AI、よくできました！

C++には数値を解析する標準関数（std::from_chars）があり、コードを大幅に簡素化できます。

std::expected<uint32_t, parse_error> parse_ip(const char *p, const char *pend) {
  const char *current = p;
  uint32_t ip = 0;
  for (int i = 0; i < 4; ++i) {
    uint8_t value;
    auto r = std::from_chars(current, pend, value);
    if (r.ec != std::errc()) {
      return std::unexpected(invalid_format);
    }
    current = r.ptr;
    ip = (ip << 8) | value;
    if (i < 3) {
      if (current == pend || *current++ != '.') {
        return std::unexpected(invalid_format);
      }
    }
  }
  return ip;
}

fast_floatライブラリをstd::from_charsの代わりに使うこともできます。fast_floatの最新版では、Soni Shikhar氏（Pavel Novikov氏による修正を含む）のおかげで8ビット整数の解析が高速化されています。

この問題のためのベンチマークを作成しました。まず、LLVM 17を搭載したApple M4プロセッサ（4.5 GHz）での結果を見てみましょう。

次に、GCC 12とIntel Ice Lakeプロセッサ（3.2 GHz）を使った結果です。

最後に、LLVM 21を搭載した中国のLongsoon 3A6000プロセッサ（2.5 GHz）での結果です。

fast_floatライブラリの最適化作業は効果がありました。特にx64プロセッサでの違いが顕著です。

この小さな実験で興味深いのは、比較的少ない労力でAIに高速なコードを生成させられたことです。私はAIを「ガイド」する必要がありました。それでも引退できるわけではありません。しかし、良いリファレンスとなるベースラインをより迅速に得られるようになったことは嬉しく、重要な部分に集中しやすくなりました。

参考: The fast_float C++ libraryは、高速な数値解析ライブラリで、GCCや主要なWebブラウザに組み込まれています。

Published by

Post navigation