Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

What was the reasoning behind not explicitly storing an array's length with an array in C?

The way I see it, there are overwhelming reasons to do so but not very many in support of the standard (C89). For instance:

  1. Having length available in a buffer can prevent buffer overrun.
  2. A Java-style arr.length is both clear and avoids the programmer from having to maintain many ints on the stack if dealing with several arrays
  3. Function parameters become more cogent.

But perhaps the most motivating reason, in my opinion, is that usually, no space is saved without keeping the length. I would venture to say that most uses of arrays involve dynamic allocation. True, there may be some cases where people use an array allocated on the stack, but that's just one function call* - the stack can handle 4 or 8 bytes extra.

Since the heap manager has to track the free block size used up by the dynamically allocated array anyway, why not make that information usable (and add the additional rule, checked at compile time, that one can't manipulate the length explicitly unless one would like to shoot oneself in the foot).

The only thing I can think of on the other side is that no length tracking may have made compilers simpler, but not that much simpler.

*Technically, one could write some kind of recursive function with an array with automatic storage, and in this (very elaborate) case storing the length may indeed result in effectively more space usage.

share|improve this question
6  
I suppose it could be argued, that when C included using structs as parameter and return value types, it should have included syntactic sugar for "vectors" (or whatever name), which would underneath be struct with length and either array or pointer to array. Language level support for this common construct (also when passed as separate arguments and not single struct) would have saved countless bugs and simplified standard library too. –  hyde Apr 28 at 19:38
3  
You might also find Why Pascal is Not My Favorite Programming Language Section 2.1 to be insightful. –  MichaelT Apr 28 at 20:55
27  
While all the other answers have some interesting points, I think the bottom line is that C was written so assembly language programmers would be able to write code easier and have it be portable. With that in mind, having an array length stored WITH an array automatically would have been a nuisance and not a shortcoming (as would have other nice candy-coating desires). These features seem nice nowadays, but back then it really was frequently a struggle to squeeze one more byte of either program or data into your system. Wasteful use of memory would have severely limited C's adoption. –  Dunk Apr 28 at 21:11
5  
The real part of your answer has already been answered many times in the way I would have, but I can extract a different point: "Why can't the size of a malloc()ed area be requested in a portable way?" That's a thing which makes me wonder several times. –  glglgl Apr 29 at 5:56
3  
Voting to reopen. There's some reason somewhere, even if it's simply "K&R didn't think of it". –  Telastyn Apr 30 at 2:54

10 Answers 10

up vote 84 down vote accepted

C arrays do keep track of their length, as the array length is a static property:

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

You can't usually query this length, but you don't need to because it's static anyway – just declare a macro XS_LENGTH for the length, and you're done.

The more important issue is that C arrays implicitly degrade into pointers, e.g. when passed to a function. This does make some sense, and allows for some nice low-level tricks, but it loses the information about the length of the array. So a better question would be why C was designed with this implicit degradation to pointers.

Another matter is that pointers need no storage except the memory address itself. C allows us to cast integers to pointers, pointers to other pointers, and to treat pointers as if they were arrays. While doing this, C is not insane enough to fabricate some array length into existence, but seems to trust in the Spiderman motto: with great power the programmer will hopefully fulfill the great responsibility of keeping track of lengths and overflows.

share|improve this answer
10  
I think you mean to say, if I am not mistaken, that C compilers keep track of static array lengths. But this does no good for functions which just get a pointer. –  VF1 Apr 28 at 15:59
21  
@VF1 yes. But the important thing is that arrays and pointers are different things in C. Assuming you're not using any compiler extensions, you can't generally pass an array itself to a function, but you can pass a pointer, and index a pointer as if it were an array. You're effectively complaining that pointers have no length attached. You should be complaining that arrays can't be passed as function arguments, or that arrays degrade to pointers implicitly. –  amon Apr 28 at 16:03
32  
"You can't usually query this length" -- actually you can, it's the sizeof operator -- sizeof(xs) would return 168 assuming int's are four bytes long. To get the 42, do: sizeof(xs) / sizeof(int) –  tcrosley Apr 28 at 19:23
11  
@tcrosley That only works within the scope of the array declaration - try passing xs as a param to another function then see what sizeof(xs) gives you... –  Gwyn Evans Apr 28 at 20:23
22  
@GwynEvans again: pointers are not arrays. So if you “pass an array as param to another function”, you aren't passing an array but a pointer. Claiming that sizeof(xs) where xs is an array would be something different in another scope is blatantly false, because the design of C does not allow arrays to leave their scope. If sizeof(xs) where xs is an array is different from sizeof(xs) where xs is a pointer, that comes as no surprise because you are comparing apples with oranges. –  amon Apr 28 at 20:47

A lot of this had to do with the computers available at the time. Not only did the compiled program have to run on a limited resource computer, but, perhaps more importantly, the compiler itself had to run on these machines. At the time Thompson developed C, he was using a PDP-7, with 8k of RAM. Complex language features that didn't have an immediate analog on the actual machine code were simply not included in the language.

A careful read through the history of C yields more understanding into the above, but it wasn't entirely a result of the machine limitations they had:

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].

