-
Notifications
You must be signed in to change notification settings - Fork 6
Description
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.