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

Use algorithm benchmarks to improve performance #1224

Closed
maxkfranz opened this issue Jan 20, 2016 · 1 comment

Comments

Projects
None yet
2 participants
@maxkfranz
Copy link
Member

commented Jan 20, 2016

Ref : #936

@maxkfranz maxkfranz added this to the 2.7.0 milestone Jan 20, 2016

@maxkfranz maxkfranz removed the enhancement label Apr 12, 2016

@maxkfranz maxkfranz modified the milestones: future, 3.2.0 Dec 7, 2016

@d2fong d2fong modified the milestones: 3.2.0, 3.3.0 Jun 7, 2017

maxkfranz added a commit that referenced this issue Jul 4, 2018

Refactor Bellman-Ford implementation
Ref:
- Use algorithm benchmarks to improve performance #1224
- Bellman-Ford returning negative weight cycles #2123

maxkfranz added a commit that referenced this issue Jul 24, 2018

Improve performance of A*
- Replace `var` with `let`
- Use a heap for the node queue
- Cheaper check for in open set & helper functions
- Reduce id() calls and use a map for faster closed set lookup
- Build resultant path without recursion
- Improves performance by ~2.1x on GAL

Ref #1224

maxkfranz added a commit that referenced this issue Jul 24, 2018

maxkfranz added a commit that referenced this issue Jul 24, 2018

maxkfranz added a commit that referenced this issue Jul 24, 2018

maxkfranz added a commit that referenced this issue Jul 24, 2018

Use `eles.byGroup()` and unmerge the loops to reduce iterations and n…
…umber of intermediary collections in Bellman-Ford

Ref #1224

maxkfranz added a commit that referenced this issue Jul 24, 2018

Tweaks to Page Rank
- Replace `var` with `let`
- Use `eles.byGroup()` to avoid double iteration for getting nodes and edges lists
- Avoid redundant ID calls
- Avoid `filter()` call by skipping loops inline
- Use multiplication instead of `Math.pow()` for squaring
- Improvement of ~1.07x

Ref #1224

maxkfranz added a commit that referenced this issue Jul 24, 2018

Update BFS/DFS with small optimisations
- Change `var` to `let`
- Avoid double iteration to create separate nodes and edges lists -- re-usable `eles.byGroup()`
- Reduce number of `filter()` calls
- Reduce number of `ele.id()` calls
- Use an in-place merge to construct the path rather than an intermediate array
- Improves performance by ~1.3x on GAL

Ref #1224

maxkfranz added a commit that referenced this issue Jul 25, 2018

maxkfranz added a commit that referenced this issue Jul 26, 2018

Add internal `eles.indexOf(ele)` function
- Gets index of element in collection
- Useful for algorithms that use matrices

Ref #1224

maxkfranz added a commit that referenced this issue Jul 26, 2018

Clean up Floyd-Warshall
- Use `util.defaults()`
- Change `var` to `let`
- Reduce overall code length -- less ~50 lines
- Remove `cy.getElementById()` calls
- Use `eles.merge()` to build resultant path rather than an intermediate array -- less memory usage
- No significant change in performance

Ref #1224

maxkfranz added a commit that referenced this issue Jul 26, 2018

Use a 1-dimensional array for Floyd-Warshall rather than multi-dimens…
…ional arrays

- Reduces array allocations
- Array allocations specify fixed N*N size
- Increases performance on GAL benchmark by ~1.8x

Ref #1224

maxkfranz added a commit that referenced this issue Jul 26, 2018

maxkfranz added a commit that referenced this issue Jul 27, 2018

maxkfranz added a commit that referenced this issue Jul 27, 2018

maxkfranz added a commit that referenced this issue Jul 27, 2018

Optimisations for Page Rank
- Use `util.defaults()`
- Use general normalisation function in `math`
- Use single dimensional array for N*N matrix
- Declare array sizes on init and do not change array lengths
- Re-use arrays that represent the vectors of the main loop of the alg. -- better memory usage & less GC
- Improves benchmark on GAL graph by ~1.5x

Ref #1224

maxkfranz added a commit that referenced this issue Jul 27, 2018

Optimisations for Kruskal
- Change `var` to `let`
- `anySame()` changes to `has()`
- `findSet()` only handles indices rather than creating new objects
- Use `merge()` to modify collections in-place rather than creating many collections

Red #1224

maxkfranz referenced this issue Jul 30, 2018

Optimisations & improvements for Karger-Stein
- Add an error message if the algorithm is run on a graph containing multiple components.
- Minimise array creations and use fixed-size allocations where possible.
- Modify returned collections in-place rather than creating intermediate arrays.
- Fix misnamed file (ES modules refactoring)
- Benchmark for Karger-Stein on GAL ~2.3x faster than v3.2.
- Clean up benchmarks.

maxkfranz referenced this issue Jul 30, 2018

Clean up unmerge filtering in algorithms
- Add `eles.unmergeAt()` to remove at a particular index
- Add `eles.unmergeBy()` to remove by a particular condition
- Misc. cleanup
@maxkfranz

This comment has been minimized.

Copy link
Member Author

commented Jul 30, 2018

Here are the latest benchmarks run on the GAL-Filtered graph, with the code as of today.

Algorithm : comparison multiplier of v3.3 speed / v3.2 speed

  • A* : ~3.3x
  • Bellman-Ford : ~1.3x
  • Betweenness centrality : ~1.2x
  • BFS/DFS : ~1.8x
  • Closeness centrality : ~1.5x
  • Degree centrality : ~1.4x
  • Dijkstra : ~2.0x
  • Floyd-Warshall : ~1.75x
  • Karger-Stein : ~2.5x
  • Kruskal : ~2.8x
  • Page Rank : ~1.5x

Computer specs:

MacBook Pro (Retina, 13-inch, Early 2015)
Mac OS 10.12.6
3.1 GHz Intel Core i7
16 GB 1867 MHz DDR3

May be of interest to : @gbader @jvwong @d2fong

@maxkfranz maxkfranz closed this Aug 2, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.