1Hash::Ordered::BenchmarUksse(r3)Contributed Perl DocumenHtaasthi:o:nOrdered::Benchmarks(3)
2
6 Hash::Ordered::Benchmarks - Ordered hash benchmarking
7
9 version 0.014
10
12 The Hash::Ordered internals are simple: a hash of data and an array of
13 ordered keys. I thought this would perform well for common tasks and
14 likely outperform more complicated ordered hash implementations, so I
15 decided to do some benchmarking to test it.
16 Note: since the initial benchmarking, "Hash::Ordered" gained just-in-
18 time indexing of the keys array to support faster tombstone deletion,
19 which adds some conditional data structures to the internals. It also
20 now supports "tie". The revised benchmarks include the "tie" mode for
21 comparison with other tied hash implementations.
22
24 In my review of alternatives to "Hash::Ordered", six seemed
25 sufficiently general-purpose to be worth benchmarking. The modules
26 tested are listed in the benchmark output in shorthand:
27 • Array::AsHash — denoted "a:ah"
29 • Array::OrdHash — denoted "a:oh"
31 • Data::XHash — denoted "d:xh"
33 • Hash::Ordered — denoted "h:o" and marked with "*"
35 • Tie::Hash::Indexed — denoted "t:h:i"
37 • Tie::IxHash — denoted "t:ix"
39 • Tie::LLHash — denoted "t:llh"
41 Note that Tie::Hash::Indexed is written in XS and also may require
43 forced installation as its tests often fail for Perl 5.18+ due to the
44 hash randomization change.
45 If there are different methods of doing something with a module, the
47 variations are described in each section below.
48
50 I conducted benchmarking with the Benchmark module. The test script is
51 in the "devel" directory of the distribution. Tests were run on Perl
52 5.20.2 on a Mac Book Pro (darwin-thread-multi-2level). Each benchmark
53 ran for 5 CPU seconds.
54 Benchmarks were run at several different scales to reveal differences
56 in efficiency as hash size grows. The details are described in each
57 section below.
58 A seed list of keys and values was generated from random integers using
60 Math::Random::MT::Auto. The same seed list was used for all benchmarks
61 unless otherwise noted.
62 I did not test advanced features of these modules, as apples-to-apples
64 comparison is difficult. Still, the performance on common, simple
65 measures could suggest how features that combine these operations might
66 perform.
67 Ordered hash creation
69 I tested hash creation for 10, 100 and 1000 elements. For some modules
70 there were different options for creating a hash:
71 • "Array::AsHash" takes an array-reference with an option to use it
73 directly or to clone it. In one case I provided the seed list
74 array reference with the clone option to true ("a:ah_cp"). In
75 another case I created a new array reference from the seed list and
76 provided it directly ("a:ah_rf").
77 • "Hash::Ordered" can be initialized either with "new" ("h:o_oo") or
79 via "tie" ("h:o_th").
80 • "Tie::IxHash" can be initialized either with "new" ("t:ix_oo") or
82 via "tie" ("t:ix_th").
83 • "Data::XHash" can be created with a list ("t:xh_ls") or an array
85 reference ("t:xh_rf").
86 As expected, when "Array::AsHash" gets an array reference, it's very
88 fast. "Tie::Hash::Indexed" does well here, also. Of the non-XS, more
89 hash-like choices, "Hash::Ordered" does well.
90 Results for ordered hash creation for 10 elements
92 t:h:i 136030/s
93 a:ah_rf 111411/s
94 h:o_oo 101293/s *
95 h:o_th 98646/s *
96 t:ix_oo 61853/s
97 t:ix_th 61715/s
98 a:ah_cp 56375/s
99 a:oh 54337/s
100 t:llh 33553/s
101 d:xh_ls 14068/s
102 d:xh_rf 13926/s
103 Results for ordered hash creation for 100 elements
105 t:h:i 16503/s
106 a:ah_rf 15398/s
107 h:o_oo 11226/s *
108 h:o_th 10793/s *
109 a:oh 7783/s
110 t:ix_th 7570/s
111 t:ix_oo 7405/s
112 a:ah_cp 7035/s
113 t:llh 3533/s
114 d:xh_ls 1561/s
115 d:xh_rf 1550/s
116 Results for ordered hash creation for 1000 elements
118 t:h:i 1552/s
119 a:ah_rf 1509/s
120 h:o_oo 1160/s *
121 h:o_th 1158/s *
122 a:oh 815/s
123 t:ix_th 772/s
124 t:ix_oo 757/s
125 a:ah_cp 684/s
126 t:llh 340/s
127 d:xh_ls 154/s
128 d:xh_rf 152/s
129 Getting hash elements
131 I tested retrieving values for 10% of the keys, randomly selected, from
132 hashes of 10, 100 and 1000 elements. The hash was created beforehand
133 so the benchmarks reflect only element access.
134 Some modules had choices for how to retrieve an value, usually between
136 a method (denoted with "_oo"), tied hash access ("_th") or with a
137 dereference ("_rf").
138 Generally, method calls turned out faster than other approaches for a
140 given module, demonstrating the inefficiency of tied objects.
141 Results for fetching ~10% of 10 elements
143 h:o_oo 1844781/s *
144 d:xh_oo 1292883/s
145 t:ix_oo 1187104/s
146 t:h:i 932793/s
147 h:o_th 817346/s *
148 d:xh_rf 703441/s
149 t:ix_th 649291/s
150 a:oh 560060/s
151 t:llh 514911/s
152 a:ah 260639/s
153 Results for fetching ~10% of 100 elements
155 h:o_oo 285983/s *
156 d:xh_oo 183292/s
157 t:ix_oo 165100/s
158 t:h:i 128713/s
159 h:o_th 107213/s *
160 d:xh_rf 87049/s
161 t:ix_th 79642/s
162 a:oh 66109/s
163 t:llh 58741/s
164 a:ah 27533/s
165 Results for fetching ~10% of 1000 elements
167 h:o_oo 30342/s *
168 d:xh_oo 19004/s
169 t:ix_oo 17132/s
170 t:h:i 13269/s
171 h:o_th 11100/s *
172 d:xh_rf 8919/s
173 t:ix_th 7844/s
174 a:oh 6763/s
175 t:llh 5666/s
176 a:ah 2772/s
177 Setting hash elements
179 I tested changing values for 10% of the keys, randomly selected, from
180 hashes of 10, 100 and 1000 elements. The hash was created beforehand
181 so the benchmarks reflect only element mutation. No new keys were
182 added.
183 Some modules had choices for how to modify a value, usually between a
185 method (denoted with "_oo"), tied hash access ("_th") or with a
186 dereference ("_rf").
187 Again, methods outperformed.
189 Results for replacing ~10% of 10 elements
191 h:o_oo 1378880/s *
192 t:h:i 945403/s
193 d:xh_oo 941643/s
194 t:ix_oo 887283/s
195 h:o_th 652269/s *
196 t:llh 590160/s
197 d:xh_rf 537694/s
198 a:oh 530787/s
199 t:ix_th 508001/s
200 a:ah 159258/s
201 Results for replacing ~10% of 100 elements
203 h:o_oo 192769/s *
204 t:h:i 126284/s
205 d:xh_oo 119845/s
206 t:ix_oo 113992/s
207 h:o_th 81159/s *
208 t:llh 72403/s
209 d:xh_rf 64791/s
210 a:oh 62666/s
211 t:ix_th 59809/s
212 a:ah 16405/s
213 Results for replacing ~10% of 1000 elements
215 h:o_oo 19909/s *
216 t:h:i 13445/s
217 d:xh_oo 12487/s
218 t:ix_oo 11601/s
219 h:o_th 8357/s *
220 t:llh 7503/s
221 d:xh_rf 6599/s
222 a:oh 6410/s
223 t:ix_th 6118/s
224 a:ah 1651/s
225 Adding hash elements
227 I tested adding 10, 100 and 1000 elements to an empty hash.
228 Some modules had choices for how to append a value, usually between a
230 method (denoted with "_oo"), tied hash access ("_th") or with a
231 dereference ("_rf").
232 For "Tie::LLHash", I did not use the "lazy" option, but did the
234 equivalent using "tied" and a method call:
235 tied(%tllh)->last( irand(), 42 ) for 1 .. $n;
237 Generally, it seemed like the differences were smaller than for other
239 benchmarks. Methods still outperformed.
240 Results for adding 10 elements to empty hash
242 h:o_oo 341022/s *
243 t:h:i 295079/s
244 t:ix_oo 258981/s
245 h:o_th 245996/s *
246 t:ix_th 211341/s
247 t:llh 191298/s
248 a:oh 137447/s
249 a:ah 112651/s
250 d:xh_oo 87215/s
251 d:xh_rf 80379/s
252 Results for adding 100 elements to empty hash
254 h:o_oo 58519/s *
255 t:h:i 55166/s
256 t:ix_oo 48658/s
257 h:o_th 42066/s *
258 t:ix_th 38632/s
259 a:oh 34842/s
260 t:llh 28384/s
261 d:xh_oo 24841/s
262 d:xh_rf 21517/s
263 a:ah 13726/s
264 Results for adding 1000 elements to empty hash
266 h:o_oo 6497/s *
267 t:h:i 6108/s
268 t:ix_oo 5528/s
269 h:o_th 4650/s *
270 t:ix_th 4329/s
271 a:oh 4233/s
272 d:xh_oo 3121/s
273 t:llh 3011/s
274 d:xh_rf 2696/s
275 a:ah 1423/s
276 Deleting hash elements
278 I tested creating hashes of 10, 100 and 1000 elements and then deleting
279 10% of the keys, chosen randomly. I would have liked to have isolated
280 creation from deletion, but I couldn't figure out a way to do that
281 given how "Benchmark" runs the same tests over and over.
282 Some modules had choices for how to delete a value, usually between a
284 method (denoted with "_oo"), tied hash access ("_th") or with a
285 dereference ("_rf").
286 The performance changes (or lack thereof) at the three different sizes
288 reveals implementation differences. (Though recall that some of this
289 is the creation performance difference as well as deletion difference.)
290 For example, "Tie::Hash::Indexed" XS does very well, which could be its
292 good creation performance, but could also be good deletion.
293 "Hash::Ordered" does linear search deleting a key for the 10 element
295 hash, but automatically switches to indexed, tombstone deletion for the
296 larger hashes. When deleting only 10% of keys, garbage collection of
297 tombstoned keys never occurs, so that amortized cost is not included.
298 "Tie::LLHash" improves at larger sizes as deleting from a linked list
300 is faster than splicing out an element of an array. Conversely,
301 "Array::AsHash" just gets worse.
302 Results for creating 10 element hash then deleting ~10%
304 t:h:i 131578/s
305 h:o_oo 94598/s *
306 h:o_th 84018/s *
307 a:ah 67109/s
308 t:ix_oo 55477/s
309 t:ix_th 52792/s
310 a:oh 46938/s
311 t:llh 30399/s
312 d:xh_oo 13756/s
313 d:xh_rf 13499/s
314 Results for creating 100 element hash then deleting ~10%
316 t:h:i 17420/s
317 h:o_oo 9242/s *
318 h:o_th 8438/s *
319 a:oh 5738/s
320 t:ix_oo 3922/s
321 t:ix_th 3862/s
322 a:ah 3286/s
323 t:llh 3250/s
324 d:xh_oo 1508/s
325 d:xh_rf 1499/s
326 Results for creating 1000 element hash then deleting ~10%
328 t:h:i 1635/s
329 h:o_oo 934/s *
330 h:o_th 799/s *
331 t:llh 319/s
332 a:oh 204/s
333 d:xh_oo 152/s
334 d:xh_rf 151/s
335 t:ix_oo 78/s
336 t:ix_th 78/s
337 a:ah 40/s
338 Extracting the hash as a list
340 I tested getting an ordered list of pairs from hashes of 10, 100 and
341 1000 elements. The hash was created beforehand so the benchmarks
342 reflect only conversion to a list.
343 Oddly, modules that usually have more than one way to do things don't
345 for this. Even "Tie::IxHash" doesn't really have an OO way to do it,
346 so I did it longhand:
347 @list = map { $_ => $tix_oo->FETCH($_) } $tix_oo->Keys;
349 Because "Array::AsHash" keeps its internal representation as an ordered
351 list of pairs, it outperforms the rest handily as it merely needs to
352 dereference that data structure.
353 Results for listing pairs of 10 element hash
355 a:ah 321044/s
356 h:o_oo 178288/s *
357 t:ix_oo 89263/s
358 t:h:i 79184/s
359 h:o_th 56112/s *
360 t:ix_th 48009/s
361 a:oh 47433/s
362 t:llh 37996/s
363 d:xh 37439/s
364 Results for listing pairs of 100 element hash
366 a:ah 36399/s
367 h:o_oo 19537/s *
368 t:ix_oo 9049/s
369 t:h:i 7768/s
370 h:o_th 6254/s *
371 a:oh 5060/s
372 t:ix_th 4907/s
373 d:xh 4122/s
374 t:llh 3813/s
375 Results for listing pairs of 1000 element hash
377 a:ah 3784/s
378 h:o_oo 1959/s *
379 t:ix_oo 905/s
380 t:h:i 773/s
381 h:o_th 625/s *
382 a:oh 523/s
383 t:ix_th 492/s
384 d:xh 427/s
385 t:llh 377/s
386
388 With the exception of hash creation and element deletion,
389 "Hash::Ordered" generally outperformed the other ordered hash
390 implementations. Even for creation, it was the fastest of the pure-
391 Perl, hash-based implementations, often by a large margin.
392 In the original release of "Hash::Ordered", deletion got worse as the
394 hash size grew. The new JIT indexing with tombstones now makes
395 deletion far faster than any pure-Perl implementation.
396 "Array::AsHash", with the opposite internal implementation compared to
398 "Hash::Ordered", performs best at creation and listing pairs, but is
399 dead last at element access and modification. I believe the poor
400 performance is mostly due to extra indirection (e.g. an extra function
401 call) and logic in the element access methods. For uses that don't
402 require much element access and have lots of creation/serialization, it
403 could still be a useful choice.
404 Generally, every module that depends on "tie" for some portion of its
406 implementation pays a substantial performance penalty. Comparing
407 "Hash::Ordered" benchmarks with and without "tie" for individual
408 element operations shows how severe this penalty can be.
409 "Tie::Hash::Indexed" — likely because of its XS implementation —
410 performs decently, but not well enough in my opinion to justify its
411 use.
412 As the author of "Hash::Ordered", I'm clearly biased, but I think these
414 benchmarks make a very good case for it being the "go to" module for
415 pure-Perl, general-purpose ordered hashes.
416
418 David Golden <dagolden@cpan.org>
419
421 This software is Copyright (c) 2014 by David Golden.
422 This is free software, licensed under:
424 The Apache License, Version 2.0, January 2004
426perl v5.36.1 2023-04-18 Hash::Ordered::Benchmarks(3)