Почему программисты C часто выделяют строки (массивы символов) по двум причинам?
Вы часто видите...
char str[128]
char str[512]
char str[2048]
Реже вы видите...
char str[100]
char str[500]
char str[2000]
Это почему?
Я понимаю, что ответ будет включать память, адресуемую в двоичном формате... Но почему мы не часто видим char str[384], что составляет 128 + 256 (несколько из двух).
Почему кратные два не используются? Почему программисты C используют две возможности?
Для этого нет веской причины, за исключением некоторых очень редких случаев.
Чтобы развенчать наиболее распространенный аргумент: он помогает распределителю памяти избегать фрагментации.
Чаще всего этого не будет. Если вы выделите - скажем - 256 байт, то распределитель памяти добавит дополнительное пространство для его внутреннего управления и домашнего хозяйства. Таким образом, ваше распределение внутренне больше. Два 256 буфера имеют тот же размер, что и 512-байтовый буфер? Не правда.
Для производительности это может даже нанести вред, так как работает кэширование CPU.
Допустим, вам нужны N буферов определенного размера, которые вы можете объявить так:
char buffer[N][256];
Теперь каждый buffer[0] в buffer[N-1] имеет одинаковые младшие значащие биты в своем адресе, и эти биты используются для выделения строк кеша. Первые байты ваших буферов занимают одно и то же место в кэше вашего процессора.
Если вы выполняете вычисления первых нескольких байтов каждого буфера снова и снова, вы не увидите большого ускорения от кеша первого уровня.
Если, с другой стороны, вы бы объявили их следующим образом:
char buffer[N][300];
Отдельные буферы не имеют одинаковых наименее значимых бит в адресе, и кеш первого уровня может полностью использовать его.
Многие люди уже столкнулись с этой проблемой, например, см. Здесь этот вопрос: Матричное умножение: небольшая разница в размере матрицы, большая разница в таймингах
Существует несколько законных вариантов использования для двух размеров буфера. Если вы пишете свой собственный распределитель памяти, например, вы хотите управлять своей необработанной памятью в размерах, равных размеру страницы операционной системы. Или у вас могут быть аппаратные ограничения, которые заставляют вас использовать цифры из двух чисел (текстуры графического процессора и т.д.).
Интересный вопрос. Блоки размеров 2 ^ k лучше подходят, когда управление памятью ОС использует технику выделения памяти Buddy. Этот метод связан с фрагментацией распределений. https://en.wikipedia.org/wiki/Buddy_memory_allocation
Эта система распределения выполняет выравнивание блока с мощностью размера 2. Но это используется для распределения кучи.
int * array = (int*) malloc(sizeof(int)*512); // OS manages heap memory allocation
Когда буфер выделяется в стеке, нет необходимости делать выравнивание блока.
int buffer[512]; // stack allocation
Я думаю, что нет причин делать размеры полномочий 2.
Это делается для того, чтобы свести к минимуму количество маленьких блоков памяти, которые слишком малы для использования во что угодно, но нужно ходить, когда программа выделяет или освобождает память. Классическое объяснение из блога Джоэла Спольскиса, все это было в 2001 году:
Смарт-программисты минимизируют потенциальное распределение malloc, всегда выделяя блоки памяти, размер которых равен 2. Вы знаете, 4 байта, 8 байт, 16 байт, 18446744073709551616 байт и т.д. По причинам, которые должны быть интуитивными для любого, кто играет с Lego, это минимизирует количество странной фрагментации, которая продолжается в свободной цепочке. Хотя может показаться, что это пространство для отходов, также легко увидеть, как он никогда не тратит больше 50% пространства. Таким образом, ваша программа использует не более чем вдвое больше памяти, чем требуется, что не так уж важно.
До этого было много других обсуждений реализаций памяти-кучи, в том числе Дональдом Кнутом в "Искусстве компьютерного программирования". Не все обязательно согласятся с этим советом, но именно поэтому люди это делают.
Сама система использует полномочия 2 для установки различных ограничений. Например, максимальное выделение для длины имени файла может быть 256 или 32768. Размер страницы диска равен 2 и т.д.
Нам часто приходится учитывать эти системные ограничения и использовать те же полномочия 2.
Но если вам нужно всего 257 байт, не превышайте выделение 512 байт. Некоторые программисты используют полномочия 2 для установки ограничений для ввода пользователем. Это может смутить пользователя. Это имело некоторые преимущества на старых компьютерах, но не сейчас.
В других случаях мы используем распределения, которые являются случайными большими. Например, мы могли бы использовать 1000 или 1024 для чтения одной строки текста, потому что мы не знаем, сколько времени занимает вход. Это плохое программирование в любом случае. Это не имеет значения, если в этом случае выделение равно 1000 или 1024.