Лучшие контейнеры STL, чтобы избежать фрагментации кучи

Question

У меня есть программа, которая анализирует 150 000 файлов. Valgrind сообщает об утечке памяти, но программа замедляется со временем.

Некоторые из проблем были связаны с использованием std :: string слишком часто, а mktime - слишком много времени. (см. C++ slows over time reading 70,000 files)

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

Я прочитал различные блок-схемы по плюсам и минусам различных контейнеров STL, но я не совсем понял это.

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

fileList.clear() 
scan all disks and build "fileList", a std::set of file paths matching a pattern. 

// filepaths are named by date, eg 20160530.051000, so are intrinsically ordered 

foreach(filePath in fileList) 
{ 
    if (alreadyHaveFileDetails(filePath)) 
     continue; 

    // otherwise 
    collect file details into a fileInfoStruct; // like size, contents, mod 

    fileInfoMap[time_t date] = fileInfoStruct; 
} 

// fileInfoMap is ordered collection of information structs of about 100,000 files 

// traverse the list in order 
foreach (fileInfo in fileInfoMap) 
{ 
    if (meetsCondition(fileInfo)) 
    { 
     TEventInfo event = makeEventInfo() 
     eventList.push_back(event); 
    } 
} 

И вышеприведенная последовательность повторяется навсегда.

Так что для выбора контейнеров, я использовал (или потребность):

fileList - список уникальных строк, содержащих 150000 имен путей.
Я выбрал std :: set, потому что он автоматически обрабатывает дубликаты и автоматически поддерживает порядок сортировки. Не произвольный доступ, только добавляйте записи, сортируйте их (вручную или автоматически) и перебирайте их.

fileInfoMap - массив структур, заданных временной меткой time_t, соответствующей дате файла. Я выбрал std :: map. Он также имел бы 150 000 записей, поэтому занимает много памяти. Нет случайного доступа, только добавьте записи в один конец. Необходимо перебирать их и, при необходимости, удалять записи из середины.

eventList - небольшой список структур «событий», например 50 наименований. Я выбрал std :: vector. Не знаю, почему на самом деле. Нет произвольного доступа, только добавьте записи в один конец, а затем итерации по коллекции.

Я довольно новичок в C++. Спасибо за внимание.

Answer 1

О управлении памятью, контейнер относится к двум большим семействам: один, который выделяет все элементы вместе, и тот, который выделяет элементы отдельно.

вектор и deque принадлежат к первому семейству, перечню, множеству и карте ко второму.

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

Один из способов избежать проблемы - использовать vector s, используя «reserve», чтобы оживить память, чтобы уменьшить перемещение и сохранить данные, отсортированные при вставке.

Другой способ - использовать «контейнер на основе ссылок» (например, список, набор и т. Д.), Предоставляя им распределитель, который выделяет память из более крупных блоков, перерабатывая их вместо вызова raw malloc/free для каждого отдельного элемента insert/remove ,

Дайте взглянуть на std::allocator

Вы можете легко написать аллокатор, выводя из станда :: распределителя и переопределения функции allocate/deallocate добавляющей вся необходимой логику, и переходя yourallocator в качестве необязательного параметра шаблона контейнера вам понравится использовать.