Давненько у меня не было чисто айтишных постов. Надо как-то исправляться, не все же тут баловством заниматься, надо как-то и в профессиональном плане аудиторию развлекать...
Сделаю-ка я серию заметок про популярные структуры данных. А то работаем с ними каждый день, а как они внутри устроены не всегда понятно. И начнем мы с самого обычного массива. Да не простого, а 1С-ного, такого который не имеет жесткого размера.
В компьютере оно же как. Вот есть у него память, и когда нам надо какой-то кусок этой памяти под свои нужды задействовать, мы говорим системе "Дай нам N байт свободных, да так, чтоб подряд шли". Это и есть массив: область памяти с адресами по нарастанию, без дырок. И самая засада с этими массивами то, что надо заранее знать, сколько памяти потребуется. У Джоэла Спольски есть шикарная статья "
Назад к основам", ее надо прочитать обязательно, если хочешь называть себя программистом. Особенно, если ты программист на языке, в котором не надо заранее знать размеры массивов.
Итак, дала нам система кусок памяти, мы им пользуемся, а что если нам надо еще чуть-чуть добавить? А все, дудки. Сразу после твоего куска памяти уже есть какие-то занятые байты и они принадлежат другим переменным, тебе туда писать ничего нельзя. На самом деле можно, а если ты хакер - даже нужно, называется "переполнение буфера", и это самый простой способ взломать что-нибудь и выполнить там свой код (disclaimer: уголовно наказывается).
Но как же тогда быть, если выделенной памяти не хватило? Я же могу в 1С написать Массив.Добавить() сколько хочу раз и никто на меня не ругается... А это потому, что массив 1С внутри использует класс std::vector (или аналогичный, я исходников не видел, но палюбому так). Как же этому вектору удается раз за разом расширяться да так, чтобы байты подряд? А никакой магии нет, он просто выделяет в другом месте новый кусок памяти, побольше, а потом КОПИРУЕТ ВСЕ СО СТАРОГО МЕСТА НА НОВОЕ.
Я не пошутил, как только вы своим Массив.Добавить() потратили первоначальный буфер, весь ваш массив будет копироваться на новое, более просторное место в памяти, а старое место будет отдано назад системе, как свободное.
В Ява-мире это называется ArrayList, т.е. как бы расширяемый список, но на базе массива, чтоб байты - подряд.
А нафига вообще байты подряд? Мне не принципиально, пусть будут раскиданы по всей памяти, мне наплевать... Подвох в том, что камплюктер любит когда байты подряд, так он эффективно использует кеш и может быстро-быстро бегать по этому массиву. Если раскидать байты где попало, то ему придется бегать по всей памяти и собирать данные, прямо как по квартире с бардаком. Но если очень хочется, то так тоже можно, называется "Связный список" и о нем как-нибудь в другом посте.
Выводы:
* для коротких массивов с заранее известной длиной лучше выделять память заранее
* на фоне прочего быстродействия системы (запросов, записей в БД и т.п.) выигрыш будет копеечный, можно не париться.
* но знать, как оно внутри работает - нужно. На всякий случай.