Open uazu opened 2 years ago
Following comments on Reddit, theoretical cost increases as O(N ln N) and ideally we should use a "sorting network" to implement the comparisons. But still no-one has come up with any example code that actually uses that many simultaneous mutable borrows, and is more efficient if coded that way (as opposed to being coded to work with borrows of 1-3 cells at a time).
I have created the motivating example for more than 3 simultaneous borrows in the separate repository. More than 3 borrows could be useful in ECS (Entity Component System) library in cases when implementation should get more than 3 borrows at the same time. The main problem in this case is that in safe Rust it is impossible to get mutable borrows of multiple, not all, values from the HashMap.
First approach was discussed in PR #26: the feature could be implemented for array of QCell
s using const generics.
But I came up with the second approach: the feature could be implemented for tuples of arity 12 and less (which is a common approach in many other crates, even in std
).
Consider we have a quite long tuple of arity 12:
(A, B, C, D, E, F, G, H, I, J, K, L)
where each type could be different from each other. With the first approach, users will not be able to use this feature with different types as it is possible with rw2
and rw3
methods, because it uses array.
With tuples existing implementation for 2 and 3 simultaneous borrows could be reused, so users will not notice any difference. But for tuples of arity from 4 to 12 implementation can make owner and distinct checks with array or similar algorithm before obtaining mutable references.
Also I think it should be possible to implement this feature for not only an array of cells, but for vector of cells of unknown at compile time length. This can increase flexibility even further in the case of ECS library, as so-called systems can use more than 12 simultaneous borrows.
Okay, for your code example, I would have put the cells inside of the Storage. If you were using TCell or TLCell, that would have zero overhead in memory or time for access. When it comes to the core part of your code, you'd end up with code like this:
position.rw(owner).x += f * 10.0;
position.rw(owner).y -= f * 10.0;
velocity.rw(owner).dx -= f * 5.0;
velocity.rw(owner).dy += f * 5.0;
mass.rw(owner).0 += f;
Since all of those rw(owner)
parts compiles down to nothing (for TCell, TLCell), it makes no difference whether the cell is put around the whole Storage, or inside the Storage.
However I'm still open to discussing things further if that does not meet your requirements.
I've been thinking some more about this idea of using QCell/etc to get mutable access to various entries in a hashmap or other collection simultaneously (rather than borrowing just one thing at a time, to which it is more suited). The same could be achieved using RefCell, actually. The relative costs are as follows:
In both cases the code will panic if you get it wrong, but that is a bug that will be fixed just once. In both cases there are runtime costs. Depending on how the cross-checks are implemented, that might or might not involve memory writes, e.g. if implemented as a sort rather than a naive double-scan, there will be writes. So there may be some benefit of the QCell approach in this case (compared to RefCell), but it's in the balance. It's not so clear cut as other uses of QCell, where we can make use of static knowledge and eliminate costs entirely and provide total guarantees of correctness at compile-time.
So the question is: Can QCell/TCell/etc actually add much value by supporting this case?
As suggested in PR #26, to get multiple unique mutable borrows from HashMap, we can also use iterator and use only those borrows which are actually needed.
So, I think that QCell/TCell/etc add no value by supporting this case.
Personally, I don't think that this is required. All the cases so far where I've needed simultaneous borrows have been handled by
rw2
. However if there are any concrete cases where 4+ simultaneous borrows are needed, and it would be inefficient to handle them as a sequence ofrw2
orrw3
borrows, it would be good to document them and analyse them. So please add a comment if you have such a requirement. If it would really work out as more efficient to borrow 4+ items at a time (considering the roughly O(N^2) comparisons), there is a draft PR #26 which could be finished off to provide this functionality.