4 ms·

Linked lists? Not a useful data structure in application programming when using imperative languages. And if you are using a functional language then most peopl

Linked lists? Not a useful data structure in application programming when using imperative languages. And if you are using a functional language then most people agree that a GC is necessary (FP without GC sounds like a research problem).

ncmncm 5y ago
FP dependence on GC is 100% cultural. FP languages come out of academia where not depending on GC makes you unwelcome at the lunch table. (You would be suspected of being about to mention performance.)
- remexre 5y ago
  That is absolutely not my experience with academic PL work, as someone in that field. From my perspective, it seems like we're currently undergoing a renaissance of more principled approaches to resource management than GC (especially for non-memory resources), including work on substructural type systems, dynamic resource reuse (I'm thinking of FBIP here), and new ways to combine effects and resource management.
  - ncmncm 5y ago
    That would be a welcome development.
- avgcorrection 5y ago
  GC makes a lot of sense if you want to provide ergonomic pure functional programming. Pure functional data structures are implemented using the idea that old versions can share nodes. With dynamic reference sharing you need something like reference counting at the least, which is a form of GC. But you probably would want something more than that since saying no to cycles would be too onerous. No-GC could be used in cases where you are just transforming one list or whatever and you don’t need to keep around any references to older nodes. That’s an optimization which is used by a research language which focuses on effects (whatever its name was). But it does use GC (reference counting). Then you have linear types and all of that. But the intent seems to be to want to complement regular functional programming, not to invent a new GC-less FP paradigm. You claim that it is merely “cultural” makes it seem to me that you just want to throw some weird shade and that you don’t have any particular technical argument in mind.
dragontamer 5y ago
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.
dehrmann 5y ago
Someone else called out std::map is linked, but unlinked hash tables often store entries to wrap the key and value, so it's a pretty common problem.

ncmncm 5y ago

FP dependence on GC is 100% cultural. FP languages come out of academia where not depending on GC makes you unwelcome at the lunch table. (You would be suspected of being about to mention performance.)

remexre 5y ago
That is absolutely not my experience with academic PL work, as someone in that field. From my perspective, it seems like we're currently undergoing a renaissance of more principled approaches to resource management than GC (especially for non-memory resources), including work on substructural type systems, dynamic resource reuse (I'm thinking of FBIP here), and new ways to combine effects and resource management.
- ncmncm 5y ago
  That would be a welcome development.
avgcorrection 5y ago
GC makes a lot of sense if you want to provide ergonomic pure functional programming. Pure functional data structures are implemented using the idea that old versions can share nodes. With dynamic reference sharing you need something like reference counting at the least, which is a form of GC. But you probably would want something more than that since saying no to cycles would be too onerous. No-GC could be used in cases where you are just transforming one list or whatever and you don’t need to keep around any references to older nodes. That’s an optimization which is used by a research language which focuses on effects (whatever its name was). But it does use GC (reference counting). Then you have linear types and all of that. But the intent seems to be to want to complement regular functional programming, not to invent a new GC-less FP paradigm. You claim that it is merely “cultural” makes it seem to me that you just want to throw some weird shade and that you don’t have any particular technical argument in mind.

dragontamer 5y ago

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.

dehrmann 5y ago

Someone else called out std::map is linked, but unlinked hash tables often store entries to wrap the key and value, so it's a pretty common problem.