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

77

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

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

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

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

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

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

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

VF1
источник
6
Я полагаю, что можно утверждать, что, когда C включал использование структур в качестве параметров и типов возвращаемых значений, он должен был включать синтаксический сахар для «векторов» (или любого другого имени), который был бы ниже struct с длиной и либо массивом, либо указателем на массив. , Поддержка на уровне языка для этой общей конструкции (также когда она передается как отдельные аргументы, а не как одна структура) спасла бы бесчисленные ошибки и упростила бы стандартную библиотеку.
Hyde
3
Вы также можете найти « Почему Паскаль не мой любимый язык программирования», раздел 2.1, чтобы понять это.
34
Хотя у всех остальных ответов есть некоторые интересные моменты, я думаю, суть в том, что C был написан так, что программисты на ассемблере могли бы писать код проще и сделать его переносимым. Имея это в виду, наличие длины массива, сохраненного в массиве автоматически, было бы неприятностью, а не недостатком (как это было бы при других приятных желаниях покрывать конфеты). Эти функции кажутся хорошими в наше время, но в те времена было действительно трудно втиснуть еще один байт программы или данных в вашу систему. Неэффективное использование памяти серьезно ограничило бы принятие С.
Данк
6
На настоящую часть вашего ответа уже много раз отвечали так, как я бы это сделал, но я могу выделить другой момент: «Почему нельзя измерить размер malloc()редактируемой области переносимым способом?» Это то, что заставляет меня удивляться несколько раз.
glglgl
5
Голосование возобновить. Где-то есть причина, даже если это просто «K & R не думал об этом».
Теластин

Ответы:

106

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

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

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

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

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

Амон
источник
13
Я думаю, вы хотите сказать, если я не ошибаюсь, что компиляторы C отслеживают длину статического массива. Но это бесполезно для функций, которые просто получают указатель.
VF1
25
@ VF1 да. Но важно то, что массивы и указатели - это разные вещи в Си . Предполагая, что вы не используете какие-либо расширения компилятора, вы, как правило, не можете передать сам массив в функцию, но вы можете передать указатель и проиндексировать указатель, как если бы это был массив. Вы эффективно жалуетесь, что указатели не имеют длины. Вы должны жаловаться, что массивы нельзя передавать в качестве аргументов функции или что массивы неявно уменьшаются до указателей.
Амон
37
«Обычно вы не можете запросить эту длину» - на самом деле вы можете, это оператор sizeof - sizeof (xs) вернет 168, предполагая, что int имеет длину четыре байта. Чтобы получить 42, выполните: sizeof (xs) / sizeof (int)
tcrosley
15
@tcrosley Это работает только в рамках объявления массива - попробуйте передать xs в качестве параметра другой функции, а затем посмотрите, что дает sizeof (xs) ...
Гвин Эванс,
26
@GwynEvans еще раз: указатели не являются массивами. Поэтому, если вы «передаете массив как параметр другой функции», вы передаете не массив, а указатель. Утверждение, что sizeof(xs)где xsнаходится массив, будет чем-то другим в другой области видимости, является явно ложным, потому что структура C не позволяет массивам покидать их область видимости. Если sizeof(xs)где xsмассив отличается от того, sizeof(xs)где xsуказатель, это неудивительно, потому что вы сравниваете яблоки с апельсинами .
Амон
38

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

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

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

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

Адам Дэвис
источник
4
Это довольно много гвоздей оригинальный вопрос. Это и тот факт, что C держался намеренно «легким прикосновением», когда речь шла о проверке того, что делал программист, как о части привлекательности для написания операционных систем.
ClickRick
5
Отличная ссылка, они также явно изменили хранение длины строк, чтобы использовать разделитель to avoid the limitation on the length of a string caused by holding the count in an 8- or 9-bit slot, and partly because maintaining the count seemed, in our experience, less convenient than using a terminator- ну, очень много для этого :-)
Voo
5
Неопределенные массивы также подходят для подхода «голый металл» языка C. Помните, что книга K & R C содержит менее 300 страниц с руководством по языку, справочником и списком стандартных вызовов. Моя книга о
регулярных выражениях
22

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

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

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

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

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

