Hashes do preserve insertion order after all

Replies are listed 'Best First'.
Re: Hashes do preserve insertion order after all by roboticus (Chancellor) on Jul 31, 2019 at 16:16 UTC
kikuchiyo: No, it's letting you sort by the address, as you mention. So it's giving you the creation order instead of the insertion order. `#!/usr/bin/perl use strict; use warnings; use feature qw/say/; my %hoh = ( foo => { value => 'first' }, bar => { value => 'second' }, baz => { value => 'third' }, ); my %h2; $h2{first} = $hoh{baz}; $h2{second} = $hoh{foo}; $h2{third} = $hoh{bar}; for my $elem (sort values %h2) { say "value => " . $elem->{value}; }` [download] Here, I'm inserting the same items into another hash in a different order, yet it returns the same order as the first. `$ perl p.pl value => first value => second value => third` [download] The creation order isn't guaranteed, either. Once you start adding and deleting objects over a longer time period, deleted chunks of memory can be reused later breaking the correlation of address and creation time. ...roboticus When your only tool is a hammer, all problems look like your thumb.	[reply] [d/l] [select]
Re: Hashes do preserve insertion order after all by LanX (Saint) on Jul 31, 2019 at 16:20 UTC
I've seen quite often that Perl was reusing reference addresses after garbage collection had them released before. So how do you want to be sure they really grow chronologically? IIRC there are sufficient solutions on CPAN for an "ordered" hash by `tie`ing an array to the hash. What's wrong with them? Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}	[reply]
Re^2: Hashes do preserve insertion order after all by kikuchiyo (Hermit) on Aug 01, 2019 at 15:49 UTC
I've seen quite often that Perl was reusing reference addresses after garbage collection had them released before. I was curious as to how often this address reusing happens: `#!/bin/bash for i in {1..15}; do perl -Mstrict -wle' use strict; use warnings; my %addr; my $count = 0; my $tries = 2**$ARGV[0]; for my $try (1..$tries) { my %h; for (reverse 1..1000) { $h{$_} = { value => $_}; $count++; } $addr{$_}++ for values %h; } my $reused = scalar grep $addr{$_}>1, keys %addr; my $addrs = scalar keys %addr; print "Address of reference reused $reused times, all addresses $addrs +, in $count tries";' $i done` [download] Address of reference reused 1 times, all addresses 1999, in 2000 tries Address of reference reused 1001 times, all addresses 2999, in 4000 tr +ies Address of reference reused 2995 times, all addresses 3007, in 8000 tr +ies Address of reference reused 3011 times, all addresses 3023, in 16000 t +ries Address of reference reused 3043 times, all addresses 3055, in 32000 t +ries Address of reference reused 3107 times, all addresses 3119, in 64000 t +ries Address of reference reused 3235 times, all addresses 3247, in 128000 +tries Address of reference reused 3491 times, all addresses 3503, in 256000 +tries Address of reference reused 4003 times, all addresses 4015, in 512000 +tries Address of reference reused 5027 times, all addresses 5039, in 1024000 + tries Address of reference reused 7075 times, all addresses 7087, in 2048000 + tries Address of reference reused 11171 times, all addresses 11183, in 40960 +00 tries Address of reference reused 19363 times, all addresses 19375, in 81920 +00 tries Address of reference reused 35747 times, all addresses 35759, in 16384 +000 tries Address of reference reused 68515 times, all addresses 68527, in 32768 +000 tries [download] These numbers seem to be stable on my machine across multiple runs. The bottom line is that address reusing happens all the time.	[reply] [d/l] [select]
Re^3: Hashes do preserve insertion order after all by bliako (Abbot) on Aug 01, 2019 at 20:20 UTC
And will all be drawn from the same lot: Perl's memory pool. When memory is freed, it can be released to perl's free memory pool rather than being released to the OS. Future allocations will dip into this pool first. From Re: Long running tasks, perl and garbage collection by ikegami	[reply]
Re^3: Hashes do preserve insertion order after all by LanX (Saint) on Aug 01, 2019 at 20:09 UTC
I suppose Perl is keeping its memory footprint low by reusing them. Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}	[reply]
Re^2: Hashes do preserve insertion order after all by bliako (Abbot) on Jul 31, 2019 at 23:30 UTC
What's wrong with them? efficiency?	[reply]
Re^3: Hashes do preserve insertion order after all by LanX (Saint) on Aug 01, 2019 at 00:09 UTC
Elaborate? Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}	[reply]
Re^4: Hashes do preserve insertion order after all by bliako (Abbot) on Aug 01, 2019 at 00:45 UTC
Re^5: Hashes do preserve insertion order after all by swl (Prior) on Aug 01, 2019 at 08:06 UTC
Some notes below your chosen depth have not been shown here
Re^5: Hashes do preserve insertion order after all by LanX (Saint) on Aug 01, 2019 at 02:37 UTC
Re: Hashes do preserve insertion order after all by swl (Prior) on Jul 31, 2019 at 22:49 UTC
See also Hash::Ordered.	[reply]
Re: Hashes do preserve insertion order after all by bliako (Abbot) on Aug 01, 2019 at 00:27 UTC
Allegedly the solution to a common headache I had recently: save control points to a curve path where order of insertion is important - shape depends on it. But also delete a control point in the middle of the path (by key): meaning retain insertion order and at the same time search/insert/delete O(1) by key ... hmmm kikuchiyo please prepare a test case to prove your hack's worth (especially when memory is not large - as others here said already). Here is a thought: `#!/usr/bin/perl use strict; use warnings; use feature qw/say/; my %hoh = ( foo => { value => 'second', time => time}, bar => { value => 'first', time => time}, baz => { value => 'third', time => time}, ); for my $elem (sort {$a->{time} <=> $b->{time}} values %hoh) { say "value => " . $elem->{value}; }` [download] which does not work because `time()` granularity is too thick/un-fine. Using DateTime::HiRes is not a guarantee either. Should one be using instruction-based counting? Perhaps Perl has a monotonically increasing counter, sort of like an incrementing-only program counter/instruction pointer? Alas, even than can not guarantee one instruction to insert only one hash element (can it?). A very interesting problem which has solutions but not EFFICIENT solutions. This is one of the most ingenious I have seen. bw, bliako (edit: aesthetical edits a minute after posting)	[reply] [d/l] [select]
Re^2: Hashes do preserve insertion order after all by bliako (Abbot) on Aug 01, 2019 at 00:37 UTC
BTW, of course this works...: `#!/usr/bin/perl use strict; use warnings; use feature qw/say/; my $HC = 0; my %hoh = ( foo => { value => 'second', time => $HC++}, bar => { value => 'first', time => $HC++}, baz => { value => 'third', time => $HC++}, ); for my $elem (sort {$a->{time} <=> $b->{time}} values %hoh) { say "value => " . $elem->{value}; }` [download] bw, bliako	[reply] [d/l]
Re^2: Hashes do preserve insertion order after all by kikuchiyo (Hermit) on Aug 01, 2019 at 16:10 UTC
All the criticism against this hack brought up in the other replies is valid. I see one context where it might still have a viable use case: in very short, one shot, one liner scripts that build one data structure, transform or filter it some way then print the result. This is the context where I've discovered it by the way. Example: I had a complex, multilevel JSON, and I wanted a flat list of some of the values from a sub-hash. The json_xs command line script from the JSON::XS module has a mode to execute arbitrary code before printing the result, so I used the following one liner: `json_xs -t string -e 'my $x; for (sort values %{ $_->{database}->{data +bases} }) {$x .= $_->{dbname}. $/;} $_=$x' < conf/test.json` [download] In this (and only this) context this hack can be used quite reliably, and it has the advantage that it is concise and does not require any external modules (and presumably it is fast, because all it uses is the built-in reference stringification and sort's default lexical sorting).	[reply] [d/l]
Re: Hashes do preserve insertion order after all by Anonymous Monk on Aug 04, 2019 at 21:51 UTC
When you start to delete things you'll see that the ordering quickly breaks and once broken does not return.	[reply]
Re^2: Hashes do preserve insertion order after all by LanX (Saint) on Aug 05, 2019 at 18:26 UTC
The OP was explicitly sorting by ref address of the values. No matter how many hash entries you delete this order won't change. The real problems with this approach were already addressed. Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}	[reply]