Skip Menu |
 

This queue is for tickets about the Net-Subnet CPAN distribution.

Report information
The Basics
Id: 107037
Status: new
Priority: 0/
Queue: Net-Subnet

People
Owner: Nobody in particular
Requestors: mark [...] markandruth.co.uk
Cc:
AdminCc:

Bug Information
Severity: (no value)
Broken in: (no value)
Fixed in: (no value)



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>
Download (untitled) / with headers
text/plain 1.5k
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; }


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

Please report any issues with rt.cpan.org to rt-cpan-admin@bestpractical.com.