Различия

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

Ссылка на это сравнение

articles:c-trics-iv [2017/09/05 02:55] (текущий)
Строка 1: Строка 1:
 +====== c-trics-IV ======
 +<​sub>​{{c-trics-IV.odt|Original file}}</​sub>​
 +
 +====== сишные трюки от мыщъх'​а\\ (4й выпуск) ======
 +
 +крис касперски ака мыщъх, no-email
 +
 +**в этом, четвертом по счету выпуске,​ мы рассмотрим трюки так или иначе связанные с памятью:​ дефрагментируем кучу, разберемся как правильнее передавать переменные по ссылке или по значению и когда их нужно инициализировать,​ а когда нет.**
 +
 +===== дефрагментация кучи =====
 +
 +При интенсивном использовании кучи может сложиться такая ситуация,​ когда свободная память есть, но выделить ее не удается. Почему?​ Представим себе, что мы имеем 100 Мбайт свободной памяти в непрерывном блоке. Выделяем 10 блоков по 10 Мбайт,​ а затем освобождаем их через один, после чего пытаемся выделить блок размеров в 20 Мбайт,​ но… это не получатся! Несмотря на то, что мы имеем 50 Мбайт свободной памяти,​ эта память раздроблена на множество мелких кусочков. Вот потому-то некоторые и рекомендуют перезагружать Windows хотя бы раз в месяц.
 +
 +Почему же менеджер кучи не дефрагментирует память,​ переупорядочив блоки? Да потому,​ что, получив указатель на выделенный блок памяти,​ программа приобретает в свое владение целый регион,​ с которым может делать все, что угодно. В частности,​ сохранять указатели на ячейки внутри блока. Но менеджер кучи ничего не знает об этих указателях и потому не может трогать память.
 +
 +А давайте попробуем написать собственный дефрагментатор кучи! Это возможно (и совсем не сложно),​ если только наша программа придерживается определенных соглашений. В частности:​ адресует все ячейки внутри выделенного блока _только_ через базовый указатель,​ который в свою очередь является указателем на указатель. Непонятно?​ Ничего,​ несколько наглядных листингов все объяснят.
 +
 +Вот классический пример использования кучи:
 +
 +foo(char* p)
 +
 +{
 +
 +static char *b = p;
 +
 +
 +
 +}
 +
 +char *p, x; int n;
 +
 +
 +
 +p = malloc(BLOCK_SIZE);​
 +
 +x = p+n;
 +
 +foo(x);
 +
 +Листинг 1 пример классического использования кучи, делающий дефрагментацию динамической памяти невозможной
 +
 +Выделив блок памяти p, программа получает указатель x, ссылающийся на некоторую ячейку внутри блока и передает его функции foo, которая сохраняется в статической переменной b, что делает блок p совершенно неперемещаемым,​ поскольку переменная b жестко привязана к своей ячейке памяти и ничего не знает про какие-то там блоки.
 +
 +А вот другой вариант той же самой программы:​
 +
 +volatile char **p; int n;
 +
 +
 +
 +p = my_malloc(BLOCK_SIZE);​
 +
 +foo(p, n);
 +
 +Листинг 2 пример использования кучи, поддерживающий возможность дефргаментации динамической памяти в однопоточных программах
 +
 +В чем разница?​ Теперь функция my_malloc возвращает не указатель на выделенный блок, а указатель на переменную,​ хранящую указатель на выделенный блок. Функции fooпередается уже не эффективный адрес ячейки памяти,​ а указатель-на-указатель p и смещение нужной ячейки относительно начала блока. Функция foo (и все остальные функции) не могут, не имеют права, хранить эффективные адреса в статических переменных или передавать их кому-либо еще. Вместо этого они при каждом обращении к ячейке должны выполнять операцию (*p+n), причем перемененная p должна быть объявлена как volatile, что запретит компилятору помещать ее в регистр.
 +
 +Теперь наш менеджер кучи (представляющий собой надстройку над malloc) может беспрепятственно двигать блоки, высвобождая непрерывные регионы требуемой длинны. Для обеспечения когерентности и взаимной непротиворечивости дефргаментация должна осуществляться внутри вызова my_malloc, да и то, только в однопоточных программах. С многопоточными этот трюк не сработает,​ поскольку акт обращения к ячейкам памяти не является атомарным действием. Допустим,​ один поток вычислил эффективный адрес ячейки и только собрался к ней обратиться,​ как другой поток в это время передвинул блок на другое место! Следовательно,​ каждый поток должен иметь свою кучу, а передача данных от одного потока к другому обязана защищаться критическими секциями или другими средствами синхронизации.
 +
 +В итоге, мы получим более тормозной и громоздкий код, что есть минус. Но зато теперь можно забыть про фрагментацию кучи, что есть плюс.
 +
 +===== по ссылке или по значению =====
 +
 +Язык Си поддерживает два способа передачи переменных — по ссылке и по значению,​ порождая тем самым извечную проблему выбора. Программистское сообщество разбилось на два больших лагеря,​ отстаивающих свои взгляды на дизайн программирования,​ и ожесточенно воющих между собой.
 +
 +Один лагерь говорит:​ все, что помещается в регистр общего назначения (то есть, физически представляет собой байт, слово или двойное слово) передается по значению,​ остальное — по ссылке,​ потому что так гораздо быстрее и требует меньше памяти.
 +
 +Другой лагерь с этим категорически не согласен:​ кому сейчас нужна быстрота?​ А потребности в памяти всегда может удовлетворить новый DIMM. Передача переменных по ссылке потенциально опасна и вносит большую сумятицу,​ поскольку при передаче по значению функции передается копия переменной,​ которую она может модифицировать как угодно,​ не затрагивая оригинал. А вот при передаче по ссылке возникает угроза непреднамеренной порчи данных,​ кроме того при чтении листинга становится непонятно то ли мы просто передаем значение функции,​ то ли принимает через эту возвращенный результат.
 +
 +Формально,​ запретить модификацию переменной,​ переданной по ссылке можно через квалификатор const, однако,​ надежной такую защиту не назовешь,​ поскольку const легко обходится через преобразование типов (как преднамеренное,​ так и нет). С другой стороны,​ передавать большие объемы данных по значению смерти подобно,​ особенно в рекурсивных функциях или при глубоком объеме вложенности.
 +
 +Выход — передаем переменные по ссылке,​ для наглядности предварив их const, а на физическом уровне защитив от модификации вызовом VirtualProtect(,,​PAGE_READONLY,​). Естественно,​ при выходе из функции защиту необходимо восстановить. Пользователи коммерческих компиляторов (вроде MicrosoftVisualC++) вынуждены делать это вручную (что чревато ошибками),​ а вот GCC, бесплатно распространяемый в исходных текстах,​ позволяет свободно модифицировать пролог и эпилог каждой функции по своему усмотрению.
 +
 +Кстати говоря,​ здесь мы снова сталкиваемся с невозможностью реализации данного механизма в многопоточных программах,​ поскольку в то время пока одна функция "​защитила"​ переменную,​ никакая другая функция чужого потока не может ее менять,​ даже если ей это действительно необходимо. Одно из главных достоинств UNIX'​а как раз и заключается в том, что в нем потоки играют второстепенную роль и вообще говоря не слишком популярны. А вот в Windows… задачи синхронизации приходится решать вручную. Как говорится,​ создавая потоки,​ вы создаете себе проблемы,​ но это уже тема для другого разговора.
 +
 +===== инициализировать или нет =====
 +
 +Программисты (особенно начинающие) часто инициализируют то, что инициализируется само и принудительно обнулять его не нужно, хоть это и не вредит,​ но отнимает время как у процессора,​ так и у самого программиста.
 +
 +Статические и глобальные переменные всегда инициализируются нулями еще на стадии загрузки PE/ELF файла в память,​ причем эта инициализация обходится очень дешево (в смысле процессорного времени),​ поэтому массивы (особенно больше) лучше всего размещать в статических переменных. Правда,​ при этом функция становится нереентерабельной,​ то есть ее нельзя вызывать рекурсивно или одновременно из нескольких потоков (ох, опять эти потоки!). Кроме того, при повторном вызове функции статические переменные будут содержать значения,​ оставленные предыдущим вызовом и, если функцию планируется вызывать многократно,​ то инициализировать переменные все-таки придется.
 +
 +Память,​ выделенная функцией VirtualAlloc так же автоматически инициализируется нулями,​ о чем сказано в первом же абзаце документации ("//​Memory allocated by this function is ////​automatically////​initialized////​to////​zero////,​ ////​unless////​the////​MEM////​_////​RESET////​flag////​is////​set//"​),​ да только кто же ту документацию читает…
 +
 +Функция malloc не инициализирует выделяемую память (во всяком случае по Стандарту),​ но в реализации от Microsoft при выделении блоков от 512 Кб и выше она обращается к VirtualAlloc,​ в результате чего происходит неявная инициализация памяти. Правда,​ никаких гарантий,​ что поведение функции не изменится в следующих версиях у нас нет, так что пусть каждый решает сам — использовать ли ему эту недокументированную особенность или же свято придерживаться его величества Стандарта,​ в котором помимо malloc предусмотрена функция calloc, выделяющая инициализированную память. Надеюсь,​ никто не сморит,​ что "​p = calloc(BLOCK_SIZE);"​ намного короче и нагляднее чем "​p = malloc(BLOCK_SIZE);​ memset(p,​ 1, BLOCK_SIZE);",​ хотя по скорости выходит одно и то же, хотя Microsoft могла бы свободно избавиться от лишнего цикла инициализации,​ если блок памяти выделен VirtualAlloc,​ но — увы — она этого не сделала.
 +
 +Наконец,​ существуют ситуации (правда,​ их довольно немного),​ когда начальное значение переменной совершенно некритично и потому ее можно не инициализировать,​ пропуская протест компилятора мимо ушей. Вот, например,​ реализация "​пропеллера":​ "​printf("​%c\r","​-\\|/"​[z++ % 4]);" Совершенно очевидно,​ что инициализировать переменную z излишне,​ хоть это и влияет на начальное положение "​лопасти",​ но… кто же на него обращает внимание?​
 +
 +