Crie ponteiros inteligentes expressivos para memória remota em C ++

Olá Habr!

Hoje estamos publicando uma tradução de um estudo interessante sobre como trabalhar com memória e ponteiros em C ++. O material é um pouco acadêmico, mas obviamente será de interesse dos leitores dos livros de Galowitz e Williams .

Siga o anúncio!

Na faculdade, estou envolvido na construção de estruturas de dados distribuídos. Portanto, a abstração que representa o ponteiro remoto é extremamente importante no meu trabalho para criar código limpo e organizado. Neste artigo, explicarei por que ponteiros inteligentes são necessários, contarei como escrevi objetos de ponteiro remoto para minha biblioteca em C ++, verifique se eles funcionam exatamente como ponteiros regulares de C ++; isso é feito usando objetos de link remoto. Além disso, explicarei em que casos essa abstração falha pela simples razão de que meu próprio ponteiro (até agora) não lida com as tarefas que os ponteiros comuns podem executar. Espero que este artigo interesse os leitores envolvidos no desenvolvimento de abstrações de alto nível.

APIs de baixo nível

Ao trabalhar com computadores distribuídos ou com hardware de rede, geralmente você tem acesso de leitura e gravação a uma parte da memória por meio da API C. Um exemplo desse tipo é a API MPI para comunicação unidirecional. Essa API usa funções que abrem o acesso direto à leitura e gravação da memória de outros nós localizados em um cluster distribuído. Veja como fica de uma maneira um pouco simplificada.

void remote_read(void* dst, int target_node, int offset, int size); void remote_write(void* src, int target_node, int offset, int size); 

No deslocamento indicado no segmento de memória compartilhada do nó de destino, o remote_read um certo número de bytes e o remote_write grava um certo número de bytes.

Essas APIs são ótimas porque nos dão acesso a primitivas importantes que são úteis para implementar programas em execução em um cluster de computadores. Eles também são muito bons porque trabalham muito rápido e refletem com precisão os recursos oferecidos no nível do hardware: acesso direto à memória remota (RDMA). Redes modernas de supercomputadores, como Cray Aries e Mellanox EDR , permitem calcular que o atraso na leitura / gravação não excederá 1-2 μs. Esse indicador pode ser alcançado devido ao fato de que a placa de rede (NIC) pode ler e gravar diretamente na RAM, sem esperar que a CPU remota ative e responda à sua solicitação de rede.

No entanto, essas APIs não são tão boas em termos de programação de aplicativos. Mesmo no caso de APIs simples, como descrito acima, não custa nada apagar dados acidentalmente, pois não há nome separado para cada objeto específico armazenado na memória, apenas um grande buffer contíguo. Além disso, a interface não é digitada, ou seja, você é privado de outra ajuda tangível: quando o compilador jura, se você anotar o valor do tipo errado no lugar errado. Seu código simplesmente estará errado e os erros serão da natureza mais misteriosa e catastrófica. A situação é ainda mais complicada porque, na realidade, essas APIs são um pouco mais complicadas e, ao trabalhar com elas, é bem possível reorganizar por engano dois ou mais parâmetros.

Ponteiros excluídos

Os ponteiros são um nível importante e necessário de abstração necessário ao criar ferramentas de programação de alto nível. Às vezes, usar ponteiros diretamente é difícil, e você pode fazer muitos bugs, mas os ponteiros são os blocos de construção fundamentais do código. Estruturas de dados e até links C ++ costumam usar ponteiros ocultos.

Se assumirmos que teremos uma API semelhante às descritas acima, um local exclusivo na memória será indicado por duas "coordenadas": (1) a classificação ou o ID do processo e (2) o deslocamento feito na parte compartilhada da memória remota ocupada pelo processo com essa classificação . Você não pode parar por aí e criar uma estrutura completa.

  template <typename T> struct remote_ptr { size_t rank_; size_t offset_; }; 

Nesse estágio, já é possível projetar uma API para leitura e gravação em ponteiros remotos, e essa API será mais segura do que a que usamos originalmente.

  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)); } 

As transferências de blocos são muito parecidas, e aqui eu as omito por brevidade. Agora, para ler e escrever valores, você pode escrever o seguinte código:

  remote_ptr<int> ptr = ...; int rval = rget(ptr); rval++; rput(ptr, rval); 

Já é melhor que a API original, pois aqui trabalhamos com objetos digitados. Agora não é tão fácil escrever ou ler um valor do tipo errado ou gravar apenas uma parte de um objeto.

Aritmética do ponteiro

