Ответ на задачку №5

Ответ на задачку №5.

Совсем забыл, что у меня одна задача осталась без ответа больше положенного срока. Видимо потому, что на неё дали ответ практически мгновенно - то ли она оказалась простой (а значит - не интересной), то ли просто ко мне зашли более опытные люди :)

В любом случае, я умудрился про неё благополучно забыть.

Итак, напомню, что у нас есть два почти одинаковых куска кода. Код в цикле формирует строки и заталкивает их в список. Если в коде сделать изменение: добавить явное копирование строки, то новый вариант будет значительнее экономичнее по расходу памяти.

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

На самом деле, как уже заметили в комментариях, дело здесь в повторном использовании строки.

В первом куске кода строка S добавляется в список. Что это значит? А то, что сама строка не копируется - у неё просто увеличивается счётчик ссылок. Когда приходит следующая итерация, счётчик старой строки уменьшается до 1, поскольку S отвязывается от неё для новой работы. Что означает, что в списке у нас будет сидеть ровно та же строка, что и была в цикле.

Во втором же случае с нашей строки S снимается копия (вызовом UniqueString) и уже она записывается в список. В этот момент до конца итерации у нас в памяти будет висеть две копии одной строки (S и копия, которую мы заносим в список). Сама строка S прекращает своё существование на следующей итерации.

В чём же разница, если в обоих случаях в списке будут сидеть одни и те же строки, которые уникальны. Пусть даже и получены слегка по-разному?

Всё дело в том, как формируется строка S: она формируется приписыванием к ней частей. Иными словами, её длина постоянно увеличивается в цикле. Как присходит увеличение длины? Если вы создаёте новую строку (выделяете новый блок памяти), то логика менеджера памяти проста - создать новый блок памяти указанного размера (это не совсем точное описание, но здесь достаточно и такого). Если же вы меняете длину существующей строки (увеличиваете размер блока памяти), то менеджер памяти увеличивает блок памяти не до указанного вами размера, а несколько больше. Хотя вы этого не видите - для вас памяти было выделено столько, сколько вы запросили. Но под капотом языка памяти было выделено больше.

Почему так происходит? А делается это как раз для оптимизации таких циклов. Представьте что будет, если вы в цикле будете прибавлять к строке по одному символу. На каждой итерации менеджер памяти будет вынужден изменять размер блока памяти - а ведь это не такая тривиальная операция и она может занимать много времени. Но если вы заранее выделите памяти больше, чем необходимо - то ещё кучу итераций менеджер памяти может просто ничего не делать: ведь память уже выделена. Он просто обновит поля учёта и вернёт тебе управление: "да, я увеличил твою строку на 1 символ" (да, это ложь, но ты об этом не знаешь!).

Иными словами, это оптимизация вида "trade size for speed". Мы платим увеличенным расходом памяти за увеличение скорости выполнения программы. Очередной инженерный компромисс. Кстати, по мотивам недавнего поста: перерасход памяти в два раза - это нормальное явление.

Ну, а теперь становится видно, почему отличается поведение этих кусков кода: ведь когда второй код создаёт копию строки, то это будет создание новой строки, а, значит, менеджер памяти выделит под неё столько памяти, сколько запрошено, без запаса. И эту строку мы занесём в список. Первый же код явно копии не создаёт и заносит в список ту же строку, что осталась у него после цикла формирования строки. А там мы постоянно изменяли размер строки, поэтому эта строка будет иметь реальный размер больше логического - потому что менеджер памяти перестраховался и увеличил размер с запасом.

Такая вот несложная задачка, но с длинным объяснением.

Примечание: смыслом задачи было не указать точные цифры, а угадать причины поведения. Это была задача на телепатию, а не точный научный подход.