This is one that can easily be done the wrong way, and seems to be done wrong as often as it is done right. I took it upon myself to compile several different ways of sorting IPv4 addresses, and benchmarked them for your benefit:

#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw(cmpthese);
use Socket qw(inet_aton inet_ntoa);

chomp( my @ips=(<>) );

cmpthese(-10,
    {
        inet_grt => sub { 
            my @sorted = map { inet_ntoa $_ }
                sort { $a cmp $b }
                map { inet_aton $_ } @ips;
        },
        inet_grt2 => sub { 
            my @sorted = map { unpack 'x4A*' }
                sort { $a cmp $b }
                map { pack('A4A*', inet_aton($_), $_) } @ips;
        },
        inet_orc => sub { 
            my @sorted = sort by_ip @ips;
        },
        splitwise => sub {
            my @sorted =
            map $_->[0],
            sort {
                $a->[1] <=> $b->[1] or
                $a->[2] <=> $b->[2] or
                $a->[3] <=> $b->[3] or
                $a->[4] <=> $b->[4]
            }
            map [$_, split /\./], @ips;
        },
        split_int => sub {
            my @sorted = map { join '.', unpack("CCCC", pack("N",$_)) 
+}
                sort { $a <=> $b }
                map { unpack("N",pack("CCCC",split /\./)) } @ips;
        },
        naive => sub {
            my @sorted = sort {
                my @a = split /\./, $a;
                my @b = split /\./, $b;
                $a[0] <=> $b[0] or
                $a[1] <=> $b[1] or
                $a[2] <=> $b[2] or
                $a[3] <=> $b[3]
                } @ips;
        },
    });

{
    my %cache;
    sub by_ip
    {
        my $orc_a = ($cache{$a} ||= inet_aton($a));
        my $orc_b = ($cache{$b} ||= inet_aton($b));
        $orc_a cmp $orc_b;
    }
}

__END__
            Rate     naive split_int splitwise  inet_orc inet_grt2  in
+et_grt
naive     8.65/s        --      -86%      -88%      -89%      -93%    
+  -96%
split_int 62.5/s      622%        --      -12%      -17%      -52%    
+  -69%
splitwise 71.1/s      722%       14%        --       -6%      -45%    
+  -65%
inet_orc  75.4/s      772%       21%        6%        --      -42%    
+  -63%
inet_grt2  129/s     1393%      107%       82%       71%        --    
+  -36%
inet_grt   201/s     2229%      222%      183%      167%       56%    
+    --

[download]

My input was a list of 1000 random IP addresses generated by nmap, listed in the HTML comments for this node

UPDATE: Thanks to ELISHEVA for catching a bug in naive that made it think the input was sorted. Updated benchmarks show it is 86% slower than the nearest competition

print pack("A25",pack("V*",map{1919242272+$_}(34481450,-49737472,6228,0,-285028276,6979,-1380265972)))

Replies are listed 'Best First'.
Re: RFC: Sorting IPv4 addresses
by salva (Canon) on Oct 06, 2009 at 23:26 UTC
    You should try Sort::Key::IPv4 or even Sort::Key::Radix.

    The modified benchmarking script:

    Read more... (2 kB)

    And that's what I get on my machine: 

                Rate splitwise inet_orc split_int naive inet_grt2 inet_grt
+   sk  skr
splitwise 94.7/s        --     -19%      -36%  -42%      -68%     -68%
+ -88% -89%
inet_orc   117/s       24%       --      -20%  -28%      -60%     -61%
+ -85% -87%
split_int  147/s       55%      26%        --   -9%      -50%     -50%
+ -82% -83%
naive      163/s       72%      39%       10%    --      -45%     -45%
+ -80% -81%
inet_grt2  295/s      211%     152%      100%   81%        --      -1%
+ -63% -66%
inet_grt   297/s      214%     154%      102%   83%        1%       --
+ -63% -66%
sk         804/s      749%     587%      446%  395%      173%     170%
+   --  -7%
skr        868/s      816%     642%      490%  434%      194%     192%
+   8%   --

    [download]
[reply]
[d/l]
[select]

      Thanks for some great suggestions! I'll definitely look at using Sort::Key::IPv4 in my own scripts.

      The main reason I felt the need to post this was because I found the naive sort being used in a CPAN module, Nmap::Parser. I guess I expected a little better from something that gets pretty wide use. I figured it would be worthwile posting some good pure-Perl sorts, since module maintainers wouldn't have to add additional dependencies if they didn't want to. Really, why not use a drop-in replacement with almost 100% speedup?

      print pack("A25",pack("V*",map{1919242272+$_}(34481450,-49737472,6228,0,-285028276,6979,-1380265972)))
[reply]
[d/l]
[select]
Re: RFC: Sorting IPv4 addresses
by ikegami (Patriarch) on Oct 06, 2009 at 22:42 UTC

    In practice, you often need the IP address in packed form anyway, so there's work reuse. That makes the solutions that pack that much more efficient.

    If not, the following would be even faster 

    unpack_ipv4s( sort { $a <=> $b } pack_ipv4s( @ips ) );

    [download]

    Where unpack_ipv4s and pack_ipv4s are efficient XS functions.

    Of course, it would be even faster if you rewrote the sorter to work with numbers directly instead of handling SVs containing numbers.

    It's curious that you only used unpack 'N' in combination with split and that you never tried split without unpack 'N'.

