Skip to content

[Idea] Trie optimizations #121

@pvdz

Description

@pvdz

We (now) use the Trie structure in two key positions in the library;

  • map var names to their index (on config.all_var_names).

Internally all vars are only referenced to by their index but while setting up the solver the api is called with (original) var names. This means we need to be able to map these efficiently and an indexOf in this area was bogging the system down with tens thousands of vars.

  • track changed vars while propagating

As an alternative strategy to keep trying until nothing changes, the code (now) steps a propagators and if it changed, record the variables that can be affected by that propagator. At the end of the loop, all these changed vars will compile a new list of propagators to check. We use a Trie to dedupe the list of vars that changed because if we didn't the complexity would explode.

The initial implementation used a naive and simple tree of objects. That worked great, now we need to reiterate on that and improve. Some things to do or try:

  • Manually implement Trie in a buffer instead of a tree of regular objects in an attempt to relieve the GC (1c940e6)
  • hash number keys in a different path (skip the ordinal step) (e70393e)
  • investigate whether we can implement a custom language to setup a solver and omit the main name-to-index lookup use case.
  • asmjs implementation
  • wasm implementation

Ftr; I tried caching the trie (per propagation call or even globally) that tracks changed vars but that didn't really change anything in terms of perf. For the sake of simplicity I'm dropping that change.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions