| Subject: | Improvements in performance using binary search |
| Date: | Fri, 11 Sep 2015 13:24:12 +0300 |
| To: | bug-Net-Subnet [...] rt.cpan.org |
| From: | Mark Zealey <mark [...] markandruth.co.uk> |
I've used your code as the basis for a piece of work I'm doing, however
performance was pretty bad. Here is a binary search implementation that
significantly improves performance (ipv4-only, and uses integer arithmetic):
# Return eg /24 as a binary mask
sub _cidr2mask_v4 {
my ( $length ) = @_;
return ( 0xffffffff << ( 32 - $length ) ) & 0xffffffff;
}
# Return inet_aton as an integer
sub _inet_aton {
my ( $ip ) = @_;
return unpack "N", Socket::inet_aton( $ip );
}
for each item {
my ( $net, $mask ) = split m!/!, $pool->{net};
$net = _inet_aton( $net );
$mask = _cidr2mask_v4( $mask );
push @out, [ ( $net & $mask ), $mask, $pool->{type} ];
}
# Sort so we can do a binary search later
@out = sort { $a->[0] <=> $b->[0] } @out;
# Do a binary search over the pool to figure out where the item may be,
# otherwise return undef
sub _find_match {
my ( $self, $ip, $pools ) = @_;
my $enc_ip = _inet_aton( $ip )
or return undef;
# First do a binary search to find where our item would be
my ( $l, $r ) = ( 0, $#$pools );
while ( $l <= $r ) {
my $mid = int( ( $l + $r ) / 2 );
my $ent = $pools->[$mid];
my ( $masked_net, $mask, $pool ) = @$ent;
my $enc_mask = $enc_ip & $mask;
#warn join ", ", map { sprintf "%08x", $_ } $enc_ip, $enc_mask,
@$ent;
return $pool if $enc_mask == $masked_net;
if ( $enc_mask < $masked_net ) {
$r = $mid - 1;
}
else {
$l = $mid + 1;
}
}
return undef;
}