最佳IP子网匹配

Question

以下代码似乎是我的程序中最热门的地方。

JAVA_OPTS=-Xprof 输出：

     Compiled + native   Method
  5.7%   173  +     0    scala.collection.IndexedSeqOptimized$class.slice
  5.1%   156  +     0    scala.collection.IndexedSeqOptimized$class.foreach
  2.9%    87  +     0    java.util.regex.Pattern$BmpCharProperty.match
  2.5%    76  +     0    scala.collection.IndexedSeqOptimized$class.sameElements
  2.4%    73  +     0    trafacct.SubNet.contains

Slice、sameElements 甚至 foreach 调用似乎也是这里最常用的。有人可以就如何优化 contains() 方法提供一两个建议吗？也许有些技术允许字节分析而不将它们转换为整数？或者没有切片的可靠全序列方法？

函数 SubNet.contains() 将 IP 地址与子网进行匹配。

object SubNet {
    def toInts(bytes: Seq[Byte]): Seq[Int] = bytes.map(_.toInt & 0xFF)
}

case class SubNet(ip:InetAddress,  maskLength:Int) extends HostCategory {
    import SubNet.toInts
    private val bytes: Int = maskLength / 8
    private val subnet = toInts(ip.getAddress)
    private val bits = bytes * 8 - maskLength
    def contains(host: Host) = {
        if (host.ip == null && ip == null) {
            true
        } else if (this.ip == null) {
            false
        } else {
            val address = toInts(host.ip.getAddress)
            if (address.length != subnet.length) {
                false
            } else {
                if (address.slice(0, bytes) != subnet.slice(0, bytes)) {
                    false
                } else {
                    ((address(bytes) >> (8-bits) ^ subnet(bytes) >> (8-bits)) & 0xFF) == 0
                }
            }
        }
    }
}

我知道，这种优化不会给我带来更好的吞吐量，我只是觉得我在这个简单的函数中花费这么多时间做错了一些事情。

该代码应该与 IPv6（16 字节）兼容，并且我不喜欢单独处理 IPv4 情况的想法。

Answer 1

你本身并没有做错什么；您只是使用旨在易于使用的集合，而不是处理基元时的性能。

如果您想加快速度，可以通过改用数组和 while 循环来获得最大的提升。我并不完全清楚您编写的代码是否适用于 IPv6（除了以 IPv6 格式存储的 IPv4 地址），因为您的子网可能包含超过 256 个项目。另外，通过测试长度，您假设同一地址没有混合的 IPv6/IPv4 表示形式。

我会忘记整个“toInts”的事情，只存储字节数组；然后执行类似的操作（警告，未经测试）

def contains(host: Host): Boolean = {
//...
  if (address.length != subnet.length) false
  else {
    var i = 0
    while (i<address.length-1) {
      if (address(i) != subnet(i)) return false
      i += 1
    }
    (address(i)&0xFF) >> (8-bits) ^ (subnet(i)&0xFF) >> (8-bits) == 0
  }
}

它实际上并不比您原来的解决方案更复杂，并且运行速度应该快 10 倍。

Answer 2

使用此代码，它无法正确验证。

例如：

scala> val ip = java.net.InetAddress.getByName("::ffff:1.2.176.0")
ip: java.net.InetAddress = /1.2.176.0

scala> val prefix = new InetPrefix(ip, 20)
prefix: InetPrefix = InetPrefix@6febf6f9

scala> prefix.contains(java.net.InetAddress.getByName("::ffff:1.2.176.20"))
res11: Boolean = true

scala> prefix.contains(java.net.InetAddress.getByName("::ffff:1.2.191.20"))
res12: Boolean = false

但是如果您计算该网络：(1.2.176.0/20)

$ sipcalc 1.2.176.0/20

-[ipv4 : 1.2.176.0/20] - 0

[CIDR]
Host address        - 1.2.176.0
Host address (decimal)  - 16953344
Host address (hex)  - 102B000
Network address     - 1.2.176.0
Network mask        - 255.255.240.0
Network mask (bits) - 20
Network mask (hex)  - FFFFF000
Broadcast address   - 1.2.191.255
Cisco wildcard      - 0.0.15.255
Addresses in network    - 4096
Network range       - 1.2.176.0 - 1.2.191.255
Usable range        - 1.2.176.1 - 1.2.191.254

-

我用 Scala 重写了这两个网络（IPv4 和 IPv6），并将其发布在 GitHub 上供大家使用。现在它也在范围内进行验证（因此 /20 等将被视为，而旧的没有这样做。）

您可以在 https://github.com/wasted/scala-util/blob/master/src/main/scala/io/wasted/util/InetPrefix.scala

我还创建了一个 关于此的博文。