sub dbl_look { my $cells = shift; my $chk = shift; my $cnt = 0; for my $p (@points2[0 .. $chk]) { (exists $cells->{$p->[0]} and exists $cells->{$p->[0]}{$p->[1]}) and ++$cnt; } exists $cells->{'notfound'} and die; exists $cells->{'notfound2'} and die; exists $cells->{'notfound3'} and die; } #### timethese 200000, { StjA => sub { stj_look($stj_ref, $npoints }, StjB => sub { stj_look($stj_ref, 2*$npoints }, StjC => sub { stj_look($stj_ref, 3*$npoints }, ... }; #### $ perl pm_1196786.pl 131, keys 131 str: 131 131, keys 131 stj: 131 big: 131 pak: 131 dbl: 131 Benchmark: timing 200000 iterations of BigA, BigB, BigC, DblA, DblB, DblC, PakA, PakB, PakC, StjA, StjB, StjC, StrA, StrB, StrC... BigA: 7 wallclock secs ( 6.51 usr + 0.00 sys = 6.51 CPU) @ 30698.39/s (n=200000) BigB: 13 wallclock secs (12.95 usr + 0.00 sys = 12.95 CPU) @ 15439.25/s (n=200000) BigC: 19 wallclock secs (18.97 usr + 0.00 sys = 18.97 CPU) @ 10543.52/s (n=200000) DblA: 6 wallclock secs ( 6.50 usr + 0.00 sys = 6.50 CPU) @ 30773.97/s (n=200000) DblB: 10 wallclock secs ( 9.23 usr + 0.00 sys = 9.23 CPU) @ 21659.09/s (n=200000) DblC: 12 wallclock secs (11.97 usr + 0.00 sys = 11.97 CPU) @ 16709.83/s (n=200000) PakA: 6 wallclock secs ( 6.31 usr + 0.00 sys = 6.31 CPU) @ 31685.68/s (n=200000) PakB: 13 wallclock secs (12.45 usr + 0.00 sys = 12.45 CPU) @ 16060.39/s (n=200000) PakC: 18 wallclock secs (18.34 usr + 0.00 sys = 18.34 CPU) @ 10902.75/s (n=200000) StjA: 7 wallclock secs ( 6.91 usr + 0.00 sys = 6.91 CPU) @ 28960.32/s (n=200000) StjB: 14 wallclock secs (13.56 usr + 0.00 sys = 13.56 CPU) @ 14746.00/s (n=200000) StjC: 20 wallclock secs (19.94 usr + 0.00 sys = 19.94 CPU) @ 10031.10/s (n=200000) StrA: 6 wallclock secs ( 6.36 usr + 0.00 sys = 6.36 CPU) @ 31446.54/s (n=200000) StrB: 13 wallclock secs (12.67 usr + 0.00 sys = 12.67 CPU) @ 15782.83/s (n=200000) StrC: 19 wallclock secs (18.69 usr + 0.00 sys = 18.69 CPU) @ 10702.63/s (n=200000) #### $ cat pm_1196786.pl use strict; # use warnings; use Benchmark qw(timethese); my @points = ( [ 0, 0 ], [ -1, -2 ], [ 1, 2 ], [ -1, 2 ], [ 1, -2 ], [ 0, 1 ], [ 1, 0 ], [ -1, 0 ], [ 0, -1 ], [ 2147483647, 2147483647 ], [ 2147483647, -2147483647 ], [ -2147483647, 2147483647 ], [ -2147483647, -2147483647 ], [ -1, 2147483647 ], [ 2147483647, 1 ], [ -2, 2147483646 ], [ 1, -2147483647 ], [ 1234561, 1234562 ], [ 1234563, -1234564 ], [ -1234565, 1234566 ], [ -1234567, -1234568 ], [ 10, 11 ], [ 11, 12 ], [ 12, 13 ], [ 13, 14 ], [ 14, 15 ], [ 15, 16 ], [ 16, 17 ], [ 17, 18 ], [ 18, 19 ], [ 19, 20 ], [ 1001, 1002 ], [ 1003, 1004 ], [ 1005, 1006 ], [ 1007, 1008 ], [ 1009, 1010 ], [ 1011, 1012 ], [ 1013, 1014 ], [ 1015, 1016 ], [ 1017, 1018 ], [ 1019, 1020 ], [ -1001, -1002 ], [ -1003, -1004 ], [ -1005, -1006 ], [ -1007, -1008 ], [ -1009, -1010 ], [ -1011, -1012 ], [ -1013, -1014 ], [ -1015, -1016 ], [ -1017, -1018 ], [ -1019, -1020 ], [ 99910, 99911 ], [ 99911, 99912 ], [ 99912, 99913 ], [ 99913, 99914 ], [ 99914, 99915 ], [ 99915, 99916 ], [ 99916, 99917 ], [ 99917, 99918 ], [ 99918, 99919 ], [ 99919, 99920 ], [ -99910, -99911 ], [ -99911, -99912 ], [ -99912, -99913 ], [ -99913, -99914 ], [ -99914, -99915 ], [ -99915, -99916 ], [ -99916, -99917 ], [ -99917, -99918 ], [ -99918, -99919 ], [ -99919, -99920 ], [ 1099910, 1099911 ], [ 1099911, 1099912 ], [ 1099912, 1099913 ], [ 1099913, 1099914 ], [ 1099914, 1099915 ], [ 1099915, 1099916 ], [ 1099916, 1099917 ], [ 1099917, 1099918 ], [ 1099918, 1099919 ], [ 1099919, 1099920 ], [ -1099910, -1099911 ], [ -1099911, -1099912 ], [ -1099912, -1099913 ], [ -1099913, -1099914 ], [ -1099914, -1099915 ], [ -1099915, -1099916 ], [ -1099916, -1099917 ], [ -1099917, -1099918 ], [ -1099918, -1099919 ], [ -1099919, -1099920 ], [ 91099910, 91099911 ], [ 91099911, 91099912 ], [ 91099912, 91099913 ], [ 91099913, 91099914 ], [ 91099914, 91099915 ], [ 91099915, 91099916 ], [ 91099916, 91099917 ], [ 91099917, 91099918 ], [ 91099918, 91099919 ], [ 91099919, 91099920 ], [ -91099910, -91099911 ], [ -91099911, -91099912 ], [ -91099912, -91099913 ], [ -91099913, -91099914 ], [ -91099914, -91099915 ], [ -91099915, -91099916 ], [ -91099916, -91099917 ], [ -91099917, -91099918 ], [ -91099918, -91099919 ], [ -91099919, -91099920 ], [ 491099910, 491099911 ], [ 491099911, 491099912 ], [ 491099912, 491099913 ], [ 491099913, 491099914 ], [ 491099914, 491099915 ], [ 491099915, 491099916 ], [ 491099916, 491099917 ], [ 491099917, 491099918 ], [ 491099918, 491099919 ], [ 491099919, 491099920 ], [ -491099910, -491099911 ], [ -491099911, -491099912 ], [ -491099912, -491099913 ], [ -491099913, -491099914 ], [ -491099914, -491099915 ], [ -491099915, -491099916 ], [ -491099916, -491099917 ], [ -491099917, -491099918 ], [ -491099918, -491099919 ], [ -491099919, -491099920 ], ); my $npoints = @points; my @points2 = @points; push @points2, [ $_->[0]+29, $_->[1]+45 ] for @points; push @points2, [ $_->[0]+450, $_->[1]+290 ] for @points; sub dbl_hash { my $cnt=0; my %cells; for my $p (@points) { $cells{$p->[0]}{$p->[1]}=undef; } for my $p (@points) { (exists $cells{$p->[0]} && exists $cells{$p->[0]}{$p->[1]}) and ++$cnt; } exists $cells{'notfound'} and die; exists $cells{'notfound2'} and die; exists $cells{'notfound3'} and die; print "dbl: $cnt\n"; return \%cells; } sub str_hash { my $cnt=0; my %cells; for my $p (@points) { my $h = $p->[0] . ':' . $p->[1]; my ( $x, $y ) = split ':', $h; if ($x != $p->[0]) { die; } if ($y != $p->[1]) { die; } $cells{$h} = undef; } print "$npoints, keys ", scalar(keys %cells), "\n"; scalar(keys %cells) == $npoints or die; for my $p (@points) { my $h = $p->[0] . ':' . $p->[1]; exists $cells{$h} and ++$cnt; #or die; } exists $cells{'notfound'} and die; exists $cells{'notfound2'} and die; exists $cells{'notfound3'} and die; print "str: $cnt\n"; return \%cells; } sub stj_hash { my $cnt=0; my %cells; for my $p (@points) { my $h = join(':', @$p); my ( $x, $y ) = split ':', $h; if ($x != $p->[0]) { die; } if ($y != $p->[1]) { die; } $cells{$h} = undef; } print "$npoints, keys ", scalar(keys %cells), "\n"; scalar(keys %cells) == $npoints or die; for my $p (@points) { exists $cells{join(':',@$p)} and ++$cnt; } exists $cells{'notfound'} and die; exists $cells{'notfound2'} and die; exists $cells{'notfound3'} and die; print "stj: $cnt\n"; return \%cells; } sub big_hash { my $cnt=0; my %cells; for my $p (@points) { my $h = ($p->[1] << 32) | ($p->[0] & 0xFFFFFFFF); my $x = $h & 0x00000000FFFFFFFF; my $y = ($h & 0xFFFFFFFF00000000) >> 32; if ($x >> 31) { $x -= 0xFFFFFFFF + 1 } if ($y >> 31) { $y -= 0xFFFFFFFF + 1 } if ($x != $p->[0]) { die; } if ($y != $p->[1]) { die; } $cells{$h} = undef; } scalar(keys %cells) == $npoints or die; for my $p (@points) { my $h = ($p->[1] << 32) | ($p->[0] & 0xFFFFFFFF); exists $cells{$h} and ++$cnt; } exists $cells{'notfound'} and die; exists $cells{'notfound2'} and die; exists $cells{'notfound3'} and die; print "big: $cnt\n"; return \%cells; } sub pak_hash { my $cnt=0; my %cells; for my $p (@points) { my $h = pack "ii", $p->[0], $p->[1]; my ( $x, $y ) = unpack "ii", $h; if ($x != $p->[0]) { die; } if ($y != $p->[1]) { die; } $cells{$h} = undef; } scalar(keys %cells) == $npoints or die; for my $p (@points) { my $h = pack "ii", $p->[0], $p->[1]; exists $cells{$h} and ++$cnt; #or die; } exists $cells{'notfound'} and die; exists $cells{'notfound2'} and die; exists $cells{'notfound3'} and die; print "pak: $cnt\n"; return \%cells; } sub stj_look { my $cells = shift; my $chk = shift; my $cnt = 0; for my $p (@points2[0 .. $chk]) { exists $cells->{join(':', @$p)} and ++$cnt; } exists $cells->{'notfound'} and die; exists $cells->{'notfound2'} and die; exists $cells->{'notfound3'} and die; } sub str_look { my $cells = shift; my $chk = shift; my $cnt = 0; for my $p (@points2[0 .. $chk]) { exists $cells->{$p->[0] . ':' . $p->[1]} and ++$cnt; } exists $cells->{'notfound'} and die; exists $cells->{'notfound2'} and die; exists $cells->{'notfound3'} and die; } sub big_look { my $cells = shift; my $chk = shift; my $cnt = 0; for my $p (@points2[0 .. $chk]) { exists $cells->{($p->[1] << 32) | ($p->[0] & 0xFFFFFFFF)} and ++$cnt; } exists $cells->{'notfound'} and die; exists $cells->{'notfound2'} and die; exists $cells->{'notfound3'} and die; } sub pak_look { my $cells = shift; my $chk = shift; my $cnt = 0; for my $p (@points2[0 .. $chk]) { exists $cells->{pack "ii", $p->[0], $p->[1]} and ++$cnt; } exists $cells->{'notfound'} and die; exists $cells->{'notfound2'} and die; exists $cells->{'notfound3'} and die; } sub dbl_look { my $cells = shift; my $chk = shift; my $cnt = 0; for my $p (@points2[0 .. $chk]) { (exists $cells->{$p->[0]} and exists $cells->{$p->[0]}{$p->[1]}) and ++$cnt; } exists $cells->{'notfound'} and die; exists $cells->{'notfound2'} and die; exists $cells->{'notfound3'} and die; } my $str_ref = str_hash(); my $stj_ref = stj_hash(); my $big_ref = big_hash(); my $pak_ref = pak_hash(); my $dbl_ref = dbl_hash(); timethese 200000, { StjA => sub { stj_look($stj_ref, $npoints) }, StrA => sub { str_look($str_ref, $npoints) }, BigA => sub { big_look($big_ref, $npoints) }, PakA => sub { pak_look($pak_ref, $npoints) }, DblA => sub { dbl_look($dbl_ref, $npoints) }, StjB => sub { stj_look($stj_ref, 2*$npoints) }, StrB => sub { str_look($str_ref, 2*$npoints) }, BigB => sub { big_look($big_ref, 2*$npoints) }, PakB => sub { pak_look($pak_ref, 2*$npoints) }, DblB => sub { dbl_look($dbl_ref, 2*$npoints) }, StjC => sub { stj_look($stj_ref, 3*$npoints) }, StrC => sub { str_look($str_ref, 3*$npoints) }, BigC => sub { big_look($big_ref, 3*$npoints) }, PakC => sub { pak_look($pak_ref, 3*$npoints) }, DblC => sub { dbl_look($dbl_ref, 3*$npoints) }, };