C arrays are inherently more powerful. Adding bounds to them restricts what the programmer can use them for. Such restrictions may be useful for programmers, but necessarily are also limiting.

share|improve this answer
4  
This pretty much nails the original question. That and the fact that C was being kept deliberately "light touch" when it came to checking what the programmer was doing, as part of making it attractive for writing operating systems. –  ClickRick Apr 28 at 21:37
4  
Great link, they also explicitly changed storing the length of strings to use a delimiter 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 - well so much for that :-) –  Voo Apr 29 at 12:46
4  
The unterminated arrays also fits with the bare metal approach of C. Remember that the K&R C book is less than 300 pages with a language tutorial, reference and a list of the standard calls. My O'Reilly Regex book is nearly twice as long as K&R C. –  Michael Shopsin Apr 29 at 15:39

Back in the day when C was created, and extra 4 bytes of space for every string no matter how short would have been quite a waste!

There's another issue - remember that C is not object-oriented, so if you do length-prefix all strings, it would have to be defined a s compiler intrinsic type, not a char*. If it was a special type, then you would not be able to compare a string to a constant string. ie

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

would have to have special compiler details to either convert that static string to a String, or have different string functions to take account of the length prefix.

I think ultimately though, they just didn't choose the length-prefix way unlike say Pascal.

share|improve this answer
10  
Bounds checking also takes time. Trivial in today's terms, but something people paid attention to when they cared about 4 bytes. –  Steven Burnap Apr 28 at 19:44
17  
@StevenBurnap: it's not that trivial even today if you are in an inner loop that goes over every pixel of a 200 MB image. In general, if you are writing C you want to go fast, and you don't want to waste time in a useless bound check at every iteration when your for loop was already set up to respect the boundaries. –  Matteo Italia Apr 28 at 20:59
3  
@VF1 "back in the day" it could well have been two bytes (DEC PDP/11 anyone?) –  ClickRick Apr 28 at 21:26
6  
Its not just "back in the day". The for the software that C is targetted at as a "portable assembly language" such as OS kernals, device drivers, embedded real time software etc.etc. wasting half a dozen instructions on bounds checking does matter, and, in many cases you need to be "out of bounds" (how could you write a debugger if you could not randomly access another programs storage?). –  James Anderson Apr 29 at 9:57
2  
This is actually a rather weak argument considering that BCPL had length counted arguments. Just as Pascal though that was limited to 1 word so generally 8 or 9 bits only, which was a bit limiting (it also precludes the possibility to share parts of strings, although that optimization was probably way too advanced for the time). And declaring a string as a struct with a length followed by the array really wouldn't need special compiler support.. –  Voo Apr 29 at 13:21

In C, any contiguous subset of an array is also an array and can be operated on as such. This applies both to read and write operations. This property would not hold if the size was stored explicitly.

