5 ms·
> There's no particular reason why C doesn't allow you to assign one array to another of the same length, it's largely just an arbitrary restriction. IIRC C ha
by derefr 4y ago
> There's no particular reason why C doesn't allow you to assign one array to another of the same length, it's largely just an arbitrary restriction.
IIRC C has an informal guarantee that no primitive syntax will ever cause the CPU to do more than O(1) work at runtime. Assignment is always O(1), and therefore assignment is limited to scalars. If you need assignment that might do O(N) work, you need to call a stdlib function (memcpy/memmove) instead. If you need an allocation that might do O(N) work, you either need a function (malloc) or you need to do your allocation not-at-runtime, by structuring the data in the program's [writable] data segment, such that it gets "allocated" at exec(2) time.
This is really one of the biggest formal changes between C and C++ — C++ assignment, and keywords `new` and `delete`, can both do O(N) work.
(Before anyone asks: a declaration `int foo[5];` in your code doesn't do O(N) work — it just moves the stack pointer, which is O(1).)
- leni536 4y agoThis reasoning falls apart for structs with array members.
- DSMan195276 4y ago> Assignment is always O(1) This depends on what you consider to be O(1) - being that the size of the array is fixed it's by definition O(1) to copy it, but I might get your point. I think in general your point isn't true though, C often supports integer types that are too large to be copied in a single instruction on the target CPU, instead it becomes a multi-instruction affair. If you consider that to still be O(1) then I think it's splitting hairs to say a fixed-size array copy would be O(N) when it's still just a fixed number of instructions or loop iterations to achieve the copy. Beyond that, struct assignments can already generate loops of as large a size as you want, Ex: https://godbolt.org/z/8Td7PT4af https://godbolt.org/z/8Td7PT4af
- LegionMammal978 4y agoI think the meaning here is that assignment is never O(N) for any variable N computed at runtime. Of course, you can create arbitrarily large assignments at compile time, but this always has an upper bound for a given program.
- enedil 4y agoThen 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 agoIIRC this is valid in C99: void foo(size_t n) { int arr[n]; … }
- LegionMammal978 4y agoVLAs 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 agoHow 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 agoIt 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 agoYes, 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
- jcelerier 4y ago> IIRC C has an informal guarantee that no primitive syntax will ever cause the CPU to do more than O(1) work at runtime. Assignment is always O(1), and therefore assignment is limited to scalars. this is absolutely and entirely wrong. You can assign a struct in C and the compiler will call memcpy when you do. Enjoy: https://godbolt.org/z/98PnhYoev https://godbolt.org/z/98PnhYoev
- wnoise 4y agoAnd any structure is O(1), not O(n), because C structures are not parameterized.
- jcelerier 4y agomemcpy is not O(1)
- LegionMammal978 4y agoIt's O(1) relative to any size computed at runtime: that is, running the same program (with the same array size) on different inputs will always take the same of work for a given assignment.
- jcelerier 4y agoWe're in the context of the assignment operation in the language here. Yes, in C you can only assign statically-known types but that does not mean you can just ignore that a = f(); may take a very different time depending on the types of a and f
- deleted 4y ago[deleted]
- xigoi 4y ago> IIRC C has an informal guarantee that no primitive syntax will ever cause the CPU to do more than O(1) work at runtime. How about CPUs that have no, say, division instruction, so it has to be emulated with a loop?
- naniwaduni 4y agoFixed-width divisions are O(1), just comparatively expensive (and potentially optimized to run in variable time). Consider that you can do long division on pairs of numerals of, say, up to 20 digits and be Pretty Confident of an upper bound on how long it's going to take you (you know it's not going to take more than 20 rounds), even though it's going to take you longer to do that than it would for you to add them.
- pratk 4y agoWell C does allow "copying" an array if it's wrapped inside a struct, which does not make it O(1). gcc generates calls to memcpy in assembly for copying the array.