Hacker News Reader

Comment by avgcorrection | Hacker News Reader

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).

View on HN

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.)

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.

That would be a welcome development.

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.

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.

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.

> 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.

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.

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.

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.

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.

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.

Reply on news.ycombinator.com