5 ms·

"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 page

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

benched 13y ago
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.
- rayiner 13y ago
  If you're programming in C, it's not unreasonable to be pedantic about stuff like this. :D
- jevinskie 13y ago
  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/Reference/ManPages/man3/malloc_size.3.html https://developer.apple.com/library/mac/documentation/Darwin...
  - benched 13y ago
    Then I retract my "not sensibly available" for "maybe sensibly available on your platform". But, it is still not the array size.
    - deleted 13y ago
      [deleted]
  - sitharus 13y ago
    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.
    - RogerL 13y ago
      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.
yan 13y ago
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.
- rayiner 13y ago
  > 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.
  - deleted 13y ago
    [deleted]
- betterunix 13y ago
  "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).
tptacek 13y ago
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.
- unwind 13y ago
  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.
angersock 13y ago
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?
wglb 13y ago
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.
ksk 13y ago
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.
gaius 13y ago
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.

benched 13y ago

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.

rayiner 13y ago
If you're programming in C, it's not unreasonable to be pedantic about stuff like this. :D
jevinskie 13y ago
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/Reference/ManPages/man3/malloc_size.3.html https://developer.apple.com/library/mac/documentation/Darwin...
- benched 13y ago
  Then I retract my "not sensibly available" for "maybe sensibly available on your platform". But, it is still not the array size.
  - deleted 13y ago
    [deleted]
- sitharus 13y ago
  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.
  - RogerL 13y ago
    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.

yan 13y ago

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.

rayiner 13y ago
> 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.
- deleted 13y ago
  [deleted]
betterunix 13y ago
"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).

tptacek 13y ago

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.

unwind 13y ago
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.

angersock 13y ago

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?

wglb 13y ago

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.

ksk 13y ago

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.

gaius 13y ago

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.