I think that this whole thing can be better expressed via sets, something like:

let sessions_to_create: BTreeSet<_> =
    sessions_to_create.iter().map(|((u, d), _)| (u, d)).collect();

let requested_sessions: BTreeSet<(_, _)> = request
    .one_time_keys
    .iter()
    .filter(|(user_id, _)| !failed_servers.contains(user_id.server_name()))
    .flat_map(|(u, d)| d.keys().map(|d| (u, d)).collect::<BTreeSet<_>>())
    .collect();

let missing_devices: BTreeSet<_> = requested_sessions.difference(&sessions_to_create).collect();

*edit: Perhaps even move the filter() for the failed servers on the let missing_devices line.

You'll have to deal with double borrows a bit further bellow, but I think the clarity is worth it:

for (user_id, device_id) in missing_devices {
    failed_devices_lock
        .entry((*user_id).to_owned())
        .or_default()
        .insert((*device_id).to_owned())
}

ok, happy to do this. The reason I avoided it was that it felt a bit redundant to build the two sets just so that we could call .difference on them, particularly given we already have the requested_sessions in a map whose keys we can check in O(n log n) (ie, the same as the BTreeSet).

I guess using sets shows the intention more clearly though.

Luckily we can check if the BTreeSet approach is slower, red is the flat_map(), blue is the BTreeSet approach:

The benchmark is processing a /keys/claim response with 163 one-time keys. I did run it a couple of times to get somewhat stable results. The BTreeSet approach does not seem to make any measurable difference.

To check I am understanding the report correctly: this is saying the mean time increased by 0.7680%? In which case, very much agreed this is not worth worrying about.

I'd be interested to see how you ran this benchmark, for future reference.

You are understanding correctly, I did have a couple of runs which claimed that the time decreased by ~0.5% as well. As the report tells us, all of this is within the noise threshold.

I'd be interested to see how you ran this benchmark, for future reference.

Please take a look at the /benchmarks folder: https://github.com/matrix-org/matrix-rust-sdk/tree/main/benchmarks