A aritmética de ponteiro é a técnica mais importante que permite ao programador gerenciar coleções de valores na memória; se estamos escrevendo um programa para trabalho distribuído na memória, presumivelmente vamos operar com grandes coleções de valores.
O que significa aumentar ou diminuir um ponteiro excluído em um? A opção mais simples é considerar a aritmética dos ponteiros excluídos como a aritmética dos ponteiros comuns: p + 1 simplesmente aponta para o próximo tamanho de memória alinhada por sizeof(T) depois de p no segmento compartilhado da classificação original.

Embora essa não seja a única definição possível da aritmética de ponteiros remotos, ela foi adotada mais ativamente recentemente, e os ponteiros remotos usados ​​dessa maneira estão contidos em bibliotecas como UPC ++ , DASH e BCL. No entanto, a linguagem Unified Parallel C (UPC), que deixou um legado rico na comunidade de especialistas em computação de alto desempenho (HPC), contém uma definição mais elaborada da aritmética dos ponteiros [1].

A implementação da aritmética do ponteiro é simples e envolve apenas a alteração do deslocamento do ponteiro.

  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}; } 

Nesse caso, temos a oportunidade de acessar matrizes de dados na memória distribuída. Assim, poderíamos conseguir que cada processo no programa SPMD realizasse uma operação de gravação ou leitura em sua variável na matriz para a qual o ponteiro remoto é direcionado [2].

 void write_array(remote_ptr<int> ptr, size_t len) { if (my_rank() < len) { rput(ptr + my_rank(), my_rank()); } } 

Também é fácil implementar outros operadores, fornecendo suporte para o conjunto completo de operações aritméticas realizadas na aritmética comum dos ponteiros.

Selecionar nullptr

Para ponteiros regulares, o valor nullptr é NULL , o que geralmente significa reduzir #define para 0x0, pois é improvável que esta seção na memória seja usada. Em nosso esquema com ponteiros remotos, podemos selecionar um valor de ponteiro específico como nullptr , tornando esse local na memória não utilizado, ou incluir um membro booleano especial que indicará se o ponteiro é nulo. Apesar de não usar a melhor maneira de usar um determinado local na memória, também consideraremos que, ao adicionar apenas um valor booleano, o tamanho do ponteiro remoto dobrará do ponto de vista da maioria dos compiladores e aumentará de 128 para 256 bits para manter o alinhamento. Isso é especialmente indesejável. Na minha biblioteca, escolhi {0, 0} , ou seja, um deslocamento de 0 com uma classificação de 0, como o valor nullptr .

Pode ser possível escolher outras opções para o nullptr que também funcionarão. Além disso, em alguns ambientes de programação, como UPC, são implementados indicadores estreitos que cabem em 64 bits cada. Assim, eles podem ser usados ​​em operações de comparação atômica com troca. Ao trabalhar com um ponteiro estreito, é necessário comprometer: o identificador de deslocamento ou o identificador de classificação devem caber em 32 bits ou menos, e isso limita a escalabilidade.

Links excluídos

Em linguagens como Python, a instrução bracket serve como açúcar sintático para chamar os __getitem__ e __getitem__ , dependendo se você lê o objeto ou escreve nele. No C ++, o operator[] não distingue a qual das categorias de valor um objeto pertence e se o valor retornado cairá imediatamente em leitura ou gravação. Para resolver esse problema, as estruturas de dados C ++ retornam links apontando para a memória contida no contêiner, que pode ser gravada ou lida. A implementação do operator[] para std::vector pode se parecer com isso.

  T& operator[](size_t idx) { return data_[idx]; } 

O fato mais significativo aqui é que retornamos uma entidade do tipo T& , que é um link C ++ bruto pelo qual você pode escrever, e não uma entidade do tipo T , que apenas representa o valor dos dados de origem.

No nosso caso, não podemos retornar um link C ++ bruto, pois estamos nos referindo à memória localizada em outro nó e não representada em nosso espaço de endereço virtual. É verdade que podemos criar nossos próprios objetos de referência personalizados.
Um link é um objeto que serve como invólucro ao redor de um ponteiro e executa duas funções importantes: pode ser convertido em um valor do tipo T e você também pode atribuí-lo a um valor do tipo T Portanto, no caso de uma referência remota, precisamos apenas implementar um operador de conversão implícita que leia o valor e também criar um operador de atribuição que escreva no valor.

 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; } }; 

Assim, podemos enriquecer nosso ponteiro remoto com novos recursos poderosos, na presença dos quais ele pode ser desreferenciado exatamente como ponteiros comuns.

 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}; } 

Portanto, agora restauramos a imagem inteira, mostrando como você pode usar ponteiros remotos normalmente. Podemos reescrever o programa simples acima.

 void write_array(remote_ptr<int> ptr, size_t len) { if (my_rank() < len) { ptr[my_rank()] = my_rank(); } } 

