0

Я считываю много данных из файла и заполняю ими вектор (про резервирование вектора знаю). После некоторых манипуляций с данными, я освобождаю память.

std::vector<unsigned int*> values;

//Резервирую память вектора, заполняю его данными с выделением памяти под них
//Обработка данных

for ( auto &value : values ) {
    delete value;
}

Вроде задача тривиальна, однако напоролся на следующую проблему - у меня выходит около 32 миллионов элементов, и, понятное дело, их обработка занимает длительное время, однако, когда я дохожу до освобождения памяти, скорость освобождения начинает падать тем сильнее, чем больше памяти я уже освободил. Таким образом, память освобождается более получаса.

Я подозреваю, что виной всему range-based for, но, видимо, не до конца понимаю как он работает и как быть с этой проблемой.

Пробовал разбить вектор на два и память из одной половины освобождать в другом потоке. Это значительно снизило время освобождения большинства памяти, но всё равно занимало слишком много и, в конце концов, не решило проблему. Грубый пример кода:

const std::size_t halfSize = values.size() / 2;
std::vector<unsigned int*> splitLow(values.begin(), values.begin() + halfSize);
std::vector<unsigned int*> splitHigh(values.begin() + halfSize, values.end());

auto lambdaMemoryRelease = []( auto &values ) {
    for ( auto value : values ) {
        delete value;
    }
};

std::thread thread( lambdaMemoryRelease, std::ref( splitLow ) );
lambdaMemoryRelease( splitHigh );
thread.join();

Затем решил пойти дальше и добавить ещё парочку потоков, и по ходу дела возникло ещё несколько вопросов (в комментариях):

const auto numberOfThreads = 3;

auto lambdaMemoryRelease = []( auto &values ) {
    for ( auto value : values ) {
        delete value;
    }
};

const auto pieceSize = values.size() / (numberOfThreads + 1);
std::vector<std::thread> threads;

for ( auto i = 0; i < numberOfThreads; ++i ) {

    std::vector<unsigned int*> splitValues( values.begin() + (i * pieceSize)
        , values.begin() + ((i + 1) * pieceSize));//Не совсем уверен, как это будет 
            //работать - что будет создан вектор, содержащий указанный диапазон 
            //итераторов понятно, но после выхода из блока for он должен быть очищен, 
            //и что произойдёт с ссылкой на вектор, переданной в лямбду?

    std::thread thread( lambdaMemoryRelease, std::ref( splitValues ) );
    threads.push_back( thread );
}

lambdaMemoryRelease( std::vector<unsigned int*>(values.begin() + (pieceSize * numberOfThreads)
    , values.end() ) );

for ( auto &thread : threads ) {
    thread.join();//Расчёт на то, что если какой-либо из потоков ещё 
        //не завершит работу, мы остановимся и дождёмся его, и так с
        //каждым потоком, а если поток ранее завершил работу, то не 
        //остановимся вовсе
}

В результате код вышел странненьким и не особо рабочим.

Итого, как быть с медленным освобождением памяти при большом количестве элементов, и какие ответы на вопросы в комментариях к последнему коду?

12
  • 1
    Тут много раз упоминается слово "медленно", но нигде нет никаких замеров или цифр. Как нет и воспроизводимого примера такого поведения. Хранение в векторе указателя на unsigned int выглядит втройне подозрительно, так как если указатель на один элемент - то он не имеет смысл, если на несколько - то в программе неопределенное поведение из-за неправильного удаления, ну и вообще непонятно, зачем что-то удалять вручную. В С++ указатели нужны по большей части для взаимодействия с С. Последний кусок кода вообще ни разу не рабочий, непонятно, зачем еще плодить векторы? 8 апр 2019 в 8:36
  • Выделять память для новых векторов для освобождения памяти - это как выделять водку на борьбу с алкоголизмом. 8 апр 2019 в 8:40
  • @VTT как таковых замеров я не делал, лишь периодически проверял в дебаге, память из под какого элемента сейчас освобождается, и если из под первых миллионов она освобождалась за десятки секунд, впоследствии время на освобождение каждого элемента росло. Полагаю дело в цикле, допускаю, что после освобождения памяти из под элемента, проход начинался с начала, что странно... Касательно указателей, мне нужно было отсортировать вектор, для чего я использовал std::sort, а он ругался и дребовал указатели, вот вы и дал ему то, чего он хотел 8 апр 2019 в 8:45
  • @VTT Вы про вектора с диапазоном из итераторов (не уверен как правильно называется)? Ничего адекватнее в голову не пришло, вот и сделал так 8 апр 2019 в 8:46
  • 1
    "проверял в дебаге" - измерение производительности в дебаге не особо толковое занятие. "std::sort, а он ругался и дребовал указатели" - да у вас тут еще и проблема XY... 8 апр 2019 в 8:49

