Hash.pick is very slow on big hashes.

[bbkr]

The Problem

my %h;
for ^100_000 { %h{$_} = $_ };

my $t1 = now;
for ^5000 { %h.pick };
say now - $t1;

The code above takes 30 seconds on i7-4770K. That's barely 170 picks per second.
(To put this into perspective array of this size can do 50_000 picks per second.)

[AlexDaniel]

Just in case: not a regression, it was even slower some time ago.

[lizmat]

This is a simple matter of algorithm. Each time you call .roll / .pick without any parameters, it needs to walk half of the keys in the hash (on average).

Is there a particular reason why you do not use the parameter to .pick / .roll to indicate how many items you want from the hash? The performance difference is staggering:

my %h;
for ^100_000 { %h{$_} = $_ };

my $t1 = now;
for ^5000 { %h.pick };
say now - $t1;    # 21.10343142

$t1 = now;
%h.pick(5000);
say now - $t1;    # 0.0848939

Of course, one could create a list of keys in the hash the first time a .roll or .pick is done. But then this would need to get invalidated / updated each time a key was added or deleted. Adding overhead that is not needed for normal operation.

FWIW, I've already spent considerable time optimizing .roll / .pick on Maps/Hashes. I don't think there's a lot to be gained there (but you're very welcome to prove me wrong!)

Closing this ticket as I think this is in the category DIHWIDT.

[AlexDaniel]

I created a doc ticket in case it's a common issue: Raku/doc#2537

[jnthn]

I guess if one has a hash backed by an array, then perhaps it'd be possible to do something more efficient, but even then there's difficulties: some slots will be empty, while others might be in collision and so a list chained off that slot. So I don't immediately know if you can do better and get the probability distribution right, rather than having it biased in various odd ways. And there's no certainty that a hash will be backed by an array; the current MoarVM one is a linked list, for example, which enforces O(n) anyway.

[samcv]

I think we could implement that in MoarVM. We would have to look at how many keys are in each bucket to make sure each key has the same probability, but I think it's quite do-able.

[lizmat]

FWIW, I think most of the algorithm exists in Map.roll(N) already.

[niner]

I trust @samcv when she says it's doable in the VM. The question remains: should we do it? That's again something every VM for Rakudo would have to provide. It's also something MoarVM will have to provide, which needs tests, JIT support, etc. Even though I understand the fun in getting such things to work, there's clearly some cost there.

This raises the question of benefit which must outweigh the cost. I'm not convinced it does. @lizmat already pointed out that %h.pick(5000) is a lot faster. And even if that didn't exist, I'd seriously wonder what the use case for picking a large number of random pairs from a large hash is. Hashes are for when you need to quickly access known keys. They really sound like just the wrong data structure for accessing random keys. If you want to do that, converting the hash into a list of pairs first sounds like a much better strategy.

[lizmat]

The use case was randomly evicting a key from a large hash.

[lizmat]

Perhaps we need to implement .grab on Hash, to reduce HLL overhead.