C ++ valarray vs. vetor

Eu gosto muito de vetores. Eles são bacanas e rápidos. Mas eu sei que essa coisa chamada valarray existe. Por que eu usaria um valarray em vez de um vetor? Eu sei que os valarrays têm um pouco de açúcar sintático, mas, além disso, quando eles são úteis?

Os valarrays (matrizes de valor) destinam-se a trazer parte da velocidade do Fortran para o C ++. Você não faria um conjunto de indicadores para que o compilador possa fazer suposições sobre o código e otimizá-lo melhor. (O principal motivo pelo qual o Fortran é tão rápido é que não há tipo de ponteiro, portanto não pode haver alias do ponteiro.)

Os valarrays também têm classes que permitem dividi-los de uma maneira razoavelmente fácil, embora essa parte do padrão possa usar um pouco mais de trabalho. Redimensioná-los é destrutivo e eles não têm iteradores.

Portanto, se você trabalha com números e a conveniência não é tão importante, use valarrays. Caso contrário, os vetores são muito mais convenientes.

valarrayé uma espécie de órfão que nasceu no lugar errado na hora errada. É uma tentativa de otimização, especificamente para as máquinas que foram usadas para matemática pesada quando foi escrita - especificamente, processadores vetoriais como o Crays.

Para um processador vetorial, o que você geralmente queria era aplicar uma única operação a uma matriz inteira, depois aplicar a próxima operação a toda a matriz, e assim por diante até que você fizesse tudo o que precisava fazer.

A menos que você esteja lidando com matrizes razoavelmente pequenas, isso tende a funcionar mal com o cache. Na maioria das máquinas modernas, o que você geralmente preferiria (na medida do possível) seria carregar parte da matriz, realizar todas as operações necessárias e depois passar para a próxima parte da matriz.

valarraytambém deve eliminar qualquer possibilidade de serrilhado, o que (pelo menos teoricamente) permite que o compilador melhore a velocidade porque é mais livre para armazenar valores nos registros. Na realidade, no entanto, não tenho certeza de que qualquer implementação real tire vantagem disso em grau significativo. Suspeito que seja um problema do tipo galinha e ovo - sem o suporte do compilador, ele não se tornou popular e, desde que não seja popular, ninguém se dará ao trabalho de trabalhar no compilador para apoiá-lo.

Há também uma variedade desconcertante (literalmente) de classes auxiliares para usar com o valarray. Você começa slice, slice_array, gslicee gslice_arraypara jogar com peças de um valarray, e torná-lo agir como um array multi-dimensional. Você também mask_arraypode "mascarar" uma operação (por exemplo, adicionar itens em x para y, mas apenas nas posições em que z é diferente de zero). Para fazer uso mais do que trivial devalarray , você precisa aprender muito sobre essas classes auxiliares, algumas das quais bastante complexas e nenhuma das quais parece (pelo menos para mim) muito bem documentada.

Conclusão: embora tenha momentos de brilho e possa fazer algumas coisas com muito bom gosto, também existem algumas boas razões para que seja (e quase certamente permanecerá) obscuro.

Editar (oito anos depois, em 2017): algumas das anteriores se tornaram obsoletas em pelo menos algum grau. Por um exemplo, a Intel implementou uma versão otimizada do valarray para seu compilador. Ele usa as primitivas de desempenho integrado da Intel (Intel IPP) para melhorar o desempenho. Embora a melhoria exata de desempenho indubitavelmente varie, um teste rápido com código simples mostra uma melhoria de velocidade de 2: 1 em comparação com código idêntico compilado com a implementação "padrão" de valarray.

Portanto, embora eu não esteja totalmente convencido de que os programadores de C ++ estejam começando a usar valarrayem grandes números, há pelo menos algumas circunstâncias em que ele pode fornecer uma melhoria na velocidade.

