Сбой при бесконечно расширяя Deque вместо вектора

Question

при выполнении этого кода:

#include <iostream> 
#include <vector> 
#include <deque> 

template< typename C > 
void fillToMax(C & collection, typename C::value_type value) 
{ 
    try 
     { 
     while(true) 
      collection.push_back(value); 

     } 
    catch(std::bad_alloc const&) 
     { 
     std::cout << "bad alloc with size " << collection.size() << std::endl; 
     } 
     return; 
} 

void fillVector() 
{ 
    std::vector<long> vecL; 
    fillToMax(vecL, 123); 
} 

void fillDeque() 
{ 
     std::deque<long> deqL; 
     fillToMax(deqL, 123); 
} 

int main() 
{ 
    fillVector(); 
    fillDeque(); 
} 

Я получаю ожидаемый bad_alloc ошибку, поэтому это легко попробовать/поймать. Проблема заключается в том, что я заменяю vector на deque, в этом случае моя машина просто падает ... черный экран, перезагружается и когда снова заявляет: у вас возникла неожиданная проблема!

Я бы хотел использовать deque вместо vector для хранения большего количества предметов без вопроса о смежном пространстве. Это позволит мне хранить больше данных, но я не могу позволить себе для моего приложения сбой и хотел бы знать, как я могу получить это для bad_alloc.

Возможно ли это?

Мои тесты используют MinGW-W64 - GCC версии 4.8.2 (x86_64-POSIX-SEH-rev4) на win8.1

Answer 1

Вы не говорите, какую систему вы используете, поэтому трудно сказать, но некоторые системы «overcommit», которые в основном делают реализацию реализации C++ (или даже C) невозможной; система будет сказать, что есть память, когда нет, и авария , когда вы пытаетесь ее использовать. Linux является наиболее широко документированным преступником , но вы можете перенастроить его для правильной работы.

Причина, по которой вы получаете bad_alloc с вектором, заключается в том, что вектор выделяет гораздо большие куски. И даже с overcommit, система откажется выделить память, если кусок слишком большой. Кроме того, многие mallocs будут использовать другую стратегию распределения для очень больших кусков; IIRC, malloc в Linux переключается на использование mmap за пределами определенного размера, и система может отказаться от mmap , даже если sbrk преуспел.

Answer 2

Быстрый ответ почему вектор может привести к сбою и не Deque в том, что, так как вектор использует смежный буфер, вы будете bad_alloc «быстрее». А также по запросу, который просит большой кусок.

Почему? Поскольку менее вероятно, что вы сможете выделить смежный буфер, чем меньший.

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

Предположим, что он будет расширяться в 1,5 раза. Таким образом, в настоящее время у вас есть 40% доступной памяти в используемом вами векторе, и ему нужно найти 60% доступной памяти, но не может сделать это в текущем местоположении. Хорошо, что доводит вас до предела, поэтому он не работает с bad_alloc, но на самом деле вы используете только 40% памяти.

Таким образом, на самом деле имеется доступная память, и те операционные системы, которые используют «оптимистичное» распределение памяти, не будут случайно перенаправлены для вас. Вы много просили, и это не могло дать вам. (Они не всегда полностью оптимистичны).

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

---

Теперь для вашего решения, как этого избежать? Ваш ответ может быть настраиваемым распределителем, то есть вторым параметром deque, который может проверить доступную реальную системную память и отказаться от выделения, если вы нажмете определенный порог.

Конечно, это зависит от системы, но вы можете иметь разные версии для разных машин.

Вы также можете установить свой произвольный «предел», конечно.

Предполагая, что ваша система Linux, вы можете быть в состоянии превратить overcommit прочь с

'echo 2 > /proc/sys/vm/overcommit_memory' 

Вам понадобится корень (администратора) разрешения, чтобы сделать это. (Или получить кого-то, у кого есть это, чтобы настроить его таким образом).

В противном случае другие способы изучения использования памяти доступны в руководствах по Linux, обычно упоминаемых в /proc.

Если ваша система не является Linux, а другая, которая перекомбинирована, вам придется искать, как вы можете ее обойти, написав свой собственный менеджер памяти. В противном случае возьмите более простой вариант произвольного настраиваемого максимального размера.

Помните, что с deque ваш распределитель вызывается только тогда, когда вам нужно выделить новый «кусок», а не для каждого push_back.

Answer 3

Xarylem, просто пытаясь ответить «как я могу предотвратить это» здесь ...

вы знаете что-то, что бросает bad_alloc - станд :: вектор. вы знаете что-то, что сбой ... std :: deque.

Таким образом, одним из способов было бы создать новый вектор размера X, если это удастся, очистите вектор и отбросьте X больше в deque. Если это не так, вы знаете, что идете в трясину. Что-то вроде:

std::vector<int> testVector; 
testeVector.reserve(1); 
std::deque<int> actualDequeToFill; 
for(size_t i = 0; ; ++i) 
{ 
     //test first 
     bool haveSpace = false; 
     try { testVector.reserve(2); } catch(...) { haveSpace = false; } 
     vector.reserve(1); 
     if (!haveSpace) throw new std::bad_alloc("Vector shows no space left"); 
     deque.push_back(something); 
} 

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

Теперь, когда это отложено, мое лучшее предположение было бы ... ваш компилятор не совместим ... как я уже упомянул в комментарии, C++ требует deque :: push_back, чтобы бросить bad_alloc. Если вы можете, удаляйтесь от этого компилятора (это основной материал, чтобы получить право)