4 ms·

std::map on C++ is a linked-tree structure, often a Red-and-black tree that very much looks like a "linked list" (or close to it) from a memory-management persp

std::map on C++ is a linked-tree structure, often a Red-and-black tree that very much looks like a "linked list" (or close to it) from a memory-management perspective. If you delete a std::map taking up 4GB of RAM, the destructor will have to traverse all 4GBs to find all the pointers and return them to the heap.

astrange 5y ago
How does the GC know there aren't any cyclic references in there to avoid tracing all the pointers the same way? nb if it used an arena allocator then it could simply not do anything on free as long as it was acceptable to reclaim the memory later.
- dragontamer 5y ago
  > How does the GC know there aren't any cyclic references in there to avoid tracing all the pointers the same way? Mark-and-sweep, as well as generational-collectors, walk through all references starting from the root of all variables. In college-level toy garbage collectors, you usually use 1-bit of the pointers to mark where your algorithm has been to (or not). EDIT: The top 16-bits of x86_64 systems are often ignored, because x86 CPUs (AMD Ryzen or Intel i7 / Xeons) only have 48-bit physical memory space, and are a common set of bits used for this "marking" process) Its basically just a depth-first-search or breadth-first-search over the graph of memory pointers. Its pretty simple in concept, but lots of details depending on performance considerations.
- belmarca 5y ago
  As sibling says. If it cannot be accessed starting from any of the GC roots, it is by definition unreachable and will be "cleaned up". What is meant by "cleaned up" varies with GC implementations.
- initplus 5y ago
  Cyclic references are an issue for ref counting as the cycle prevents the count ever reaching 0. Not an issue for mark & sweep where if an allocation isn't accessible from the GC root it's safe to free.
  - astrange 5y ago
    The question isn't whether they're "an issue" for GC, it's whether the GC algorithm has to read in all the memory in the first place and therefore take longer to GC it/disturb caches.
avgcorrection 5y ago
std may not always have the best of datastructures even though they have generic-sounding names. A standard library could either be a testament to great foresight or just a list of regrets. Chandler Carruth has discouraged its use (Google talk 2014) because it’s a cache killer. I wouldn’t use LinkedHashMap in Java unless I needed to preserve the order.

astrange 5y ago

How does the GC know there aren't any cyclic references in there to avoid tracing all the pointers the same way? nb if it used an arena allocator then it could simply not do anything on free as long as it was acceptable to reclaim the memory later.

dragontamer 5y ago
> How does the GC know there aren't any cyclic references in there to avoid tracing all the pointers the same way? Mark-and-sweep, as well as generational-collectors, walk through all references starting from the root of all variables. In college-level toy garbage collectors, you usually use 1-bit of the pointers to mark where your algorithm has been to (or not). EDIT: The top 16-bits of x86_64 systems are often ignored, because x86 CPUs (AMD Ryzen or Intel i7 / Xeons) only have 48-bit physical memory space, and are a common set of bits used for this "marking" process) Its basically just a depth-first-search or breadth-first-search over the graph of memory pointers. Its pretty simple in concept, but lots of details depending on performance considerations.
belmarca 5y ago
As sibling says. If it cannot be accessed starting from any of the GC roots, it is by definition unreachable and will be "cleaned up". What is meant by "cleaned up" varies with GC implementations.
initplus 5y ago
Cyclic references are an issue for ref counting as the cycle prevents the count ever reaching 0. Not an issue for mark & sweep where if an allocation isn't accessible from the GC root it's safe to free.
- astrange 5y ago
  The question isn't whether they're "an issue" for GC, it's whether the GC algorithm has to read in all the memory in the first place and therefore take longer to GC it/disturb caches.

avgcorrection 5y ago

std may not always have the best of datastructures even though they have generic-sounding names. A standard library could either be a testament to great foresight or just a list of regrets. Chandler Carruth has discouraged its use (Google talk 2014) because it’s a cache killer. I wouldn’t use LinkedHashMap in Java unless I needed to preserve the order.