gbjbaanb
источник
10
Проверка границ также требует времени. Тривиально в сегодняшнем выражении, но то, на что люди обращали внимание, когда заботились о 4 байтах.
Gort the Robot
18
@StevenBurnap: это не так тривиально даже сегодня, если вы находитесь во внутреннем цикле, который проходит по каждому пикселю изображения размером 200 МБ. В общем, если вы пишете на C, вы хотите идти быстро и не хотите тратить время на бесполезную проверку границ на каждой итерации, когда ваш forцикл уже настроен на соблюдение границ.
Matteo Italia
4
@ VF1 «назад в день» вполне могло бы быть два байта (DEC PDP / 11 кто-нибудь?)
ClickRick
7
Это не просто "назад в день". Для программного обеспечения, на которое ориентирован C как «переносимый язык ассемблера», такого как ядра операционной системы, драйверы устройств, встроенное программное обеспечение реального времени и т. Д. трата полдюжины инструкций по проверке границ имеет значение, и во многих случаях вам нужно быть «вне границ» (как вы можете написать отладчик, если не можете получить произвольный доступ к хранилищу других программ?).
Джеймс Андерсон
3
Это на самом деле довольно слабый аргумент, учитывая, что у BCPL аргументы были посчитаны. Точно так же, как Паскаль, хотя это было ограничено 1 словом, как правило, только 8 или 9 битами, что было немного ограничивающим (это также исключает возможность совместного использования частей строк, хотя эта оптимизация, вероятно, была слишком продвинутой в то время). И объявление строки как структуры с длиной, за которой следует массив, на самом деле не требует специальной поддержки компилятора ..
Voo
11

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

MSalters
источник
6
«Дизайн был бы другим» - это не причина, чтобы дизайн был другим.
VF1
7
@ VF1: Вы когда-нибудь программировали на Стандартном Паскале? Способность C быть достаточно гибким с массивами была огромным улучшением по сравнению со сборкой (никакой безопасности) и первым поколением безопасных типов языков (избыточная безопасность типов, включая точные границы массивов)
MSalters
5
Эта способность нарезать массив действительно является весомым аргументом для дизайна C89.
Хакеры старой школы Фортрана также хорошо использовали это свойство (хотя оно требует передачи фрагмента в массив на Фортране). Запутывает и болезненно программирует или отлаживает, но быстро и элегантно работает.
dmckee
3
Есть одна интересная альтернатива дизайна, которая позволяет нарезку: не храните длину вместе с массивами. Для любого указателя на массив сохраните длину с указателем. (Когда у вас есть только реальный массив C, размер является константой времени компиляции и доступен для компилятора.) Он занимает больше места, но позволяет разрезать, сохраняя длину. Rust делает это для &[T]типов, например.
8

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

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 быстрее, если нет необходимости выполнять проверку.

Supercat
источник
Если бы у массивов был размер среды выполнения, то указатель на массив принципиально отличался бы от указателя на элемент массива. Последние могут вообще не быть конвертируемыми в прежние (без создания нового массива). []Синтаксис может все еще существовать для указателей, но он будет отличаться от этих гипотетических «реальных» массивов, и описанная вами проблема, вероятно, не будет существовать.
Hyde
@hyde: Вопрос в том, следует ли разрешать арифметику для указателей, базовый адрес объекта которых неизвестен. Также я забыл еще одну сложность: массивы внутри структур. Размышляя об этом, я не уверен, что найдется какой-либо тип указателя, который мог бы указывать на массив, хранящийся в структуре, не требуя, чтобы каждый указатель включал не только адрес самого указателя, но также верхний и нижний правовые диапазоны, к которым он может получить доступ.
суперкат
Точка пересечения Я думаю, что это все еще сводится к ответу Амона, хотя.
VF1
Вопрос задает насчет массивов. Указатель является адресом памяти и не будет меняться в зависимости от предпосылки вопроса, насколько он понимает намерение. Массивы получат длину, указатели останутся неизменными (за исключением того, что указатель на массив должен быть новым, отличным, уникальным типом, очень похожим на указатель на структуру).
Hyde
@hyde: если достаточно изменить семантику языка, возможно, что массивы будут иметь соответствующую длину, хотя массивы, хранящиеся в структурах, будут представлять определенные трудности. При такой семантике проверка границ массива будет полезна только в том случае, если такая же проверка применяется к указателям на элементы массива.
суперкат
7

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

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

