O std :: vector é muito mais lento que as matrizes simples?

212

Eu sempre pensei que é a sabedoria geral que std::vectoré "implementada como uma matriz", blá blá blá. Hoje desci e testei, e parece não ser assim:

Aqui estão alguns resultados dos testes:

UseArray completed in 2.619 seconds
UseVector completed in 9.284 seconds
UseVectorPushBack completed in 14.669 seconds
The whole thing completed in 26.591 seconds

Isso é cerca de 3 a 4 vezes mais lento! Realmente não justifica os comentários " vectorpode ser mais lento para alguns nanossegundos".

E o código que eu usei:

#include <cstdlib>
#include <vector>

#include <iostream>
#include <string>

#include <boost/date_time/posix_time/ptime.hpp>
#include <boost/date_time/microsec_time_clock.hpp>

class TestTimer
{
    public:
        TestTimer(const std::string & name) : name(name),
            start(boost::date_time::microsec_clock<boost::posix_time::ptime>::local_time())
        {
        }

        ~TestTimer()
        {
            using namespace std;
            using namespace boost;

            posix_time::ptime now(date_time::microsec_clock<posix_time::ptime>::local_time());
            posix_time::time_duration d = now - start;

            cout << name << " completed in " << d.total_milliseconds() / 1000.0 <<
                " seconds" << endl;
        }

    private:
        std::string name;
        boost::posix_time::ptime start;
};

struct Pixel
{
    Pixel()
    {
    }

    Pixel(unsigned char r, unsigned char g, unsigned char b) : r(r), g(g), b(b)
    {
    }

    unsigned char r, g, b;
};

void UseVector()
{
    TestTimer t("UseVector");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels;
        pixels.resize(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

void UseVectorPushBack()
{
    TestTimer t("UseVectorPushBack");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels;
            pixels.reserve(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
            pixels.push_back(Pixel(255, 0, 0));
    }
}

void UseArray()
{
    TestTimer t("UseArray");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        Pixel * pixels = (Pixel *)malloc(sizeof(Pixel) * dimension * dimension);

        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }

        free(pixels);
    }
}

int main()
{
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();
    UseVectorPushBack();

    return 0;
}

Estou fazendo errado ou algo assim? Ou acabei de quebrar esse mito da performance?

Estou usando o modo Release no Visual Studio 2005 .


No Visual C ++ , #define _SECURE_SCL 0reduz UseVectorpela metade (diminuindo para 4 segundos). Isso é realmente enorme, IMO.

kizzx2
fonte
23
Algumas versões do vetor quando você está no modo de depuração adicionam instruções extras para verificar se você não acessa além do final da matriz e coisas assim. Para obter tempos reais, você deve criar no modo de liberação e ativar as otimizações.
Martin York
40
É bom que você tenha avaliado em vez de acreditar nas alegações que ouviu na Internet.
usar o seguinte comando
51
vetor é implementado como uma matriz. Isso não é "sabedoria convencional", é a verdade. Você descobriu que vectoré uma matriz redimensionável de uso geral. Parabéns. Como em todas as ferramentas de uso geral, é possível criar situações especializadas em que isso é subótimo. É por isso que a sabedoria convencional é começar com vectorae considerar alternativas, se necessário.
Dennis Zickefoose
37
lol, qual é a diferença de velocidade de "jogar louça suja em uma pia" e "jogar louça suja em uma pia e verificar se não quebraram"?
precisa
9
Pelo menos no VC2010, parece que a principal diferença é que malloc () é mais rápido que redimensionar (). Remova a alocação de memória do tempo, compile com _ITERATOR_DEBUG_LEVEL == 0 e os resultados são os mesmos.
Andreas Magnusson

Respostas:

260

Usando o seguinte:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseArray concluído em
2,196 segundos UseVector concluído em 4,412 segundos
UseVectorPushBack concluído em 8,017 segundos
A coisa toda foi concluída em 14,626 segundos

Portanto, o array é duas vezes mais rápido que o vetor.

Mas, depois de analisar o código com mais detalhes, isso é esperado; conforme você percorre o vetor duas vezes e a matriz apenas uma vez. Nota: quando você resize()vector, você não está apenas alocando a memória, mas também executando o vetor e chamando o construtor em cada membro.

Reorganizando o código levemente para que o vetor inicialize apenas cada objeto uma vez:

 std::vector<Pixel>  pixels(dimensions * dimensions, Pixel(255,0,0));

Agora, fazendo o mesmo tempo novamente:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseVector concluído em 2,216 segundos

O vetor agora apresenta desempenho apenas ligeiramente pior que o da matriz. Na OMI, essa diferença é insignificante e pode ser causada por várias coisas não associadas ao teste.