2 ответа 2

0
for ( auto i = 0; i < numberOfThreads; ++i ) {

    std::vector<unsigned int*> splitValues( values.begin() + (i * pieceSize)
        , values.begin() + ((i + 1) * pieceSize));

    std::thread thread( lambdaMemoryRelease, std::ref( splitValues ) );
    threads.push_back( thread );
}

Здесь splitValues - объект в стеке, с каждой итерацией будет вызван конструктор и деструктор. А вы отдаёте адрес в рабочем стеке нитям. Всё должно полностью обрушится. Сначала создавайте вектор в куче так:

std::vector<unsigned int*> * psplitValues = 
  new std::vector<unsigned int*>(values.begin() + (i * pieceSize)
    , values.begin() + ((i + 1) * pieceSize))

и удаляйте потом. Желательно, чтобы это сделали сами нити.

2
  • Спасибо за ответ, в целом я так и предполагал, но хотелось разобраться. Хотел бы уточнить, "Желательно, чтобы это сделали сами нити." - как именно? Вы имеете ввиду такую запись std::thread thread( lambdaMemoryRelease, std::ref( new std::vector<unsigned int*>(values.begin() + (i * pieceSize), values.begin() + ((i + 1) * pieceSize))) ); , или передачу всего контейнера в нить, с последующим получением нужного диапазона итераторов? Как будет корректнее? 8 апр 2019 в 20:13
  • Если вектор, как аргумент для нити больше никому не нужен после заканчивания её работы, то проще пусть сама нить занимается удалением данного аргумента. Для главного потока эта задача будет тяжелее в три раза.
    – AlexGlebe
    9 апр 2019 в 10:03
-6

Вообще-то std::vector нужен только если заранее неизвестен размер вектора и надо вектор пополнять в рантайме заранее неизвестным числом элементов. Если размер вектора заранее известен, то лучше пользоваться std::array. Если же время становится критично, то можно написать свой массив с полным контролем всех операций.

UPD1:

И вообще, если уж затрагивать философские основы, то программирование с использованием stl превращает С++ в Яву. Контроль над распределением памяти утрачивается, все переменные перекочевывают в кучу с соответствующим оверхедом по времени в виде запроса-освобождения памяти. Итераторы тоже все живут в куче. Вобщем получается нормальная такая Ява. Ну и за что боролись? Проще работать на Яве и не париться.

UPD2:

Все равно его в куче хранить придется.

Зато его освобождать быстро так как это один кусок памяти. А std::vector это же не вектор на самом деле, а список со всеми вытекающими последствиями в виде долгого времени доступа и долгого времени освобождения всех цепочек.

А как же кастомные аллокаторы?

Ну и чем помогут кастомные аллокаторы? Свою кучу писать и в ней выделять место? Так тоже самое и будет что в общей куче, быстрее не будет.

"Итераторы тоже все живут в куче" Почему это?

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

UPD3:

Список - в смысле связный список?

Ну конечно. std::vector это эмуляция массива с помощью списка. Внутри у std::vector содержится список из векторов. Запрашиваются маленькие вектора по 100-1000 элементов и в них добавляются элементы. Когда все места становятся заняты, то запрашивается еще один маленький вектор, который помещается в список. И так далее. А иначе никак не возможно сделать вектор с переменным размером.

UPD4:

vector - это непрерывный участок.

Как известно, при создании std::vector не указывается его размер. Поэтому std::vector не может быть непрерывным участком, так как при добавлении элементов неизвестно, сколько надо резервировать места.

UPD5:

std::vector представляет собой неразрывный в памяти массив элементов

