On: The "C is Efficient" Language Fallacy (2006)

[emillon]

> In C and C++, there's no such thing as an array

Yes there is. `int a[10]` allocates 10 consecutive `int`s on the stack, and it's the only language construct to express that (with `alloca` but it's a builtin function).

[exDM69 → emillon]

The OP wants to point out that C hasn't got first class arrays the same way that Fortran does. The C kind of arrays get passed to and from functions using naked pointers and that makes lots of compiler optimizations more difficult because of aliasing issues while a Fortran compiler knows that two arrays cannot alias (use overlapping memory areas). By adding a "restricted" declaration to your pointer types in function signatures, the compiler assumes no aliasing occurs and goes on with the optimizations. It's the coders' responsibility to make sure no aliasing happens, but if it does, all hell can break loose.

[jrockway → exDM69]

Sort of true. In C99, you can:

  void f(int len){
    int array[len];
    printf("sizeof len: %zu\n", sizeof(array));
  }

Yes, I was weirded out when I saw this for the first time. But C does in fact have arrays; they're just not very good arrays.

[pjmlp → jrockway]

If len is big enough your f() call will crash with a stack overflow.

[repsilat → pjmlp]

I don't understand why stacks are still so small. On nice operating systems memory is only needed when it's touched, not when it's asked for, so making the stack large doesn't cost anything unless you need a large stack. On 64-bit systems you could make the stack a billion gigabytes and still have 95% of your process' virtual address space available for the heap.

On Windows the stack is one megabyte by default. We live in the future and we're still afraid of recursion without tail-call optimisation and arrays on the stack. Ridiculous.

[jemfinch → repsilat]

Stacks are small because every thread in the system has to have one, it's that simple.

[quotemstr → jemfinch]

Who said stacks had to be contiguous and allocated ahead of time?

[emillon → quotemstr]

How would you manage non-contiguous stacks ? ie, how would you know (upon return) where is the caller's stack frame is ?

[exDM69 → emillon]

The stack is only contiguous in the virtual address space. The physical address space is a different beast. The operating system allocates a big chunk of virtual address space for the stack but doesn't allocate the physical memory to fill that. When an app wants to read or write from the unallocated part of the stack, a page fault interrupt is generated and the operating system allocates physical memory frames and assigns them to the virtual memory addresses of the stack. When the thread/process is interrupted for servicing, the operating system checks the value of the stack pointer register (rsp in x86_64) and frees the physical memory corresponding to the virtual addresses above that in the stack.

So having a large stack will only consume virtual address space which we have plenty of (2^48 bytes in most x86_64's) but will not consume physical memory, which is a more limited resource.

[stephencanon → emillon]

You would keep a frame pointer, which would tell you where to find the caller's stack frame. Most systems already do this, to aid debugging and tracing tools, to support variable-length stack allocations, or for any number of other reasons.