Существует ли ограничение на количество новых выделений [] и delete [], прежде чем программа станет неэффективной?

Question

Я не уверен, задавалось ли это раньше, поэтому попробую.

У меня есть код для загрузки большого списка клиентов (200 тыс. Клиентов). Каждый клиент хранится в (в настоящее время) структуре фиксированного размера, которая содержит его имя, адрес и номер телефона следующим образом:

struct client {
    char name[80];
    char address[80];
    char phonenumber[80];
};

Как видите, размер этой структуры составляет 240 байт. Таким образом, 200 тыс. Клиентов заняли бы 48 МБ памяти. Очевидно, что преимуществами такой структуры является простота управления и создание «свободного списка» для утилизации клиентов. Однако если завтра мне потребуется загрузить 5M клиентов, это увеличит объем оперативной памяти до 1,2 ГБ.

Теперь, очевидно, в большинстве случаев имя, адрес и номер телефона клиента занимают намного меньше 80 байт, поэтому вместо вышеупомянутой структуры я подумал об использовании структуры как следующее:

struct client {
    char *name;
    char *address;
    char *phonenumber;
};

И затем * name, * address и * phonenumber указывают на динамически распределенные структуры с точным необходимым размером для хранения каждой информации.

Однако я подозреваю, что чем больше клиентов будет загружено таким образом, это значительно увеличит количество новых выделенных ресурсов [] и delete [], и мой вопрос в том, может ли это в какой-то момент повлиять на производительность, например, если я хочу внезапно удалить 500 КБ клиентов 1 МБ и заменить их на 350 КБ различных клиентов?

Я подозреваю, выделил ли я 1 МБ небольших буферов «переменной длины», если я «удалю» многие из них а затем хотите создать новые распределения, которые будут перерабатывать те, которые были удалены, не вызовет ли это сом накладные расходы, чтобы распределитель мог их найти?

Answer 1

Ответ заключается в том, что существуют некоторые накладные расходы (как с точки зрения циклов ЦП на выделение, так и в памяти учета на выделение) для создания множества небольших динамических c выделений и освобождений. Сколько накладных расходов будет во многом зависеть от того, как была реализована куча памяти вашей среды выполнения; однако, большинство современных / популярных сред выполнения имеют реализации кучи, которые были оптимизированы, чтобы быть достаточно эффективными. Есть некоторые статьи о том, как реализованы различные кучи ОС, о которых вы можете прочитать, чтобы получить представление о том, как они работают.

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

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

Как и другие предлагали в комментариях, явно не рекомендуется вызывать new и delete в C ++; почти всегда лучше использовать высокоуровневые структуры данных (например, std::string, std::map, std::vector, et c или даже соответствующий уровень базы данных), так как при этом сделать это очень сложно работа по проектированию будет сделана для вас, избавляя вас от необходимости заново открывать и решать все проблемы, с которыми другие уже сталкивались в прошлом. Например, std::string уже реализует оптимизацию коротких строк , которая позволяет хранить строки короче определенного количества байтов без отдельного выделения кучи; аналогично компромиссу, который вы пытаетесь создать в своих собственных проектах, за исключением того, что вы получаете эту оптимизацию «бесплатно», когда это уместно, просто используя std::string для хранения ваших строковых данных.

Answer 2

есть ли ограничение на количество новых выделенных ресурсов [] и delete [], прежде чем программа станет неэффективной?

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

Нет объективного ограничения на то, когда программа эффективна, а когда - неэффективна. Если вы пишете программу с жесткими требованиями в реальном времени, то у вас есть ограничение на то, когда ваша программа слишком неэффективна, но для других программ, то есть большинства программ, объективного ограничения на программа слишком неэффективна. Как правило, если выполнение вашей программы занимает слишком много времени, пользователь может считать ее неэффективной. «Слишком долго» субъективно для тех, кто использует программу.

Лучшее решение, чем вы предлагаете, - это использовать std::string участников. Теперь его размер может быть несколько кратным размеру указателя (~ 4 в зависимости от реализации), но (при условии достойной реализации) он делает magi c и избегает динамического выделения c, когда строка помещается в это пространство. Это экономит массу времени по сравнению с отдельным выделением для каждого и тонну пространства по сравнению с массивом на месте. Что еще более важно, оно не требует ручного управления памятью, подверженного ошибкам.

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