3 ms·

Then you are wrong, since we're already talking about arrays of sizes known at compile time. Indeed, otherwise we would also need to remember the size in the ru

by enedil 4y ago

Then you are wrong, since we're already talking about arrays of sizes known at compile time. Indeed, otherwise we would also need to remember the size in the runtime.

IgorPartola 4y ago
IIRC this is valid in C99: void foo(size_t n) { int arr[n]; … }
- LegionMammal978 4y ago
  VLAs can be declared in a single statement, but they cannot be initialized in C17 (6.7.9): > The type of the entity to be initialized shall be an array of unknown size or a complete object type that is not a variable length array type. Curiously, C23 actually seems to break the O(1) rule, by allowing VLAs to be initialized with an empty initializer: int arr[n] = {}; GCC generates a memset call (https://godbolt.org/z/5v31bKs5a https://godbolt.org/z/5v31bKs5a) to fill the array with zeros.
- throwaway2037 4y ago
  How do you think it works? Does the compiler generate some kind of stack alloc? Stupid question: Does that mean a huge value for 'n' can cause stack overflow at runtime? I recall that threads normally get a fixed size stack size, e.g., 1MB.
  - IgorPartola 4y ago
    It just moves the stack pointer by n which is O(1). It doesn’t initialize it of course. But my point is that the array size isn’t known at compile time.
  - jcelerier 4y ago
    Yes, it causes stack overflow at runtime. Compilers warn for it, in particular clang has a warning that you can configure to pop up whenever the stack usage of a function goes beyond some limit you set - I think that setting it to 32k or 64k is a safe and sane default as e.g. macOS thread stack sizes are just 512kb
LegionMammal978 4y ago
I don't think we're actually in disagreement here. It looks like I misread the parent comment to be claiming that fixed-size array assignment ought to be considered O(N), when no such claim is made.
- DSMan195276 4y ago
  Yeah to clarify I'm definitely in agreement with you that it's O(1), the size is fixed so it's constant time. It's not like the 'n' has to be "sufficiently small" or something for it to be O(1), it just has to be constant :) People are being very loose about what O(n) means so I attempted to clarify that a bit. Considering what assignments can already do in C it's somewhat irrelevant whether they think it's O(n) anyway, it doesn't actually make their point correct XD

by enedil 4y ago

Then you are wrong, since we're already talking about arrays of sizes known at compile time. Indeed, otherwise we would also need to remember the size in the runtime.

IgorPartola 4y ago

IIRC this is valid in C99: void foo(size_t n) { int arr[n]; … }

LegionMammal978 4y ago
VLAs can be declared in a single statement, but they cannot be initialized in C17 (6.7.9): > The type of the entity to be initialized shall be an array of unknown size or a complete object type that is not a variable length array type. Curiously, C23 actually seems to break the O(1) rule, by allowing VLAs to be initialized with an empty initializer: int arr[n] = {}; GCC generates a memset call (https://godbolt.org/z/5v31bKs5a https://godbolt.org/z/5v31bKs5a) to fill the array with zeros.
throwaway2037 4y ago
How do you think it works? Does the compiler generate some kind of stack alloc? Stupid question: Does that mean a huge value for 'n' can cause stack overflow at runtime? I recall that threads normally get a fixed size stack size, e.g., 1MB.
- IgorPartola 4y ago
  It just moves the stack pointer by n which is O(1). It doesn’t initialize it of course. But my point is that the array size isn’t known at compile time.
- jcelerier 4y ago
  Yes, it causes stack overflow at runtime. Compilers warn for it, in particular clang has a warning that you can configure to pop up whenever the stack usage of a function goes beyond some limit you set - I think that setting it to 32k or 64k is a safe and sane default as e.g. macOS thread stack sizes are just 512kb

LegionMammal978 4y ago

I don't think we're actually in disagreement here. It looks like I misread the parent comment to be claiming that fixed-size array assignment ought to be considered O(N), when no such claim is made.

DSMan195276 4y ago
Yeah to clarify I'm definitely in agreement with you that it's O(1), the size is fixed so it's constant time. It's not like the 'n' has to be "sufficiently small" or something for it to be O(1), it just has to be constant :) People are being very loose about what O(n) means so I attempted to clarify that a bit. Considering what assignments can already do in C it's somewhat irrelevant whether they think it's O(n) anyway, it doesn't actually make their point correct XD