C++ Warming std vector

Question

Зачем заполнять std :: vector второй раз - FASTER? Даже если пространство было зарезервировано с самого начала?

int total = 1000000; 

struct BaseClass { 
    float m[16]; 
    int id; 

    BaseClass(int _id) { id = _id; } 
}; 

int main() { 

    std::vector<BaseClass> ar; 
    ar.reserve(total); 

    { 
    auto t_start = std::chrono::high_resolution_clock::now(); 
    for (int var = 0; var < total; ++var) { 
     ar.emplace_back(var); 
    } 
    auto t_end = std::chrono::high_resolution_clock::now(); 
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(
        t_end - t_start).count() << "\n"; 
    ar.clear(); 
    } 

    { 
    auto t_start = std::chrono::high_resolution_clock::now(); 
    for (int var = 0; var < total; ++var) { 
     ar.emplace_back(var); 
    } 
    auto t_end = std::chrono::high_resolution_clock::now(); 
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(
        t_end - t_start).count() << "\n"; 
    ar.clear(); 
    } 

    { 
    auto t_start = std::chrono::high_resolution_clock::now(); 
    for (int var = 0; var < total; ++var) { 
     ar.emplace_back(var); 
    } 
    auto t_end = std::chrono::high_resolution_clock::now(); 
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(
        t_end - t_start).count() << "\n"; 
    ar.clear(); 
    } 

    return 0; 
} 

онлайн просмотр: http://coliru.stacked-crooked.com/a/229e4ba47adddb1a

РЕЗУЛЬТАТЫ:

P.S. Я спрашиваю, почему он становится быстрее, если единственной причиной замедления для вектора является распределение/перераспределение. И мы выделили массив BEFORE start.

Answer 1

Причина, по которой первый запуск медленнее, чем два других, заключается в том, что среда выполнения еще не получила страницы памяти из ОС.

Я измерил вашу программу для вывода числа основных и второстепенных ошибок страницы, которые были выполнены в начале и после каждого из трех этапов выше. (Примечание: Это работает на Linux Понятия не имею, если он не будет работать на любой ОС вы на..) Код:

^{Примечание: обновлен до последней, с reserve() переехал в верхней и завернутые в своих собственных getrusage call.}

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

#include <sys/time.h> 
#include <sys/resource.h> 

using namespace std; 

int total = 1000000; 

struct BaseClass { 
    float m[16]; 
    int id; 

    BaseClass(int _id) { id = _id; } 
}; 

int main() { 

    std::vector<BaseClass> ar; 
    struct rusage r; 
    { 
    auto t_start = std::chrono::high_resolution_clock::now(); 
    } 

    getrusage(RUSAGE_SELF, &r); 
    cout << "minflt: " << r.ru_minflt << " majflt: " << r.ru_majflt << endl; 

    ar.reserve(total); 

    getrusage(RUSAGE_SELF, &r); 
    cout << "minflt: " << r.ru_minflt << " majflt: " << r.ru_majflt << endl; 

    { 
    auto t_start = std::chrono::high_resolution_clock::now(); 
    for (int var = 0; var < total; ++var) { 
     ar.emplace_back(var); 
    } 
    auto t_end = std::chrono::high_resolution_clock::now(); 
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(
        t_end - t_start).count() << "\n"; 
    ar.clear(); 
    } 

    getrusage(RUSAGE_SELF, &r); 
    cout << "minflt: " << r.ru_minflt << " majflt: " << r.ru_majflt << endl; 

    { 
    auto t_start = std::chrono::high_resolution_clock::now(); 
    for (int var = 0; var < total; ++var) { 
     ar.emplace_back(var); 
    } 
    auto t_end = std::chrono::high_resolution_clock::now(); 
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(
        t_end - t_start).count() << "\n"; 
    ar.clear(); 
    } 

    getrusage(RUSAGE_SELF, &r); 
    cout << "minflt: " << r.ru_minflt << " majflt: " << r.ru_majflt << endl; 

    { 
    auto t_start = std::chrono::high_resolution_clock::now(); 
    for (int var = 0; var < total; ++var) { 
     ar.emplace_back(var); 
    } 
    auto t_end = std::chrono::high_resolution_clock::now(); 
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(
        t_end - t_start).count() << "\n"; 
    ar.clear(); 
    } 

    getrusage(RUSAGE_SELF, &r); 
    cout << "minflt: " << r.ru_minflt << " majflt: " << r.ru_majflt << endl; 

    return 0; 
} 

