Skip to content

Consider hashing duplicate transition-id validation in statum-graph #14

Description

@eboody

Context

statum-graph::validate_graph(...) currently detects duplicate transition ids by storing seen ids in a Vec and calling contains(...) for each transition, which is O(n^2) in the number of transitions.

Why this is not an immediate PR blocker

  • The current code is correct.
  • This path is not known to be hot today.
  • Switching directly to HashSet would tighten the external generic contract for MachineDoc::try_from_graph(...) because it would require T: Hash, not just T: Copy + Eq.

Follow-up decision

Decide whether to:

  1. Keep the current external API and accept the linear scan because this is not a proven bottleneck, or
  2. Explicitly require T: Hash for the external path and switch duplicate transition-id detection to a HashSet.

Relevant code

  • statum-graph/src/lib.rs validate_graph(...)
  • statum-core/src/introspection.rs MachineIntrospection::TransitionId already requires Hash for Statum-generated graphs

Acceptance criteria

  • Either document why the current Vec approach is intentional, or
  • Change the bound and implementation deliberately rather than as an incidental micro-optimization.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

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