Почему массивы C не отслеживают их длину?

Что послужило причиной отсутствия явного хранения длины массива в массиве C?

На мой взгляд, есть веские причины для этого, но не очень много в поддержку стандарта (C89). Например:

1. Наличие длины в буфере может предотвратить переполнение буфера.
2. Стиль Java arr.lengthпонятен и избавляет программиста от необходимости поддерживать много ints в стеке при работе с несколькими массивами.
3. Параметры функции становятся более убедительными.

Но, пожалуй, самая мотивирующая причина, на мой взгляд, заключается в том, что обычно не сохраняется место без сохранения длины. Рискну сказать, что в большинстве случаев использование массивов связано с динамическим распределением. Правда, могут быть случаи, когда люди используют массив, выделенный в стеке, но это всего лишь один вызов функции * - стек может обрабатывать дополнительно 4 или 8 байтов.

Поскольку диспетчер кучи должен отслеживать размер свободного блока, используемого динамически размещаемым массивом, в любом случае, почему бы не сделать эту информацию пригодной для использования (и добавить дополнительное правило, проверенное во время компиляции), что нельзя манипулировать длиной явно, если не будет люблю стрелять себе в ногу).

Единственное , что я могу думать на другой стороне, что ни трекинга длина не может быть сделано компиляторы проще, но не , что гораздо проще.

* Технически, можно написать некую рекурсивную функцию с массивом с автоматическим хранением, и в этом (очень сложном) случае сохранение длины может действительно привести к эффективному использованию пространства.

Массивы C отслеживают их длину, так как длина массива является статическим свойством:

int xs[42];  /* a 42-element array */

Обычно вы не можете запросить эту длину, но вам это не нужно, потому что она все равно статическая - просто объявите макрос XS_LENGTHдля длины, и все готово.

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

Другое дело, что указатели не нуждаются в хранении, кроме самого адреса памяти. C позволяет нам приводить целые числа к указателям, указатели на другие указатели и обрабатывать указатели, как если бы они были массивами. Делая это, C не настолько безумен, чтобы создать некоторую длину массива, но, похоже, верит в девиз Spiderman: с большой силой, мы надеемся, программист выполнит большую ответственность за отслеживание длин и переполнений.

Многое из этого было связано с компьютерами, доступными в то время. Мало того, что скомпилированная программа должна была работать на компьютере с ограниченными ресурсами, но, что еще более важно, сам компилятор должен был работать на этих машинах. В то время, когда Томпсон разработал C, он использовал PDP-7 с 8 КБ ОЗУ. Сложные языковые функции, которые не имели непосредственного аналога в реальном машинном коде, просто не были включены в язык.

Внимательное чтение истории C дает более глубокое понимание вышесказанного, но это не было полностью результатом ограничений машины, которые у них были:

Более того, язык (C) демонстрирует значительную мощность для описания важных понятий, например, векторов, длина которых изменяется во время выполнения, с несколькими базовыми правилами и соглашениями. ... Интересно сравнить подход Си с подходом двух почти одновременных языков: Алгол 68 и Паскаль [Йенсен 74]. Массивы в Algol 68 либо имеют фиксированные границы, либо являются «гибкими»: требуется значительный механизм как в определении языка, так и в компиляторах, для размещения гибких массивов (и не все компиляторы полностью их реализуют). Оригинальный Pascal имел только фиксированный размер массивы и строки, и это оказалось ограничивающим [Kernighan 81].

С-массивы по своей природе более мощные. Добавление к ним границ ограничивает то, для чего программист может их использовать. Такие ограничения могут быть полезны для программистов, но обязательно также являются ограничивающими.

Назад в тот день, когда был создан C, и дополнительные 4 байта пространства для каждой строки, независимо от того, насколько коротким был бы пустая трата!

