巨大なhashの性能について調べてみた

とあるバッチで、30万件のデータをハッシュに突っ込む漢仕様で作ったものの、
これって乱暴なのではないか、またどのくらい乱暴なのか、気になって乱暴に調べてみた。

実行内容
- Perl 5.30 + M1 MacBook Air(2020)
- ランダム文字列をキーに巨大なハッシュを生成
- ハッシュに対しランダムなキーでアクセス(10000回)
- 上記を10回繰り返し、平均値を取得

結果
- メモリはほぼ線形。1000万キーだと1GB超えるので注意。
- 生成時間もほぼ線形。
- アクセス時間は非線形だが、1000万キーでも現実的な時間だった。
- ハッシュすごい（ぉ

perl hash.pl key数
mem_avg:メモリ使用量(Byte)
allocs_avg:ハッシュ作成にかかった時間(Sec)
hash_avg:ハッシュに100回アクセスするのにかかった時間(Sec)

perl hash.pl 10000
mem_avg:1459590.7
allocs_avg:0.1082496
hash_avg:0.0005871

perl hash.pl 100000
mem_avg:15411318.1
allocs_avg:1.0736417
hash_avg:0.0007625

perl hash.pl 1000000
mem_avg:150276410
allocs_avg:11.1518984
hash_avg:0.0019721

perl hash.pl 10000000
mem_avg:1472240922
allocs_avg:112.6321977
hash_avg:0.0025895

乱暴にソース貼り付け。
MarkDownほしい。

use strict;

use utf8;



use Time::HiRes qw/gettimeofday tv_interval/;

use Devel::Size qw/total_size/;



use constant{

	LOOP_COUNT=>10000,

	MAX_WORD_LEN=>100,

	DO_COUNT=>10,

};



my @words = qw/1 2 3 4 5 6 7 8 9 0 a b c d e f g h i j k l m n o p q r s t u v w x y z/;



#MAIN

my $hsize = $ARGV[0];

die("usage: perl this.pl hash_size(1-)") unless($hsize=~/^[0-9]+$/);



my(@allocs_ts, @words_ts, @hash_ts, @mem_ts);

&do_main() foreach(1..DO_COUNT);

print 'mem_avg:'.&calc_avg(\@mem_ts)."\n";

print 'allocs_avg:'.&calc_avg(\@allocs_ts)."\n";

print 'words_avg:'.&calc_avg(\@words_ts)."\n";

print 'hash_avg:'.&calc_avg(\@hash_ts)."\n";



sub do_main{

	# ready huge hash

	my $t0 = [gettimeofday];

	my %hash;

	my $i = 0;

	while($i<$hsize){

		my $w = &make_word();

		next if($hash{$w});

		$hash{$w} = 1;

		$i++;

	}

	my $t1 = [gettimeofday];

	my $diff = tv_interval($t0, $t1);

	push(@allocs_ts, $diff);

	push(@mem_ts, total_size(\%hash));



	# generate trial keys

	$t0 = [gettimeofday];

	my @keywords;

	foreach(1..LOOP_COUNT){

		push(@keywords, &make_word());

	}

	$t1 = [gettimeofday];

	$diff = tv_interval($t0, $t1);

	push(@words_ts, $diff);



	# access hash

	$t0 = [gettimeofday];

	foreach(@keywords){

		next if(exists($hash{$_}));	

	}

	$t1 = [gettimeofday];

	$diff = tv_interval($t0, $t1);

	push(@hash_ts, $diff);

}



#SUBs

sub calc_avg{

	my($nums) = @_;

	my $sum = 0;

	$sum += $_ foreach(@$nums);

	return $sum / scalar(@$nums);

}



sub make_word{

	my $len = &int_rand(MAX_WORD_LEN)+1;

	my $w = '';

	$w.= &get_char() foreach(1..$len);

	return $w;

}



sub get_char{

	return $words[&int_rand(scalar(@words))];

}



sub int_rand{

	my($max) = @_;

	return int(rand($max));

}