🔖Минутка вопросов с собеседований
Однажды, на собесе меня спросили интересный вопрос, который сейчас мне кажется очевидным, но в то время я напрягся, и даже не помню, выдал ли верный ответ или нет.
Вопрос звучал так:
Вот есть у нас необходимость иметь поддержку в миллион сущностей, может быльше, точное число неизвестно. Как сделать хранение и обработку этих сущностей наиболее эффективно?
Перед тем как ответить, расскажу, чем обычный лист плох в этом плане.
Все дело в количестве, и том, как объекты хранятся в динамических листах. Напомню, что лист - это массив внутри. По умолчанию, массива нет, он создается при первом добавлении элемента, первоначальная емкость - 4 записи. При внесении 5го элемента, создаётся новый массив в два раза больше первого и туда переносятся 4 старых объекта, плюс пятый. И так далее для 8, 16 и т.д. Каждый новый массив - это новая аллокация, удвоение объема. На малых объемах это незаметно, а вот когда выходим начисла с шестью нулями - тяжеловато.
Но можно же создать массив с заданным объемом! Скажете вы и будете правы! Но и тут нас ждёт подвох: по ТЗ массив динамический, так что риск просадок во время копирования все еще присутствует.
Ответ, который от меня ожидали: использовать массив массивов (или чанков), где чанк - кучка массивов, объединенных каким-то правилом.
Такой подход используется в Ecs, кстати, в том числе и в дотсах, хотя там немножк сложнее чем просто чанки. Сущности хранятся в чанках, размер каждого чанка определен.
Плюсы: рост массива не подразумевает копирование, а подразумевает создание нового "чанка" с указанной размерностью и всьо
Нюансы:
• Как я уже сказал, такой подход используется в ECS, но не только в расширении массивов дело. Дело в том, что для максимальной скорости обработки данных процессор помещает кусочки себе в кеш L1, L2 вот это вот. Кеш маленький, зачастую 32Кб, поэтому быстрее всего обрабатывается такой чанк, элементы которого в куче (памяти имеется ввиду) лежит последовательно, и при этом не выходит за границы размера кеша процессора. Поэтому имеет смысл выбирать размерность таких чанков с опорой на размер кеша процессора целевой аудитории.
• Но и это еще не все! Как я и сказал, элементы на куче должны располагаться плотничком для максимальной эффективности. А значит, речь идет о типе данных значение (Value Type). Потому что если в массиве будет лежать 1000 ссылок, то это не имеет смысла в вопросе скорости, все равно не получится закешировать весь объем данных в L1/L2, потому что сами объекты раскиданы по куче.
#полезное
