É std :: deque mais rápido que std :: vector para inserir no final?

9

Comecei a fazer comparações entre:

  • inserindo na frente da lista
  • inserindo na parte de trás de um vetor
  • inserindo na frente de um deque

Mas então notei que mesmo em push_back() o deque parecia ser mais rápido. Eu devo estar fazendo algo errado, eu não posso acreditar que um contêiner mais geral superaria um em particular.

Meu código usando o benchmark do Google:

#include "benchmark/benchmark.h"
#include <deque>
#include <vector>

#define NUM_INS 1000

static void BM_InsertVector(benchmark::State& state) {
    std::vector<int> v;
    v.reserve(NUM_INS);
    while (state.KeepRunning()) {
        state.PauseTiming();
        v.clear();
        state.ResumeTiming();
        for (size_t i = 0; i < NUM_INS; i++)
            v.push_back(i);
    }
}
BENCHMARK(BM_InsertVector);

static void BM_InsertDeque(benchmark::State& state) {
    std::deque<int> v;
    while (state.KeepRunning()) {
        state.PauseTiming();
        v.clear();
        state.ResumeTiming();
        for (size_t i = 0; i < NUM_INS; i++)
            v.push_back(i);
    }
}
BENCHMARK(BM_InsertDeque);

BENCHMARK_MAIN();

Resultados:

Run on (1 X 2592 MHz CPU )
2016-02-18 14:03:47
Benchmark         Time(ns)    CPU(ns) Iterations
------------------------------------------------
BM_InsertVector       2820       2470     312500                                 
BM_InsertDeque        1872       1563     406977

Noto algumas diferenças ao jogar com o número de elementos, mas o deque sempre supera o vetor.

EDITAR: compilador: gcc version 5.2.1 compilação com: g++ -O3 -std=c++11 push_front.cpp -lbenchmark -lpthread

Eu acho que o -O3 é realmente instrumental; quando desligo, fico com um desempenho deque ligeiramente pior.

    
por Iosif Spulber 18.02.2016 в 15:09
fonte

2 respostas

1

Acho que o vetor é mais lento porque você está chamando clear() , o que, dependendo da sua implementação de STL, pode liberar o armazenamento de matriz subjacente.

Se for esse o caso, a sua chamada reserve() não está ajudando; e seu vetor é redimensionado continuamente, o que requer que todos os elementos sejam movidos para o novo e maior armazenamento.

    
por Dominic Dos Santos 10.03.2017 / 23:54
fonte
1

Existem basicamente três fontes de custo envolvidas na anexação contínua de elementos a um contêiner dinâmico:

  1. Gerenciamento de memória.
  2. A contabilidade interna do contêiner.
  3. Qualquer operação que precise ser executada nos próprios elementos. Notavelmente; qualquer contêiner que invalide referências na inserção está potencialmente movendo / copiando elementos.

Vamos começar com 1. vector continua pedindo o dobro da memória e deque aloca pedaços de tamanho fixo ( deque é normalmente implementado como uma matriz de matrizes, com matrizes de camada inferior sendo de tamanho fixo). Pedir mais memória pode demorar mais do que pedir menos, mas normalmente, a menos que seu heap seja muito fragmentado, pedir um grande pedaço de uma vez é o modo mais rápido de obter alguma memória. É provavelmente mais rápido alocar um meg uma vez, depois pedir um kilobyte 1000 vezes. Portanto, parece claro que vector acabará tendo a vantagem aqui (até que o contêiner seja tão grande que seja afetado pela fragmentação). No entanto, isso não acontece: você solicitou apenas 1000 elementos. Eu escrevi o seguinte código link . Não é muito interessante, mas basicamente usa um alocador trivial que incrementa um global para ver quantas alocações são executadas.

No decorrer do seu benchmark, vector pede memória 11 vezes e deque apenas 10. deque continua pedindo a mesma quantia, vector pede o dobro de valores. Além disso, vector deve chamar free 10 vezes. E deque 0. Isso parece uma pequena vitória para deque .

Para a contabilidade interna, vector tem uma implementação mais simples que deque . Afinal, vector é apenas uma matriz dinâmica e deque é uma matriz de matrizes e é estritamente mais complexa. Então, isso é claramente uma vitória para vector .

Finalmente, elementos nas próprias operações. Em deque , nada é movido. Com vector , cada nova alocação de heap também envolve mover todos os elementos. Provavelmente, é otimizado para usar memcpy para tipos triviais, mas mesmo assim, são 10 chamadas para memcpy para copiar 1, 2, 4, 8 ... 512 inteiros. Esta é claramente uma vitória para deque .

Eu posso especular que a ativação até O3 permitiu um alinhamento muito agressivo de muitos dos caminhos de código mais complexos em deque , reduzindo o peso de 2. Mas obviamente, a menos que você faça um trabalho muito mais detalhado (muito cuidado! ) benchmark, você nunca saberá com certeza.

Principalmente, este post é para mostrar que é mais complexo do que simplesmente um container especializado versus um mais geral. Vou fazer uma previsão (ponha meu pescoço para fora, por assim dizer): se você aumentar o número de elementos até mesmo dizer um fator de 2 ou 4, você não verá mais deque ganhar. Isso porque deque fará 2x ou 4x como muitas alocações de heap, mas o vetor fará apenas mais 1-2.

Eu também posso notar aqui que deque é na verdade uma estrutura de dados estranha; teoricamente, é uma matriz de matrizes, mas em muitas implementações, a matriz é um determinado tamanho ou apenas um elemento, o que for maior. Além disso, algumas de suas grandes garantias O são absurdas. push_back é apenas tempo constante fixo, porque em C ++, apenas as operações nos próprios elementos contam para o grande O. Caso contrário, deve ficar claro que, como é uma matriz de matrizes, a matriz de nível superior será proporcional ao tamanho número de elementos já armazenados. E, eventualmente, esse array de nível superior fica sem espaço, e você tem que realocá-lo, movendo os ponteiros O (N). Então não é realmente O (1) push_back .

    
por Nir Friedman 12.03.2017 / 03:52
fonte