Obviamente, nossa nova API de ponteiros nos permite escrever programas mais complexos, por exemplo, uma função para realizar redução paralela com base em uma árvore [3]. As implementações que usam nossa classe de ponteiro remoto são mais seguras e limpas do que aquelas normalmente obtidas usando a API C descrita acima.

Custos decorrentes do tempo de execução (ou falta dele!)

No entanto, quanto nos custaria usar uma abstração de alto nível? Cada vez que acessamos a memória, chamamos o método de desreferenciação, retornamos o objeto intermediário que envolve o ponteiro e, em seguida, chamamos o operador de conversão ou o operador de atribuição que afeta o objeto intermediário. Quanto nos custará em tempo de execução?

Acontece que, se você designar cuidadosamente o ponteiro e as classes de referência, não haverá sobrecarga para essa abstração em tempo de execução - os compiladores C ++ modernos lidam com esses objetos intermediários e chamadas de método por incorporação agressiva. Para avaliar quanto essa abstração nos custará, podemos compilar um programa de exemplo simples e verificar como a montagem irá ver quais objetos e métodos existirão em tempo de execução. No exemplo descrito aqui com redução baseada em árvore compilada com classes de ponteiros remotos e referências, os compiladores modernos reduzem a redução baseada em árvore a várias remote_write e remote_write [4]. Nenhum método de classe é chamado, nenhum objeto de referência existe no tempo de execução.

Interação com bibliotecas de estrutura de dados

Programadores experientes em C ++ lembram que a biblioteca de modelos C ++ padrão declara: Os contêineres STL devem suportar alocadores C ++ personalizados . Alocadores permitem que você aloque memória e, em seguida, essa memória pode ser referenciada usando os tipos de ponteiros feitos por nós. Isso significa que você pode simplesmente criar um "alocador remoto" e conectá-lo para armazenar dados na memória remota usando contêineres STL?

Infelizmente não. Presumivelmente, por motivos de desempenho, o padrão C ++ não requer mais suporte para tipos de referência personalizados e, na maioria das implementações da biblioteca padrão C ++, eles realmente não são suportados. Portanto, por exemplo, se você usa o libstdc ++ do GCC, pode recorrer a ponteiros personalizados, mas ao mesmo tempo pode usar apenas links C ++ normais, o que não permite o uso de contêineres STL na memória remota. Algumas bibliotecas de modelos C ++ de alto nível, por exemplo, Agency , que usam tipos de ponteiros e tipos de referência personalizados, contêm suas próprias implementações de algumas estruturas de dados do STL que realmente permitem trabalhar com tipos de referência remota. Nesse caso, o programador obtém mais liberdade em uma abordagem criativa para criar tipos de alocadores, ponteiros e links e, além disso, obtém uma coleção de estruturas de dados que podem ser usadas automaticamente com eles.

Contexto amplo

Neste artigo, abordamos vários problemas mais amplos e ainda não resolvidos.

• Alocação de memória . Agora que podemos fazer referência a objetos na memória remota, como reservamos ou alocamos essa memória remota?
• Suporte para objetos . E o armazenamento na memória remota de objetos que são do tipo mais complicado que o int? É possível um suporte puro para tipos complexos? Tipos simples podem ser suportados ao mesmo tempo sem desperdiçar recursos na serialização?
• Projetando estruturas de dados distribuídos . Agora que você tem essas abstrações, quais estruturas e aplicativos de dados você pode construir com eles? Quais abstrações devem ser usadas para distribuição de dados?

Anotações

[1] No UPC, os ponteiros têm uma fase que determina qual classificação o ponteiro será direcionado após aumentar um. Devido às fases, as matrizes distribuídas podem ser encapsuladas em ponteiros e os padrões de distribuição podem ser muito diferentes. Esses recursos são muito poderosos, mas podem parecer mágicos para um usuário iniciante. Embora alguns ases do UPC realmente prefiram essa abordagem, uma abordagem orientada a objetos mais razoável é escrever uma classe simples de ponteiro remoto primeiro e depois garantir que os dados sejam alocados com base nas estruturas de dados projetadas especificamente para isso.

[2] A maioria dos aplicativos no HPC é escrita no estilo SPMD , esse nome significa "um programa, dados diferentes". A API do SPMD oferece uma função ou variável my_rank() que informa ao processo que está executando o programa uma classificação ou ID exclusivo, com base no qual ele pode ramificar do programa principal.

[3] Aqui está uma simples redução de árvore escrita no estilo SPMD usando a classe de ponteiro remoto. O código é adaptado com base em um programa originalmente escrito pelo meu colega 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] O resultado compilado do código acima pode ser encontrado aqui .