什么时候假设哈希是有意义的？

Question

从perldata:

You can preallocate space for a hash by assigning to the keys() function.
This rounds up the allocated buckets to the next power of two:

   keys(%users) = 1000;      # allocate 1024 buckets

在预设哈希值会提高性能时是否有经验法则？

Answer 1

经验法则是,你知道Hash越大,你就越有可能从预先确定它的大小中获得价值.考虑一下你的哈希是否有10个槽,并且你开始一个接一个地添加,扩展的数量将a)很少(如果有的话),和b)小(因为数据很少).

但是如果你知道你将需要至少1M项,那么没有理由扩展,并在表增长时反复复制底层和不断扩展的数据结构.

你会注意到这种扩张吗？呃,也许吧.现代机器非常快,可能不会出现.但这对于堆扩展来说是一个巨大的机会,从而导致了GC和各种各样的事情.所以,如果你知道你将要使用它,这是一个"廉价"的解决方案,可以调整一些更多的性能.

Answer 2

我试图对哈希增长的扩展成本进行基准测试:

use Benchmark qw(cmpthese);

# few values
cmpthese(-4, {
    prealloc => sub {
        my %hash;
        keys(%hash) = 17576;
        $hash{$_} = $_ for 'aaa' .. 'zzz';
    },
    normal   => sub {
        my %hash;
        $hash{$_} = $_ for 'aaa' .. 'zzz';
    },
});

# more values
cmpthese(-8, {
    prealloc => sub {
        my %hash;
        keys(%hash) = 456976;
        $hash{$_} = $_ for 'aaaa' .. 'zzzz';
    },
    normal   => sub {
        my %hash;
        $hash{$_} = $_ for 'aaaa' .. 'zzzz';
    },
});

结果听起来不像是大优化,但是减少Will Hartung提到的堆碎片可能会带来好处.在WinXP机器上运行perl 5.12.

       Rate   normal prealloc
normal   48.3/s       --      -2%
prealloc 49.4/s       2%       --
        (warning: too few iterations for a reliable count)
     s/iter   normal prealloc
normal     3.62       --      -1%
prealloc   3.57       1%       --