share|improve this answer
2  
"The design would be different" is not a reason against the design being different. –  VF1 Apr 28 at 20:25
6  
@VF1: Have you ever programmed in Standard Pascal? C's ability to be reasonably flexible with arrays was a huge improvement over assembly (no safety whatsoever) and the first generation of typesafe languages (overkill typesafety, including exact array bounds) –  MSalters Apr 28 at 20:30
3  
This ability to slice an array is indeed a massive argument for the C89 design. –  Tibo Apr 28 at 20:37
    
Old school Fortran hackers also ma[dk]e good use of this property (albeit, it requires passing the slice to an array in Fortran). Confusing and painful to program or debug, but fast and elegant when working. –  dmckee Apr 28 at 21:22
2  
There is one interesting design alternative that allows slicing: Don't store the length alongside the arrays. For any pointer to an array, store the length with the pointer. (When you just have a real C array, the size is a compile time constant and available to the compiler.) It takes more space, but allows slicing while maintaining the length. Rust does this for the &[T] types, for example. –  delnan Apr 29 at 10:43

The biggest problem with having arrays tagged with their length is not so much the space required to store that length, nor the question of how it should be stored (using one extra byte for short arrays generally wouldn't be objectionable, nor would using four extra bytes for long arrays, but using four bytes even for short arrays might be). A much bigger problem is that given code like:

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

the only way that code would be able to accept the first call to ClearTwoElements but reject the second would be for the ClearTwoElements method to receive information sufficient to know that in each case it was receiving a reference to part of the array foo in addition to knowing which part. That would typically double the cost of passing pointer parameters. Further, if each array was preceded by a pointer to an address just past the end (the most efficient format for validation), optimized code for ClearTwoElements would likely become something like:

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 that a method caller could, in general, perfectly legitimately pass a pointer to the start of the array or the last element to a method; only if the method tries to access elements which go outside passed-in array would such pointers cause any trouble. Consequently, a called method would have to first ensure the array was large enough that the pointer arithmetic to validate its arguments won't itself go out of bounds, and then do some pointer calculations to validate the arguments. The time spent in such validation would likely exceed the cost spent doing any real work. Further, the method could likely be more efficient if it was written and called:

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

The concept of a type which combines something to identify an object with something to identify a piece thereof is a good one. A C-style pointer is faster, however, if it's not necessary to perform validation.

share|improve this answer
    
If arrays had runtime size, then pointer to array would be fundamentally different from pointer to an element of array. Latter might not be directly convertible to former at all (without creating new array). [] syntax might still exist for pointers, but it would be different than for these hypothetical "real" arrays, and the problem you describe would probably not exist. –  hyde Apr 28 at 19:49
    
@hyde: The question is whether arithmetic should be allowed on pointers whose object base address is unknown. Also, I forgot another difficulty: arrays within structures. Thinking about it, I'm not sure there would be any to have a pointer type which could point to an array stored within a structure, without requiring each pointer to include not only the address of the pointer itself, but also upper and lower legal ranges it can access. –  supercat Apr 28 at 20:18
    
Interseting point. I think that this still reduces to amon's answer, though. –  VF1 Apr 28 at 20:30
    
The question asks about arrays. Pointer is memory address and would not change with question's premise, as far as understand the intention. Arrays would get length, pointers would be unchanged (except pointer to array would need to be a new, distinct, unique type, much like pointer to struct). –  hyde Apr 28 at 20:36
    
@hyde: If one sufficiently changed the semantics of the language, it might be possible to have arrays include an associated length, though arrays stored within structures would pose some difficulties. With semantics as they are, array bounds-checking would only be useful if that same checking applied to pointers to array elements. –  supercat Apr 28 at 20:40

One of the fundemental differences between C and most other 3rd generation languages, and all more recent languages that I am aware of, is that C was not designed to make life easier or safer for the programmer. It was designed with the expectation that the programmer knew what they were doing and wanted to do exactly and only that. It does not do anything 'behind the scenes' so you do not get any surprises. Even compiler level optimisation is optional (unless you use a Microsoft compiler).

If a programmer wants to write bounds checking in their code, C makes it is simple enough to do it, but the programmer must choose to pay the corresponding price in terms of space, complexity and performance. Even though I haven't used it in anger for many years, I still use it when teaching programming to get across the concept of constraint based decision making. Basically, that means you can choose to do anything you want, but every decision you make has a price that you need to be aware of. This becomes even more important when you starting telling others what you want their programs to do.

share|improve this answer
2  
C wasn't so much "designed" as it evolved. Originally, a declaration like int f[5]; wouldn't create f as a five-item array; instead, it was equivalent to int CANT_ACCESS_BY_NAME[5]; int *f = CANT_ACCESS_BY_NAME;. The former declaration could be processed without the compiler having to really "understand" array times; it simply had to output an assembler directive to allocate space and could then forget that f ever had anything to do with an array. The inconsistent behaviors of array types stem from this. –  supercat Apr 29 at 18:20

The problem of the extra storage is an issue, but in my opinion a minor one. After all, most of the time you are going to need to track the length anyway, although amon made a good point that it can often be tracked statically.

A bigger problem is where to store the length and how long to make it. There isn't one place that works in all situations. 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?

Leaving the length out allows the programmer to create his own abstractions for the appropriate situation, and there are plenty of ready made libraries available for the general purpose case. The real question is why aren't those abstractions being used in security-sensitive applications?

share|improve this answer
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? Could you please explain this a little bit more? Also that something that might happen too often or it's just a rare case? –  Mahdi May 2 at 10:45

Short answer: because C is lower level, expecting programmers to take care of these issues themselves but also as a result offering more flexibility.

It has a compile-time concept of an array that is initialised with a length but at runtime the whole thing is simply stored as a single pointer to the start of the data. If you want to pass the array length to a function along with the array, you do it yourself:

retval = my_func(my_array, my_array_length);

Or you could use a struct with a pointer and length, or any other solution.

A higher level language would do this for you as part of its array type. In C you're given the responsibility of doing this yourself.

And if all the code you're writing already knows the length of the array, you don't need to pass the length around as a variable at all.

The obvious downside is that with no inherent bounds checking on arrays passed around as pointers you can create some dangerous code but that is the nature of low level/systems languages and the trade-off they give.

share|improve this answer

From The Development of the C Language:

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.

That passage addresses why array expressions decay to pointers in most circumstances, but the same reasoning applies to why the array length isn't stored with the array itself; if you want a one-to-one mapping between the type definition and its representation in memory (as Ritchie did), then there's no good place to store that metadata.

Also, think about multidimensional arrays; where would you store the length metadata for each dimension such that you could still walk through the array with something like

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++ );
share|improve this answer