Пол Смит
источник
3
C был не столько «разработан», сколько развивался. Первоначально объявление вроде int f[5];бы не создавалось fкак массив из пяти элементов; вместо этого это было эквивалентно int CANT_ACCESS_BY_NAME[5]; int *f = CANT_ACCESS_BY_NAME;. Предыдущее объявление может быть обработано без необходимости «понимать» время массива компилятором; он просто должен был вывести директиву ассемблера для выделения пространства и затем мог забыть, что fкогда-либо имел какое-либо отношение к массиву. Непоследовательное поведение типов массивов проистекает из этого.
суперкат
1
Оказывается, что никто из программистов не знает, что они делают в той степени, в которой это требуется для C.
CodesInChaos
7

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

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

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

retval = my_func(my_array, my_array_length);

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

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

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

thomasrutter
источник
1
+1 «И если весь код, который вы пишете, уже знает длину массива, вам вообще не нужно передавать длину как переменную».
林果 at
Если бы только указатель + структура длины были запечены в язык и стандартную библиотеку. Так много дыр в безопасности можно было бы избежать.
CodesInChaos
Тогда это не был бы C. Есть другие языки, которые делают это. С тебя низкий уровень.
Томасруттер
C был изобретен как низкоуровневый язык программирования, и многие диалекты все еще поддерживают низкоуровневое программирование, но многие авторы компиляторов предпочитают диалекты, которые на самом деле нельзя назвать языками низкого уровня. Они допускают и даже требуют низкоуровневый синтаксис, но затем пытаются вывести высокоуровневые конструкции, поведение которых может не соответствовать семантике, подразумеваемой синтаксисом.
суперкат
5

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

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

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

Карл Билефельдт
источник
1
You might say just store the length in the memory just before the data. What if the array isn't pointing to memory, but something like a UART buffer?Не могли бы вы объяснить это немного больше? Кроме того, это может случиться слишком часто или это просто редкий случай?
Махди
Если бы я это разработал, аргумент функции, записанный как T[], не был бы эквивалентен, T*а скорее передавал бы указатель и размер функции. Массивы фиксированного размера могут распадаться на такой срез массива, вместо того, чтобы распадаться на указатели, как они делают в C. Основное преимущество этого подхода не в том, что он сам по себе безопасен, но это соглашение, на котором все, включая стандартную библиотеку, может строить.
CodesInChaos
1

Из развития языка 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++ );
Джон Боде
источник
-2

Вопрос предполагает, что в 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 - просто (несколько) более читаемый и портативный ассемблер.

aragaer
источник
2
Я не думаю, что вы ответили на вопрос.
Роберт Харви
2
То, что вы сказали, правда, но спрашивающий хочет знать, почему это так.
9
Помните, одно из прозвищ для C - «портативная сборка». Хотя в более новые версии стандарта добавлены концепции более высокого уровня, по своей сути он состоит из простых конструкций низкого уровня и инструкций, которые являются общими для большинства нетривиальных машин. Это определяет большинство проектных решений, принятых на языке. Единственные переменные, которые существуют во время выполнения - это целые числа, числа с плавающей запятой и указатели. Инструкции включают в себя арифметику, сравнения и прыжки. Практически все остальное - тонкий слой, построенный поверх этого.
8
Неправильно говорить, что в C нет массивов, учитывая, что вы действительно не можете сгенерировать тот же двоичный файл с другими конструкциями (по крайней мере, если не учитывать использование #defines для определения размеров массива). Массивы в C - это «непрерывные последовательности данных», ничего страшного в этом нет. Использование указателей как массивов является синтаксическим сахаром здесь (вместо явной арифметики указателей), а не самих массивов.
Hyde
2
Да, рассмотреть этот код struct Foo { int arr[10]; }. arrэто массив, а не указатель.
Gort the Robot