Eu também consideraria que você não está inicializando / destruindo corretamente o objeto Pixel no UseArrray()método, pois nem o construtor / destruidor é chamado (isso pode não ser um problema para essa classe simples, mas algo um pouco mais complexo (por exemplo, com ponteiros ou membros com ponteiros) causará problemas.

Loki Astari
fonte
48
@ kizzx2: Você precisa usar em reserve()vez de resize(). Isso aloca espaço para os objetos (ou seja, altera a capacidade do vetor), mas não cria os objetos (ou seja, o tamanho do vetor permanece inalterado).
James McNellis
25
Você está fazendo 1 000 000 000 acessos de matriz. A diferença horária é de 0.333 segundos. Ou uma diferença de 0.000000000333 por acesso à matriz. Supondo que um processador de 2,33 GHz como o meu esteja em 0,7 etapas do pipeline de instruções por acessos de array. Portanto, o vetor parece estar usando uma instrução extra por acesso.
Martin York
3
@ James McNellis: Você não pode simplesmente substituir resize()por reserve(), porque isso não ajusta a ideia interna do vetor de seu próprio tamanho; portanto, as gravações subsequentes em seus elementos são tecnicamente "gravadas além do fim" e produzirão UB. Embora, na prática, toda implementação de STL "se comporte" a esse respeito, como você ressincroniza o tamanho do vetor? Se você tentar chamar resize() depois de preencher o vetor, ele provavelmente substituirá todos esses elementos com valores construídos por padrão!
j_random_hacker
8
@j_random_hacker: Não foi exatamente isso que eu disse? Eu pensei que era muito claro que reserveapenas altera a capacidade de um vetor, não seu tamanho.
James McNellis
7
Ok, vai entender. Havia muitos problemas relacionados a exceções nos métodos vetoriais. A adição /EHscde opções de compilação limpava isso e assign()atualmente supera a matriz. Yay.
Pavel Minaev 08/09/10
55

Ótima pergunta. Eu vim aqui esperando encontrar alguma correção simples que agilizasse os testes de vetores. Isso não funcionou como eu esperava!

A otimização ajuda, mas não é suficiente. Com a otimização ativada, ainda vejo uma diferença de desempenho 2X entre o UseArray e o UseVector. Curiosamente, o UseVector foi significativamente mais lento que o UseVectorPushBack sem otimização.

# g++ -Wall -Wextra -pedantic -o vector vector.cpp
# ./vector
UseArray completed in 20.68 seconds
UseVector completed in 120.509 seconds
UseVectorPushBack completed in 37.654 seconds
The whole thing completed in 178.845 seconds
# g++ -Wall -Wextra -pedantic -O3 -o vector vector.cpp
# ./vector
UseArray completed in 3.09 seconds
UseVector completed in 6.09 seconds
UseVectorPushBack completed in 9.847 seconds
The whole thing completed in 19.028 seconds

Idéia # 1 - Use novo [] em vez de malloc

Tentei mudar malloc()para new[]no UseArray para que os objetos fossem construídos. E mudando da atribuição de campo individual para a atribuição de uma instância de Pixel. Ah, e renomear a variável de loop interno para j.

void UseArray()
{
    TestTimer t("UseArray");

    for(int i = 0; i < 1000; ++i)
    {   
        int dimension = 999;

        // Same speed as malloc().
        Pixel * pixels = new Pixel[dimension * dimension];

        for(int j = 0 ; j < dimension * dimension; ++j)
            pixels[j] = Pixel(255, 0, 0);

        delete[] pixels;
    }
}

Surpreendentemente (para mim), nenhuma dessas mudanças fez qualquer diferença. Nem mesmo a alteração na new[]qual o padrão será construído em todos os pixels. Parece que o gcc pode otimizar as chamadas de construtor padrão ao usar new[], mas não ao usar vector.

Idéia # 2 - Remover chamadas repetidas do operador []

Também tentei me livrar da operator[]pesquisa tripla e armazenar em cache a referência pixels[j]. Isso realmente desacelerou o UseVector! Opa

for(int j = 0; j < dimension * dimension; ++j)
{
    // Slower than accessing pixels[j] three times.
    Pixel &pixel = pixels[j];
    pixel.r = 255;
    pixel.g = 0;
    pixel.b = 0;
}

# ./vector 
UseArray completed in 3.226 seconds
UseVector completed in 7.54 seconds
UseVectorPushBack completed in 9.859 seconds
The whole thing completed in 20.626 seconds

Idéia # 3 - Remover construtores

Que tal remover completamente os construtores? Talvez o gcc possa otimizar a construção de todos os objetos quando os vetores são criados. O que acontece se mudarmos Pixel para:

struct Pixel
{
    unsigned char r, g, b;
};

Resultado: cerca de 10% mais rápido. Ainda mais lento que um array. Hum.

# ./vector 
UseArray completed in 3.239 seconds
UseVector completed in 5.567 seconds

Idéia # 4 - Use o iterador em vez do índice de loop

Que tal usar um vector<Pixel>::iteratoríndice em vez de um loop?

for (std::vector<Pixel>::iterator j = pixels.begin(); j != pixels.end(); ++j)
{
    j->r = 255;
    j->g = 0;
    j->b = 0;
}

Resultado:

# ./vector 
UseArray completed in 3.264 seconds
UseVector completed in 5.443 seconds

Não, não é diferente. Pelo menos não é mais lento. Eu pensei que isso teria desempenho semelhante ao # 2, onde eu usei uma Pixel&referência.

Conclusão

Mesmo que algum cookie inteligente descubra como fazer o loop de vetor tão rápido quanto o array, isso não fala bem do comportamento padrão de std::vector. O suficiente para o compilador ser inteligente o suficiente para otimizar todo o C ++ ness e tornar os contêineres STL tão rápidos quanto os arrays brutos.

O ponto principal é que o compilador não pode otimizar as chamadas de construtor padrão no-op ao usar std::vector. Se você usar simples, new[]ele os otimiza muito bem. Mas não com std::vector. Mesmo que você possa reescrever seu código para eliminar as chamadas do construtor que aparecem diante do mantra por aqui: "O compilador é mais inteligente que você. O STL é tão rápido quanto o normal C. Não se preocupe."

John Kugelman
fonte
2
Mais uma vez, obrigado por realmente executar o código. Às vezes, é fácil ser espancado sem motivos quando alguém tenta desafiar as opiniões populares.
precisa saber é o seguinte
3
"O suficiente para o compilador ser inteligente o suficiente para otimizar todo o C ++ e tornar os contêineres STL tão rápidos quanto os arrays brutos". Bons comentários. Eu tenho uma teoria de que esse "compilador é inteligente" é apenas um mito - a análise de C ++ é extremamente difícil e o compilador é apenas uma máquina.
kizzx2
3
Não sei. Claro, ele conseguiu retardar o teste de matriz, mas não acelerou o vetor. Editei acima, onde removi os construtores do Pixel e o tornei uma estrutura simples, e ainda era lenta. Isso é uma má notícia para quem usa tipos simples, como vector<int>.
John Kugelman
2
Eu gostaria de poder realmente votar sua resposta duas vezes. Idéias inteligentes para experimentar (mesmo que nenhuma realmente funcionou) nas quais eu nem conseguia pensar!
kizzx2
9
Só queria observar que a complexidade de analisar C ++ (que é incrivelmente complexo, sim) não tem nada a ver com a qualidade da otimização. O último geralmente ocorre em estágios em que o resultado da análise já é transformado várias vezes para uma representação de nível muito mais baixo.
Pavel Minaev
44

Esta é uma pergunta antiga, mas popular.

Neste ponto, muitos programadores estarão trabalhando no C ++ 11. E no C ++ 11, o código do OP, como escrito, é executado igualmente rápido para UseArrayou UseVector.

UseVector completed in 3.74482 seconds
UseArray completed in 3.70414 seconds

O problema fundamental era que, enquanto sua Pixelestrutura não foi inicializada, cria std::vector<T>::resize( size_t, T const&=T() )um padrão Pixele o copia . O compilador não percebeu que estava sendo solicitado a copiar dados não inicializados e, portanto, executou a cópia.

No C ++ 11, std::vector<T>::resizetem duas sobrecargas. O primeiro é std::vector<T>::resize(size_t), o outro é std::vector<T>::resize(size_t, T const&). Isso significa que quando você invoca resizesem um segundo argumento, ele simplesmente constrói o padrão, e o compilador é inteligente o suficiente para perceber que a construção padrão não faz nada, portanto ignora a passagem sobre o buffer.

(As duas sobrecargas foram adicionadas para lidar com tipos móveis, construtíveis e não copiáveis ​​- a melhoria de desempenho ao trabalhar com dados não inicializados é um bônus).

A push_backsolução também faz a verificação de vedação, o que a torna mais lenta, permanecendo mais lenta que a mallocversão.

exemplo ao vivo (também substituí o temporizador por chrono::high_resolution_clock).

Observe que, se você possui uma estrutura que geralmente requer inicialização, mas deseja manipulá-la após aumentar seu buffer, pode fazer isso com um std::vectoralocador personalizado . Se você quiser movê-lo para um estado mais normal std::vector, acredito que o uso cuidadoso allocator_traitse a substituição de ==podem fazer isso, mas não tenho certeza.

Yakk - Adam Nevraumont
fonte
Também seria interessante ver como emplace_backvs vs push_backaqui.
Daniel
1
Não consigo reproduzir seus resultados. Compilando seu código clang++ -std=c++11 -O3tem UseArray completed in 2.02e-07 secondse UseVector completed in 1.3026 seconds. Eu também adicionei uma UseVectorEmplaceBackversão que é de aprox. 2,5x mais rápido que UseVectorPushBack.
Daniel
1
As probabilidades do @daniel são que o otimizador removeu tudo da versão do array. Sempre um risco com micro benchmarks.
Yakk - Adam Nevraumont 30/08/2015
4
sim, você está certo, apenas olhou para a montagem (ou falta dela). Deveria provavelmente ter pensado nisso, dada a diferença ~ 6448514x! Eu me pergunto por que a versão vetorial não pode fazer a mesma otimização. Isso é feito se construído com as dimensões e não redimensionado.
Daniel
34

Para ser justo, você não pode comparar uma implementação C ++ com uma implementação C, como eu chamaria sua versão malloc. O malloc não cria objetos - apenas aloca memória não processada. O fato de você tratar essa memória como objetos sem chamar o construtor é um C ++ ruim (possivelmente inválido - deixarei isso para os advogados de linguagem).

Dito isso, simplesmente alterar o malloc para new Pixel[dimensions*dimensions]e free to delete [] pixelsnão faz muita diferença com a implementação simples do Pixel que você possui. Aqui estão os resultados na minha caixa (E6600, 64 bits):

UseArray completed in 0.269 seconds
UseVector completed in 1.665 seconds
UseVectorPushBack completed in 7.309 seconds
The whole thing completed in 9.244 seconds

Mas com uma ligeira mudança, as mesas viram:

Pixel.h

struct Pixel
{
    Pixel();
    Pixel(unsigned char r, unsigned char g, unsigned char b);

    unsigned char r, g, b;
};

Pixel.cc

#include "Pixel.h"

Pixel::Pixel() {}
Pixel::Pixel(unsigned char r, unsigned char g, unsigned char b) 
  : r(r), g(g), b(b) {}

main.cc

#include "Pixel.h"
[rest of test harness without class Pixel]
[UseArray now uses new/delete not malloc/free]

Compilado desta maneira:

$ g++ -O3 -c -o Pixel.o Pixel.cc
$ g++ -O3 -c -o main.o main.cc
$ g++ -o main main.o Pixel.o

obtemos resultados muito diferentes:

UseArray completed in 2.78 seconds
UseVector completed in 1.651 seconds
UseVectorPushBack completed in 7.826 seconds
The whole thing completed in 12.258 seconds

Com um construtor não embutido para Pixel, std :: vector agora supera uma matriz bruta.

Parece que a complexidade da alocação por meio de std :: vector e std: alocador é demais para ser otimizada de maneira tão eficaz quanto simples new Pixel[n]. No entanto, podemos ver que o problema está simplesmente na alocação e não no acesso ao vetor, ajustando algumas das funções de teste para criar o vetor / matriz uma vez movendo-o para fora do loop:

void UseVector()
{
    TestTimer t("UseVector");

    int dimension = 999;
    std::vector<Pixel> pixels;
    pixels.resize(dimension * dimension);

    for(int i = 0; i < 1000; ++i)
    {
        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

e

void UseArray()
{
    TestTimer t("UseArray");

    int dimension = 999;
    Pixel * pixels = new Pixel[dimension * dimension];

    for(int i = 0; i < 1000; ++i)
    {
        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
    delete [] pixels;
}

Agora obtemos esses resultados:

UseArray completed in 0.254 seconds
UseVector completed in 0.249 seconds
UseVectorPushBack completed in 7.298 seconds
The whole thing completed in 7.802 seconds

O que podemos aprender com isso é que std :: vector é comparável a uma matriz bruta de acesso, mas se você precisar criar e excluir o vetor / matriz muitas vezes, a criação de um objeto complexo consumirá mais tempo do que a criação de uma matriz simples quando o construtor do elemento não estiver embutido. Não acho que isso seja muito surpreendente.

camh
fonte
3
Você ainda tem um construtor embutido - o construtor de cópia.
Ben Voigt
26

Tente com isto:

void UseVectorCtor()
{
    TestTimer t("UseConstructor");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels(dimension * dimension, Pixel(255, 0, 0));
    }
}

Eu tenho quase exatamente o mesmo desempenho que com o array.

A questão vectoré que é uma ferramenta muito mais geral do que uma matriz. E isso significa que você deve considerar como usá-lo. Ele pode ser usado de várias maneiras diferentes, fornecendo funcionalidades que nem mesmo uma matriz possui. E se você usá-lo "errado" para o seu objetivo, gera muita sobrecarga, mas se usá-lo corretamente, geralmente é basicamente uma estrutura de dados com zero sobrecarga. Nesse caso, o problema é que você inicializou o vetor separadamente (fazendo com que todos os elementos tivessem seu nome padrão chamado) e, em seguida, substituiu cada elemento individualmente com o valor correto. Isso é muito mais difícil para o compilador otimizar o processo do que quando você faz a mesma coisa com uma matriz. É por isso que o vetor fornece um construtor que permite fazer exatamente isso:NX.

E quando você usa isso, o vetor é tão rápido quanto uma matriz.

Então não, você não quebrou o mito da performance. Mas você mostrou que isso só é verdade se você usar o vetor de maneira ideal, o que também é um bom argumento. :)

Pelo lado positivo, é realmente o uso mais simples que acaba sendo o mais rápido. Se você contrastar meu snippet de código (uma única linha) com a resposta de John Kugelman, contendo montes e montes de ajustes e otimizações, que ainda não eliminam completamente a diferença de desempenho, é bem claro que, apesar de tudo, vectoré muito inteligente. Você não precisa pular aros para obter velocidade igual a uma matriz. Pelo contrário, você deve usar a solução mais simples possível.

jalf
fonte
1
Ainda questiono se essa é uma comparação justa. Se você estiver se livrando do loop interno, o equivalente da matriz seria construir um único objeto Pixel e depois misturar isso em toda a matriz.
John Kugelman
1
O uso new[]executa as mesmas construções padrão que o vector.resize()faz, mas é muito mais rápido. new[]+ loop interno deve ter a mesma velocidade que vector.resize()+ loop interno, mas não é, é quase o dobro da velocidade.
John Kugelman
@ John: É uma comparação justa. No código original, a matriz é alocada com a mallocqual não inicializa ou constrói nada; portanto, é efetivamente um algoritmo de passagem única, como o meu vectorexemplo. E new[]a resposta é obviamente que ambas exigem duas passagens, mas, no new[]caso, o compilador é capaz de otimizar essa sobrecarga adicional, o que não ocorre no vectorcaso. Mas não vejo por que é interessante o que acontece em casos abaixo do ideal. Se você se preocupa com o desempenho, não escreve código assim.
jalf
@ John: Comentário interessante. Se eu quisesse citar toda a matriz, acho que a matriz é novamente a solução ideal - já que não posso dizer vector::resize()para me fornecer um pedaço contingente de memória sem perder tempo chamando construtores inúteis.
Kizzx2 12/09/10
@ kizzx2: sim e não. Uma matriz é normalmente inicializada também em C ++. Em C, você usaria o mallocque não executa inicialização, mas que não funcionará em C ++ com tipos não POD. Portanto, no caso geral, uma matriz C ++ seria igualmente ruim. Talvez a questão seja: se você realizar esse cego com frequência, não reutilizará o mesmo vetor / matriz? E se você fizer isso, pagará apenas o custo dos "construtores inúteis" uma vez, logo no início. O blitting real é tão rápido, afinal.
jalf
22

Não foi uma comparação justa quando olhei seu código pela primeira vez; Eu definitivamente pensei que você não estava comparando maçãs com maçãs. Então pensei: vamos chamar construtores e destruidores em todos os testes; e depois compare.

const size_t dimension = 1000;

void UseArray() {
    TestTimer t("UseArray");
    for(size_t j = 0; j < dimension; ++j) {
        Pixel* pixels = new Pixel[dimension * dimension];
        for(size_t i = 0 ; i < dimension * dimension; ++i) {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = (unsigned char) (i % 255);
        }
        delete[] pixels;
    }
}

void UseVector() {
    TestTimer t("UseVector");
    for(size_t j = 0; j < dimension; ++j) {
        std::vector<Pixel> pixels(dimension * dimension);
        for(size_t i = 0; i < dimension * dimension; ++i) {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = (unsigned char) (i % 255);
        }
    }
}

int main() {
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();

    return 0;
}

Meu pensamento era que, com essa configuração, eles deveriam ser exatamente os mesmos. Acontece que eu estava errado.

UseArray completed in 3.06 seconds
UseVector completed in 4.087 seconds
The whole thing completed in 10.14 seconds

Então, por que essa perda de desempenho de 30% ocorreu? O STL possui tudo nos cabeçalhos, portanto, deveria ter sido possível para o compilador entender tudo o que era necessário.

Meu pensamento era que é como o loop inicializa todos os valores para o construtor padrão. Então eu fiz um teste:

class Tester {
public:
    static int count;
    static int count2;
    Tester() { count++; }
    Tester(const Tester&) { count2++; }
};
int Tester::count = 0;
int Tester::count2 = 0;

int main() {
    std::vector<Tester> myvec(300);
    printf("Default Constructed: %i\nCopy Constructed: %i\n", Tester::count, Tester::count2);

    return 0;
}

Os resultados foram como eu suspeitava:

Default Constructed: 1
Copy Constructed: 300

Essa é claramente a fonte da desaceleração, o fato de o vetor usar o construtor de cópia para inicializar os elementos de um objeto construído padrão.

Isso significa que a seguinte ordem de pseudo-operação está acontecendo durante a construção do vetor:

Pixel pixel;
for (auto i = 0; i < N; ++i) vector[i] = pixel;

Que, devido ao construtor de cópia implícita feito pelo compilador, é expandido para o seguinte:

Pixel pixel;
for (auto i = 0; i < N; ++i) {
    vector[i].r = pixel.r;
    vector[i].g = pixel.g;
    vector[i].b = pixel.b;
}

Assim, o padrão Pixelcontinua a ser inicializado-un, enquanto o resto são inicializados com o padrão Pixel's inicializado-un valores.

Em comparação com a situação alternativa com New[]/ Delete[]:

int main() {
    Tester* myvec = new Tester[300];

    printf("Default Constructed: %i\nCopy Constructed:%i\n", Tester::count, Tester::count2);

    delete[] myvec;

    return 0;
}

Default Constructed: 300
Copy Constructed: 0

Todos são deixados com seus valores não inicializados e sem a iteração dupla sobre a sequência.

Armado com esta informação, como podemos testá-la? Vamos tentar sobrescrever o construtor de cópias implícitas.

Pixel(const Pixel&) {}

E os resultados?

UseArray completed in 2.617 seconds
UseVector completed in 2.682 seconds
The whole thing completed in 5.301 seconds

Então, em resumo, se você estiver criando centenas de vetores com muita frequência: repense seu algoritmo .

Em qualquer caso, a implementação do STL não é mais lenta por algum motivo desconhecido, apenas faz exatamente o que você pede; esperando que você saiba melhor.

deceleratedcaviar
fonte
3
A julgar pela diversão que nós (você e eu e outras pessoas inteligentes aqui) tivemos, a "esperança" da implementação da STL é realmente bastante exigente: P Basicamente, podemos exagerar e concluir que ela espera ter lido e analisado toda a sua fonte código. Enfim: P
kizzx2 01/09/11
1
Awsome! No VS 2013, isso tornava o vetor mais rápido que as matrizes. Embora pareça que, para sistemas críticos de desempenho, você precise testar muito o STL para poder usá-lo com eficiência.
rozina
7

Tente desativar os iteradores verificados e criar no modo de liberação. Você não deve ver muita diferença de desempenho.

Kloffy
fonte
1
Tentei #define _SECURE_SCL 0. Isso fez UseVectoralgo em torno de 4 segundos (semelhante ao gccabaixo), mas ainda é duas vezes mais lento.
kizzx2 8/09/10
Esta é quase certamente a causa. Por padrão, a Microsoft nos oferece a depuração do iterador, por padrão, para depuração e versão. Descobrimos que essa é a causa raiz de uma grande desaceleração após a atualização de 2003 para 2008. Definitivamente, uma das armadilhas mais perniciosas do visual studio.
Doug T.
2
@ kizzx2 existe outra macro para desativar: HAS_ITERATOR_DEBUGGING ou algo parecido.
Doug T.
Como o @Martin e minhas respostas mostram, o gcc mostra o mesmo padrão, mesmo com a otimização em -O3.
John Kugelman
1
@ Doug: Olhando para o documento, acho que _HAS_ITERATOR_DEBUGGINGestá desabilitado na versão: msdn.microsoft.com/en-us/library/aa985939(VS.80).aspx
kizzx2
4

O STL do GNU (e outros), dado vector<T>(n), o padrão constrói um objeto prototípico T()- o compilador otimizará o construtor vazio - mas, em seguida, uma cópia do lixo que estiver nos endereços de memória agora reservados para o objeto é obtida pelos STLs __uninitialized_fill_n_aux, que loops que preenchem cópias desse objeto como os valores padrão no vetor. Portanto, "my" STL não está construindo um loop, mas construindo um loop / cópia. É contra-intuitivo, mas eu deveria ter lembrado quando comentei uma recente pergunta sobre o stackoverflow sobre esse ponto: a construção / cópia pode ser mais eficiente para objetos de referência contados etc.

Assim:

vector<T> x(n);

ou

vector<T> x;
x.resize(n);

é - em muitas implementações de STL - algo como:

T temp;
for (int i = 0; i < n; ++i)
    x[i] = temp;

O problema é que a geração atual de otimizadores de compilador não parece funcionar com a percepção de que temp é um lixo não inicializado e falha ao otimizar as invocações de loop e construtor de cópia padrão. Você pode argumentar com credibilidade que os compiladores absolutamente não devem otimizar isso, pois um programador que escrever o acima tem uma expectativa razoável de que todos os objetos serão idênticos após o loop, mesmo que lixo (advertências comuns sobre 'idêntico' / operador == vs memcmp / operator = etc aplicável). Não se pode esperar que o compilador tenha uma visão extra do contexto maior de std :: vector <> ou o uso posterior dos dados que sugerem que essa otimização é segura.

Isso pode ser contrastado com a implementação direta mais óbvia:

for (int i = 0; i < n; ++i)
    x[i] = T();

O que podemos esperar que um compilador otimize.

Para ser um pouco mais explícito sobre a justificativa para esse aspecto do comportamento do vetor, considere:

std::vector<big_reference_counted_object> x(10000);

Claramente, é uma grande diferença se criarmos 10000 objetos independentes versus 10000 fazendo referência aos mesmos dados. Há um argumento razoável de que a vantagem de proteger usuários casuais de C ++ de fazer algo acidentalmente supera o custo muito pequeno do mundo real da construção de cópias difíceis de otimizar.

RESPOSTA ORIGINAL (para referência / interpretação dos comentários): Sem chance. o vetor é tão rápido quanto uma matriz, pelo menos se você reservar espaço sensatamente. ...

Tony Delroy
fonte
6
Realmente não posso justificar que essa resposta seja um pouco útil para alguém. Espero poder votar novamente duas vezes.
Kizzx2
-1, lá vai o meu suporte no kizzx2. o vetor nunca será tão rápido quanto o array, devido ao recurso adicional que ele fornece, regra do universo, tudo tem um preço!
YeenFei
Você está perdendo, Tony ... é um exemplo de uma referência artificial, mas prova o que ela pretende.
Potatoswatter
Rosas são verdes, violetas são alaranjadas, os votos negativos são amargos, mas a resposta lhes implora.
Pavel Minaev 08/09/10
3

A resposta de Martin York me incomoda porque parece uma tentativa de escovar o problema de inicialização debaixo do tapete. Mas ele tem razão em identificar a construção padrão redundante como a fonte de problemas de desempenho.

[EDIT: A resposta de Martin não sugere mais alterar o construtor padrão.]

Para o problema imediato em questão, você certamente poderia chamar a versão de 2 parâmetros do vector<Pixel>ctor:

std::vector<Pixel> pixels(dimension * dimension, Pixel(255, 0, 0));

Isso funciona se você deseja inicializar com um valor constante, que é um caso comum. Mas o problema mais geral é: como você pode inicializar eficientemente com algo mais complicado que um valor constante?

Para isso, você pode usar a back_insert_iterator, que é um adaptador iterador. Aqui está um exemplo com um vetor de ints, embora a ideia geral funcione igualmente bem para Pixels:

#include <iterator>
// Simple functor return a list of squares: 1, 4, 9, 16...
struct squares {
    squares() { i = 0; }
    int operator()() const { ++i; return i * i; }

private:
    int i;
};

...

std::vector<int> v;
v.reserve(someSize);     // To make insertions efficient
std::generate_n(std::back_inserter(v), someSize, squares());

Como alternativa, você pode usar copy()ou em transform()vez de generate_n().

A desvantagem é que a lógica para construir os valores iniciais precisa ser movida para uma classe separada, o que é menos conveniente do que tê-lo no lugar (embora as lambdas em C ++ 1x tornem isso muito melhor). Também espero que isso ainda não seja tão rápido quanto uma malloc()versão não-STL baseada em, mas espero que seja próxima, pois ele faz apenas uma construção para cada elemento.

j_random_hacker
fonte
2

Os vetores também estão chamando construtores de Pixel.

Cada um deles está causando quase um milhão de execuções de ctor que você está cronometrando.

edit: então há o loop externo 1 ... 1000, então faça com que um bilhão de ctor ligue!

edit 2: seria interessante ver a desmontagem do caso UseArray. Um otimizador pode otimizar tudo, já que não tem outro efeito senão queimar a CPU.

Graham Perks
fonte
Você está certo, mas a pergunta é: como essas chamadas inúteis de controlador podem ser desativadas? É fácil para a abordagem não STL, mas difícil / feio para a maneira STL.
Jrandom_hacker
1

Veja como o push_backmétodo no vetor funciona:

  1. O vetor aloca uma quantidade X de espaço quando é inicializado.
  2. Conforme indicado abaixo, ele verifica se há espaço na matriz subjacente atual para o item.
  3. Faz uma cópia do item na chamada push_back.

Depois de chamar os push_backitens X:

  1. O vetor realoca a quantidade de espaço kX em uma segunda matriz.
  2. Ele copia as entradas da primeira matriz para a segunda.
  3. Descarta a primeira matriz.
  4. Agora usa a segunda matriz como armazenamento até atingir as entradas do kX.

Repetir. Se você não está no reservingespaço, definitivamente será mais lento. Mais do que isso, se for caro copiar o item, então 'push_back' assim o comerá vivo.

Quanto à vectorcoisa versus matriz, vou ter que concordar com as outras pessoas. Execute a liberação, ative as otimizações e coloque mais algumas bandeiras para que as pessoas amigáveis ​​da Microsoft não # #% $ ^ façam isso por você.

Mais uma coisa, se você não precisar redimensionar, use o Boost.Array.

wheaties
fonte
Entendo que as pessoas não gostam de ler um monte de código quando é postado literalmente. Mas eu usei reservecomo deveria.
Kizzx2 08/09/10
Desculpe, eu perdi. Nada mais que eu coloquei lá foi útil?
wheaties
push_backamortizou o tempo constante. Parece que você está descrevendo um processo O (N). (As etapas 1 e 3 parecem completamente deslocadas.) O que torna push_backlento o OP é a verificação do intervalo para verificar se a realocação precisa ocorrer, atualizando os ponteiros, a verificação contra o NULL no posicionamento interno newe outras pequenas coisas que normalmente são abafadas pelo o trabalho real do programa.
Potatoswatter
Vai ser mais lento, mesmo com reserveele ainda precisa fazer essa verificação (se é necessário realocar) em todos push_back.
Pavel Minaev 08/09/10
Todos os bons pontos. O que estou descrevendo soa como um processo O (N), mas não é, bem, não é bem assim. A maioria das pessoas que conheço não entende como uma vectorfuncionalidade é redimensionada, é apenas "mágica". Aqui, deixe-me esclarecer um pouco mais.
wheaties
1

Alguns dados do criador de perfil (o pixel está alinhado a 32 bits):

g++ -msse3 -O3 -ftree-vectorize -g test.cpp -DNDEBUG && ./a.out
UseVector completed in 3.123 seconds
UseArray completed in 1.847 seconds
UseVectorPushBack completed in 9.186 seconds
The whole thing completed in 14.159 seconds

Blah

andrey@nv:~$ opannotate --source libcchem/src/a.out  | grep "Total samples for file" -A3
Overflow stats not available
 * Total samples for file : "/usr/include/c++/4.4/ext/new_allocator.h"
 *
 * 141008 52.5367
 */
--
 * Total samples for file : "/home/andrey/libcchem/src/test.cpp"
 *
 *  61556 22.9345
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_vector.h"
 *
 *  41956 15.6320
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_uninitialized.h"
 *
 *  20956  7.8078
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_construct.h"
 *
 *   2923  1.0891
 */

Em allocator:

               :      // _GLIBCXX_RESOLVE_LIB_DEFECTS
               :      // 402. wrong new expression in [some_] allocator::construct
               :      void
               :      construct(pointer __p, const _Tp& __val)
141008 52.5367 :      { ::new((void *)__p) _Tp(__val); }

vector:

               :void UseVector()
               :{ /* UseVector() total:  60121 22.3999 */
...
               :
               :
 10790  4.0201 :        for (int i = 0; i < dimension * dimension; ++i) {
               :
   495  0.1844 :            pixels[i].r = 255;
               :
 12618  4.7012 :            pixels[i].g = 0;
               :
  2253  0.8394 :            pixels[i].b = 0;
               :
               :        }

matriz

               :void UseArray()
               :{ /* UseArray() total:  35191 13.1114 */
               :
...
               :
   136  0.0507 :        for (int i = 0; i < dimension * dimension; ++i) {
               :
  9897  3.6874 :            pixels[i].r = 255;
               :
  3511  1.3081 :            pixels[i].g = 0;
               :
 21647  8.0652 :            pixels[i].b = 0;

A maior parte da sobrecarga está no construtor de cópias. Por exemplo,

    std::vector < Pixel > pixels;//(dimension * dimension, Pixel());

    pixels.reserve(dimension * dimension);

    for (int i = 0; i < dimension * dimension; ++i) {

        pixels[i].r = 255;

        pixels[i].g = 0;

        pixels[i].b = 0;
    }

Tem o mesmo desempenho que uma matriz.

Anycorn
fonte
2
Infelizmente, após a "solução" que você deu, pixels.size()será quebrada.
precisa saber é o seguinte
1
isso é errado, você não pode chamar de reserva e, em seguida, usar os elementos, você ainda deve usar push_back para adicionar itens
paulm
1

Meu laptop é o Lenova G770 (4 GB de RAM).

O sistema operacional é o Windows 7 de 64 bits (aquele com laptop)

O compilador é o MinGW 4.6.1.

O IDE é Code :: Blocks .

Eu testo os códigos-fonte do primeiro post.

Os resultados

Otimização de O2

UseArray concluído em 2,841 segundos

UseVector concluído em 2.548 segundos

UseVectorPushBack concluído em 11,95 segundos

A coisa toda concluída em 17,342 segundos

pausa no sistema

Otimização de O3

UseArray concluído em 1.452 segundos

UseVector concluído em 2.514 segundos

UseVectorPushBack concluído em 12,967 segundos

A coisa toda concluída em 16.937 segundos

Parece que o desempenho do vetor é pior na otimização do O3.

Se você alterar o loop para

    pixels[i].r = i;
    pixels[i].g = i;
    pixels[i].b = i;

A velocidade da matriz e do vetor sob O2 e O3 é quase a mesma.

StereoMatching
fonte
Mesmo alterando malloc para new, no primeiro caso de teste em O3, o desempenho do vetor ainda é mais lento que o array.Mas quando você altera o valor atribuído de (255, 0, 0) para (i, i, i), o desempenho de vector e variedade são quase os mesmos, sob O2 e O3, é muito estranho
StereoMatching
Desculpe, esqueci-me de mudar livre para excluir.Depois de mudar livre para excluir, o desempenho no O3 do vetor e da matriz são os mesmos agora, parece que o alocador é o principal motivo?
StereoMatching
1

Uma referência melhor (eu acho ...), o compilador devido às otimizações pode alterar o código, porque os resultados dos vetores / matrizes alocados não são usados ​​em lugar algum. Resultados:

$ g++ test.cpp -o test -O3 -march=native
$ ./test 
UseArray inner completed in 0.652 seconds
UseArray completed in 0.773 seconds
UseVector inner completed in 0.638 seconds
UseVector completed in 0.757 seconds
UseVectorPushBack inner completed in 6.732 seconds
UseVectorPush completed in 6.856 seconds
The whole thing completed in 8.387 seconds

Compilador:

gcc version 6.2.0 20161019 (Debian 6.2.0-9)

CPU:

model name  : Intel(R) Core(TM) i7-3630QM CPU @ 2.40GHz

E o código:

#include <cstdlib>
#include <vector>

#include <iostream>
#include <string>

#include <boost/date_time/posix_time/ptime.hpp>
#include <boost/date_time/microsec_time_clock.hpp>

class TestTimer
{
    public:
        TestTimer(const std::string & name) : name(name),
            start(boost::date_time::microsec_clock<boost::posix_time::ptime>::local_time())
        {
        }

        ~TestTimer()
        {
            using namespace std;
            using namespace boost;

            posix_time::ptime now(date_time::microsec_clock<posix_time::ptime>::local_time());
            posix_time::time_duration d = now - start;

            cout << name << " completed in " << d.total_milliseconds() / 1000.0 <<
                " seconds" << endl;
        }

    private:
        std::string name;
        boost::posix_time::ptime start;
};

struct Pixel
{
    Pixel()
    {
    }

    Pixel(unsigned char r, unsigned char g, unsigned char b) : r(r), g(g), b(b)
    {
    }

    unsigned char r, g, b;
};

void UseVector(std::vector<std::vector<Pixel> >& results)
{
    TestTimer t("UseVector inner");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel>& pixels = results.at(i);
        pixels.resize(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

void UseVectorPushBack(std::vector<std::vector<Pixel> >& results)
{
    TestTimer t("UseVectorPushBack inner");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel>& pixels = results.at(i);
            pixels.reserve(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
            pixels.push_back(Pixel(255, 0, 0));
    }
}

void UseArray(Pixel** results)
{
    TestTimer t("UseArray inner");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        Pixel * pixels = (Pixel *)malloc(sizeof(Pixel) * dimension * dimension);

        results[i] = pixels;

        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }

        // free(pixels);
    }
}

void UseArray()
{
    TestTimer t("UseArray");
    Pixel** array = (Pixel**)malloc(sizeof(Pixel*)* 1000);
    UseArray(array);
    for(int i=0;i<1000;++i)
        free(array[i]);
    free(array);
}

void UseVector()
{
    TestTimer t("UseVector");
    {
        std::vector<std::vector<Pixel> > vector(1000, std::vector<Pixel>());
        UseVector(vector);
    }
}

void UseVectorPushBack()
{
    TestTimer t("UseVectorPush");
    {
        std::vector<std::vector<Pixel> > vector(1000, std::vector<Pixel>());
        UseVectorPushBack(vector);
    }
}


int main()
{
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();
    UseVectorPushBack();

    return 0;
}
Michał Szczepaniak
fonte
1

Eu fiz alguns testes extensivos que eu queria por um tempo agora. Pode muito bem compartilhar isso.

Esta é a minha máquina de inicialização dupla i7-3770, 16 GB de RAM, x86_64, no Windows 8.1 e no Ubuntu 16.04. Mais informações e conclusões, comentários abaixo. Testou o MSVS 2017 e o g ++ (no Windows e no Linux).

Programa de teste

#include <iostream>
#include <chrono>
//#include <algorithm>
#include <array>
#include <locale>
#include <vector>
#include <queue>
#include <deque>

// Note: total size of array must not exceed 0x7fffffff B = 2,147,483,647B
//  which means that largest int array size is 536,870,911
// Also image size cannot be larger than 80,000,000B
constexpr int long g_size = 100000;
int g_A[g_size];


int main()
{
    std::locale loc("");
    std::cout.imbue(loc);
    constexpr int long size = 100000;  // largest array stack size

    // stack allocated c array
    std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
    int A[size];
    for (int i = 0; i < size; i++)
        A[i] = i;

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "c-style stack array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "c-style stack array size=" << sizeof(A) << "B\n\n";

    // global stack c array
    start = std::chrono::steady_clock::now();
    for (int i = 0; i < g_size; i++)
        g_A[i] = i;

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "global c-style stack array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "global c-style stack array size=" << sizeof(g_A) << "B\n\n";

    // raw c array heap array
    start = std::chrono::steady_clock::now();
    int* AA = new int[size];    // bad_alloc() if it goes higher than 1,000,000,000
    for (int i = 0; i < size; i++)
        AA[i] = i;

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "c-style heap array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "c-style heap array size=" << sizeof(AA) << "B\n\n";
    delete[] AA;

    // std::array<>
    start = std::chrono::steady_clock::now();
    std::array<int, size> AAA;
    for (int i = 0; i < size; i++)
        AAA[i] = i;
    //std::sort(AAA.begin(), AAA.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::array size=" << sizeof(AAA) << "B\n\n";

    // std::vector<>
    start = std::chrono::steady_clock::now();
    std::vector<int> v;
    for (int i = 0; i < size; i++)
        v.push_back(i);
    //std::sort(v.begin(), v.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::vector duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::vector size=" << v.size() * sizeof(v.back()) << "B\n\n";

    // std::deque<>
    start = std::chrono::steady_clock::now();
    std::deque<int> dq;
    for (int i = 0; i < size; i++)
        dq.push_back(i);
    //std::sort(dq.begin(), dq.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::deque duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::deque size=" << dq.size() * sizeof(dq.back()) << "B\n\n";

    // std::queue<>
    start = std::chrono::steady_clock::now();
    std::queue<int> q;
    for (int i = 0; i < size; i++)
        q.push(i);

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::queue duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::queue size=" << q.size() * sizeof(q.front()) << "B\n\n";
}

Resultados

//////////////////////////////////////////////////////////////////////////////////////////
// with MSVS 2017:
// >> cl /std:c++14 /Wall -O2 array_bench.cpp
//
// c-style stack array duration=0.15ms
// c-style stack array size=400,000B
//
// global c-style stack array duration=0.130ms
// global c-style stack array size=400,000B
//
// c-style heap array duration=0.90ms
// c-style heap array size=4B
//
// std::array duration=0.20ms
// std::array size=400,000B
//
// std::vector duration=0.544ms
// std::vector size=400,000B
//
// std::deque duration=1.375ms
// std::deque size=400,000B
//
// std::queue duration=1.491ms
// std::queue size=400,000B
//
//////////////////////////////////////////////////////////////////////////////////////////
//
// with g++ version:
//      - (tdm64-1) 5.1.0 on Windows
//      - (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609 on Ubuntu 16.04
// >> g++ -std=c++14 -Wall -march=native -O2 array_bench.cpp -o array_bench
//
// c-style stack array duration=0ms
// c-style stack array size=400,000B
//
// global c-style stack array duration=0.124ms
// global c-style stack array size=400,000B
//
// c-style heap array duration=0.648ms
// c-style heap array size=8B
//
// std::array duration=1ms
// std::array size=400,000B
//
// std::vector duration=0.402ms
// std::vector size=400,000B
//
// std::deque duration=0.234ms
// std::deque size=400,000B
//
// std::queue duration=0.304ms
// std::queue size=400,000
//
//////////////////////////////////////////////////////////////////////////////////////////

Notas

  • Montado por uma média de 10 execuções.
  • Inicialmente, também realizei testes std::sort()(você pode vê-lo comentado), mas os removi mais tarde porque não havia diferenças significativas.

Minhas conclusões e observações

  • observe como a matriz global de estilo c leva quase tanto tempo quanto a matriz heap de estilo c
  • Em todos os testes, notei uma estabilidade notável no std::array variações de tempo entre execuções consecutivas, enquanto outras, especialmente as estruturas std :: data, variaram bastante em comparação
  • A otimização da O3 não mostrou diferenças de tempo notáveis
  • A remoção da otimização no Windows cl (sem -O2) e no g ++ (Win / Linux não -O2, sem -march = nativo) aumenta o tempo SIGNIFICANTEMENTE. Particularmente para estruturas std :: data. Tempos gerais mais altos no MSVS do que no g ++, mas std::arraymatrizes no estilo c mais rapidamente no Windows sem otimização
  • O g ++ produz código mais rápido que o compilador da microsoft (aparentemente ele roda mais rápido, mesmo no Windows).

Veredito

Claro que isso é código para uma compilação otimizada. E já que a pergunta era sobrestd::vector sim, é sim! matrizes mais lentas do que simples (otimizadas / não otimizadas). Mas quando você está fazendo um benchmark, naturalmente deseja produzir código otimizado.

A estrela do show para mim foi std::array.

Nikos
fonte
0

Com as opções corretas, vetores e matrizes podem gerar asm idênticas . Nesses casos, é claro que eles têm a mesma velocidade, porque você obtém o mesmo arquivo executável de qualquer maneira.


fonte
1
Nesse caso, eles não parecem gerar o mesmo conjunto. Em particular, parece não haver maneira de suprimir a chamada para construtores usando vetores. Você pode consultar as respostas aqui para esse problema (é uma leitura longa, mas explica por que há uma diferença de desempenho em casos diferentes do caso de teste simples no link que você provou.) (Na verdade, parece haver uma maneira - - escrever um alocador de STL costume, como sugerido Pessoalmente, acho que é desnecessariamente mais trabalho do que usar malloc).
kizzx2
1
@ kizzx2: O fato de você ter que se esforçar tanto para usar objetos não-construídos é uma coisa boa, porque isso é um erro de 99% (posso estar subestimando muito) do tempo. Li as outras respostas e percebo que não lido com sua situação específica (não há necessidade, as outras respostas estão corretas), mas ainda queria fornecer a você este exemplo de como vetores e matrizes podem se comportar exatamente da mesma maneira.
@ Roger: isso é ótimo! Obrigado pelo link
kizzx2
0

A propósito, a desaceleração da visualização em classes usando vetor também ocorre com tipos padrão como int. Heres um código multithread:

#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <typeinfo>
#include <vector>
#include <pthread.h>
#include <sstream>
#include <fstream>
using namespace std;

//pthread_mutex_t map_mutex=PTHREAD_MUTEX_INITIALIZER;

long long num=500000000;
int procs=1;

struct iterate
{
    int id;
    int num;
    void * member;
    iterate(int a, int b, void *c) : id(a), num(b), member(c) {}
};

//fill out viterate and piterate
void * viterate(void * input)
{
    printf("am in viterate\n");
    iterate * info=static_cast<iterate *> (input);
    // reproduce member type
    vector<int> test= *static_cast<vector<int>*> (info->member);
    for (int i=info->id; i<test.size(); i+=info->num)
    {
        //printf("am in viterate loop\n");
        test[i];
    }
    pthread_exit(NULL);
}

void * piterate(void * input)
{
    printf("am in piterate\n");
    iterate * info=static_cast<iterate *> (input);;
    int * test=static_cast<int *> (info->member);
    for (int i=info->id; i<num; i+=info->num) {
        //printf("am in piterate loop\n");
        test[i];
    }
    pthread_exit(NULL);
}

int main()
{
    cout<<"producing vector of size "<<num<<endl;
    vector<int> vtest(num);
    cout<<"produced  a vector of size "<<vtest.size()<<endl;
    pthread_t thread[procs];

    iterate** it=new iterate*[procs];
    int ans;
    void *status;

    cout<<"begining to thread through the vector\n";
    for (int i=0; i<procs; i++) {
        it[i]=new iterate(i, procs, (void *) &vtest);
    //  ans=pthread_create(&thread[i],NULL,viterate, (void *) it[i]);
    }
    for (int i=0; i<procs; i++) {
        pthread_join(thread[i], &status);
    }
    cout<<"end of threading through the vector";
    //reuse the iterate structures

    cout<<"producing a pointer with size "<<num<<endl;
    int * pint=new int[num];
    cout<<"produced a pointer with size "<<num<<endl;

    cout<<"begining to thread through the pointer\n";
    for (int i=0; i<procs; i++) {
        it[i]->member=&pint;
        ans=pthread_create(&thread[i], NULL, piterate, (void*) it[i]);
    }
    for (int i=0; i<procs; i++) {
        pthread_join(thread[i], &status);
    }
    cout<<"end of threading through the pointer\n";

    //delete structure array for iterate
    for (int i=0; i<procs; i++) {
        delete it[i];
    }
    delete [] it;

    //delete pointer
    delete [] pint;

    cout<<"end of the program"<<endl;
    return 0;
}

O comportamento do código mostra que a instanciação do vetor é a parte mais longa do código. Depois de passar pelo gargalo da garrafa. O restante do código é executado extremamente rápido. Isso é verdade, não importa quantos threads você esteja executando.

A propósito, ignore o número absolutamente insano de inclusões. Eu tenho usado esse código para testar as coisas de um projeto, para que o número de inclusões continue crescendo.

Zachary Kraus
fonte
0

Eu só quero mencionar que vetor (e smart_ptr) é apenas uma fina camada adicionada em cima de matrizes brutas (e ponteiros brutos). E, na verdade, o tempo de acesso de um vetor na memória contínua é mais rápido que o array. O código a seguir mostra o resultado da inicialização e acesso ao vetor e matriz.

#include <boost/date_time/posix_time/posix_time.hpp>
#include <iostream>
#include <vector>
#define SIZE 20000
int main() {
    srand (time(NULL));
    vector<vector<int>> vector2d;
    vector2d.reserve(SIZE);
    int index(0);
    boost::posix_time::ptime start_total = boost::posix_time::microsec_clock::local_time();
    //  timer start - build + access
    for (int i = 0; i < SIZE; i++) {
        vector2d.push_back(vector<int>(SIZE));
    }
    boost::posix_time::ptime start_access = boost::posix_time::microsec_clock::local_time();
    //  timer start - access
    for (int i = 0; i < SIZE; i++) {
        index = rand()%SIZE;
        for (int j = 0; j < SIZE; j++) {

            vector2d[index][index]++;
        }
    }
    boost::posix_time::ptime end = boost::posix_time::microsec_clock::local_time();
    boost::posix_time::time_duration msdiff = end - start_total;
    cout << "Vector total time: " << msdiff.total_milliseconds() << "milliseconds.\n";
    msdiff = end - start_acess;
    cout << "Vector access time: " << msdiff.total_milliseconds() << "milliseconds.\n"; 


    int index(0);
    int** raw2d = nullptr;
    raw2d = new int*[SIZE];
    start_total = boost::posix_time::microsec_clock::local_time();
    //  timer start - build + access
    for (int i = 0; i < SIZE; i++) {
        raw2d[i] = new int[SIZE];
    }
    start_access = boost::posix_time::microsec_clock::local_time();
    //  timer start - access
    for (int i = 0; i < SIZE; i++) {
        index = rand()%SIZE;
        for (int j = 0; j < SIZE; j++) {

            raw2d[index][index]++;
        }
    }
    end = boost::posix_time::microsec_clock::local_time();
    msdiff = end - start_total;
    cout << "Array total time: " << msdiff.total_milliseconds() << "milliseconds.\n";
    msdiff = end - start_acess;
    cout << "Array access time: " << msdiff.total_milliseconds() << "milliseconds.\n"; 
    for (int i = 0; i < SIZE; i++) {
        delete [] raw2d[i];
    }
    return 0;
}

A saída é:

    Vector total time: 925milliseconds.
    Vector access time: 4milliseconds.
    Array total time: 30milliseconds.
    Array access time: 21milliseconds.

Portanto, a velocidade será quase a mesma se você a usar corretamente. (como outros mencionados usando reserve () ou redimensionar ()).

Charles Chow
fonte
0

Bem, porque vector :: resize () faz muito mais processamento do que alocação de memória simples (por malloc).

Tente colocar um ponto de interrupção no construtor de cópias (defina-o para que você possa interromper!) E o tempo de processamento adicional será gasto.

YeenFei
fonte
0

Devo dizer que não sou especialista em C ++. Mas, para adicionar alguns resultados de experimentos:

compile: gcc-6.2.0 / bin / g ++ -O3 -std = c ++ 14 vector.cpp

máquina:

Intel(R) Xeon(R) CPU E5-2690 v2 @ 3.00GHz 

OS:

2.6.32-642.13.1.el6.x86_64

Resultado:

UseArray completed in 0.167821 seconds
UseVector completed in 0.134402 seconds
UseConstructor completed in 0.134806 seconds
UseFillConstructor completed in 1.00279 seconds
UseVectorPushBack completed in 6.6887 seconds
The whole thing completed in 8.12888 seconds

Aqui, a única coisa que me parece estranha é o desempenho do "UseFillConstructor" em comparação com o "UseConstructor".

O código:

void UseConstructor()
{
    TestTimer t("UseConstructor");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels(dimension*dimension);
        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}


void UseFillConstructor()
{
    TestTimer t("UseFillConstructor");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels(dimension*dimension, Pixel(255,0,0));
    }
}

Portanto, o "valor" adicional fornecido diminui bastante o desempenho, o que eu acho que é devido à chamada múltipla para copiar o construtor. Mas...

Compilar:

gcc-6.2.0/bin/g++ -std=c++14 -O vector.cpp

Resultado:

UseArray completed in 1.02464 seconds
UseVector completed in 1.31056 seconds
UseConstructor completed in 1.47413 seconds
UseFillConstructor completed in 1.01555 seconds
UseVectorPushBack completed in 6.9597 seconds
The whole thing completed in 11.7851 seconds

Portanto, nesse caso, a otimização do gcc é muito importante, mas não pode ajudá-lo muito quando um valor é fornecido como padrão. Isso é contra a minha mensalidade, na verdade. Espero que ajude o novo programador a escolher qual formato de inicialização do vetor.

user2189731
fonte
0

Parece depender dos sinalizadores do compilador. Aqui está um código de referência:

#include <chrono>
#include <cmath>
#include <ctime>
#include <iostream>
#include <vector>


int main(){

    int size = 1000000; // reduce this number in case your program crashes
    int L = 10;

    std::cout << "size=" << size << " L=" << L << std::endl;
    {
        srand( time(0) );
        double * data = new double[size];
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of C style heap array:    " << duration << "ms\n";
        delete data;
    }

    {
        srand( 1 + time(0) );
        double data[size]; // technically, non-compliant with C++ standard.
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of C99 style stack array: " << duration << "ms\n";
    }

    {
        srand( 2 + time(0) );
        std::vector<double> data( size );
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of std::vector array:     " << duration << "ms\n";
    }

    return 0;
}

Diferentes sinalizadores de otimização fornecem respostas diferentes:

$ g++ -O0 benchmark.cpp 
$ ./a.out 
size=1000000 L=10
Calculation result is 181182
Duration of C style heap array:    118441ms
Calculation result is 181240
Duration of C99 style stack array: 104920ms
Calculation result is 181210
Duration of std::vector array:     124477ms
$g++ -O3 benchmark.cpp
$ ./a.out 
size=1000000 L=10
Calculation result is 181213
Duration of C style heap array:    107803ms
Calculation result is 181198
Duration of C99 style stack array: 87247ms
Calculation result is 181204
Duration of std::vector array:     89083ms
$ g++ -Ofast benchmark.cpp 
$ ./a.out 
size=1000000 L=10
Calculation result is 181164
Duration of C style heap array:    93530ms
Calculation result is 181179
Duration of C99 style stack array: 80620ms
Calculation result is 181191
Duration of std::vector array:     78830ms

Seus resultados exatos variam, mas isso é bastante típico na minha máquina.

shuhalo
fonte
0

Na minha experiência, às vezes, apenas às vezes, vector<int>pode ser muitas vezes mais lento que int[]. Uma coisa a ter em mente é que os vetores de vetores são muito diferentes int[][]. Como os elementos provavelmente não são contíguos na memória. Isso significa que você pode redimensionar vetores diferentes dentro do principal, mas a CPU pode não ser capaz de armazenar em cache elementos, assim como no caso de int[][].

Íhor Mé
fonte