Faster way to iterate over keys?

[crclark]

First off, thanks for this great library. :)

Is there any faster way to iterate over keys than the Keys API? I'm noticing that I can't get more than 1 - 2 million items per second. Given that papaya can effectively scale to billions of keys and hundreds of millions of concurrent accesses, getting bottlenecked on the "easy" stuff is tough. 😆

[ibraheemdev]

So there are a couple easy things you could try here:

• Set resize_mode to ResizeMode::Blocking. With incremental resizing, it's possible that your map is split across multiple hash tables, and so before every iteration, the map is forced to block and complete the resize itself to ensure consistent results. Blocking resizing should improve iteration while sacrificing insert latency.
• Set epoch_frequency to None on the Collector. This should improve performance in general across all operations while sacrificing memory usage in the event of stalled threads, e.g. a thread holding an iterator guard for a long period of time and preventing memory reclamation.

Implementation wise, there is another issue here. Iterators read the metadata for every entry before loading the entry itself, even though they do not necessarily need to. In a mostly empty table, this may improve performance as the metadata is cheaper to load. However, if the table is mostly full, then this is probably hurting performance quite significantly, as metadata is stored in a separate segment of the table.

The reason this is necessary is to preserve consistency with get operations, which also read the metadata first. It would be possible to add a "weak" iterator that does not read the metadata, which should be faster. However, it may fail on an example like this:

let map = map.pin();
for (key, _) in map.weak_iter() {
   assert!(map.contains(key)); // Not guaranteed, even assuming no removals.
}

[crclark]

Thanks for the detailed reply!

I never delete keys in my use case, and I just need to iterate through the keys once, at the end of my program, after doing all the hard work in parallel. So it sounds like .weak_iter() would probably be the best solution. If so, please consider this issue a feature request. :)

[ibraheemdev]

I just need to iterate through the keys once, at the end of my program, after doing all the hard work in parallel

Do you happen to have an owned or mutable reference to the map at that point? If so, maybe what you really want is a IntoIterator or iter_mut API.

[crclark]

Do you happen to have an owned or mutable reference to the map at that point? If so, maybe what you really want is a IntoIterator or iter_mut API.

I do, actually. I don't see an iter_mut in the papaya docs, though, and the only IntoIterator impl I see is after I get an Iter from the hashmap itself, which I'm assuming wouldn't be faster. I think I'm missing something obvious. Could you point me to the exact thing I should be using?

[ibraheemdev]

It doesn't exist yet :) I was just wondering if that would be a better solution to your problem.

[crclark]

Oh, sorry, I misunderstood. I need to do a couple sequential passes over the map, non-mutably, after the heavy parallel work is done. So IntoIterator should suffice, I think.