Acme-CPANModules-OrderedHash
view release on metacpan or search on metacpan
lib/Acme/CPANModules/OrderedHash.pm view on Meta::CPAN
package Acme::CPANModules::OrderedHash;
use strict;
our $AUTHORITY = 'cpan:PERLANCAR'; # AUTHORITY
our $DATE = '2025-04-15'; # DATE
our $DIST = 'Acme-CPANModules-OrderedHash'; # DIST
our $VERSION = '0.004'; # VERSION
our $LIST = {
summary => "List of modules that provide ordered hash data type",
description => <<'MARKDOWN',
When you ask a Perl's hash for the list of keys, the answer comes back
unordered. In fact, Perl explicitly randomizes the order of keys it returns
everytime. The random ordering is a (security) feature, not a bug. However,
sometimes you want to know the order of insertion. These modules provide you
with an ordered hash; most of them implement it by recording the order of
insertion of keys in an additional array.
Other related modules:
<pm:Tie::SortHash> - will automatically sort keys when you call `keys()`,
`values()`, `each()`. But this module does not maintain insertion order.
MARKDOWN
entries => [
{
module => 'Tie::IxHash',
bench_code => sub {
my ($op, $numkeys, $numrep) = @_;
tie my %hash, "Tie::IxHash";
for (1..$numkeys) { $hash{"key$_"} = $_ }
if ($op eq 'delete') {
for (1..$numkeys) { delete $hash{"key$_"} }
} elsif ($op eq 'keys') {
for (1..$numrep) { my @keys = keys %hash }
} elsif ($op eq 'iterate') {
for (1..$numrep) { while (my ($k,$v) = each %hash) {} }
}
},
},
{
module => 'Hash::Ordered',
bench_code => sub {
my ($op, $numkeys, $numrep) = @_;
my $hash = Hash::Ordered->new;
for (1..$numkeys) { $hash->set("key$_" => $_) }
if ($op eq 'delete') {
for (1..$numkeys) { $hash->delete("key$_") }
} elsif ($op eq 'keys') {
for (1..$numrep) { my @keys = $hash->keys }
} elsif ($op eq 'iterate') {
for (1..$numrep) { my $iter = $hash->iterator; while (my ($k,$v) = $iter->()) {} }
}
},
},
{
module => 'Tie::Hash::Indexed',
description => <<'MARKDOWN',
Provides two interfaces: tied hash and OO.
MARKDOWN
bench_code => sub {
my ($op, $numkeys, $numrep) = @_;
tie my %hash, "Tie::Hash::Indexed";
for (1..$numkeys) { $hash{"key$_"} = $_ }
if ($op eq 'delete') {
for (1..$numkeys) { delete $hash{"key$_"} }
} elsif ($op eq 'keys') {
for (1..$numrep) { my @keys = keys %hash }
} elsif ($op eq 'iterate') {
for (1..$numrep) { while (my ($k,$v) = each %hash) {} }
}
},
},
{
module => 'Tie::LLHash',
bench_code => sub {
my ($op, $numkeys, $numrep) = @_;
tie my %hash, "Tie::LLHash";
for (1..$numkeys) { (tied %hash)->insert("key$_" => $_) }
if ($op eq 'delete') {
for (1..$numkeys) { delete $hash{"key$_"} }
} elsif ($op eq 'keys') {
for (1..$numrep) { my @keys = keys %hash }
} elsif ($op eq 'iterate') {
for (1..$numrep) { while (my ($k,$v) = each %hash) {} }
}
},
},
{
module => 'Tie::StoredOrderHash',
bench_code => sub {
my ($op, $numkeys, $numrep) = @_;
tie my %hash, "Tie::StoredOrderHash";
for (1..$numkeys) { $hash{"key$_"} = $_ }
lib/Acme/CPANModules/OrderedHash.pm view on Meta::CPAN
if ($op eq 'delete') {
for (1..$numkeys) { delete $hash->{"key$_"} }
} elsif ($op eq 'keys') {
for (1..$numrep) { my @keys = keys %$hash }
} elsif ($op eq 'iterate') {
for (1..$numrep) { while (my ($k,$v) = each %$hash) {} }
}
},
},
{
module => 'List::Unique::DeterministicOrder',
description => <<'MARKDOWN',
Provide a list, not hash.
MARKDOWN
bench_tags => ["no_iterate"].
bench_code => sub {
my ($op, $numkeys, $numrep) = @_;
my $hash = List::Unique::DeterministicOrder->new(data=>[]);
for (1..$numkeys) { $hash->push("key$_") }
if ($op eq 'delete') {
for (1..$numkeys) { $hash->delete("key$_") }
} elsif ($op eq 'keys') {
for (1..$numrep) { my @keys = $hash->keys }
} elsif ($op eq 'iterate') {
for (1..$numrep) { while (my ($k,$v) = each %$hash) {} }
}
},
},
{
module => 'Tree::RB::XS',
description => <<'MARKDOWN',
Multi-purpose tree data structure which can record insertion order and act as an
ordered hash. Use `track_recent => 1, keys_in_recent_order => 1` options. Can
be used as a tied hash, or as an object (faster).
MARKDOWN
bench_code => sub {
my ($op, $numkeys, $numrep) = @_;
my $tree= Tree::RB::XS->new(compare_fn => 'str', track_recent => 1, keys_in_recent_order => 1);
for (1..$numkeys) { $tree->insert("key$_") }
if ($op eq 'delete') {
for (1..$numkeys) { $tree->delete("key$_") }
} elsif ($op eq 'keys') {
for (1..$numrep) { my @keys= $tree->keys }
} elsif ($op eq 'iterate') {
for (1..$numrep) { my $iter = $tree->iter; while (my $v = $iter->next) {} }
}
},
},
],
bench_datasets => [
{name=>'insert 1000 pairs', argv => ['insert', 1000]},
{name=>'insert 1000 pairs + delete', argv => ['delete', 1000]},
{name=>'insert 1000 pairs + return keys 100 times', argv => ['keys', 1000, 100]},
{name=>'insert 1000 pairs + iterate 10 times', argv => ['iterate', 1000, 10], exclude_participant_tags => ['no_iterate']},
],
};
1;
# ABSTRACT: List of modules that provide ordered hash data type
__END__
=pod
=encoding UTF-8
=head1 NAME
Acme::CPANModules::OrderedHash - List of modules that provide ordered hash data type
=head1 VERSION
This document describes version 0.004 of Acme::CPANModules::OrderedHash (from Perl distribution Acme-CPANModules-OrderedHash), released on 2025-04-15.
=head1 SYNOPSIS
To run benchmark with default option:
% bencher --cpanmodules-module OrderedHash
To run module startup overhead benchmark:
% bencher --module-startup --cpanmodules-module OrderedHash
For more options (dump scenario, list/include/exclude/add participants, list/include/exclude/add datasets, etc), see L<bencher> or run C<bencher --help>.
=head1 DESCRIPTION
When you ask a Perl's hash for the list of keys, the answer comes back
unordered. In fact, Perl explicitly randomizes the order of keys it returns
everytime. The random ordering is a (security) feature, not a bug. However,
sometimes you want to know the order of insertion. These modules provide you
with an ordered hash; most of them implement it by recording the order of
insertion of keys in an additional array.
Other related modules:
L<Tie::SortHash> - will automatically sort keys when you call C<keys()>,
C<values()>, C<each()>. But this module does not maintain insertion order.
=head1 ACME::CPANMODULES ENTRIES
=over
=item L<Tie::IxHash>
=item L<Hash::Ordered>
=item L<Tie::Hash::Indexed>
Provides two interfaces: tied hash and OO.
=item L<Tie::LLHash>
=item L<Tie::StoredOrderHash>
=item L<Array::OrdHash>
Provide something closest to PHP's associative array, where you can refer
elements by key or by numeric index, and insertion order is remembered.
=item L<List::Unique::DeterministicOrder>
Provide a list, not hash.
=item L<Tree::RB::XS>
Multi-purpose tree data structure which can record insertion order and act as an
ordered hash. Use C<< track_recent =E<gt> 1, keys_in_recent_order =E<gt> 1 >> options. Can
be used as a tied hash, or as an object (faster).
=back
=head1 BENCHMARKED MODULES
Version numbers shown below are the versions used when running the sample benchmark.
L<Tie::IxHash> 1.23
L<Hash::Ordered> 0.014
lib/Acme/CPANModules/OrderedHash.pm view on Meta::CPAN
=item * Tie::Hash::Indexed (perl_code)
L<Tie::Hash::Indexed>
=item * Tie::LLHash (perl_code)
L<Tie::LLHash>
=item * Tie::StoredOrderHash (perl_code)
L<Tie::StoredOrderHash>
=item * Array::OrdHash (perl_code)
L<Array::OrdHash>
=item * Tree::RB::XS (perl_code)
L<Tree::RB::XS>
=back
=head1 BENCHMARK DATASETS
=over
=item * insert 1000 pairs
=item * insert 1000 pairs + delete
=item * insert 1000 pairs + return keys 100 times
=item * insert 1000 pairs + iterate 10 times
=back
=head1 BENCHMARK SAMPLE RESULTS
=head2 Sample benchmark #1
Run on: perl: I<< v5.40.1 >>, CPU: I<< AMD Ryzen 5 7535HS with Radeon Graphics (6 cores) >>, OS: I<< GNU/Linux Ubuntu version 24.10 >>, OS kernel: I<< Linux version 6.11.0-8-generic >>.
Benchmark command (default options):
% bencher --cpanmodules-module OrderedHash
Result formatted as table (split, part 1 of 4):
#table1#
{dataset=>"insert 1000 pairs"}
+----------------------+-----------+-----------+-----------------------+-----------------------+---------+---------+
| participant | rate (/s) | time (ms) | pct_faster_vs_slowest | pct_slower_vs_fastest | errors | samples |
+----------------------+-----------+-----------+-----------------------+-----------------------+---------+---------+
| Tie::StoredOrderHash | 539 | 1.85 | 0.00% | 528.45% | 1.4e-06 | 22 |
| Tie::LLHash | 640 | 1.6 | 19.19% | 427.28% | 3.4e-06 | 20 |
| Array::OrdHash | 889 | 1.12 | 64.84% | 281.24% | 9.6e-07 | 20 |
| Tie::IxHash | 1080 | 0.928 | 99.73% | 214.65% | 6.1e-07 | 20 |
| Hash::Ordered | 1460 | 0.684 | 170.98% | 131.92% | 4.1e-07 | 20 |
| Tie::Hash::Indexed | 1600 | 0.62 | 196.91% | 111.67% | 9.6e-07 | 20 |
| Tree::RB::XS | 3400 | 0.3 | 528.45% | 0.00% | 5.4e-07 | 21 |
+----------------------+-----------+-----------+-----------------------+-----------------------+---------+---------+
The above result formatted in L<Benchmark.pm|Benchmark> style:
Rate T:S T:L A:O T:I H:O TH:I TR:X
T:S 539/s -- -13% -39% -49% -63% -66% -83%
T:L 640/s 15% -- -29% -42% -57% -61% -81%
A:O 889/s 65% 42% -- -17% -38% -44% -73%
T:I 1080/s 99% 72% 20% -- -26% -33% -67%
H:O 1460/s 170% 133% 63% 35% -- -9% -56%
TH:I 1600/s 198% 158% 80% 49% 10% -- -51%
TR:X 3400/s 516% 433% 273% 209% 128% 106% --
Legends:
A:O: participant=Array::OrdHash
H:O: participant=Hash::Ordered
T:I: participant=Tie::IxHash
T:L: participant=Tie::LLHash
T:S: participant=Tie::StoredOrderHash
TH:I: participant=Tie::Hash::Indexed
TR:X: participant=Tree::RB::XS
The above result presented as chart:
=begin html
<img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAtAAAAH4CAMAAABUnipoAAAAIGNIUk0AAHomAACAhAAA+gAAAIDoAAB1MAAA6mAAADqYAAAXcJy6UTwAAADDUExURf///wAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
=end html
Result formatted as table (split, part 2 of 4):
#table2#
{dataset=>"insert 1000 pairs + delete"}
+----------------------+-----------+-----------+-----------------------+-----------------------+---------+---------+
| participant | rate (/s) | time (ms) | pct_faster_vs_slowest | pct_slower_vs_fastest | errors | samples |
+----------------------+-----------+-----------+-----------------------+-----------------------+---------+---------+
| Tie::IxHash | 31 | 32 | 0.00% | 5838.76% | 4.8e-05 | 21 |
| Tie::StoredOrderHash | 310 | 3.3 | 875.00% | 509.10% | 8.6e-06 | 21 |
| Tie::LLHash | 376 | 2.66 | 1098.31% | 395.59% | 2.5e-06 | 20 |
| Array::OrdHash | 440 | 2.3 | 1289.81% | 327.31% | 6.1e-06 | 20 |
| Hash::Ordered | 610 | 1.6 | 1854.01% | 203.93% | 1.9e-06 | 20 |
| Tie::Hash::Indexed | 1060 | 0.946 | 3272.21% | 76.11% | 5.7e-07 | 20 |
| Tree::RB::XS | 1900 | 0.54 | 5838.76% | 0.00% | 6.3e-07 | 20 |
+----------------------+-----------+-----------+-----------------------+-----------------------+---------+---------+
The above result formatted in L<Benchmark.pm|Benchmark> style:
Rate T:I T:S T:L A:O H:O TH:I TR:X
T:I 31/s -- -89% -91% -92% -95% -97% -98%
T:S 310/s 869% -- -19% -30% -51% -71% -83%
T:L 376/s 1103% 24% -- -13% -39% -64% -79%
A:O 440/s 1291% 43% 15% -- -30% -58% -76%
H:O 610/s 1900% 106% 66% 43% -- -40% -66%
TH:I 1060/s 3282% 248% 181% 143% 69% -- -42%
TR:X 1900/s 5825% 511% 392% 325% 196% 75% --
Legends:
A:O: participant=Array::OrdHash
H:O: participant=Hash::Ordered
T:I: participant=Tie::IxHash
T:L: participant=Tie::LLHash
T:S: participant=Tie::StoredOrderHash
TH:I: participant=Tie::Hash::Indexed
TR:X: participant=Tree::RB::XS
The above result presented as chart:
=begin html
<img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAtAAAAH4CAMAAABUnipoAAAAIGNIUk0AAHomAACAhAAA+gAAAIDoAAB1MAAA6mAAADqYAAAXcJy6UTwAAADDUExURf///wAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
=end html
Result formatted as table (split, part 3 of 4):
#table3#
{dataset=>"insert 1000 pairs + iterate 10 times"}
+----------------------+-----------+-----------+-----------------------+-----------------------+---------+---------+
| participant | rate (/s) | time (ms) | pct_faster_vs_slowest | pct_slower_vs_fastest | errors | samples |
+----------------------+-----------+-----------+-----------------------+-----------------------+---------+---------+
| Tie::StoredOrderHash | 71 | 14 | 0.00% | 508.52% | 2e-05 | 20 |
| Tie::LLHash | 75.4 | 13.3 | 5.52% | 476.69% | 1.2e-05 | 24 |
| Array::OrdHash | 87.2 | 11.5 | 22.04% | 398.65% | 1e-05 | 20 |
| Tie::IxHash | 107 | 9.36 | 49.51% | 307.02% | 2.5e-06 | 20 |
| Tie::Hash::Indexed | 171 | 5.85 | 139.18% | 154.42% | 5e-06 | 21 |
| Hash::Ordered | 250 | 4 | 250.17% | 73.78% | 6.1e-06 | 20 |
| Tree::RB::XS | 435 | 2.3 | 508.52% | 0.00% | 8.2e-07 | 20 |
+----------------------+-----------+-----------+-----------------------+-----------------------+---------+---------+
The above result formatted in L<Benchmark.pm|Benchmark> style:
Rate T:S T:L A:O T:I TH:I H:O TR:X
T:S 71/s -- -4% -17% -33% -58% -71% -83%
T:L 75.4/s 5% -- -13% -29% -56% -69% -82%
A:O 87.2/s 21% 15% -- -18% -49% -65% -80%
T:I 107/s 49% 42% 22% -- -37% -57% -75%
TH:I 171/s 139% 127% 96% 60% -- -31% -60%
H:O 250/s 250% 232% 187% 134% 46% -- -42%
TR:X 435/s 508% 478% 400% 306% 154% 73% --
Legends:
A:O: participant=Array::OrdHash
H:O: participant=Hash::Ordered
T:I: participant=Tie::IxHash
T:L: participant=Tie::LLHash
T:S: participant=Tie::StoredOrderHash
TH:I: participant=Tie::Hash::Indexed
TR:X: participant=Tree::RB::XS
The above result presented as chart:
=begin html
<img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAtAAAAH4CAMAAABUnipoAAAAIGNIUk0AAHomAACAhAAA+gAAAIDoAAB1MAAA6mAAADqYAAAXcJy6UTwAAADJUExURf///wAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
=end html
Result formatted as table (split, part 4 of 4):
#table4#
{dataset=>"insert 1000 pairs + return keys 100 times"}
+----------------------+-----------+-----------+-----------------------+-----------------------+-----------+---------+
| participant | rate (/s) | time (ms) | pct_faster_vs_slowest | pct_slower_vs_fastest | errors | samples |
+----------------------+-----------+-----------+-----------------------+-----------------------+-----------+---------+
| Tie::StoredOrderHash | 17 | 58 | 0.00% | 1439.14% | 6.1e-05 | 20 |
| Tie::LLHash | 20 | 50 | 16.39% | 1222.37% | 7.3e-05 | 20 |
| Array::OrdHash | 25 | 40 | 44.54% | 964.81% | 0.00011 | 21 |
| Tie::IxHash | 26.8 | 37.3 | 54.99% | 893.08% | 3.3e-05 | 20 |
| Tie::Hash::Indexed | 44 | 23 | 154.54% | 504.67% | 2.7e-05 | 20 |
| Hash::Ordered | 135 | 7.43 | 678.48% | 97.71% | 7.1e-06 | 20 |
| Tree::RB::XS | 270 | 3.8 | 1439.14% | 0.00% | 4.3e-06 | 20 |
+----------------------+-----------+-----------+-----------------------+-----------------------+-----------+---------+
The above result formatted in L<Benchmark.pm|Benchmark> style:
Rate T:S T:L A:O T:I TH:I H:O TR:X
T:S 17/s -- -13% -31% -35% -60% -87% -93%
T:L 20/s 15% -- -19% -25% -54% -85% -92%
A:O 25/s 44% 25% -- -6% -42% -81% -90%
T:I 26.8/s 55% 34% 7% -- -38% -80% -89%
TH:I 44/s 152% 117% 73% 62% -- -67% -83%
H:O 135/s 680% 572% 438% 402% 209% -- -48%
TR:X 270/s 1426% 1215% 952% 881% 505% 95% --
Legends:
A:O: participant=Array::OrdHash
H:O: participant=Hash::Ordered
T:I: participant=Tie::IxHash
T:L: participant=Tie::LLHash
T:S: participant=Tie::StoredOrderHash
TH:I: participant=Tie::Hash::Indexed
TR:X: participant=Tree::RB::XS
The above result presented as chart:
=begin html
<img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAtAAAAH4CAMAAABUnipoAAAAIGNIUk0AAHomAACAhAAA+gAAAIDoAAB1MAAA6mAAADqYAAAXcJy6UTwAAADMUExURf///wAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
=end html
=head2 Sample benchmark #2
Benchmark command (benchmarking module startup overhead):
% bencher --cpanmodules-module OrderedHash --module-startup
Result formatted as table:
#table5#
+----------------------+-----------+-------------------+-----------------------+-----------------------+-----------+---------+
| participant | time (ms) | mod_overhead_time | pct_faster_vs_slowest | pct_slower_vs_fastest | errors | samples |
+----------------------+-----------+-------------------+-----------------------+-----------------------+-----------+---------+
| Hash::Ordered | 14 | 6 | 0.00% | 80.85% | 0.00011 | 20 |
| Tie::Hash::Indexed | 13 | 5 | 3.99% | 73.91% | 9.5e-05 | 21 |
| Array::OrdHash | 13 | 5 | 9.26% | 65.51% | 9.4e-05 | 20 |
| Tree::RB::XS | 12 | 4 | 9.34% | 65.39% | 9.6e-05 | 20 |
| Tie::LLHash | 12 | 4 | 12.48% | 60.77% | 8.7e-05 | 20 |
| Tie::IxHash | 12 | 4 | 13.93% | 58.73% | 3.8e-05 | 20 |
| Tie::StoredOrderHash | 10 | 2 | 39.06% | 30.05% | 0.0001 | 20 |
( run in 0.559 second using v1.01-cache-2.11-cpan-39bf76dae61 )