Есть еще одна проблема - помните, что C не является объектно-ориентированным, поэтому, если вы делаете префикс длины для всех строк, он должен быть определен как внутренний тип компилятора, а не как a char*. Если бы это был специальный тип, то вы не смогли бы сравнить строку с константной строкой, то есть:

String x = "hello";
if (strcmp(x, "hello") == 0) 
  exit;

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

В конечном счете, я думаю, что они просто не выбрали путь префикса длины в отличие от, скажем, Паскаля.

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

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

void ClearTwoElements(int *ptr)
{
  ptr[-2] = 0;
  ptr[2] = 0;
}
void blah(void)
{
  static int foo[10] = {1,2,3,4,5,6,7,8,9,10};
  ClearTwoElements(foo+2);
  ClearTwoElements(foo+7);
  ClearTwoElements(foo+1);
  ClearTwoElements(foo+8);
}

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

void ClearTwoElements(int *ptr)
{
  int* array_end = ARRAY_END(ptr);
  if ((array_end - ARRAY_BASE(ptr)) < 10 ||
      (ARRAY_BASE(ptr)+4) <= ADDRESS(ptr) ||          
      (array_end - 4) < ADDRESS(ptr)))
    trap();
  *(ADDRESS(ptr) - 4) = 0;
  *(ADDRESS(ptr) + 4) = 0;
}

Обратите внимание, что вызывающий метод, в общем, вполне законно может передать указатель на начало массива или последний элемент метода; только если метод попытается получить доступ к элементам, которые выходят за пределы переданного массива, такие указатели вызовут какие-либо проблемы. Следовательно, вызываемый метод должен был бы сначала убедиться, что массив был достаточно большим, чтобы арифметика указателя для проверки его аргументов сама по себе не выходила за пределы, а затем выполнить некоторые вычисления указателя для проверки аргументов. Время, потраченное на такую ​​проверку, вероятно, превысит затраты, потраченные на выполнение любой реальной работы. Кроме того, метод мог бы быть более эффективным, если бы он был написан и вызван:

void ClearTwoElements(int arr[], int index)
{
  arr[index-2] = 0;
  arr[index+2] = 0;
}
void blah(void)
{
  static int foo[10] = {1,2,3,4,5,6,7,8,9,10};
  ClearTwoElements(foo,2);
  ClearTwoElements(foo,7);
  ClearTwoElements(foo,1);
  ClearTwoElements(foo,8);
}

Идея типа, который объединяет что-то для идентификации объекта с чем-то для идентификации его части, является хорошей. Однако указатель в стиле C быстрее, если нет необходимости выполнять проверку.

Одно из фундаментальных отличий между C и большинством других языков 3-го поколения и всеми более свежими языками, которые мне известны, заключается в том, что C не был разработан, чтобы сделать жизнь программиста проще или безопаснее. Он был разработан с расчетом на то, что программист знает, что делает, и хочет делать именно и только это. Он не делает ничего «за кадром», поэтому вы не получите никаких сюрпризов. Даже оптимизация на уровне компилятора не обязательна (если вы не используете компилятор Microsoft).

Если программист хочет написать проверку границ в своем коде, C делает это достаточно просто, но программист должен решить заплатить соответствующую цену с точки зрения пространства, сложности и производительности. Несмотря на то, что я не использовал его в гневе в течение многих лет, я все еще использую его при обучении программированию, чтобы понять концепцию принятия решений на основе ограничений. По сути, это означает, что вы можете делать все, что захотите, но каждое принятое вами решение имеет цену, о которой вы должны знать. Это становится еще более важным, когда вы начинаете говорить другим, что вы хотите, чтобы их программы делали.

Краткий ответ:

Поскольку C является языком программирования низкого уровня , он ожидает, что вы сами позаботитесь об этих проблемах, но это добавляет большую гибкость в том, как именно вы его реализуете.

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

retval = my_func(my_array, my_array_length);

Или вы можете использовать структуру с указателем и длиной, или любое другое решение.

