You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
The text was updated successfully, but these errors were encountered:
We (now) use the Trie structure in two key positions in the library;
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.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:
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.
The text was updated successfully, but these errors were encountered: