Оптимизация размера памяти и производительности

Question

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

char* input = (char*)malloc(sizeof (char)* MAX_CHAR_INPUT_SIZE); 
scanf_s("%s", input, MAX_CHAR_INPUT_SIZE); 

Как вы можете видеть, если строка обеспечивается пользователем мала много памяти впустую. Моя единственная идея состоит в том, чтобы скопировать эту строку, после чтения, в нужный блок памяти, а затем освободить большую. Это хороший подход? (Я знаю, что это будет O (N)).

Также может кто-нибудь объяснить мне, как это решается на языках более высокого уровня? (например, C# Console.Read())

Answer 1

Если вы делаете это в цикле, то вы можете прочитать его на временный перед выделением памяти для конечной строки:

char input[MAX_CHAR_INPUT_SIZE]; 

scanf_s("%s", input, sizeof input); 

size_t input_size = strlen(input) + 1; 
char *input_final = malloc(input_size); 
memcpy(input_final, input, input_size); 

Таким образом, вы по-прежнему есть только один вызов malloc() на строку, но каждый раз выделяйте точно правильный размер.

Answer 2

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

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

Аналогичные работы для сред «управляемой памяти», таких как JVM и CLR (с любыми языками). Ознакомьтесь с этой статьей о высокопроизводительной торговой системе Java (подход тот же: предварительно распределите память, затем скопируйте широко, чтобы свести к минимуму совместное состояние): http://martinfowler.com/articles/lmax.html

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