最佳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

从这里开始，切片、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的想法。

- Basilevs

---

嗯，这里有一个实现，你可以用来测试你的代码，看看他们的测试案例http://docs.guava-libraries.googlecode.com/git-history/release09/javadoc/index.html - oluies

Answer 1

您并没有做错任何事情；您只是在处理基元时使用了旨在提高易用性而不是性能的集合。

如果您想加快速度，最好使用数组和while循环来进行切换。我并不完全清楚您编写的代码是否适用于IPv6，除非IPv4地址以IPv6格式存储，因为子网可能有超过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倍。

- Rex Kerr

---

subnet(i)&&0xFF对字节的处理让我很困扰。字节是有符号的，而负数的移位行为很奇怪：-1>>2 == -1。这不会影响比较吗？ - Basilevs

我不太理解你关于子网中255个项目的说法。为什么不能有更多呢？ - Basilevs

确实，消除toInt映射和序列切片会带来显著的改进。谢谢。 - Basilevs

关于子网的最后一个字节，我必须将其转换为：((address(bytes).toInt >> (8-bits) ^ subnet(bytes).toInt >> (8-bits)) & 0xFF) == 0 - Basilevs

@Basilevs - 字节是有符号的，但所有的计算都是整数计算。因此，b&0xFF表示从0到255的整数。双“&”是打字错误。你需要在移位之前进行位掩码。 - Rex Kerr

这段代码计算不正确，请查看下面的错误。 - Franz Bettag

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找到代码（我将其分成了IPv4和IPv6）。

我还创建了一篇关于此事的博客文章。

- Franz Bettag

---

我从来没有声称它能正确验证。我只是向提问者展示如何让他们（可能是有问题的）代码运行得更快。如果你能修复它，那将是一个很好的答案——否则你的“答案”就太像一条评论了！ - Rex Kerr

我必须编写两种检查方式，IPv6是您的方式，而IPv4则依赖于计算范围的起始/结束作为长整型，然后比较值。这两种方法都非常直接简单。欢迎提出建议 :) - Franz Bettag