4 ms·

OK, then I'll pick a different example: a general graph.

• mwkaufma 11mo ago
  "How do you apply algo X to a problem which has been narrowly-tailored and/or under-specified to specifically exclude X" isn't exactly a constructive inquiry.
  • lisper 11mo ago
    A general graph is not exactly "narrowly tailored". Graphs are pretty common.
    • mwkaufma 11mo ago
      No but they are under-specified. OP is specifically working with a document-hierarchy data-structure with a natural ownership/weak-pointer distinction to exploit -- no need to abstract it to a general graph.
      • lisper 11mo ago
        Yes, but then they also said: > hopefully design your language semantics to discourage cycles thus expanding the scope of their comment beyond that specific use case.
        • mwkaufma 11mo ago
          Yes, but they said that in the context of a tailored language for persistent/HDD-backed data, where implicitly performance crosses the line into an additional measure of correctness, rather than an orthogonal one. ("to find live references means walking nearly the entire heap including the portions living in secondary storage, and now you're in a world of pain") So the "increased cognitive overhead" is intrinsic to the problem domain, not an unforced defect of the language design. Overgeneralization in such a case would induce even worse overhead as there'd be no user-level way to fix perf.
          • lisper 11mo ago
            Fair point.
          • zozbot234 11mo ago
            You don't always have to walk the entire program heap to find cyclic references, only the fraction of it that may in fact be involved in a cycle. That fraction may or may not be inherently small enough, depending on the kind of problems you'll be working with.
    • RossBencina 11mo ago
      Graphs are common. But you don't have to represent each edge as a pointer. For example you can represent them using (sparse) adjacency matrices. Or you can represent edges using a pointer in each direction (even for a directed graph) or some other data structure (as is commonly the case in triangle mesh data structures). Lots of options. Most do not require GC.
• adgjlsfhk1 11mo ago
  If you put all the nodes into an array and use weakrefs (or indices) for node->node edges you move the node ownership to a single object which will make your garbage collection faster for either algorithm, and will also improve your memory locality.