Skip to content

Make tanru relation-expression projection graph-indexed and near-linear #745

Description

@int19h

Problem

project_tanru_compositions becomes the dominant cost when SFN-XML indexes a large semantic graph. The implementation repeatedly walks candidate regions and, for each recognized candidate, serializes unrelated graph objects to strings and performs quoted-ID substring searches:

  • candidate ordering calls tanru_region_walk for candidate pairs;
  • recognize_tanru_and loops over the full object map;
  • each unrelated object is converted with Value::to_string();
  • every consumed ID is tested with serialized.contains(...).

During #744's newly unblocked exhaustive XML contract test, the ~49,000-object whole-Alice fixture drained all other Rayon work and then spent over twenty minutes on one debug expensive-contract worker. A 3-second profile attributed the active path to GraphData::from_value -> project_tanru_compositions -> recognize_tanru_and, dominated by str::contains. Resident memory remained flat at ~8.5 GiB, so this is CPU complexity rather than a leak.

This performance debt predates #741/#744; those changes merely allow the exhaustive test to reach the large fixture instead of failing earlier.

Acceptance criteria

  • Build a typed reverse-reference/index structure once from semantic graph values; do not detect graph references through serialized JSON substring search.
  • Determine tanru candidate nesting/outermost order without pairwise repeated region walks over the same graph.
  • Preserve the exact recognition guards, consumed-object sets, projection order, transformed graph, and re-expansion contract from XML body leaks internal Lojban markers: PREDICATE="tanru", CONNECTOR SOURCE-WORD="tanru", LOCUS="SELBRI" #719/Type connective surfaces and project tanru as relation expressions (Ref #719) #724.
  • Add small adversarial structural tests for quoted strings that resemble object IDs, shared references, nested compositions, and disjoint candidates.
  • Add a scalable synthetic or corpus-backed performance/operation-count regression that fails the previous repeated full-map scan shape without relying on a fragile wall-clock threshold.
  • Run the full relation-expression acceptance suite, SFN-XML fixture contract, release tests, and all fixture profiles.
  • Re-measure whole-Alice SFN-XML construction in release and debug expensive-contract configurations and document the improvement.

Evidence

Local transient profile captured during #741 verification: /build/jbotci/scratch/issue-741/xml-active.perf.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions