Заморозка в программе на C ++ с использованием огромного вектора
У меня проблема с программой на C ++. Я думаю, что это проблема памяти.
В моей программе я использовал для создания какого-то огромного std :: vector (я использую резерв для выделения некоторой памяти). С размером вектора 1 000 000, это нормально, но если я увеличу это число (около десяти миллионов), моя программа заморозит мой компьютер, и я ничего не могу сделать, кроме ожидания сбоя (или завершения программы, если мне повезет) , Мой вектор содержит структуру под названием Point, которая содержит вектор double.
Я использовал valgrind, чтобы проверить, не хватает ли памяти. Но нет. По нему проблем нет. Может быть, использование вектора объектов не рекомендуется? Или, может быть, есть какие-то системные параметры для проверки или что-то? Или просто вектор слишком велик для компьютера?
Что Вы думаете об этом ?
Решение
отказ
Обратите внимание, что этот ответ предполагает несколько вещей о вашей машине; точное использование памяти и вероятность ошибок зависит от вашей среды. И, конечно, сбой еще проще, если вы не вычисляете 2d-Points, но, например, 4d-точки, которые обычно используются в компьютерной графике, или даже более крупные точки для других числовых целей.
О вашей проблеме
Это достаточно много памяти для выделения:
#include <iostream>
#include <vector>
struct Point {
std::vector<double> coords;
};
int main () {
std::cout << sizeof(Point) << std::endl;
}
Это печатает 12, который является размером в байтах пустого Point, Если у вас есть двумерные точки, добавьте еще 2*sizeof(double)=8 на каждый элемент, т. е. теперь у вас есть 20 байтов на Point,
Имея десятки миллионов элементов, вы запрашиваете 200 миллионов миллионов байтов данных, например, для 20 миллионов элементов вы запрашиваете 400 миллионов байтов. Хотя это не превышает максимальный индекс в std::vectorВполне возможно, что ОС не имеет столько свободной памяти для вас.
Кроме того, ваш vectorПамять нужно копировать довольно часто, чтобы иметь возможность расти. Это происходит, например, когда вы push_backпоэтому, когда у вас уже есть 400MiB vectorна следующий push_back у вас может быть старая версия vectorплюс выделенная память 400 МБ * X, так что вы можете легко превысить 1000 МБ временно и т. д.
Оптимизации (высокий уровень; предпочтительным)
Вам нужно на самом деле хранить данные все время? Можете ли вы использовать подобный алгоритм, который не требует так много памяти? Можете ли вы реорганизовать свой код, чтобы уменьшить объем хранилища? Можете ли вы внести некоторые данные, когда узнаете, что потребуется некоторое время, пока они вам снова не понадобятся?
Оптимизации (низкий уровень)
Если вы знаете количество элементов перед созданием внешнего вектора, используйте std::vector конструктор, который вы можете сказать начальный размер:
vector<Foo> foo(12) // initialize have 12 elements
Конечно, вы можете много оптимизировать для памяти; например если вы знаете, что у вас всегда есть только 2d-баллы, просто два doubles как члены: 20 байтов -> 16 байтов. Когда вам действительно не нужна точность doubleиспользовать float: 16 байтов -> 8 байтов. Это оптимизация до $ 2/5 $:
// struct Point { std::vector<double> coords; }; <-- old
struct Point { float x, y; }; // <-- new
Если этого все еще недостаточно, специальное решение может быть std::dequeили другой несмежный контейнер: нет «удвоения» временной памяти, потому что не требуется изменение размера; Также не нужно, чтобы ОС нашла вам такой непрерывный блок памяти.
Вы также можете использовать механизмы сжатия, индексированные данные или числа с фиксированной запятой. Но это зависит от ваших конкретных обстоятельств.
struct Point { signed char x, y; }; // <-- or even this? examine a proper type
struct Point { short x_index, y_index; };
Другие решения
Не видеть ваш код, это всего лишь предположение, но я подозреваю, что это во многом из-за вашей попытки выделить огромный объем памяти, который смежный. std::vector гарантированно находится в непрерывной памяти, поэтому, если вы пытаетесь выделить большой объем пространства, операционная система должна попытаться найти такой большой объем памяти, который она может использовать. Это может не быть проблемой для 2 МБ, но если вы вдруг пытаетесь выделить 200 МБ или 2 ГБ непрерывной памяти …
Кроме того, каждый раз, когда вы добавляете новый элемент к вектору и его размер изменяется, все существующие элементы должны быть скопированы в выделенное новое пространство. Если у вас 9 миллионов элементов, а для добавления элемента 9 000 001 необходимо изменить размер, то есть 9 миллионов элементов, которые необходимо переместить. Поскольку ваш вектор становится больше, это время копирования занимает больше времени.
Попробуйте использовать std::deque вместо. Он будет в основном размещать страницы (которые будут смежными), но каждая страница может быть размещена там, где она может поместиться.