Hacker News Reader

Comment by betterunix | Hacker News Reader

"the length of the array isn't stored in memory anywhere"

This is probably not true. For arrays on the heap, the size (or an approximation e.g. number of pages the array spans) would have to be stored somewhere in order for the array to be deallocated. For arrays on the stack, the size is either known at compile time, or else it was at least available when the array was allocated and could be kept in the stack frame (and in many cases would be kept in the frame anyway).

Not only that, but the common pattern of passing a pointer to an array and its length as arguments to a function implies that most of the time C programmers keep the length of the array stored somewhere. You are really talking about niche cases where the length of the array is truly and inherently unavailable.

Really this has more to do with the fact that C is meant to do as little as possible for programmers -- it is supposed to be "close to the machine."

View on HN

I'm sorry, but I think the article's version is actually closer to the truth.

Regarding stack arrays, while the compiler certainly knows how large an array is (of course it has to, you're using the length in the code it parses), it will almost certainly not write code or immediates that hold the size anywhere to the resultant binary. If you allocate three arrays, each of 12 doubles, a compiler can simply emit "sub esp, 288" and be done with it. It also won't stop you from referencing memory at an unreasonable offset from any of those arrays. (Compilers can warn you though.)

Passing the array along with its size further goes to prove the original statement, not refute it. If you have to do something manually, it strongly implies that the language/runtime isn't doing it for you.

Regarding arrays on the heap, the runtime even then does not require you to place a size anywhere. What likely happens is the right cell from a bucket of the closest size to the allocation you need is returned to you and marked in use. It will be as large as the size you're allocating, or larger. The only artifact of its original size is which span of memory it's located at. When you free() that allocation, that block simply gets marked as free, no size needed.

> What likely happens is the right cell from a bucket of the closest size to the allocation you need is returned to you and marked in use. It will be as large as the size you're allocating, or larger. The only artifact of its original size is which span of memory it's located at.

Almost every segregated-fit allocator I've ever seen still stores the size of each cell in the bucket header, although of course you only need to store the size once for the whole bucket since each cell is the same size. Still, it's stored somewhere. Also, only some allocators are segregated fit. dlmalloc, for example, which is very widely used, uses boundary tags, storing the allocation size with the allocation itself.

"What likely happens is the right cell from a bucket of the closest size to the allocation you need is returned to you and marked in use"

...implying that the size of the block is, in fact, available to the allocator. This might not be stored explicitly (it could be stored as a pair of pointers) but it is not unavailable. It is also necessarily available to the deallocator, which must in some way be aware of what it is marking as free. As I said, this might only be an approximation of the size of the array, though for bounds checking purposes it would usually be good enough (since nothing else should be allocated in the "excess" space that is marked as in-use).

"Passing the array along with its size further goes to prove the original statement, not refute it. If you have to do something manually, it strongly implies that the language/runtime isn't doing it for you."

Take a closer look at the original statement. He did not merely say that the size is unavailable to programmers, he said it is not available at all. That is not really true -- it is more that the compiler does not do anything useful with the information.

To put it another way, a compiler could conceivably emit bounds-checking code but still not provide programmers with an explicit way to get the size of an array. The result would be the same: programmers would still be forced to pass array sizes around, to avoid a call to abort (or whatever behavior occurs when a bounds check failed).

No it couldn't, because the compiler cannot make assumptions about the heap allocator beyond what the C spec says, which is basically just the function signatures. An allocator that never frees memory is entirely within the C spec and would need not know individual allocated sizes after allocation.

Or, if a compiler decided to anyway, it would have to link a compiler-specific standard library because it's entirely implementation-dependant what and where bookkeeping information is stored. In turn, this means you couldn't safely link code compiled by different compilers. Bjarne might think that fine and dandy, but C never had that level of damage.

The fact that C programmers pass around explicit lengths kind of illustrates the point the author is trying to make, and that you're arguing with. The allocator stores enough state to make "free" work, but that state is not idiomatically available to C programmers. It would be a code smell if a C programmer pawed around malloc to get the size of a block. If you need to know the size of something in C, you arrange to always know it.

It would be way, way, worse than a smell. It'd be a clear-the-room-this-sh*t-is-baad type of situation. At least in my book, but I can be somewhat delicate in my sensitivities sometimes. :)

And yes, of course it's true that C APIs use explicit lengths because they're nowhere to be found at run-time. We didn't all just miss that and add an extra argument for fun.

Consider the case where you have a struct containing something in addition to an array. If you malloc sizeof the struct, then the array size is likely not to be found anywhere.

In an attempt to be pedantic for no reason you have opened yourself to criticism by other pedants ;) The words heap and stack are not even mentioned in the C standard specification. You're conflating the implementation with the language itself. The post was about the language.

I have often wished for this. If you can pass a pointer to free() and it frees the previous allocation, it must "know" how big it was, so why is there no way to ask it? You can obviously stash it yourself at malloc() time in a lookup table, but still.

You are really talking about niche cases where the length of the array is truly and inherently unavailable.

You mean like the niche case of null-terminated strings?

That's a lot of words just to be pedantic. What a heap allocator does in its bookkeeping is not necessarily "storing the length of the array" - and whatever it does isn't sensibly available to the running program. Yes, the size of a static array is known at compile time, but it's length is still not available to the running program unless the programmer explicitly arranges for it to be.

If you're programming in C, it's not unreasonable to be pedantic about stuff like this. :D

I looked into this. It seems that OS X provides malloc_size. [0] I wonder if other *BSDs have it or if it is a XNUism. I can't find an equivalent for glibc, which I find disappointing given how immense glibc is. Even if it is potentially a "shoot yourself in the foot" feature, I can see many judicious uses of it.

And even with such a size query, it is still obviously not something nice and built into the language. But C folks are used to that! =P

[0]: https://developer.apple.com/library/mac/documentation/Darwin...

malloc_size won't give you the size of the array though, it'll give you the number of bytes malloced. malloc is free to return any number of bytes, so long as it's at least the size requested.

Yes, and consider

char* c = malloc(...);

char* d = c+ 100;

malloc_size(d);

Perfectly cromulent C, and I submit the result of the call is not what you might hope it will be.

The article is correct. There is no way in the C language to get the size of the array. Any implementation is, of course, free to build in anything extra in the memory allocator, but it is not part of the language. Specifically, you cannot add anything to the array itself, because memory layout is prescribed. ptr[0] must point to the first byte of memory that was allocated, and if you added some kind of table you'd be pointing to that.

Then I retract my "not sensibly available" for "maybe sensibly available on your platform".

But, it is still not the array size.

Reply on news.ycombinator.com