Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[Idea] Trie optimizations #121

Open
2 of 5 tasks
pvdz opened this issue Jul 20, 2016 · 0 comments
Open
2 of 5 tasks

[Idea] Trie optimizations #121

pvdz opened this issue Jul 20, 2016 · 0 comments

Comments

@pvdz
Copy link
Contributor

pvdz commented Jul 20, 2016

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.

pvdz added a commit that referenced this issue Jul 22, 2016
=============================== Coverage summary ================
Statements   : 91.9% ( 3743/4073 ), 28 ignored
Branches     : 86.74% ( 1602/1847 ), 45 ignored
Functions    : 93.87% ( 352/375 ), 8 ignored
Lines        : 91.89% ( 3138/3415 )
=================================================================
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant