-2

I read somewhere that the time taken to allocate k words of memory is O(k), I want to know that is this time same for both run-time and compile-time memory allocation, means want to know does int A[100]; and int *A = (int*) malloc(sizeof(int) * 100); would take same time or different

Nimit Bhardwaj
  • 827
  • 9
  • 19
  • 1
    Algorithmically speaking, static allocation is O(1) and dynamic allocation is depending on the specific `malloc` algorithm. Technically, the static allocation might affect the binary loading/process spawning time. But not linearly at all. – Eugene Sh. Jun 17 '16 at 17:29
  • 3
    There's no such thing as "compile-time allocation". Allocation is generally a dynamic interaction between your program and the OS. Storage that can be placed automatically by the compiler (static and automatic) is recorded in the executable, and the allocation is performed by the OS loader before your code is run. There are details regarding whether you storage is initialized or uninitialized, and whether it is constant or mutable. – Kerrek SB Jun 17 '16 at 17:33
  • 1
    So in plain English, static allocation (`int a[100]`) is done before Your `main()` is called, and it will not start if there is not enough memory (say `int a[99999999]`). If You count time from start, then yes it 'faster' cause it might start and not take time to allocate dynamically or may not start at all, while dynamic allocation takes some CPU cycles during runtime. – JustMe Jun 17 '16 at 18:39
  • IMO, allocation of $k$ words is never $O(k)$ and I wonder how it could be. Compile-time allocation virtually comes for free, as it is performed at load time, i.e. before execution has started. On the opposite, run-time allocation takes an unspecified amount of time. –  Jun 17 '16 at 19:21

1 Answers1

0

Dynamically allocating memory might take O(k) time. It depends on whether the allocator (malloc) or one of the functions it calls initializes the memory before returning. For example if malloc calls the Windows LocalAlloc function to get memory from the operating system, it could pass the LMEM_ZEROINIT flag to initialize all the bytes to 0.

Some operating system memory allocators automatically zero-init memory for security reasons. Some implementations of malloc will initialize memory with a known pattern like 0xDEADBEEF, especially in debug mode. That way if you read a core dump you can see if your program is accessing memory that was allocated but not initialized by the program.

So the answer to the explicit question you didn't ask is that, yes, it's possible, maybe even likely, that dynamic memory allocation of k bytes will take O(k) time.

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351
  • For security, memory must be initialized by the OS before it is handed to a process, and that also applies to the process image, including bss segments (i.e. static variables). If a call to malloc results in a request to the OS, then it will involve initialization. But in many applications, a lot of calls to malloc are satisfied with memory which was previously allocated and freed. With this, initialization is not necessary and often not done, aside from debugging. – rici Jun 17 '16 at 21:25
  • @rici: It looks like Windows clears memory on a separate thread when a process releases memory. See http://stackoverflow.com/questions/18385556/does-windows-clear-memory-pages. If that's the case, then the call to the OS to allocate memory will not incur the cost of initialization. – Jim Mischel Jun 18 '16 at 00:00
  • That's interesting and clever, but it only delays the cost. Doing it in a separate thread only complicates the bookkeeping; it still happens and it is still chargeable to the allocation. But I believe it improves the UX. – rici Jun 18 '16 at 02:14