Durante a padronização do C ++ 98, o valarray foi projetado para permitir algum tipo de computação matemática rápida. No entanto, nessa época, Todd Veldhuizen inventou modelos de expressão e criou o blitz ++ , e técnicas similares de meta-modelo foram inventadas, o que tornava os valarrays praticamente obsoletos antes do lançamento do padrão. O IIRC, o (s) proponente (s) original (ais) do valarray, abandonou-o a meio caminho da padronização, o que (se verdadeiro) também não ajudou.

ISTR de que o principal motivo pelo qual não foi removido do padrão é que ninguém teve tempo para avaliar o problema completamente e escrever uma proposta para removê-lo.

Lembre-se, no entanto, de que tudo isso é vagamente lembrado. Tome isso com um grão de sal e espero que alguém corrija ou confirme isso.

Eu sei que os valarrays têm um pouco de açúcar sintático

Eu tenho que dizer que acho que não std::valarraystem muito açúcar sintático. A sintaxe é diferente, mas eu não chamaria a diferença de "açúcar". A API é estranha. A seção std::valarrays na linguagem de programação C ++ menciona essa API incomum e o fato de que, desdestd::valarray se espera que seja altamente otimizado, todas as mensagens de erro que você recebe ao usá-las provavelmente não serão intuitivas.

Por curiosidade, cerca de um ano atrás eu opus std::valarraycontra std::vector. Não tenho mais o código ou os resultados precisos (embora não deva ser difícil escrever o seu próprio). Usando GCC I fez ficar um pouco benefício de desempenho quando se utiliza std::valarraypara a matemática simples, mas não para os meus implementações para calcular o desvio padrão (e, claro, o desvio padrão não é tão complexo, na medida em matemática vai). Eu suspeito que as operações em cada item em uma grande std::vectorpeça melhor com caches do que as operações em std::valarrays. ( NOTA , seguindo os conselhos de musiphil , eu consegui um desempenho quase idêntico de vectore valarray).

No final, decidi usar std::vectorprestando muita atenção a coisas como alocação de memória e criação temporária de objetos.

Ambos std::vectore std::valarrayarmazenam os dados em um bloco contíguo. No entanto, eles acessam esses dados usando padrões diferentes e, mais importante, a API std::valarrayincentiva diferentes padrões de acesso que a API std::vector.

Para o exemplo de desvio padrão, em uma etapa específica, eu precisava encontrar a média da coleção e a diferença entre o valor de cada elemento e a média.

Para o std::valarray, eu fiz algo como:

std::valarray<double> original_values = ... // obviously I put something here
double mean = original_values.sum() / original_values.size();
std::valarray<double> temp(mean, original_values.size());
std::valarray<double> differences_from_mean = original_values - temp;

Eu posso ter sido mais inteligente com std::sliceou std::gslice. Já faz mais de cinco anos.

Pois std::vector, eu fiz algo como:

std::vector<double> original_values = ... // obviously, I put something here
double mean = std::accumulate(original_values.begin(), original_values.end(), 0.0) / original_values.size();

std::vector<double> differences_from_mean;
differences_from_mean.reserve(original_values.size());
std::transform(original_values.begin(), original_values.end(), std::back_inserter(differences_from_mean), std::bind1st(std::minus<double>(), mean));

Hoje certamente escreveria isso de maneira diferente. Se nada mais, eu aproveitaria o C ++ 11 lambdas.

É óbvio que esses dois trechos de código fazem coisas diferentes. Por um lado, o std::vectorexemplo não cria uma coleção intermediária como o std::valarrayexemplo. No entanto, acho justo compará-los porque as diferenças estão ligadas às diferenças entre std::vectore std::valarray.

Quando escrevi esta resposta, suspeitei que subtrair o valor dos elementos de dois std::valarrays (última linha no std::valarrayexemplo) seria menos compatível com o cache do que a linha correspondente no std::vectorexemplo (que também é a última linha).

Acontece, no entanto, que

std::valarray<double> original_values = ... // obviously I put something here
double mean = original_values.sum() / original_values.size();
std::valarray<double> differences_from_mean = original_values - mean;

