File Coverage

blib/lib/Sort/HashKeys.pm
Criterion Covered Total %
statement 6 6 100.0
branch n/a
condition n/a
subroutine 2 2 100.0
pod n/a
total 8 8 100.0


line stmt bran cond sub pod time code
1 3     3   40849 use strict;
  3         7  
  3         76  
2 3     3   14 use warnings;
  3         7  
  3         218  
3             package Sort::HashKeys;
4              
5             # ABSTRACT: Get a sorted-by-key list from a hash
6             our $VERSION = '0.007'; # VERSION
7              
8             require XSLoader;
9             XSLoader::load('Sort::HashKeys', $VERSION);
10              
11             =pod
12              
13             =encoding utf8
14              
15             =head1 NAME
16              
17             Sort::HashKeys - Get a sorted-by-key list from a hash
18              
19              
20             =head1 SYNOPSIS
21              
22             use Sort::HashKeys;
23              
24             my %hash;
25              
26             @sorted_1 = map { ($_, $hash{$_}) } sort keys %hash;
27             @sorted_2 = Sort::HashKeys::sort(%hash);
28             # Same outcome, but the second is faster
29              
30             =head1 DESCRIPTION
31              
32             [13:37:51] Is there a better way to get a sorted list out of a hash
33             than map { ($_, $versions{$_}) } reverse sort keys @versions
34             or iterating manually?
35             [13:39:06] oh I could provide a compare function to sort and chunk the
36             list two by two..
37             [13:40:15] i'd probably go with the map{} reverse sort keys
38             [13:41:04] I don't like it that it repeats the lookup for all keys.
39             Of course wouldn't matter in practice but still…
40             [13:43:40] whatever other solution you find will be slower
41             [13:49:05] put it into a list, pass it to XS, run qsort(3) over it
42             with double the element size. and compare taking only the
43             first part into account. return it back?
44              
45             =head1 BENCHMARK
46              
47             See L in this distribution. Test was run on a Haswell 2.6 GHz i5 CPU (4278U) for a minute each on a copy of a randomly generated hash of 1000 keys. Keys were alphanumeric with length between 1 and 6 and values of integers between 1 and 1000.
48              
49             # perl-5.24.0 w/ BSD libc
50             Rate
51             map {($_,$h{$_})} sort keys %h 1589/s -- 0% -28% -28% -32% -33%
52             map +($_,$h{$_}), sort keys %h 1592/s 0% -- -28% -28% -32% -33%
53             %h{sort keys %h} 2204/s 39% 38% -- 0% -6% -7%
54             S::HK::sort(%h) w/ qsort (threaded) 2199/s 38% 38% 0% -- -6% -7%
55             S::HK::sort(%h) w/ qsort_r (threaded) 2338/s 47% 47% 6% 6% -- -2%
56             S::HK::sort(%h) w/ qsort (non-threaded) 2375/s 49% 49% 8% 8% 2% --
57              
58              
59             49% faster on non-threaded Perl and up to 47% faster on threaded Perl. Aristotle Pagaltzis L adding hash slices available since Perl v5.20.0 to the benchmark. This doesn't solve the unncessary hash lookup, but skipping the C appears to have a much bigger impact on performance. The XS solution is only 8% faster than the pure Perl sort using hash slices.
60              
61             The Slowdown with C on threaded build is because the interpreter state is fetched from thread local storage on every comparison. On GNU and FreeBSD libcs, this is avoided by using non-standard C, which allows passing an extra parameter to the comparison function.
62              
63              
64             =head1 METHODS AND ARGUMENTS
65              
66             =over 4
67              
68             =item sort(@)
69              
70             Sorts a hash-like list C<< (key1 => val1, key2 => val2>) >> by means of your libc's
71             L in ascending order according to Perl's internal C function.
72              
73             Unlike Perl's built-in L. C is not required to be a stable sort and providing a custom comparison function is not yet supported.
74              
75             Lists with odd number of elements are padded by an C.
76              
77             =item reverse_sort(@)
78              
79             Sorts in descending order.
80              
81             =cut
82              
83             1;
84             __END__