Neden vektör arıyor.rezerv(1 gerekli) daha hızlı vektör.rezerv(gerekli)?

SORU

29 Mart 2013, Cuma

Neden vektör arıyor.rezerv(1 gerekli) daha hızlı vektör.rezerv(gerekli)?

Bazı testler çeşitli koşullar altında standart konteyner, performans ölçüm yapıyorum, ve bir şey üzerinde tuhaf geldi. Ne zaman ben ekleme birçok öğe içine orta std::vector, eğer ben İlk Çağrı rezerv ile tam sayısı unsurları o olacağım ekleme, görüyorum aslında hiçbir performans farkı en koşullara göre değil arama rezerv, hangi şaşırtıcı. Eğer 1 ihtiyacım elemanları tam sayı ile rezerv ararsam sonra önemli bir performans artışı olsun daha şaşırtıcı, ancak,. Bu sadece (her zaman saniye olarak) var sonuçları örnek bir tablo

 --------------- -------- ------------------- ----------------------- 
| # of elements | vector | vector (reserved) | vector (reserved   1) |
 --------------- -------- ------------------- ----------------------- 
|         10000 | 0.04   | 0.04              | 0.03                  |
|         20000 | 0.14   | 0.14              | 0.11                  |
|         30000 | 0.32   | 0.32              | 0.25                  |
|         40000 | 0.55   | 0.55              | 0.44                  |
|         50000 | 0.87   | 0.85              | 0.66                  |
|         60000 | 1.24   | 1.24              | 0.96                  |
|         70000 | 1.69   | 1.68              | 1.31                  |
|         80000 | 2.17   | 2.21              | 1.71                  |
|         90000 | 2.78   | 2.75              | 2.16                  |
|        100000 | 3.43   | 3.44              | 2.68                  |
|        110000 | 4.13   | 4.15              | 3.23                  |
|        120000 | 4.88   | 4.89              | 3.86                  |
|        130000 | 5.79   | 5.8               | 4.51                  |
|        140000 | 6.71   | 6.71              | 5.24                  |
|        150000 | 7.7    | 7.7               | 6.02                  |
|        160000 | 8.76   | 8.67              | 6.86                  |
|        170000 | 9.9    | 9.91              | 7.74                  |
|        180000 | 11.07  | 10.98             | 8.64                  |
|        190000 | 12.34  | 12.35             | 9.64                  |
|        200000 | 13.64  | 13.56             | 10.72                 |
|        210000 | 15.1   | 15.04             | 11.67                 |
|        220000 | 16.59  | 16.41             | 12.89                 |
|        230000 | 18.05  | 18.06             | 14.13                 |
|        240000 | 19.64  | 19.74             | 15.36                 |
|        250000 | 21.34  | 21.17             | 16.66                 |
|        260000 | 23.08  | 23.06             | 18.02                 |
|        270000 | 24.87  | 24.89             | 19.42                 |
|        280000 | 26.5   | 26.58             | 20.9                  |
|        290000 | 28.51  | 28.69             | 22.4                  |
|        300000 | 30.69  | 30.74             | 23.97                 |
|        310000 | 32.73  | 32.81             | 25.57                 |
|        320000 | 34.63  | 34.99             | 27.28                 |
|        330000 | 37.12  | 37.17             | 28.99                 |
|        340000 | 39.36  | 39.43             | 30.83                 |
|        350000 | 41.7   | 41.48             | 32.45                 |
|        360000 | 44.11  | 44.22             | 34.55                 |
|        370000 | 46.62  | 46.71             | 36.22                 |
|        380000 | 49.09  | 48.91             | 38.46                 |
|        390000 | 51.71  | 51.98             | 40.22                 |
|        400000 | 54.45  | 54.56             | 43.03                 |
|        410000 | 57.23  | 57.29             | 44.84                 |
|        420000 | 60     | 59.73             | 46.67                 |
|        430000 | 62.9   | 63.03             | 49.3                  |
 --------------- -------- ------------------- -----------------------

Uygulama kontrol ettim ve tek bir hata var gibi görünmüyor. Ben daha sonra başka bir boyutu baskı ve rezerv çağrıldıktan sonra kapasitesi hemen Test, ve sonra onları tekrar vektör doldurduktan sonra çıktısını aldım, ve her şey iyi görünüyor.

before:
    size: 0
    capacity: 10000
after:
    size: 10000
    capacity: 10000

before:
    size: 0
    capacity: 20000
after:
    size: 20000
    capacity: 20000

...

Derleyici gcc Linux x86_64 Fedora üzerinde 4.7.2. Derleyici seçenekleri -std=c 11 -Ofast -march=native -funsafe-loop-optimizations -flto=4 - fwhole-program

Kodu aşağıda.

#include <algorithm>
#include <array>
#include <cstdint>
#include <vector>
#include <random>
#include <string>
#include <iostream>
#include <fstream>

#include <boost/timer.hpp>