The question assumes that there are arrays in C. There aren't. Things that are called arrays are just a syntactic sugar for operations on continuous sequences of data and pointer arithmetics.

The following code copies some data from src to dst in int-sized chunks not knowing that it is actually character string.

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

Why C is so simplified it doesn't have proper arrays? I don't know correct answer to this new question. But some people often say that C is just (somewhat) more readable and portable assembler.

share|improve this answer
2  
I don't think you've answered the question. –  Robert Harvey Apr 28 at 15:47
1  
What you said is true, but the person asking wants to know why this is the case. –  Snowman Apr 28 at 15:53
9  
Remember, one of the nicknames for C is "portable assembly." While newer versions of the standard have added higher level concepts, at its core, it consists of simple low level constructs and instructions that are common across most non-trivial machines. This drives most of the design decisions made in the language. The only variables that exist at runtime are integers, floats, and pointers. Instructions include arithmetic, comparisons, and jumps. Pretty much everything else is a thin layer build on top of that. –  Snowman Apr 28 at 16:47
6  
It's wrong to say C has no arrays, considering how you really can't generate same binary with other constructs (well, at least not if you consider use of #defines for determining array sizes). Arrays in C are "continuous sequences of data", nothing sugary about it. Using pointers like they were arrays is the syntactic sugar here (instead of explicit pointer arithmetic), not arrays themselves. –  hyde Apr 28 at 19:28
2  
Yes, consider this code: struct Foo { int arr[10]; }. arr is an array, not a pointer. –  Steven Burnap Apr 28 at 21:31

protected by maple_shaft Apr 29 at 11:31

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.