Увы, но это не так. Именно поэтому у Вас так долго удаляется std::vector (конечно если у Вас нет еще и других ошибок). Ну конечно полчаса на удаление даже 32 миллионов беззнаковых целых это слишком, даже в дебажной версии. Скорее всего у Вас там и какие-то другие ошибки.

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

Если бы это было так, то любое добавление в вектор занимало бы (в общем случае) время О(n) (где n текущий размер вектора) что явно неприемлемо ни по каким законам, ни Божеским, ни человеческим.

std::vector представляет собой неразрывный в памяти массив элементов

Вот std::array он да, представляет собой неразрывный в памяти массив элементов. Ну зато std::array не умеет изменять свой размер. А std::vector никак не может представлять неразрывный в памяти массив элементов по всем вышеизложенным причинам.

Вообще-то чем спорить, лучше надо поглядеть реализацию std::vector где-нибудь в приличном месте, ну хотя бы в VS. Когда-то давно я глядел реализации stl. Но это было дело муторное, там и тогда сам черт ногу сломал бы. А сейчас особенно.

UPD6:

размер увеличивают в N (1.5 или 2) раза

Не, ну сделать можно как угодно криво. Ну вот у человека 32 мега интов в векторе. Ему надо добавить 1 элемент, а ему сразу отводят еще 32 мега пустой памяти? И это называется полный контроль над памятью и экономное использование ресурсов? А если у него вектор на гигабайт? Что, сразу второй гигабайт ему отвалят? Это не наш метод и с таким подходом система завалится на раз-два-три.

The elements are stored contiguously, which means that elements can be accessed not only through iterators, but also using offsets to regular pointers to elements. This means that a pointer to an element of a vector may be passed to any function that expects a pointer to an element of an array.

Действительно, такое написано. Правда там приписка есть что все это - (since C++03). Вобщем если это действительно сделано так начиная с 2003 года, то значит что начиная с 2003 года std::vector нельзя применять для сколько-нибудь больших векторов. То есть если на 10 килобайт данных еще потянет, то большие массивы данных будут либо постоянно занимать время на перекопирование, либо отхватывать по слишком большому куску памяти и дополнительно в этот момент перекопирования гига данных вся программа будет тормозиться что тоже не далеко фонтан.

UPD7:

Вместо этого размер увеличивают в N (1.5 или 2) раза, когда место в векторе кончается. За счет этого получается вставка за (амортизированное) О(1).

В std::vector есть метод insert (начиная с С++11). Если хранить данные в std::vector в виде неразрывного массива в памяти, то insert будет выполняться за О(n). И никакие увеличения размера в 1.5 или 2 раза тут не помогут получить "амортизированное" О(1). И что же, прикажете при каждом insert перекопировать весь вектор?

Скорее всего непрерывный участок памяти получается при выполнении метода data. Это как было сделано в std::string. Хранятся данные по кусочкам, но есть метод c_str, которые заводит непрерывный буфер и копирует в него данные.

9
  • Учитывая "миллионы элементов", упомянутые в комментах, не уверен, чем std::array здесь лучше std::vector. Все равно его в куче хранить придется. Проблема ТС в том, как я понимаю, что он под каждый отдельный инт выделяет отдельный кусок памяти в куче. "Контроль над распределением памяти утрачивается" А как же кастомные аллокаторы? "Итераторы тоже все живут в куче" Почему это? 8 апр 2019 в 18:20
  • "std::vector это же не вектор на самом деле, а список со всеми вытекающими последствиями" Не понимаю. Список - в смысле связный список? Вектор же в одном куске памяти хранит все элементы, не хуже выделенного в куче std::array. 8 апр 2019 в 18:33
  • 1
    "UPD5: Увы, но это не так." RTFM же, ну. "The elements are stored contiguously, which means that elements can be accessed not only through iterators, but also using offsets to regular pointers to elements. This means that a pointer to an element of a vector may be passed to any function that expects a pointer to an element of an array." - "Элементы хранятся [в памяти] подряд" 8 апр 2019 в 20:25
  • 3
    "Итераторы тоже все живут в куче", "std::vector это эмуляция массива с помощью списка" - закусывать надо 8 апр 2019 в 21:08
  • 1
    Мда, столько бреда в одном месте... 9 апр 2019 в 3:54

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.