Skip to content

compute_entropy walks cyclic object graphs without cycle detection — two back-references make every observed assignment take ~2^32 work #571

Description

@InauguralPhysicist

Found porting Deslan Studio's 4d mixer/drum/piano-roll panels: mounting the SECOND UI view that held a "sh" back-reference to the app-shell dict made shell_new hang at 100% CPU for >10 minutes. One back-reference was fine (the 4c arrangement view shipped that way); two hung.

Root cause (src/eigenscript.c, compute_entropy_impl): the observer's entropy walk recurses through every list/dict element with only a depth cap (depth > 64) and no cycle or sharing detection. On an acyclic graph that's one pass. With one cycle of length 2 the walk re-enters the graph depth/2 = 32 times — linear, unnoticed. With k distinct back-edges the re-entries multiply: ~k^32 subtree walks. Two cycles ≈ 2^32 × (subtree cost) per observed assignment.

Minimal repro (first print ~0.07 ms; the second never completes):

a is {"name": "hub", "kids": []}
b is {"parent": a}
append of [a.kids, b]
t0 is monotonic_ms of null
z1 is {"a": a}
print of f"one cycle: {(monotonic_ms of null) - t0} ms"

c is {"parent": a}
append of [a.kids, c]
z2 is {"a": a}          # hangs here — ~2^32 entropy work
print of "two cycles"

Note this also bites shared acyclic structure (a DAG walked once per path), just less catastrophically.

Suggested fix directions (any one suffices):

  • a visited set (pointer set / gc-mark-style bit) so each Value contributes once per entropy computation;
  • or memoize per-Value entropy within one compute_entropy call;
  • treat container revisits as 0-entropy leaves (cheapest, keeps semantics close to today's acyclic behavior).

Downstream workaround (DeslanStudio 4d): view dicts no longer store the shell back-reference at all — closures (VAL_FN, an entropy leaf) carry shell access instead, keeping the app's object graph acyclic. Ledgered in DeslanStudio PORTING.md; part of the #561#569 forcing-function series, though this one is an observer/runtime gap rather than lib/ui.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions