Comment écrire sur une tranche mutable à partir de plusieurs threads à des index arbitraires sans utiliser de mutex ?

Question

J'ai deux tranches qui sont transmises par une autre méthode :

fn example<T>(a1: &[T], a2: &mut [T]) {}

Je veux traiter a1 avec plusieurs fils d'exécution, puis écrire dans a2 en utilisant totalement arbitraire qui ne sont connus que lors de l'exécution de chaque thread. Mon algorithme garantit que les indices sont mutuellement exclusifs Il n'y a donc pas de course aux données.

Le vérificateur d'emprunts n'aime pas partager les références mutables entre les threads, car il ne connaît pas la garantie offerte par notre algorithme. J'obtiens également un lifetime 'static required rustc (E0621) erreur.

Comment faire cela en Rust ?

Réponses à

• Comment passer une référence à une variable de pile à un thread ?
• Accès mutable simultané à des indices arbitraires d'un grand vecteur dont la disjonction est garantie
• Comment passer des tranches disjointes d'un vecteur à différents threads ?
• Comment exécuter des fils de calcul parallèles sur un tableau partitionné ?
• Comment obtenir des références mutables sur deux éléments de tableau en même temps ?

Ne répondez pas à ma question.

La réponse à la première question aborde le problème du champ d'application, mais pas celui de l'accès à l'information. arbitraire index mutuellement disjoints. La réponse à la deuxième question suggère as_slice_of_cells mais cela ne fonctionne pas ici pour la raison mentionnée plus haut, à savoir la arbitraire l'accès. La réponse à la troisième question suggère également as_slice_of_cells mais là encore, l'hypothèse selon laquelle le tableau peut être divisé en parties disjointes ne peut être satisfaite. La quatrième question porte à nouveau sur la partition du tableau, ce que nous ne pouvons pas faire ici. Il en va de même pour la cinquième question.

Une réponse au problème du champ d'application ( https://stackoverflow.com/a/64502824/10056727 ) en fait tentatives pour résoudre ce problème, mais elle ne suggère pas d'utiliser des traverses et l'alternative proposée est plus dangereuse que la première réponse ici.

Answer 1

Vous rencontrez deux problèmes distincts lorsque vous essayez de mettre en œuvre votre algorithme :

1. Partage non 'static entre les threads n'est pas possible avec std::thread::spawn .
2. L'écriture sur des index mutuellement disjoints dans une tranche sans synchronisation ne peut être effectuée en toute sécurité que si vous pouvez diviser la tranche en plusieurs tranches plus petites et donner chaque tranche divisée exclusivement à chacun des threads.

Le premier problème est facilement évité en utilisant crossbeam::scope pour lancer les threads plutôt que std::thread::spawn . Toutefois, ce dernier problème nécessite une solution non sécurisée. Cependant, comme vous savez que les index sont mutuellement disjoints, il n'y a pas de course aux données dans la pratique, et vous pouvez utiliser UnsafeCell pour affirmer au compilateur qu'il n'y a pas de traces de données. Pour ce faire pour une tranche, vous pouvez utiliser l'utilitaire suivant :

use std::cell::UnsafeCell;

#[derive(Copy, Clone)]
pub struct UnsafeSlice<'a, T> {
    slice: &'a [UnsafeCell<T>],
}
unsafe impl<'a, T: Send + Sync> Send for UnsafeSlice<'a, T> {}
unsafe impl<'a, T: Send + Sync> Sync for UnsafeSlice<'a, T> {}

impl<'a, T> UnsafeSlice<'a, T> {
    pub fn new(slice: &'a mut [T]) -> Self {
        let ptr = slice as *mut [T] as *const [UnsafeCell<T>];
        Self {
            slice: unsafe { &*ptr },
        }
    }

    /// SAFETY: It is UB if two threads write to the same index without
    /// synchronization.
    pub unsafe fn write(&self, i: usize, value: T) {
        let ptr = self.slice[i].get();
        *ptr = value;
    }
}

Cet utilitaire vous permet de convertir une tranche exclusive &mut [T] en une tranche qui peut être partagée, mais qui est toujours utilisée pour la mutation. Bien sûr, cela signifie que l'écriture dans cet index peut entraîner une course aux données, si plusieurs threads écrivent dans le même index sans synchronisation. Ainsi, l'index write n'est pas sûre et provoquera l'UB si cette hypothèse n'est pas respectée.

En UnsafeSlice garantira toujours que vous n'avez pas d'erreurs de type "use-after-free" ou "out-of-bounds" lorsque vous l'utilisez. Seule la vérification des conditions de course est désactivée avec UnsafeSlice .

Pour voir que la conversion dans le constructeur est saine, veuillez consulter les commentaires de sécurité à l'intérieur de l'élément Cell::from_mut y Cell::as_slice_of_cells des méthodes.

Answer 2

Comment faire cela en Rust ? Le recours à unsafe est acceptable.

Si vous avez besoin de deux threads pour faire muter le fichier même données, sans verrou, alors vous doit utiliser unsafe . Il s'agit d'un comportement non défini pour deux références mutables ( &mut ) aux mêmes données pour exister, il faudrait donc accéder aux données par l'intermédiaire de *mut des pointeurs bruts, tout en étant extrêmement prudent pour éviter les courses de données.

Toutefois, en fonction de votre algorithme, vous pourrez peut-être éviter unsafe en créant des &mut références avec split_at_mut .