# PODNAME: Hash::Ordered::Benchmarks # ABSTRACT: Ordered hash benchmarking __END__ =pod =encoding UTF-8 =head1 NAME Hash::Ordered::Benchmarks - Ordered hash benchmarking =head1 VERSION version 0.002 =head1 INTRODUCTION The L internals are simple: a hash of data and an array of ordered keys. I thought this would perform well for common tasks and likely outperform more complicated ordered hash implementations, so I decided to do some benchmarking to test it. In my review of alternatives to C, six seemed sufficiently general-purpose to be worth benchmarking. The modules tested are listed in the benchmark output in shorthand: =over 4 =item * L — denoted C =item * L — denoted C =item * L — denoted C =item * L — denoted C =item * L — denoted C =item * L — denoted C =item * L — denoted C =back Note that L is written in XS and also may require forced installation as its tests often fail for Perl 5.18+ due to the hash randomization change. If there are different methods of doing something with a module, the variations are described in each section below. =head1 BENCHMARKS I conducted benchmarking with the L module. The test script is in the C directory of the distribution. Tests were run on Perl 5.21.0 (essentially the same as 5.20.0) on a Mac Book Pro. Each benchmark ran for 5 CPU seconds. Benchmarks were run at several different scales to reveal differences in efficiency as hash size grows. The details are described in each section below. A seed list of keys and values was generated from random integers using L. The same seed list was used for all benchmarks unless otherwise noted. I did not test advanced features of these modules, as apples-to-apples comparison is difficult. Still, the performance on common, simple measures could suggest how features that combine these operations might perform. =head2 Ordered hash creation I tested hash creation for 10, 100 and 1000 elements. For some modules there were different options for creating a hash: =over 4 =item * C takes an array-reference with an option to use it directly or to clone it. In one case I provided the seed list array reference with the clone option to true ("a:ah_cp"). In another case I created a new array reference from the seed list and provided it directly ("a:ah_rf"). =item * C can be initialized either with C ("t:ix_oo") or via C ("t:ix_th"). =item * C can be created with a list ("t:xh_ls") or an array reference ("t:xh_rf"). =back As expected, when C gets an array reference, it's very fast. C does well here, also. Of the non-XS, more hash-like choices, C does well. Results for ordered hash creation for 10 elements t:h:i 129713/s a:ah_rf 104034/s h:o 94121/s a:ah_cp 62539/s t:ix_th 60136/s t:ix_oo 59895/s a:oh 49399/s t:llh 32122/s d:xh_rf 13288/s d:xh_ls 13223/s Results for ordered hash creation for 100 elements t:h:i 15026/s a:ah_rf 14304/s h:o 10931/s a:ah_cp 7512/s t:ix_oo 7368/s t:ix_th 7161/s a:oh 6572/s t:llh 3306/s d:xh_ls 1498/s d:xh_rf 1491/s Results for ordered hash creation for 1000 elements a:ah_rf 1410/s t:h:i 1285/s h:o 1022/s a:ah_cp 763/s t:ix_oo 703/s t:ix_th 697/s a:oh 694/s t:llh 290/s d:xh_rf 147/s d:xh_ls 146/s =head2 Getting hash elements I tested retrieving values for 10% of the keys, randomly selected, from hashes of 10, 100 and 1000 elements. The hash was created beforehand so the benchmarks reflect only element access. Some modules had choices for how to retrieve an value, usually between a method (denoted with "_oo"), tied hash access ("_th") or with a dereference ("_rf"). Generally, method calls turned out faster than other approaches for a given module, demonstrating the inefficiency of tied objects. Results for fetching ~10% of 10 elements h:o 1417712/s d:xh_oo 1231973/s t:ix_oo 1120271/s t:h:i 792250/s d:xh_rf 722683/s t:ix_th 624603/s a:oh 553755/s t:llh 504533/s a:ah 246063/s Results for fetching ~10% of 100 elements h:o 244800/s d:xh_oo 181520/s t:ix_oo 175981/s t:h:i 132963/s d:xh_rf 93519/s t:ix_th 82154/s a:oh 68270/s t:llh 57013/s a:ah 28280/s Results for fetching ~10% of 1000 elements h:o 24871/s d:xh_oo 19125/s t:ix_oo 17655/s t:h:i 13407/s d:xh_rf 9590/s t:ix_th 8455/s a:oh 6995/s t:llh 5781/s a:ah 2219/s =head2 Setting hash elements I tested changing values for 10% of the keys, randomly selected, from hashes of 10, 100 and 1000 elements. The hash was created beforehand so the benchmarks reflect only element mutation. No new keys were added. Some modules had choices for how to modify a value, usually between a method (denoted with "_oo"), tied hash access ("_th") or with a dereference ("_rf"). Again, methods outperformed. Results for replacing ~10% of 10 elements h:o 1353795/s d:xh_oo 952485/s t:h:i 943983/s t:ix_oo 923874/s t:llh 600717/s d:xh_rf 568693/s a:oh 547233/s t:ix_th 519939/s a:ah 164170/s Results for replacing ~10% of 100 elements h:o 197232/s t:h:i 131238/s d:xh_oo 121692/s t:ix_oo 114869/s t:llh 71720/s d:xh_rf 67130/s a:oh 63634/s t:ix_th 59784/s a:ah 16843/s Results for replacing ~10% of 1000 elements h:o 20364/s t:h:i 13254/s d:xh_oo 12512/s t:ix_oo 11542/s t:llh 7295/s d:xh_rf 7004/s a:oh 6376/s t:ix_th 6175/s a:ah 1635/s =head2 Adding hash elements I tested adding 10, 100 and 1000 elements to an empty hash. Some modules had choices for how to append a value, usually between a method (denoted with "_oo"), tied hash access ("_th") or with a dereference ("_rf"). For C, I did not use the "lazy" option, but did the equivalent using C and a method call: tied(%tllh)->last( irand(), 42 ) for 1 .. $n; Generally, it seemed like the differences were smaller than for other benchmarks. Methods still outperformed. Results for adding 10 elements to empty hash h:o 367588/s t:h:i 300357/s t:ix_oo 263158/s t:ix_th 214085/s t:llh 187981/s a:oh 141308/s a:ah 96523/s d:xh_oo 87498/s d:xh_rf 84316/s Results for adding 100 elements to empty hash h:o 66495/s t:h:i 57307/s t:ix_oo 49676/s t:ix_th 38222/s a:oh 35476/s t:llh 27998/s d:xh_oo 24371/s d:xh_rf 22326/s a:ah 14114/s Results for adding 1000 elements to empty hash h:o 7217/s t:h:i 6244/s t:ix_oo 5671/s a:oh 4335/s t:ix_th 4313/s d:xh_oo 2977/s t:llh 2899/s d:xh_rf 2683/s a:ah 1466/s =head2 Deleting hash elements I tested creating hashes of 10, 100 and 1000 elements and then deleting 10% of the keys, chosen randomly. I would have liked to have isolated creation from deletion, but I couldn't figure out a way to do that given how C runs the same tests over and over. Some modules had choices for how to delete a value, usually between a method (denoted with "_oo"), tied hash access ("_th") or with a dereference ("_rf"). Interestingly, the performance of different modules changes a lot at the three different sizes, revealing implementation differences. (Though recall that some of this is the creation performance difference as well as deletion difference.) For example, C XS does very well, which could be its good creation performance, but could also be good deletion. C does linear search deleting a key, which is slow at larger sizes. C really shines at larger sizes as deleting from a linked list is faster than splicing out an element of an array. Results for creating 10 element hash then deleting ~10% t:h:i 139517/s h:o 95284/s a:ah 66495/s t:ix_oo 52892/s t:ix_th 50254/s a:oh 45609/s t:llh 28599/s d:xh_rf 13223/s d:xh_oo 13173/s Results for creating 100 element hash then deleting ~10% t:h:i 16745/s h:o 6924/s t:ix_oo 4063/s a:oh 3963/s t:ix_th 3590/s a:ah 3014/s t:llh 2459/s d:xh_oo 1449/s d:xh_rf 1434/s Results for creating 1000 element hash then deleting ~10% t:h:i 1604/s t:llh 269/s a:oh 171/s d:xh_rf 146/s h:o 144/s d:xh_oo 130/s t:ix_oo 85/s t:ix_th 77/s a:ah 36/s =head2 Extracting the hash as a list I tested getting an ordered list of pairs from hashes of 10, 100 and 1000 elements. The hash was created beforehand so the benchmarks reflect only conversion to a list. Oddly, modules that usually have more than one way to do this don't for this. Even C doesn't really have an OO way to do it, so I did it longhand: @list = map { $_ => $tix_oo->FETCH($_) } $tix_oo->Keys; Because C keeps its internal representation as an ordered list of pairs, it outperforms the rest handily. Results for listing pairs of 10 element hash a:ah 290725/s h:o 170187/s t:ix_oo 92118/s t:h:i 80408/s t:ix_th 48756/s t:llh 38509/s a:oh 36126/s d:xh 35766/s Results for listing pairs of 100 element hash a:ah 39222/s h:o 18839/s t:ix_oo 9525/s t:h:i 7742/s a:oh 5081/s t:ix_th 5014/s d:xh 4160/s t:llh 3841/s Results for listing pairs of 1000 element hash a:ah 3703/s h:o 1877/s t:ix_oo 961/s t:h:i 768/s a:oh 508/s t:ix_th 505/s d:xh 413/s t:llh 385/s =head1 CONCLUSION With the exception of hash creation and element deletion, C consistently outperformed the other ordered hash implementations. Even for creation, it was the fastest of the pure-Perl, hash-based implementations, often by a large margin. However, C deletion gets worse as the hash size grows large. This was an intentional trade-off, as keeping an index of keys to allow faster deletion would slow down other operations. I think large-scale key deletion is probably rare in practice, but frequently using the C or C methods on existing keys to move them to the end/start of the list will have similar performance problems. C, with the opposite internal implementation compared to C, performs best at creation and listing pairs, but is dead last at element access and modification. I believe the poor performance is mostly due to extra indirection (e.g. an extra function call) and logic in the element access methods. For uses that don't require much element access and have lots of creation/serialization, it could still be a useful choice. Generally, every module that depends on C for some portion of its implementation pays a substantial performance penalty. C — likely because of its XS implementation — performs decently, but not well enough in my opinion to justify its use. As the author of C, I'm clearly biased, but unless you have very large hashes with lots of deletes, I think these benchmarks make a very good case for it being the "go to" module for general-purpose ordered hashes. =head1 AUTHOR David Golden =head1 COPYRIGHT AND LICENSE This software is Copyright (c) 2014 by David Golden. This is free software, licensed under: The Apache License, Version 2.0, January 2004 =cut