Por que os arrays C não acompanham seu comprimento?

75

Qual foi o raciocínio por trás de não armazenar explicitamente o tamanho de um array com um array em C ?

Do jeito que eu vejo, existem razões esmagadoras para fazê-lo mas não muitas em apoio ao padrão (C89). Por exemplo:

  1. Ter comprimento disponível em um buffer pode impedir a saturação do buffer.
  2. Um arr.length no estilo Java é claro e evita que o programador tenha que manter muitos int s na pilha se lidar com várias matrizes
  3. Os parâmetros de função tornam-se mais convincentes.

Mas talvez a razão mais motivadora, na minha opinião, é que normalmente, nenhum espaço é salvo sem manter o comprimento. Eu me atreveria a dizer que a maioria dos usos de arrays envolve alocação dinâmica. É verdade que pode haver alguns casos em que as pessoas usam uma matriz alocada na pilha, mas isso é apenas uma chamada de função * - a pilha pode manipular 4 ou 8 bytes extras.

Como o gerenciador de heap tem que rastrear o tamanho do bloco livre usado pelo array dinamicamente alocado, por que não tornar essa informação utilizável (e adicionar a regra adicional, verificada em tempo de compilação, que não é possível manipular o comprimento explicitamente? a menos que alguém queira atirar em si mesmo no pé).

A única coisa que posso pensar no outro lado é que nenhum rastreamento de comprimento pode ter tornado os compiladores mais simples, mas não isso muito mais simples.

* Tecnicamente, pode-se escrever algum tipo de função recursiva com um array com armazenamento automático, e neste caso (muito elaborado) o armazenamento do tamanho pode de fato resultar em efetivamente mais uso de espaço.

    
por VF1 28.04.2014 / 17:27
fonte

10 respostas

104

As matrizes C mantêm o controle de seu tamanho, já que o comprimento da matriz é uma propriedade estática:

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

Normalmente, você não pode consultar esse tamanho, mas não é necessário, porque está estático de qualquer forma. Basta declarar uma macro XS_LENGTH para o tamanho e pronto.

A questão mais importante é que as matrizes C se degradam implicitamente em ponteiros, por exemplo quando passado para uma função. Isso faz algum sentido e permite alguns truques interessantes de baixo nível, mas perde a informação sobre o comprimento do array. Então, uma pergunta melhor seria por que o C foi projetado com essa degradação implícita para ponteiros.

Outra questão é que os ponteiros não precisam de armazenamento, exceto o próprio endereço de memória. C nos permite converter inteiros para ponteiros, ponteiros para outros ponteiros e para tratar ponteiros como se fossem matrizes. Ao fazer isso, C não é insano o suficiente para fabricar alguns comprimentos de array, mas parece confiar no lema do Homem-Aranha: com grande poder o programador esperará cumprir a grande responsabilidade de manter o controle de comprimentos e transbordamentos.

    
por 28.04.2014 / 17:54
fonte
38

Muito disso tinha a ver com os computadores disponíveis na época. Não só o programa compilado teve que rodar em um computador de recursos limitado, mas, talvez mais importante, o próprio compilador teve que rodar nessas máquinas. Na época Thompson desenvolveu C, ele estava usando um PDP-7, com 8k de RAM. Recursos de linguagem complexos que não tinham um análogo imediato no código de máquina real simplesmente não eram incluídos na linguagem.

Uma leitura atenta da história do C fornece mais compreensão do que foi dito acima, mas não foi inteiramente um resultado das limitações da máquina que eles tinham:

Moreover, the language (C) shows considerable power to describe important concepts, for example, vectors whose length varies at run time, with only a few basic rules and conventions. ... It is interesting to compare C's approach with that of two nearly contemporaneous languages, Algol 68 and Pascal [Jensen 74]. Arrays in Algol 68 either have fixed bounds, or are 'flexible:' considerable mechanism is required both in the language definition, and in compilers, to accommodate flexible arrays (and not all compilers fully implement them.) Original Pascal had only fixed-sized arrays and strings, and this proved confining [Kernighan 81].

Os arrays C são inerentemente mais poderosos. Adicionando limites a eles restringe o que o programador pode usá-los. Tais restrições podem ser úteis para programadores, mas necessariamente também são limitantes.

    
por 28.04.2014 / 22:19
fonte
22