namespace {
constexpr size_t array_size = 1;

unsigned number() {
        static std::random_device rd;
        static std::mt19937 random_engine(rd());
        static std::uniform_int_distribution<uint32_t> distribution(0, std::numeric_limits<uint32_t>::max());
        return distribution(random_engine);
}

class Class {
        public:
                Class() {
                        x[0] = number();
                }
                std::string to_string() const {
                        return std::to_string(x[0]);
                }
                inline friend bool operator<=(Class const & lhs, Class const & rhs) {
                        return lhs.x[0] <= rhs.x[0];
                }
        private:
                std::array<uint32_t, array_size> x;
};

template<typename Container>
void add(Container & container, Class const & value) {
        auto const it = std::find_if(std::begin(container), std::end(container), [&](Class const & c) {
                return value <= c;
        });
        container.emplace(it, value);
}

// Do something with the result
template<typename Container>
void insert_to_file(Container const & container) {
        std::fstream file("file.txt");
        for (auto const & value : container) {
                file << value.to_string() << '\n';
        }
}

template<typename Container>
void f(std::vector<Class> const & values) {
        Container container;
        container.reserve(values.size());
        for (auto const & value : values) {
                add(container, value);
        }
        insert_to_file(container);
}

}

int main(int argc, char ** argv) {
        std::size_t const size = (argc == 1) ? 1 : std::stoul(argv[1]);
        // Default constructor of Class fills in values here
        std::vector<Class> const values_to_be_copied(size);
        typedef std::vector<Class> Container;
        boost::timer timer;
        f<Container>(values_to_be_copied);
        std::cerr << "Finished in " << timer.elapsed() << " seconds.\n";
}

Ben oluşturulan bir C 03 sürümünü denemek ve yardım etmek diğer insanlar yeniden, ama yeniden bu sürüm, rağmen yapmaya çalışan bu haritayı sorun hale getirerek doğrudan bir çeviri mümkün:

#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <vector>
#include <string>
#include <iostream>

#include <boost/array.hpp>
#include <boost/cstdint.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int_distribution.hpp>
#include <boost/timer.hpp>

namespace {
unsigned number() {
        static boost::random::mt19937 random_engine;
        static boost::random::uniform_int_distribution<boost::uint32_t> distribution(0, std::numeric_limits<boost::uint32_t>::max());
        return distribution(random_engine);
}

class Class {
        public:
                Class() {
                        x[0] = number();
                }
                inline friend bool operator<=(Class const & lhs, Class const & rhs) {
                        return lhs.x[0] <= rhs.x[0];
                }
                std::string to_string() const {
                        return boost::lexical_cast<std::string>(x[0]);
                }
        private:
                boost::array<boost::uint32_t, 1> x;
};

class Less {
public:
        Less(Class const & c):
                value(c) {
        }
        bool operator()(Class const & c) const {
                return value <= c;
        }
private:
        Class value;
};

void add(std::vector<Class> & container, Class const & value) {
        std::vector<Class>::iterator it = std::find_if(container.begin(), container.end(), Less(value));
        container.insert(it, value);
}

// Do something with the result
void insert_to_file(std::vector<Class> const & container) {
        std::fstream file("file.txt");
        for (std::vector<Class>::const_iterator it = container.begin(); it != container.end();   it) {
                file << it->to_string() << '\n';
        }
}

void f(std::vector<Class> const & values) {
        std::vector<Class> container;
        container.reserve(values.size()   1);
        for (std::vector<Class>::const_iterator it = values.begin(); it != values.end();   it) {
                add(container, *it);
        }
        insert_to_file(container);
}

}

int main(int argc, char ** argv) {
        std::size_t const size = (argc == 1) ? 1 : boost::lexical_cast<std::size_t>(argv[1]);
        // Default constructor of Class fills in values here
        std::vector<Class> const values_to_be_copied(size);
        boost::timer timer;
        f(values_to_be_copied);
        std::cerr << "Finished in " << timer.elapsed() << " seconds.\n";
}

Şu anda rezerv çağıran satır 1 içerecek şekilde değiştirilmiş veya tamamen, koşuyordum bağlı olarak kaldırıldı. Tüm şey 10000 unsurları başladı bir kabuk betiği çalıştırmak ve 430000 elemanları, bir defada bir sürüm ulaşmıştır.

Benim işlemci ı5 4 çekirdekli işlemci, Intel, bellek 4 GB var. Deneyin ve kod C 11 sürümü varsa, sorunu yalıtmak görmem mümkün olduğunca kolaylaştırmak.

Kimseye ihtiyacım olan birden fazla element ayırma hızı bu artışa neden olduğunu neden biliyor mu?

CEVAP

31 Mart 2013, Pazar

Programı aşağıdaki değişiklik yaptım:

size_t a = getenv("A") ? 1 : 0;

void f(std::vector<Class> const & values) {
    ...
    container.reserve(values.size()   a);
    ...
}

Şimdi performansı ne olursa olsun, eğer bir 0 veya 1 ise aynı (hızlı). Sonuç olarak ekstra bir öğe rezervasyonu performans etkisi soru olarak kabul edildi) sahip olmalıdır. Ayrıca kaynak kodu veya derleyici bayrakları için diğer küçük değişiklikler performans arasında hızlı ve yavaş açar, kod İyileştiricisi, diğerlerine göre bazı durumlarda daha iyi bir şans var gibi görünüyor.

F aşağıdaki uygulama() tetikler aynı derleyici bayrakları ile ters davranış, böylece boyutu ayrılmış ve ekstra bir öğe saklıdır yavaş olur hızlı olur:

template<typename Container>
void f(std::vector<Class> const & values) {
    Container container;
    container.reserve(values.size());
    for (auto it = values.begin(); it != values.end();   it) {
        add(container, *it);
    }
    insert_to_file(container);
}

Bunu Paylaş: