C ++ valarray vs. vetor

159

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?

rlbond
fonte
2
Só estava pensando isso no outro dia também. Até onde eu sei, é realmente apenas um vetor matemático especializado.
GManNickG 21/10/09
O valarray não cria modelos de expressão?
quer
O físico Ulrich mütze fornece um caso de uso para valarray aqui e aqui
lifebalance

Respostas:

70

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.

Tim Allman
fonte
11
Eles não foram projetados para evitar ponteiros. C ++ 11 define começar () e final () em que valarray iterators voltar a elas
Mohamed El-Nakib
3
@ user2023370: É por isso que muitos usuários preferem Fortran Fortran 77. :)
Michael
152

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.

Jerry Coffin
fonte
1
É especificamente proibido armazenar tipos de objetos arbitrários dentro do valarray?
user541686
6
@ Mehrdad: Sim - há uma lista (bastante longa) de restrições em [Numeric.Requirements]. Para apenas alguns exemplos, todas as classes abstratas e exceções são proibidas. Também requer equivalência entre (por exemplo) a construção da cópia e uma sequência de construção padrão seguida pela atribuição.
Jerry Coffin
@JerryCoffin sheesh que é assustador. nós prometemos que não vamos usá-lo.
Hani Goc
4
Eu não decidiria isso com base no medo. Decidiria com base na necessidade de armazenar elementos que usem recursos proibidos.
Jerry Coffin
3
@annoying_squid: Se você tiver informações mais específicas e (você acredita) precisas para adicionar, sinta-se à vontade para adicionar uma resposta. Como está agora, seu comentário não parece adicionar nenhuma informação útil.
Jerry Coffin
39

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.

sbi
fonte
modelos de expressão também podem ser creditados a Vandevoorde, certo?
Nikos Athanasiou
@ Nikos: Não que eu saiba. Eu posso estar errado, no entanto. O que você tem a favor dessa leitura?
Sb
1
Como é mencionado no livro "Modelos C ++ - O guia completo", acho que geralmente é aceito que os dois os inventaram independentemente .
Nikos Athanasiou
27

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.

Max Lybbert
fonte
Não consigo pensar em nenhuma razão pela qual a std::vectorjogaria melhor com caches do que a std::valarray; ambos alocam um único bloco contíguo de memória para seus elementos.
Musiphil 27/03
1
@musiphil Minha resposta foi longa demais para um comentário, por isso atualizei a resposta.
Max Lybbert
1
Para o seu valarrayexemplo acima, você não precisou construir um temp valarrayobjeto, mas poderia ter feito isso std::valarray<double> differences_from_mean = original_values - mean;, e o comportamento do cache deve ser semelhante ao do vectorexemplo. (A propósito, se meané realmente int, não double, você pode precisar static_cast<double>(mean).)
musiphil
Obrigado pela sugestão de limpar o arquivo valarray. Vou precisar ver se isso melhora o desempenho. Quanto a meanser int: isso foi um erro. Originalmente, escrevi o exemplo usando ints e, em seguida, percebi que o valor meanestaria muito longe da média real por causa do truncamento. Mas perdi algumas alterações necessárias na minha primeira rodada de edições.
Max Lybbert
@musiphil Você está certo; essa alteração levou o código de exemplo a um desempenho quase idêntico.
Max Lybbert
23

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.

timday
fonte
16

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

insira a descrição da imagem aqui

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()
Zeta
fonte
2
Eu tinha literalmente exatamente os mesmos pensamentos que você quando descobri sobre o valarray hoje no trabalho. Penso que a partir de agora, para problemas de processamento de matemática em c ++, usarei o valarray, pois o código parece muito mais fácil de entender do ponto de vista matemático.
Zachary Kraus
8

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.

Lingxi
fonte
Como presumo que o Padrão define quais formulários, você pode citá-los? Além disso, eles são implementados usando truques de codificação ou são exceções baseadas em compilador para regras de alias em outras partes do idioma?
underscore_d
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.

Paul Jurczak
fonte
0

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.

mrpivello
fonte