De volta ao dia em que C foi criado, e 4 bytes extras de espaço para cada string, não importa quão curto , seria um desperdício!

Existe outro problema - lembre-se de que C não é orientado a objetos, portanto, se você usar length-prefix em todas as strings, ele teria que ser definido como um tipo intrínseco de compilador, não um char* . Se fosse um tipo especial, você não seria capaz de comparar uma string a uma string constante, por exemplo:

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

teria que ter detalhes especiais do compilador para converter essa string estática em uma String ou ter diferentes funções de string para levar em consideração o prefixo de comprimento.

Eu acho que, no final das contas, eles simplesmente não escolheram o prefixo de comprimento, ao contrário do Pascal.

    
por 28.04.2014 / 17:50
fonte
11

Em C, qualquer subconjunto contíguo de uma matriz também é uma matriz e pode ser operado como tal. Isso se aplica tanto a operações de leitura e gravação. Esta propriedade não seria válida se o tamanho fosse armazenado explicitamente.

    
por 28.04.2014 / 22:22
fonte
8

O maior problema em ter matrizes marcadas com seu comprimento não é tanto o espaço necessário para armazenar esse tamanho, nem a questão de como ele deve ser armazenado (usar um byte extra para matrizes curtas geralmente não seria censurável, nem iria usar quatro bytes extras para matrizes longas, mas usando quatro bytes, mesmo para matrizes curtas pode ser). Um problema muito maior é que determinado código como:

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);
}

a única maneira de o código aceitar a primeira chamada para ClearTwoElements , mas rejeitar a segunda, seria para o método ClearTwoElements receber informações suficientes para saber que, em cada caso, recebia uma referência a parte de o array foo além de saber qual parte. Isso normalmente dobraria o custo de passar parâmetros de ponteiro. Além disso, se cada matriz foi precedida por um ponteiro para um endereço logo após o final (o formato mais eficiente para validação), o código otimizado para ClearTwoElements provavelmente se tornaria algo como:

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;
}

Note que um chamador de método poderia, em geral, passar legitimamente um ponteiro para o início da matriz ou o último elemento para um método; somente se o método tentar acessar elementos que estão fora da matriz transmitida, esses indicadores causarão algum problema. Conseqüentemente, um método chamado teria que primeiro garantir que o array fosse grande o suficiente para que a aritmética do ponteiro para validar seus argumentos não saísse dos limites e fizesse alguns cálculos de ponteiro para validar os argumentos. O tempo gasto em tal validação provavelmente excederia o custo gasto com qualquer trabalho real. Além disso, o método provavelmente seria mais eficiente se fosse escrito e chamado:

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);
}

O conceito de um tipo que combina algo para identificar um objeto com algo para identificar uma parte dele é bom. Um ponteiro no estilo C é mais rápido, no entanto, se não for necessário realizar a validação.

    
por 28.04.2014 / 21:30
fonte
7

Uma das diferenças fundamentais entre o C e a maioria das outras linguagens de 3ª geração, e todas as linguagens mais recentes que conheço, é que o C não foi projetado para tornar a vida mais fácil ou mais segura para o programador. Foi projetado com a expectativa de que o programador sabia o que estava fazendo e queria fazer exatamente e apenas isso. Não faz nada 'nos bastidores' para que você não tenha surpresas. Mesmo a otimização do nível do compilador é opcional (a menos que você use um compilador da Microsoft).

Se um programador quiser escrever a verificação de limites em seu código, C o torna simples o suficiente para fazê-lo, mas o programador deve optar por pagar o preço correspondente em termos de espaço, complexidade e desempenho. Mesmo que eu não tenha usado isso com raiva por muitos anos, eu ainda o uso quando estou ensinando programação para atravessar o conceito de tomada de decisão baseada em restrições. Basicamente, isso significa que você pode escolher fazer o que quiser, mas cada decisão que você toma tem um preço que você precisa conhecer. Isso se torna ainda mais importante quando você começa a dizer aos outros o que deseja que seus programas façam.

    
por 29.04.2014 / 13:17
fonte
7

Resposta curta:

Como C é uma linguagem de programação baixo nível , espera que você cuide desses problemas sozinho, mas isso adiciona uma maior flexibilidade em exatamente como você implementá-lo.