Язык более высокого уровня сделает это за вас как часть типа массива. В Си вы несете ответственность за выполнение этого самостоятельно, а также за гибкость выбора того, как это сделать. И если весь код, который вы пишете, уже знает длину массива, вам вообще не нужно передавать длину как переменную.

Очевидный недостаток заключается в том, что без проверки внутренних границ массивов, передаваемых в виде указателей, вы можете создавать опасный код, но это природа языков низкого уровня / систем и компромисса, который они дают.

Проблема дополнительного хранилища - это проблема, но, на мой взгляд, незначительная. В конце концов, в большинстве случаев вам все равно придется отслеживать длину, хотя amon подчеркнул, что ее часто можно отслеживать статически.

Большая проблема заключается в том, где хранить длину и как долго ее делать. Нет одного места, которое работает во всех ситуациях. Вы можете сказать, просто сохранить длину в памяти непосредственно перед данными. Что если массив не указывает на память, а что-то вроде буфера UART?

Отсутствие длины позволяет программисту создавать свои собственные абстракции для соответствующей ситуации, и есть множество готовых библиотек, доступных для случая общего назначения. Реальный вопрос в том, почему эти абстракции не используются в приложениях, чувствительных к безопасности?

Из развития языка C :

Кажется, что структуры должны отображаться интуитивно понятным образом в память машины, но в структуре, содержащей массив, нет подходящего места для хранения указателя, содержащего основание массива, или какого-либо удобного способа упорядочить его. инициализируется. Например, записи каталога ранних систем Unix могут быть описаны в C как

struct {
    int inumber;
    char    name[14];
};

Я хотел, чтобы структура не просто характеризовала абстрактный объект, но и описывала набор битов, которые могут быть прочитаны из каталога. Где компилятор может скрыть указатель на nameто, что требует семантика? Даже если бы структуры рассматривались более абстрактно, а пространство для указателей могло бы быть каким-то образом скрыто, как я мог бы решить техническую проблему правильной инициализации этих указателей при выделении сложного объекта, возможно, такого, который указывал структуры, содержащие массивы, содержащие структуры на произвольную глубину?

Решение представляет собой решающий скачок в эволюционной цепочке между типизированным BCPL и типизированным C. Это устраняет материализацию указателя в хранилище и вместо этого вызывает создание указателя, когда имя массива упоминается в выражении. Правило, которое сохраняется в сегодняшнем C, состоит в том, что значения типа массива преобразуются, когда они появляются в выражениях, в указатели на первый из объектов, составляющих массив.

В этом отрывке объясняется, почему выражения массивов в большинстве случаев распадаются на указатели, но те же соображения применимы к тому, почему длина массива не сохраняется в самом массиве; если вы хотите, чтобы между определением типа и его представлением в памяти было однозначное соответствие (как это сделал Ричи), тогда нет подходящего места для хранения этих метаданных.

Кроме того, подумайте о многомерных массивах; где бы вы хранили метаданные длины для каждого измерения, чтобы вы могли пройти через массив с чем-то вроде

T *p = &a[0][0];

for ( size_t i = 0; i < rows; i++ )
  for ( size_t j = 0; j < cols; j++ )
    do_something_with( *p++ );

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

Следующий код копирует некоторые данные из src в dst кусками типа int, не зная, что это на самом деле символьная строка.

char src[] = "Hello, world";
char dst[1024];
int *my_array = src; /* What? Compiler warning, but the code is valid. */
int *other_array = dst;
int i;
for (i = 0; i <= sizeof(src)/sizeof(int); i++)
    other_array[i] = my_array[i]; /* Oh well, we've copied some extra bytes */
printf("%s\n", dst);

Почему C настолько упрощен, что не имеет правильных массивов? Я не знаю правильного ответа на этот новый вопрос. Но некоторые люди часто говорят, что C - просто (несколько) более читаемый и портативный ассемблер.