in reply to Re: Sorting IP addresses, lots of them, quickly
in thread Sorting IP addresses, lots of them, quickly

I'm seeing what appears to be a hardware dependence, too. On an old dual P-II/450 with 1G of RAM, I get (with my original 11818 address list): 
               Rate    ukeysort         grt schwartzian gloryhackish  
+   keysort
ukeysort     1.63/s          --        -20%        -21%         -39%  
+      -70%
grt          2.04/s         25%          --         -0%         -23%  
+      -62%
schwartzian  2.05/s         26%          0%          --         -23%  
+      -62%
gloryhackish 2.66/s         63%         30%         30%           --  
+      -51%
keysort      5.41/s        232%        165%        163%         103%  
+        --

[download]

Somehow, ukeysort went to the back of the line, with GRT not being a whole lot zippier and inconsequentially slower than ST. On a similar machine with just a single P-II/500 and 640M of RAM, though:

               Rate schwartzian    ukeysort         grt gloryhackish  
+   keysort
schwartzian  2.28/s          --        -22%        -27%         -42%  
+      -71%
ukeysort     2.92/s         28%          --         -7%         -25%  
+      -63%
grt          3.14/s         38%          8%          --         -20%  
+      -60%
gloryhackish 3.91/s         72%         34%         25%           --  
+      -50%
keysort      7.86/s        245%        169%        151%         101%  
+        --

[download]

GRT beats ukeysort again and is well ahead of ST. But on an Athlon 3900+ w/1G RAM:

               Rate schwartzian         grt    ukeysort gloryhackish  
+   keysort
schwartzian  6.83/s          --        -37%        -46%         -52%  
+      -76%
grt          10.9/s         59%          --        -13%         -24%  
+      -61%
ukeysort     12.6/s         84%         16%          --         -12%  
+      -55%
gloryhackish 14.2/s        108%         31%         13%           --  
+      -50%
keysort      28.2/s        312%        159%        124%          98%  
+        --

[download]

None of these machines are memory constrained, none are swapping, and none are particularly busy doing other things. All are running the same version of Debian with the stock kernels, running the exact same test code just copied from machine to machine. keysort is always out front, but unlike my AMD64 the gloryhackish stays in the #2 spot every time, while the others wiggle around depending upon the machine used.

'Tis a puzzle, seems to point toward something at a very low level being the source of the disparate numbers. The only conclusion I can come up with is that keysort is the way to go when a large number of IP addresses must be sorted in a time constrained environment, gloryhackish might be a good choice if no non-core module dependencies are allowed, even though it might not always be the second best choice. It's good to know about Sort::Key, in any event.

Replies are listed 'Best First'.
Re^3: Sorting IP addresses, lots of them, quickly
by salva (Canon) on May 16, 2007 at 20:58 UTC
    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! :-)

[reply]
      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;
}

      [download]
      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%           -
+-

      [download]
      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%           -
+-

      [download]
      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%           -
+-

      [download]
[reply]
[d/l]
[select]
        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!

[reply]
        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

        [download]

        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.

[reply]
[d/l]

In Section Cool Uses for Perl