Bonjour, Habr!
Aujourd'hui, nous publions la traduction d'une étude intéressante sur l'utilisation de la mémoire et des pointeurs en C ++. Le matériel est un peu académique, mais il intéressera évidemment les lecteurs des livres de
Galowitz et
Williams .
Suivez l'annonce!
A l'école doctorale, je suis engagé dans la construction de structures de données distribuées. Par conséquent, l'abstraction représentant le pointeur distant est extrêmement importante dans mon travail pour créer du code propre et bien rangé. Dans cet article, je vais expliquer pourquoi des pointeurs intelligents sont nécessaires, expliquer comment j'ai écrit des objets de pointeur distant en C ++ pour ma bibliothèque, m'assurer qu'ils fonctionnent exactement comme des pointeurs C ++ normaux; cela se fait en utilisant des objets de liaison distante. De plus, j'expliquerai dans quels cas cette abstraction échoue pour la simple raison que mon propre pointeur (jusqu'à présent) ne fait pas face aux tâches que les pointeurs ordinaires peuvent faire. J'espère que cet article intéressera les lecteurs impliqués dans le développement d'abstractions de haut niveau.
API de bas niveau
Lorsque vous travaillez avec des ordinateurs distribués ou avec du matériel réseau, vous avez souvent un accès en lecture et en écriture à un morceau de mémoire via l'API C. Un exemple de ce type est l'API
MPI pour la communication unidirectionnelle. Cette API utilise des fonctions qui ouvrent un accès direct pour lire et écrire à partir de la mémoire d'autres nœuds situés dans un cluster distribué. Voici à quoi cela ressemble de manière légèrement simplifiée.
void remote_read(void* dst, int target_node, int offset, int size); void remote_write(void* src, int target_node, int offset, int size);
Au
décalage indiqué dans le segment de mémoire partagée du nœud cible,
remote_read un certain nombre d'octets et
remote_write écrit un certain nombre d'octets.
Ces API sont excellentes car elles nous donnent accès à des primitives importantes qui nous sont utiles pour implémenter des programmes s'exécutant sur un cluster d'ordinateurs. Ils sont également très bons car ils fonctionnent très rapidement et reflètent avec précision les capacités offertes au niveau matériel: accès direct à la mémoire à distance (RDMA). Les réseaux de superordinateurs modernes, tels que
Cray Aries et
Mellanox EDR , nous permettent de calculer que le retard de lecture / écriture ne dépassera pas 1-2 μs. Cet indicateur peut être atteint du fait que la carte réseau (NIC) peut lire et écrire directement sur la RAM, sans attendre que le CPU distant se réveille et réponde à votre demande de réseau.
Cependant, ces API ne sont pas si bonnes en termes de programmation d'application. Même dans le cas de ces API simples comme décrit ci-dessus, l'effacement accidentel des données ne coûte rien, car il n'y a pas de nom distinct pour chaque objet spécifique stocké en mémoire, seulement un grand tampon contigu. De plus, l'interface n'est pas typée, c'est-à-dire que vous êtes privé d'une autre aide tangible: lorsque le compilateur jure, si vous écrivez la valeur du mauvais type au mauvais endroit. Votre code se révélera simplement faux et les erreurs seront de la nature la plus mystérieuse et la plus catastrophique. La situation est encore plus compliquée car en réalité
ces API sont un peu plus compliquées, et lorsque vous travaillez avec elles, il est tout à fait possible de réorganiser par erreur deux ou plusieurs paramètres.
Pointeurs supprimés
Les pointeurs sont un niveau d'abstraction important et nécessaire lors de la création d'outils de programmation de haut niveau. L'utilisation directe de pointeurs est parfois difficile, et vous pouvez faire beaucoup de bugs, mais les pointeurs sont les blocs de construction fondamentaux du code. Les structures de données et même les liens C ++ utilisent souvent des pointeurs sous le capot.
Si nous supposons que nous aurons une API similaire à celles décrites ci-dessus, un emplacement unique en mémoire sera indiqué par deux «coordonnées»: (1) le
rang ou l'ID de processus et (2) le décalage apporté à la partie partagée de la mémoire distante occupée par le processus avec ce rang . Vous ne pouvez pas vous arrêter là et faire une structure à part entière.
template <typename T> struct remote_ptr { size_t rank_; size_t offset_; };
À ce stade, il est déjà possible de concevoir une API pour lire et écrire sur des pointeurs distants, et cette API sera plus sécurisée que celle que nous utilisions à l'origine.
template <typename T> T rget(const remote_ptr<T> src) { T rv; remote_read(&rv, src.rank_, src.offset_, sizeof(T)); return rv; } template <typename T> void rput(remote_ptr<T> dst, const T& src) { remote_write(&src, dst.rank_, dst.offset_, sizeof(T)); }
Les transferts de blocs sont très similaires, et ici je les omet par souci de concision. Maintenant, pour lire et écrire des valeurs, vous pouvez écrire le code suivant:
remote_ptr<int> ptr = ...; int rval = rget(ptr); rval++; rput(ptr, rval);
C'est déjà mieux que l'API d'origine, car ici nous travaillons avec des objets typés. Désormais, il n'est pas si facile d'écrire ou de lire une valeur de mauvais type ou d'écrire uniquement une partie d'un objet.
Arithmétique des pointeurs
L'arithmétique des pointeurs est la technique la plus importante qui permet à un programmeur de gérer des collections de valeurs en mémoire; si nous écrivons un programme pour le travail distribué en mémoire, nous allons vraisemblablement fonctionner avec de grandes collections de valeurs.
Que signifie augmenter ou diminuer un pointeur supprimé d'une façon? L'option la plus simple consiste à considérer l'arithmétique des pointeurs supprimés comme l'arithmétique des pointeurs ordinaires: p + 1 pointe simplement vers la taille suivante de la mémoire alignée
sizeof(T) après p dans le segment partagé du rang d'origine.
Bien que ce ne soit pas la seule définition possible de l'arithmétique des pointeurs distants, elle a récemment été la plus activement adoptée, et les pointeurs distants utilisés de cette manière sont contenus dans des bibliothèques telles que
UPC ++ ,
DASH et BCL. Cependant, le
langage Unified Parallel C (UPC), qui a laissé un riche héritage dans la communauté des spécialistes du calcul haute performance (HPC), contient une définition plus élaborée de l'arithmétique des pointeurs [1].
L'implémentation de l'arithmétique du pointeur de cette manière est simple et ne nécessite que la modification du décalage du pointeur.
template <typename T> remote_ptr<T> remote_ptr<T>::operator+(std::ptrdiff_t diff) { size_t new_offset = offset_ + sizeof(T)*diff; return remote_ptr<T>{rank_, new_offset}; }
Dans ce cas, nous avons la possibilité d'accéder à des tableaux de données en mémoire distribuée. Ainsi, nous pourrions réaliser que chaque processus du programme SPMD effectuerait une opération d'écriture ou de lecture sur sa variable dans le tableau vers lequel le pointeur distant est dirigé [2].
void write_array(remote_ptr<int> ptr, size_t len) { if (my_rank() < len) { rput(ptr + my_rank(), my_rank()); } }
Il est également facile d'implémenter d'autres opérateurs, prenant en charge l'ensemble complet des opérations arithmétiques effectuées dans l'arithmétique de pointeur ordinaire.
Sélectionnez nullptr
Pour les pointeurs réguliers, la valeur
nullptr est
NULL , ce qui signifie généralement réduire
#define à 0x0, car il est peu probable que cette section en mémoire soit utilisée. Dans notre schéma avec des pointeurs distants, nous pouvons soit choisir une valeur de pointeur spécifique comme
nullptr , rendant ainsi cet emplacement en mémoire inutilisé, soit inclure un membre booléen spécial qui indiquera si le pointeur est nul. Bien que l'utilisation d'un certain emplacement dans la mémoire ne soit pas la meilleure solution, nous tiendrons également compte du fait que lors de l'ajout d'une seule valeur booléenne, la taille du pointeur distant doublera du point de vue de la plupart des compilateurs et passera de 128 à 256 bits pour maintenir l'alignement. Ceci est particulièrement indésirable. Dans ma bibliothèque, j'ai choisi
{0, 0} , c'est-à-dire un décalage de 0 avec un rang de 0, comme valeur
nullptr .
Il peut être possible de choisir d'autres options pour
nullptr qui fonctionneront tout aussi bien. De plus, dans certains environnements de programmation, tels que UPC, des pointeurs étroits sont implémentés qui tiennent sur 64 bits chacun. Ainsi, ils peuvent être utilisés dans des opérations de comparaison atomique avec échange. Lorsque vous travaillez avec un pointeur étroit, vous devez faire des compromis: soit l'identificateur de décalage, soit l'identificateur de rang doit tenir sur 32 bits ou moins, ce qui limite l'évolutivité.
Liens supprimés
Dans des langages comme Python, l'instruction bracket sert de sucre syntaxique pour appeler les
__getitem__ __setitem__ et
__getitem__ , selon que vous lisez ou écrivez l'objet. En C ++, l'
operator[] ne distingue pas à laquelle des
catégories de valeurs un objet appartient et si la valeur retournée tombera immédiatement en lecture ou en écriture. Pour résoudre ce problème, les structures de données C ++ renvoient des liens pointant vers la mémoire contenue dans le conteneur, qui peut être écrite ou lue. L'implémentation de l'
operator[] pour
std::vector pourrait ressembler à ceci.
T& operator[](size_t idx) { return data_[idx]; }
Le fait le plus significatif ici est que nous renvoyons une entité de type
T& , qui est un lien C ++ brut par lequel vous pouvez écrire, et non une entité de type
T , qui représente simplement la valeur des données source.
Dans notre cas, nous ne pouvons pas renvoyer un lien C ++ brut, car nous faisons référence à la mémoire située sur un autre nœud et non représentée dans notre espace d'adressage virtuel. Certes, nous pouvons créer nos propres objets de référence personnalisés.
Un lien est un objet qui sert de wrapper autour d'un pointeur, et il remplit deux fonctions importantes: il peut être converti en une valeur de type
T , et vous pouvez également l'affecter à une valeur de type
T Ainsi, dans le cas d'une référence distante, nous avons juste besoin d'implémenter un opérateur de conversion implicite qui lit la valeur, et également de créer un opérateur d'affectation qui écrit dans la valeur.
template <typename T> struct remote_ref { remote_ptr<T> ptr_; operator T() const { return rget(ptr_); } remote_ref& operator=(const T& value) { rput(ptr_, value); return *this; } };
Ainsi, nous pouvons enrichir notre pointeur distant de nouvelles fonctionnalités puissantes, en présence desquelles il peut être déréférencé exactement comme des pointeurs ordinaires.
template <typename T> remote_ref<T> remote_ptr<T>::operator*() { return remote_ref<T>{*this}; } template <typename T> remote_ref<T> remote_ptr<T>::operator[](ptrdiff_t idx) { return remote_ref<T>{*this + idx}; }
Alors maintenant, nous avons restauré l'image entière montrant comment vous pouvez utiliser des pointeurs distants comme d'habitude. Nous pouvons réécrire le programme simple ci-dessus.
void write_array(remote_ptr<int> ptr, size_t len) { if (my_rank() < len) { ptr[my_rank()] = my_rank(); } }
Bien sûr, notre nouvelle API de pointeur nous permet d'écrire des programmes plus complexes, par exemple, une fonction pour effectuer une réduction parallèle basée sur un arbre [3]. Les implémentations utilisant notre classe de pointeur distant sont plus sûres et plus propres que celles généralement obtenues à l'aide de l'API C décrite ci-dessus.
Coûts résultant de l'exécution (ou de leur absence!)
Cependant, combien cela nous coûterait-il d'utiliser une telle abstraction de haut niveau? Chaque fois que nous accédons à la mémoire, nous appelons la méthode de déréférencement, renvoyons l'objet intermédiaire qui enveloppe le pointeur, puis nous appelons l'opérateur de conversion ou l'opérateur d'affectation qui affecte l'objet intermédiaire. Combien cela nous coûtera-t-il à l'exécution?
Il s'avère que si vous désignez soigneusement le pointeur et les classes de référence, il n'y aura pas de surcharge pour cette abstraction au moment de l'exécution - les compilateurs C ++ modernes gèrent ces objets intermédiaires et les appels de méthode par incorporation agressive. Pour évaluer ce qu'une telle abstraction nous coûtera, nous pouvons compiler un exemple de programme simple et vérifier comment l'assemblage se déroulera pour voir quels objets et méthodes existeront au moment de l'exécution. Dans l'exemple décrit ici avec la réduction basée sur l'arborescence compilée avec des classes de pointeurs et de références distants, les compilateurs modernes réduisent la réduction basée sur l'arborescence à plusieurs
remote_read et
remote_write [4]. Aucune méthode de classe n'est appelée, aucun objet de référence n'existe au moment de l'exécution.
Interaction avec les bibliothèques de structure de données
Les programmeurs C ++ expérimentés se souviennent que la bibliothèque de modèles C ++ standard indique: Les conteneurs STL doivent prendre en charge
les allocateurs C ++ personnalisés . Les allocateurs vous permettent d'allouer de la mémoire, puis cette mémoire peut être référencée à l'aide des types de pointeurs que nous avons créés. Cela signifie-t-il que vous pouvez simplement créer un «allocateur distant» et le connecter pour stocker des données dans la mémoire distante à l'aide de conteneurs STL?
Malheureusement non. Vraisemblablement, pour des raisons de performances, la norme C ++ ne nécessite plus la prise en charge des types de référence personnalisés, et dans la plupart des implémentations de la bibliothèque standard C ++, elles ne sont vraiment pas prises en charge. Ainsi, par exemple, si vous utilisez libstdc ++ de GCC, vous pouvez recourir à des pointeurs personnalisés, mais seuls les liens C ++ normaux sont disponibles, ce qui ne vous permet pas d'utiliser des conteneurs STL dans la mémoire distante. Certaines bibliothèques de modèles C ++ de haut niveau, par exemple,
Agency , qui utilisent des types de pointeurs et des types de référence personnalisés, contiennent leurs propres implémentations de certaines structures de données de STL qui vous permettent vraiment de travailler avec des types de référence distants. Dans ce cas, le programmeur obtient plus de liberté dans une approche créative pour créer des types d'allocateurs, de pointeurs et de liens, et, en outre, obtient une collection de structures de données qui peuvent automatiquement être utilisées avec elles.
Contexte large
Dans cet article, nous avons abordé un certain nombre de problèmes plus vastes et non encore résolus.
- Allocation de mémoire . Maintenant que nous pouvons référencer des objets dans la mémoire distante, comment réserver ou allouer une telle mémoire distante?
- Prise en charge des objets . Qu'en est-il du stockage en mémoire distante de tels objets de types plus compliqués qu'int? Un support soigné pour les types complexes est-il possible? Les types simples peuvent-ils être pris en charge en même temps sans gaspiller les ressources sur la sérialisation?
- Conception de structures de données distribuées . Maintenant que vous disposez de ces abstractions, quelles structures de données et applications pouvez-vous créer avec elles? Quelles abstractions devraient être utilisées pour la distribution des données?
Remarques
[1] Dans UPC, les pointeurs ont une phase qui détermine quel rang le pointeur sera dirigé après avoir augmenté d'une unité. En raison des phases, les tableaux distribués peuvent être encapsulés dans des pointeurs et les modèles de distribution peuvent être très différents. Ces fonctionnalités sont très puissantes, mais elles peuvent sembler magiques à un utilisateur novice. Bien que certains as UPC préfèrent cette approche, une approche orientée objet plus raisonnable consiste à écrire d'abord une classe de pointeur distant simple, puis à s'assurer que les données sont allouées en fonction de structures de données spécialement conçues à cet effet.
[2] La plupart des applications dans HPC sont écrites dans le style de
SPMD , ce nom signifie "un programme, des données différentes". L'API SPMD offre une fonction ou variable
my_rank() qui indique au processus exécutant le programme un rang ou un ID unique, sur la base duquel il peut ensuite se dériver du programme principal.
[3] Voici une simple réduction d'arbre écrite dans le style SPMD en utilisant la classe de pointeur distant. Le code est adapté sur la base d'un programme écrit à l'origine par mon collègue
Andrew Belt .
template <typename T> T parallel_sum(remote_ptr<T> a, size_t len) { size_t k = len; do { k = (k + 1) / 2; if (my_rank() < k && my_rank() + k < len) { a[my_rank()] += a[my_rank() + k]; } len = k; barrier(); } while (k > 1); return a[0]; }
[4] Le résultat compilé du code ci-dessus
peut être trouvé ici .