C tem um conceito em tempo de compilação de um array que é inicializado com um comprimento, mas em tempo de execução, tudo é simplesmente armazenado como um único ponteiro para o início dos dados. Se você quiser passar o comprimento da matriz para uma função junto com a matriz, faça você mesmo:

retval = my_func(my_array, my_array_length);

Ou você poderia usar uma estrutura com um ponteiro e tamanho, ou qualquer outra solução.

Uma linguagem de nível superior faria isso para você como parte de seu tipo de matriz. Em C, você tem a responsabilidade de fazer isso sozinho, mas também a flexibilidade de escolher como fazê-lo. E se todo o código que você está escrevendo já conhece o tamanho da matriz, você não precisa passar o tamanho do objeto como uma variável.

A desvantagem óbvia é que, sem a verificação de limites inerentes em matrizes passadas como ponteiros, é possível criar um código perigoso, mas essa é a natureza das linguagens de sistemas de baixo nível e o trade-off que elas fornecem.

    
por 29.04.2014 / 07:12
fonte
5

O problema do armazenamento extra é um problema, mas na minha opinião um problema menor. Afinal de contas, na maioria das vezes você precisará rastrear o comprimento de qualquer maneira, embora a amon tenha feito um bom argumento de que muitas vezes ela pode ser rastreada estaticamente.

Um problema maior é onde armazenar o tamanho e por quanto tempo. Não há um lugar que funcione em todas as situações. Você pode dizer apenas armazenar o comprimento na memória antes dos dados. E se a matriz não estiver apontando para a memória, mas algo como um buffer UART?

Deixar o comprimento fora permite que o programador crie suas próprias abstrações para a situação apropriada, e há muitas bibliotecas prontas disponíveis para o caso de uso geral. A verdadeira questão é por que essas abstrações não são usadas em aplicativos sensíveis à segurança?

    
por 28.04.2014 / 22:39
fonte
1

De O desenvolvimento da linguagem C :

Structures, it seemed, should map in an intuitive way onto memory in the machine, but in a structure containing an array, there was no good place to stash the pointer containing the base of the array, nor any convenient way to arrange that it be initialized. For example, the directory entries of early Unix systems might be described in C as
struct {
    int inumber;
    char    name[14];
};
I wanted the structure not merely to characterize an abstract object but also to describe a collection of bits that might be read from a directory. Where could the compiler hide the pointer to name that the semantics demanded? Even if structures were thought of more abstractly, and the space for pointers could be hidden somehow, how could I handle the technical problem of properly initializing these pointers when allocating a complicated object, perhaps one that specified structures containing arrays containing structures to arbitrary depth?

The solution constituted the crucial jump in the evolutionary chain between typeless BCPL and typed C. It eliminated the materialization of the pointer in storage, and instead caused the creation of the pointer when the array name is mentioned in an expression. The rule, which survives in today's C, is that values of array type are converted, when they appear in expressions, into pointers to the first of the objects making up the array.

Essa passagem aborda porque as expressões de matriz decaem para ponteiros na maioria das circunstâncias, mas o mesmo raciocínio se aplica ao motivo pelo qual o comprimento da matriz não é armazenado com a própria matriz; Se você quiser um mapeamento um-para-um entre a definição de tipo e sua representação na memória (como fez Ritchie), então não há nenhum bom lugar para armazenar esses metadados.

Além disso, pense em matrizes multidimensionais; onde você armazenaria os metadados de comprimento para cada dimensão, de modo que você ainda pudesse percorrer o array com algo como

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++ );
    
por 20.06.2014 / 18:01
fonte
-2

A questão assume que existem matrizes em C. Não há. Coisas que são chamadas matrizes são apenas um açúcar sintático para operações em sequências contínuas de dados e aritmética de ponteiros.

O código a seguir copia alguns dados de src para dst em blocos int-sized sem saber que é realmente uma string de caracteres.

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);

Por que o C é tão simplificado que não possui matrizes adequadas? Eu não sei a resposta correta para essa nova pergunta. Mas algumas pessoas costumam dizer que C é apenas um montador (um pouco) mais legível e portátil.

    
por 28.04.2014 / 17:45
fonte

Tags