get_many_mut with variable number of keys

[Ten0]

get_many_mut on slices (rust-lang/rust#83608) does not need to handle a variable number of keys (although it might be nice) because, worse case scenario, you can sort your input array of indexes and iterate over it with successive split_at_mut.

In this case however, that's not an option, as HashMaps don't have the equivalent of split_at_mut.
So it may be useful to be able to lookup a variable (somewhat large) number of distinct keys at the same time in a HashMap, and get mutable references back.

That is in particular needed when we have a storage of many entries, and we want to run a round of updates on distinct subsets of keys, and want to run these in parallel.

Having get_many_mut follow a similar model to what is described at rust-lang/rust#83608 (review) and providing an interface that allows for this would consequently be useful - in fact, that is something I currently would use.

[What42Pizza]

I'd also really like to have this, I'm in a situation right now where I need to have an arbitrary number of mutable references and the way I'm doing it for now isn't great

Update: I've made some code that allows you to do this, I can share it if anyone needs it

[Amanieu]

The problem with returning a variable number of mutable references is that it requires returning a Vec<&mut T> which requires a dynamic allocation. It might end up being faster to just keep the keys around and doing a hash table lookup every time the value is needed.

[Ten0]

It might end up being faster to just keep the keys around and doing a hash table lookup every time the value is needed.

It seems that this would be for the end user to decide, no?
In particular if the follow-up is e.g. rayon parallel processing or that kind of stuff it quickly becomes worth it.

[Amanieu]

Keep in mind that get_many_mut has a complexity of O(n^2) where n is the number of keys to look up. This is because each returned value must be checked against every other returned value to ensure that none of them point to the same entry, which is necessary to satisfy Rust's safety guarantees (mutable references are unique). This can quickly add up when n becomes large.

[Ten0]

each returned value must be checked against every other returned value

That seems reasonable on the const size version because those are unlikely to ever be very large, but here indeed that would seem a bit too expensive, so probably flagging entry as currently being borrowed would fix this?

By the way, on the const size version, how do you deal with Eq implementations that are inconsistent? ("It's ok I'm equal to nobody - oh wait in fact I'm the same key" -> yields several mutable borrows to the same entry)
It looks like the flag at the entry level would be the solution for this as well, no?

[Amanieu]

We compare the pointers to the entries that are actually returned by the lookups.

[Ten0]

Ah of course! ^^
Then I guess if n is too large just sorting the pointers and checking for no consecutive dupes works in O(n* log(n)).

The problems becomes similar to this one:
rust-lang/rust#83608 (review)

[JustForFun88]

Ah of course! ^^ Then I guess if n is too large just sorting the pointers and checking for no consecutive dupes works in O(n* log(n)).

Unlikely, since you still need to take into account the sort itself

[Amanieu]

Currently the implementation is optimized for small n (the most common case is expected to be n = 2).

[Ten0]

Unlikely, since you still need to take into account the sort itself

The sort itself is O(n* log(n)) where n is the number of queried entries.

Currently the implementation is optimized for small n

For the const-size version it's pretty clear that we want to ensure that we are as optimized as possible for small slice sizes. It's also very practical to be able to pattern-match directly on the result (so we don't want to remove a const size version), and I would imagine as well that the most common case is 2.

However it looks like we could provide different APIs through the same function via a GetManyMut trait, as was considered for the std's version on slices.

Then we could have different versions based on the slice size:

let ptrs: Vec<*mut ??> = /* ... */;
if n < 10 { // 10 is the limit for insertion sort in std
    // do n^2
} else {
    let mut ptrs_sorted = ptrs.clone();
    ptrs_sorted.sort_unstable(); // n * log(n)
    assert!(ptrs_sorted.windows(2).all(|w| w[0] != w[1]); // n
}

having optimal perf for both cases. (That was actually also suggested for the std const version here)

With pointers, it looks like the problem becomes essentially exactly the same as they have in std with indexes.
rust-lang/rust#83608 (review)
rust-lang/rust#83608 (comment)

[JustForFun88]

Unlikely, since you still need to take into account the sort itself

The sort itself is O(n* log(n)) where n is the number of queried entries.

Well, as you can see from your own example, you first need to sort, and then go through the array again, looking for the equal pointers. In addition, you do not take into account that sorting will violate the order of the values. That is, the corresponding key will not point to the corresponding value.

[Ten0]

Well, as you can see from your own example, you first need to sort, and then go through the array again, looking for the equal pointers

I'm not sure why that is an issue.

In addition, you do not take into account that sorting will violate the order of the values. That is, the corresponding key will not point to the corresponding value.

I do, that's what the ptrs.clone() is for. I'm returning ptrs at the end.
If we want to have a single alloc we could also with_capacity(n*2) and duplicate the contents at the end of the vec, sort the subslice for the check, then truncate it.

[JustForFun88]

I do, that's what the ptrs.clone() is for. I'm returning ptrs at the end. If we want to have a single alloc we could also with_capacity(n*2) and duplicate the contents at the end of the vec, sort the subslice for the check, then truncate it.

Hmm... it might work. It looks like the method you suggested will improve the existing implementation as well.

As for variable length. Why not consider using something like https://doc.rust-lang.org/std/array/struct.IntoIter.html. For example, create a separate search array and a separate output array. Then push only unique pointers into the output array and return it as IntoIter?