Re^3: Sorting IP addresses, lots of them, quickly

[salva]

The ukeysort variant is slower than the others because converting from the IPv4 dot notation to an unsigned int in Perl is much, much, much, slower than calling inet_aton. If an XSUB were used to make the conversion ukeysort would be the fastest!

But anyway, as the data set size increases, the conversion cost from IPv4 to uint would become less decisive than the comparison function used inside the sort, and at some point the ukeysort solution would become the fastest of all the alternatives (and BTW, it also uses less memory! :-)

[salva]

If an XSUB were used to make the conversion ukeysort would be the fastest!

And to show it, I have just uploaded Sort::Key::IPv4 to CPAN ;-)

Now, adding this test to the benchmarks...

use Sort::Key::IPv4 qw(ipv4sort);

sub ipv4ks {
    my @sorted = ipv4sort @address;
}

I get for 10_000 addresses:

               Rate gloryhackish     ukeysort      keysort     ipv4sor
+t
gloryhackish 6.14/s           --         -31%         -54%         -79
+%
ukeysort     8.91/s          45%           --         -34%         -70
+%
keysort      13.5/s         119%          51%           --         -54
+%
ipv4sort     29.4/s         378%         229%         118%           -
+-

For 100_000:

             s/iter gloryhackish     ukeysort      keysort     ipv4sor
+t
gloryhackish   1.80           --         -31%         -33%         -78
+%
ukeysort       1.25          44%           --          -3%         -68
+%
keysort        1.21          49%           3%           --         -67
+%
ipv4sort      0.400         350%         212%         202%           -
+-

And for 1_000_000:

             s/iter gloryhackish      keysort     ukeysort     ipv4sor
+t
gloryhackish   24.3           --         -29%         -46%         -79
+%
keysort        17.2          41%           --         -24%         -71
+%
ukeysort       13.2          85%          31%           --         -62
+%
ipv4sort       4.99         388%         245%         164%           -
+-

[gloryhack]

NOW we're talkin' fast! On my AMD64 X2 workstation with my original 11818 addresses, ip4sort beats the pants off of everything, 258% faster than gloryhackish, and a whopping 727% over Schwartzian Transform. At 100,000 addresses, the numbers are 281% and 1169%, respectively, and at a million it's 248% and 1140% (looks like the curves are flattening a bit way up there). Good work!

So guess who's just decided to use ip4sort from now on? :-) Thanks!

[monarch]

Great idea.

I wonder, is this sorting routine truly dependant on the regexp mentioned in the documentation (Sort::Key::IPv4), or can be extended to sorting SNMP Object Identifiers (OIDs) which are dotted strings up to any number of elements, e.g.:

  1.3.6.1.4.1.2203.1.2.102945.12.0
  1.3.6.1.4.1.2203.1.2.102946.1.0
  1.3.6.1.2.1.1.2.3.4.5.0

SNMP OIDs are a lot like IPv4 addresses in the way they are sorted, they are represented as dot strings, however unlike IPv4 addresses they can contain an unlimited number of elements and each element can contain an integer of any (non-infinite and non-negative) value.

[salva]

Sort::Key::OID is now available from CPAN!

[salva]

I wonder, is this sorting routine truly dependant on the regexp mentioned in the documentation

Yes, it is, because Sort::Key::IPv4 internally converts the IP addresses to 32 bit unsigned integers that can be sorted very fast.

For OIDs, you can use Sort::Key::Natural that even if it is not going to be as fast as ipv4sort, would probably outperform any other pure perl method.