Faz a mesma coisa que o std::vectorexemplo e tem desempenho quase idêntico. No final, a questão é qual API você prefere.

O valarray deveria permitir que algumas vantagens do processamento de vetor FORTRAN fossem reproduzidas no C ++. De alguma forma, o suporte necessário ao compilador nunca realmente aconteceu.

Os livros de Josuttis contêm alguns comentários interessantes (um tanto depreciativos) sobre o valarray ( aqui e aqui ).

No entanto, a Intel agora parece revisitar o valarray em seus recentes lançamentos de compiladores (por exemplo, veja o slide 9 ); esse é um desenvolvimento interessante, uma vez que o conjunto de instruções SIMD SSE de quatro vias está prestes a ser acompanhado pelas instruções AVX de 8 e Larrabee de 16 vias e, no interesse da portabilidade, provavelmente será muito melhor codificar com uma abstração como valarray do que (digamos) intrínsecos.

Eu encontrei um bom uso para valarray. É usar valarray como matrizes numpy.

auto x = linspace(0, 2 * 3.14, 100);
plot(x, sin(x) + sin(3.f * x) / 3.f + sin(5.f * x) / 5.f);

Podemos implementar acima com valarray.

valarray<float> linspace(float start, float stop, int size)
{
    valarray<float> v(size);
    for(int i=0; i<size; i++) v[i] = start + i * (stop-start)/size;
    return v;
}

std::valarray<float> arange(float start, float step, float stop)
{
    int size = (stop - start) / step;
    valarray<float> v(size);
    for(int i=0; i<size; i++) v[i] = start + step * i;
    return v;
}

string psstm(string command)
{//return system call output as string
    string s;
    char tmp[1000];
    FILE* f = popen(command.c_str(), "r");
    while(fgets(tmp, sizeof(tmp), f)) s += tmp;
    pclose(f);
    return s;
}

string plot(const valarray<float>& x, const valarray<float>& y)
{
    int sz = x.size();
    assert(sz == y.size());
    int bytes = sz * sizeof(float) * 2;
    const char* name = "plot1";
    int shm_fd = shm_open(name, O_CREAT | O_RDWR, 0666);
    ftruncate(shm_fd, bytes);
    float* ptr = (float*)mmap(0, bytes, PROT_WRITE, MAP_SHARED, shm_fd, 0);
    for(int i=0; i<sz; i++) {
        *ptr++ = x[i];
        *ptr++ = y[i];
    }

    string command = "python plot.py ";
    string s = psstm(command + to_string(sz));
    shm_unlink(name);
    return s;
}

Além disso, precisamos de script python.

import sys, posix_ipc, os, struct
import matplotlib.pyplot as plt

sz = int(sys.argv[1])
f = posix_ipc.SharedMemory("plot1")
x = [0] * sz
y = [0] * sz
for i in range(sz):
    x[i], y[i] = struct.unpack('ff', os.read(f.fd, 8))
os.close(f.fd)
plt.plot(x, y)
plt.show()

O padrão C ++ 11 diz:

As classes da matriz valarray são definidas como livres de certas formas de alias, permitindo assim que as operações nessas classes sejam otimizadas.

Veja C ++ 11 26.6.1-2.

Com std::valarrayvocê pode usar a notação matemática padrão como v1 = a*v2 + v3fora da caixa. Isso não é possível com vetores, a menos que você defina seus próprios operadores.

std :: valarray destina-se a tarefas numéricas pesadas, como Dinâmica de Fluidos Computacional ou Dinâmica de Estrutura Computacional, nas quais você possui matrizes com milhões, às vezes dezenas de milhões de itens, e você as itera em um loop com também milhões de timestaps. Talvez hoje o std :: vector tenha um desempenho comparável, mas, há 15 anos, o valarray era quase obrigatório se você quisesse escrever um solucionador numérico eficiente.