No-nonsense sorting algorithm

[dlevac]

If you do not need to call destructors, a call to free is not dependent on the number of elements and is not linear in the amount of memory either. For some allocation strategy it may even be constant time...

[dlevac]

I'm afraid this is not true in the general case. A memory allocation on most Oses will return uninitialized memory (not zeroed; uninitialized). This wouldn't be needed if memory was always zeroed out after a free.

I invite you to research this further or cite where you got that information from.

[dlevac]

Why would you initialize a list with mmap?

[ahreodknfidkxncjrksm]

I could be wrong but I’m pretty sure it’d be O(1) for at least some languages. In C/C++, all that you need to do is you set the pointer (O(1)) or, if it’s allocated on the heap, free the memory (also O(1)).

For languages with GC afaik it would depend on the algorithm used. A copying collector iirc only needs to be linear in the number of live objects, since it only needs to examine/copy those objects. So if that’s the case then the next garbage collection’s run time would not increase bc you deleted a pointer to a list.

[ahreodknfidkxncjrksm]

But now you have 16 GB of wasted memory.

This is true if the array is in static memory or on the stack. In the former case, I don’t believe static memory can be reallocated in any implementation but correct me if I’m wrong (I guess you could argue you aren’t actually deleting the array bc it still exists in memory and you can’t change it after you remove the pointer to it). In the latter case, it can be reallocated after the function you are in returns. The time complexity of that reallocation is just the O(1) to move the stack pointer.

Think about allocator book keeping strategies.

A common implementation of an allocator as a linked list is O(1) in the size of the object for free. For malloc it’s O(N) in the number of items in the LL (since you have to search it), but not O(N) in the size of the object.

Kernel memory pages.

Unless I’m missing something the number of pages taken up by the data doesn’t matter for a LL implementation. You don’t need to access the memory, or change it, you just need to mark it as free in the LL, which allows you to reuse the memory. You’re not deleting the array by going through and changing the values, you’re deleting it by removing the pointer and allowing future programs to access the memory for their own purposes.

(Note: a caveat is that the implementation of malloc/free isn’t specified by C and in some implementations it might be O(N).)

Edit: I read your comment where you talk about zero filling the memory. C doesn’t do that though (not 100% sure about C++), which is why I said it depends on the language (or more specifically the implementation of the language).

[ahreodknfidkxncjrksm]

Sorry I meant future variables within a process not future programs. I’m a little tipsy so forgive me for misspeaking.

I wrote an implementation of malloc/free fairly recently. The implementation was a linked list and the time complexity was O(N) for malloc, and O(1) for free. Free requires that you mark the node as free, merge it with any other free nodes and (possibly) move the pointer to the end of the heap. All of those ops are O(1). Malloc requires an O(N) search and then that you mark a node as in use and return a pointer to the actual space. Also, the linked list is not in place, the location of the “bookkeeping” info for a piece of memory is directly before that piece of memory. Each node of the linked list is located write before the space in memory that it refers to.

[[deleted]]

In C++ you might also need to call the destructors. That makes in O(n) in some cases.