I have a big grid which multiple threads access simultaneously. I have it divided into regions, each of which is independently locked. I want to be able to have atomic operations that operate on specified sets of points, which may or may not be part of the same region.
What I have now includes:
pub struct RwGrid<T>{
width : usize,
height : usize,
region_size : usize,
regions : [RwLock<Vec<T>>; TOTAL_REGIONS]
}
impl<T: Copy Colored> Grid<T> for RwGrid<T>{
...
fn set_if<F>(&self, p : Point, f : F, value : T) -> bool where
F : Fn(T) -> bool{
let (region_index, index_in_region) = self.map_coordinates(p);
let mut region = self.regions[region_index].write().unwrap();
let pre_existing = region[index_in_region];
if f(pre_existing){
region[index_in_region] = value;
true
} else {false}
}
...
}
Where map_coordinates is a helper function that maps Cartesian coordinates onto the index of the appropriate region, and the index of the given point within that region.
My goal is (among other things) a variant of that set_if function that atomically looks at a set of points, rather than a single point (specifically, it would look at the nine points making up the immediate neighborhood of a given point.) This set of points might be from the same region, or might come from multiple regions. Further, the locks need to be acquired in a particular order, or deadlock may be possible.
The atomicity requirement is important to note. If it helps, imagine you're trying to sometimes color points red, with the invariant that no red point may be adjacent to another red point. If two threads non-atomically read the neighborhood of the point they're considering, they may interleave, both checking that the other's target point is currently black, then setting two adjacent points red.
I don't know how to abstract over this. I can easily find the regions for a set of points, or for a single point I can acquire the lock and operate on it, but I've been beating my head on how to acquire a set of locks and then operate on points using the appropriate lock, without having enormous amounts of hard-coded boiler plate.
To illustrate the problem, here's a variant of set_if that looks at just two points, and sets one of them based on a condition that depends on both:
fn set_if_2<F>(&self, p1 : Point, p2 : Point, f : F, value : T) -> bool where
F : Fn(T, T) -> bool{
let (region_index_1, index_in_region_1) = self.map_coordinates(p1);
let (region_index_2, index_in_region_2) = self.map_coordinates(p2);
if (region_index_1 == region_index_2){
let mut region = self.regions[region_index_1].write().unwrap();
let pre_existing_1 = region[index_in_region_1];
let pre_existing_2 = region[index_in_region_2];
if f(pre_existing_1, pre_existing_2){
region[index_in_region_1] = value;
true
} else {false}
} else {
let mut region1 = self.regions[region_index_1].write().unwrap();
let region2 = self.regions[region_index_2].write().unwrap();
let pre_existing_1 = region1[index_in_region_1];
let pre_existing_2 = region2[index_in_region_2];
if f(pre_existing_1, pre_existing_2){
region1[index_in_region_1] = value;
true
} else {false}
}
}
This code has two branches based on whether or not the points belong to the same region (and thus need one lock) or different regions (each with their own lock.) As you can imagine, expanding that pattern out to nine different points that might belong to many different configurations of region would be painful and wrong.
So far I have two ideas and they both sound bad:
- Have a function that returns a
Vec<RwLockWriteGuard<T>>and a structure which holds indexes into that vector each point should use. (So if all points come from the same region, theVecwould be one element long and each point would map to0). - Have the data actually live in a single unsafe
Vecwith no locks (I'm not even sure how to do that), but have "fake" locks corresponding to regions, and code theRegionmodule so that points are only accessed after the corresponding lock has been grabbed. One chunk of code could then recognize and acquire the appropriate locks, but that would be independent of subsequently reading or writing to the points.
Are either of those ideas workable? Is there a better way to approach this?
EDIT: Some more code:
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub struct Point(pub usize, pub usize);
fn map_coordinates(&self, p : Point) -> (usize, usize){
let Point(x, y) = self.fix(p);
let (region_width, region_height) = (self.width / REGIONS_PER_DIMENSION, self.height/REGIONS_PER_DIMENSION);
let (target_square_x, target_square_y) = (x/region_width, y/region_height);
let target_square_i = target_square_y * REGIONS_PER_DIMENSION target_square_x;
let (x_in_square, y_in_square) = (x % region_width, y % region_width);
let index_in_square = y_in_square * region_width x_in_square;
(target_square_i, index_in_square)
}
fn fix(&self, p: Point) -> Point{
let Point(x, y) = p;
Point(modulo(x as i32, self.width), modulo(y as i32, self.height))
}
#[inline(always)]
pub fn modulo(a: i32, b: usize) -> usize {
(((a % b as i32) b as i32) % b as i32) as usize
}
One thing to note is that the wrapping behavior (which is enabled by the fix function above) slightly complicates avoiding deadlocks. Points will often be accessed by compass direction, like asking for the northern neighbor of a point. Because the grid wraps, if you always lock in order by compass direction - like, "Northern neighbor, then center, then southern" - you can get a deadlocked cycle. Another way of phrasing this is that if you access Points by the order they're specified in the request, rather than by the order they exist in the grid, you can get cycles.
CodePudding user response：
Alright, so I've figured out a couple ways to do this. Both have the same signature of taking a generic number of points, and treating the point at index 0 as the "target" point to write the value to.
- Without Allocating
This version loops through all points for each region at play, making it O(R*P) where R is the number of regions and P is the number of points.
fn set_if<const N: usize, F: Fn([T; N]) -> bool>(&self, points: [Point; N], f: F, value: T) -> bool {
// The region and index within that region for each point
let point_coords = points.map(|p| self.map_coordinates(p));
// Extract the target point data for direct usage later
let (target_region_index, target_index_in_region) = point_coords[0];
// Iterate through the regions, locking each one,
// and reading the pre-existing values.
let mut pre_existing = [None; N];
// Loop through each region
let mut region_locks: [_; TOTAL_REGIONS] = std::array::from_fn(|region_index| {
let mut region = None;
// Loop through each point
for (j, (this_region_index, index_in_region)) in point_coords.into_iter().enumerate() {
// If the point is in this region
if this_region_index == region_index {
// Acquire a new lock if necessary
// (if this is the first point in the region)
let region = region.get_or_insert_with(|| {
self.regions[region_index].write().unwrap()
});
// Then read the pre-existing value for this point
pre_existing[j] = Some(region[index_in_region])
}
}
// Store region locks to hold the lock until we're done
region
});
// Should never fail
let pre_existing = pre_existing.map(|v| v.unwrap());
let target_region = region_locks[target_region_index].as_mut().unwrap();
if f(pre_existing) {
target_region[target_index_in_region] = value;
true
} else {
false
}
// Region locks dropped at end of scope
}
- With Allocating
This version loops through all points once, collecting the points for each region, and then loops through each region with points, obtaining a lock and handling each point in the region.
This makes it O(R 2P).
fn set_if<const N: usize, F: Fn([T; N]) -> bool>(&self, points: [Point; N], f: F, value: T) -> bool {
// Store a set of indices for each region
let mut region_indices: [Vec<(usize, usize)>; TOTAL_REGIONS] = Default::default();
// Handle the target point first
let (target_region_index, target_index_in_region) = self.map_coordinates(points[0]);
region_indices[target_region_index] = vec![
// We store the index of the point in `points` and
// the index associated with that point within its region
(0, target_index_in_region),
];
// Then handle all of the rest
for (j, p) in points.into_iter().enumerate().skip(1) {
let (region_index, index_in_region) = self.map_coordinates(p);
// Store the index of the point within `points` and
// the index associated with that point within its region
region_indices[region_index].push((j, index_in_region));
}
// Iterate through the regions, locking each one,
// and reading the pre-existing values.
let mut pre_existing = [None; N];
// Store region locks to hold the lock until we're done
let mut region_locks: [_; TOTAL_REGIONS] = Default::default();
for (region_index, indices_in_region) in region_indices.into_iter().enumerate() {
// Skip if there were no points in this region
if indices_in_region.is_empty() {
continue;
};
// Acquire a lock for this region
let region = self.regions[region_index].write().unwrap();
// Read the pre-existing value for each point in the region
for (j, index_in_region) in indices_in_region {
pre_existing[j] = Some(region[index_in_region]);
}
// Store region locks to hold the lock until we're done
region_locks[region_index] = Some(region);
}
// Should never fail
let pre_existing = pre_existing.map(|v| v.unwrap());
let target_region = region_locks[target_region_index].as_mut().unwrap();
if f(pre_existing) {
target_region[target_index_in_region] = value;
true
} else {
false
}
// Region locks dropped at end of scope
}
I prefer option #1, because it is simpler and has no allocations. Given you will likely have a small fixed number of regions and points, I expect performance of option 1 to be better as well. If performance is very important, I'd recommend benchmarking both, though.