Optimal IP Subnet Compliance

Question

The following code is the hottest spot in my program.

JAVA_OPTS = -Xprof output:

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 

Slimes, the same Elements, and even foreach calls seem to be most used here. Can someone give some advice or two on how to optimize the contains() method? Maybe some methods allow you to analyze Bytes without converting them to integers? Or a solid approach of a whole sequence without a cut?

The SubNet.contains () function corresponds to the IP address for the subnet.

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

I understand that this optimization will not give me much better bandwidth, I just feel like I am doing something wrong, I spend so much time on this simple function.

This code must be compatible with IPv6 (16 bytes), and I don't like the idea of ​​processing IPv4 code separately.

Answer 1

You are not doing something wrong as such; you just use collections designed for ease of use, not for working with primitives.

If you want to speed this up, you will get the greatest boost by switching to using arrays and loops. It’s not entirely clear to me that the code you wrote even works for IPv6, with the exception of IPv4 addresses stored in IPv6 format, since you can have a subnet with more than 256 elements. In addition, when testing lengths, you do not allow mixed representations of IPv6 / IPv4 with the same address.

I would forget the whole "toInts" thing and just save byte arrays; then do something like (warning, untested)

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

It really is no more complicated than your original solution, and should work at a speed of ~ 10 times faster.

Answer 2

With this code, it is not verified correctly.

For instance:

 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 

But if you calculate this network: (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 - 

I rewrote both (IPv4 and IPv6) in Scala, put it for everyone on GitHub. Now it is also checked within ranges (so / 20, etc. It will be considered what the old one did not do.)

You can find the code (I split it into IPv4 and IPv6) at https://github.com/wasted/scala-util/blob/master/src/main/scala/io/wasted/util/InetPrefix.scala

I also created a blogpost about this .