Я тогда запустил его на своей коробке. В результате получается просветление:

minflt: 343 majflt: 0 
minflt: 367 majflt: 0 
48 minflt: 16968 majflt: 0 
16 
minflt: 16968 majflt: 0 
15 
minflt: 16968 majflt: 0 

Обратите внимание, что первый измеренный контур, понесенный более чем 16 000 мелких неисправностей. Эти недостатки делают память доступной для приложения и учитывают более медленное время работы. После этого дополнительных сбоев не возникает. В противоположность этому, вызов reserve() вызвал только 24 незначительных сбоя.

В большинстве современных операционных систем с виртуальной памятью ОС реализует ленивое выделение памяти, даже если на нем не работает программное обеспечение. Когда среда выполнения запрашивает дополнительную память из ОС, ОС замечает запрос. Если запрос завершается успешно, среда выполнения теперь имеет новый диапазон доступных ему виртуальных адресов. (Информация зависит от API и ОС, но суть одна и та же.) ОС может указывать диапазон виртуальных адресов на одну нулевую заполненную страницу с пометкой «только для чтения».

ОС не обязательно сделает эти страницы доступными для задачи. Скорее, ОС ждет, пока задача фактически не попытается записать в выделенную память. В этот момент ОС выделяет физическую страницу для возврата к виртуальной странице, назначенной задаче. Это регистрируется как «незначительная ошибка» на языке UNIX. Этот процесс может быть дорогостоящим.

Это то ленивое распределение, которое ваша задача измеряет.

Чтобы доказать это, я сделал также strace приложения. Значимая часть ниже.

getrusage(RUSAGE_SELF, {ru_utime={0, 0}, ru_stime={0, 0}, ...}) = 0 
fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 0), ...}) = 0 
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fe3aa339000 
write(1, "minflt: 328 majflt: 0\n", 22) = 22 
mmap(NULL, 68001792, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fe3a551c000 
getrusage(RUSAGE_SELF, {ru_utime={0, 0}, ru_stime={0, 0}, ...}) = 0 
write(1, "minflt: 352 majflt: 0\n", 22) = 22 
write(1, "52\n", 3)      = 3 
getrusage(RUSAGE_SELF, {ru_utime={0, 30000}, ru_stime={0, 20000}, ...}) = 0 
write(1, "minflt: 16953 majflt: 0\n", 24) = 24 
write(1, "20\n", 3)      = 3 
getrusage(RUSAGE_SELF, {ru_utime={0, 50000}, ru_stime={0, 20000}, ...}) = 0 
write(1, "minflt: 16953 majflt: 0\n", 24) = 24 
write(1, "15\n", 3)      = 3 
getrusage(RUSAGE_SELF, {ru_utime={0, 70000}, ru_stime={0, 20000}, ...}) = 0 
write(1, "minflt: 16953 majflt: 0\n", 24) = 24 
munmap(0x7fe3a551c000, 68001792)  = 0 
exit_group(0)       = ? 

Как вы можете видеть, задачу распределенной памяти с mmap вызова между первыми двумя getrusage системными вызовами. И тем не менее, этот шаг вызвал только 24 незначительных недостатка.Итак, хотя C++ был не ленив, Linux ленился в предоставлении памяти для задачи.

В частности, первый вызов mmap, как представляется, выделяет буфер ввода-вывода для первого сообщения write. Второй вызов mmap (выделение 68001792 байт) происходит до второй getrusage звонок. И все же вы можете увидеть только 24 дополнительных сбоя между ними в этом прогоне.

Ястребиный глаз среди вас заметит, что цифры для этого прогона немного отличаются от чисел, показанных выше. Я запускаю этот исполняемый файл много раз, и числа меняются каждый раз. Но они всегда в одном общем зачете.