[reply]
[d/l]
[select]

      The packing and XS things are good points. My intended audience was the more casual user who would be uncomfortable implementing anything in XS (I'm only just barely dabbling in Inline::C, myself).

      As for split without unpack, I thought that was covered in the splitwise case, which I unabashedly stole from Understanding transformation sorts (ST, GRT), the details. Did you mean something else?

      print pack("A25",pack("V*",map{1919242272+$_}(34481450,-49737472,6228,0,-285028276,6979,-1380265972)))
[reply]
[d/l]
[select]

        As for split without unpack, I thought that was covered in the splitwise case

        No, that one doesn't pack

[reply]
Re: RFC: Sorting IPv4 addresses
by ELISHEVA (Prior) on Oct 07, 2009 at 18:54 UTC

    Curious. On my machine (Debian Etch, Perl 5.8.8) the naive run wins every time looses in all cases. Here are the results:

                 Rate naive splitwise inet_orc split_int split_pack inet_g
+rt inet_grt2
naive      12.9/s    --      -79%     -82%      -86%       -86%     -9
+3%      -93%
splitwise  62.1/s  382%        --     -11%      -32%       -33%     -6
+5%      -65%
inet_orc   69.9/s  443%       13%       --      -23%       -24%     -6
+1%      -61%
split_int  91.2/s  608%       47%      30%        --        -1%     -4
+9%      -49%
split_pack 92.2/s  617%       49%      32%        1%         --     -4
+8%      -48%
inet_grt    178/s 1284%      187%     155%       95%        93%       
+--       -0%
inet_grt2   179/s 1287%      188%     155%       96%        94%       
+0%        --

    [download]

    Note:The version of the test I used includes split_pack, but not Sort::Key::IPv4 or Sort::Key::Radix and fixes a small typo in naive_sort (my @b = split /\./, $a; should be my @b = split /\./, $b;)

    Still, this makes me wonder about the Schwartian transform. The argument for it is that during a naive sort we are likely to need to extract the sort key several times. The cumulative time for the repeat derivation of the sort key is more than the extra work of reconstructing the original value from the sort key and the extra copying and memory allocation needed by the three step process. Hence the Schwartzian transform is faster. But is this always true?

    It would seem to depend on four factors:

    • the time needed by the rule for extracting the sort key from the original value
    • the time needed by the rule for reconstructing the original value from the sort key
    • how badly out of order the initial array is.
    • the size of your data set

    Perl sort uses quicksort. If the array is completely ordered,then each sort key (other than the first and last) will be derived twice - once to compare N-1 to N and once to compare N to N+1. In the average case 2N becomes 2N*logN and only in the worst case it is 2*N^2.

    Putting this all together, the Schwartzian transform is only faster if N*(extract_sortkey + reconstruct_value + 2*memcopy) < extract_sortKey*N*X where X is 2 in the best case, log N on average and N in the worst case. This simplifies to reconstruct_value + 2*memcopy < extract_sortkey*(X - 1). Thus we have:

    • Best case: reconstruct_key+2*memcopy < extract_key
    • On average: reconstruct_key+2*memcopy < extract_key*log N
    • Worst case: reconstruct_key+2*memcopy < extract_key*N

    Note that the Schwartian side is a constant and the naive side scales with respect to N. Surely a process that scales by N will be slower than a constant process? Not necessarily. The problem here is that we are comparing apples and oranges. On one side of the equation is "reconstruct_key + 2*memcopy" and on the other is "extract key". These are very different operations and we may be comparing very slow operations to very fast operations. For instance, if the process of reconstructing the original value is 10X slower than extracting the key, we would need to be sorting a fairly large array of N=1024=2^10 values before the Schwartzian transfom would give us any speed advantage.

    The moral of this story is that there is no automatically right way to sort - it all depends on the size of your data set, the likelihood that it will be badly ordered, and the difference between the time involved in extracting sort keys and the time needed to reconstruct original values.

    Best, beth

    Update:Fixed who "wins" - misunderstood output! Thanks to bv, ikegami below.

[reply]
[d/l]
[select]

      Curious. On my machine (Debian Etch, Perl 5.8.8) the naive run wins every time. Here are the results:

      Win at having the lowest rate? I wouldn't call that winning. Other factors being equal, I'd consider the fastest to be the winner, and 179/s (0.00559s) is 13x faster than 12.9/s (0.0775s).

[reply]

      Great information, but did you really mean wins? Your benchmark shows naive coming in dead last, since it's reporting iterations/second. From the documentation,

      The COUNT can be zero or negative: this means the minimum number of CPU seconds to run. A zero signifies the default of 3 seconds.

      [...]

      The benchmark output will, however, also tell the number of $code runs/second, which should be a more interesting number than the actually spent seconds.

      print pack("A25",pack("V*",map{1919242272+$_}(34481450,-49737472,6228,0,-285028276,6979,-1380265972)))
[reply]
[d/l]
[select]

Back to Meditations