Will calling “free” or “delete” in C/C++ release the memory to the system?
lemire.me
lemire.me
This is another reason to prefer single-threaded processes, which are less subject to such shootdowns, and less-coupled forms of parallelism.
Besides the TLB potholes, releasing memory means that the next time memory is requested, the OS is obliged to zero it before the process gets to see it again. Furthermore, each page will be marked read-only, causing a trap the first time it is touched, and then zeroed lazily.
As a result, freeing memory to the OS should only be essayed with the support of a great deal of measurement of the consequences.
There is no known algorithm for GC that searches for garbage to delete, the way GCs work is exactly opposite - find all live objects (reachable from roots - registers,stack, statics/globals) and the rest of the heap by definition is garbage.
> tracing garbage collection is a form of automatic memory management that consists of determining which objects should be deallocated ("garbage collected") by tracing which objects are reachable by a chain of references from certain "root" objects, and considering the rest as "garbage" and collecting them
So it starts at the root and, in a sense, "iterates" down through the reference tree to see which allocations are reachable, and then the inverse of that is freed. In the OP case, by contrast, "which allocations to free" is known at "collection" time, but there's still an extra step of actually doing the collection.
Which I believe is the important distinction, and quite often it doesn’t know or care “which allocations to free” because it does it in bulk. That allows it to be efficient.
But my original point was just that it's interesting that there is an extra step at all in the C++ case, where we tend to think of collection as happening "for free". It has a constant-time overhead, which is not the same as zero overhead.
During _collection_ and N is size of live set, so divided by allocation the cost is amortized and can safely considered as O(1) much like appending a dynamic array where costly O(N) resize is amortized over N appends.
Typically GCs allocate via bump a pointer allocation which is actually faster then what pretty much all of libc malloc implementations would do.
> C++ case iterates over nothing (incurring a cost of O(1)).
Not quite, take a look at jemalloc paper for instance:
https://www.facebook.com/notes/facebook-engineering/scalable...
A lookup to get the metadata for this specific allocation could be anything from O(1) to O(lgN) depending on size and malloc strategy.
However: Most (all?) general memory allocators have small-allocation buckets for minimizing this effect, which basically groups allocations of specific sizes into different memory pages.
Despite that, virtual address space fragmentation in 32-bit applications is definitely a thing. Memory might still become fragmented over time so that "big" allocations (bigger than a memory page) are failing because there's no big-enough gap left in the processes virtual address space, despite having enough free physical memory available for mapping.
This usually isn't a problem in 64-bit processes, because there's always enough room at the "front" (new memory allocations would basically move like a tidal wave through the 64-bit address space, leaving a mess of fragmented address space behind).
The best way to prevent memory fragmentation of course is to minimize allocation frequency in long-running applications (ideally only allocate memory when the program starts up).