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.

Sign up for GitHub

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

Jump to bottom

Speed up NRI/NTI calcs #786

Closed
shawnlaffan opened this issue Mar 27, 2021 · 1 comment
Closed

Speed up NRI/NTI calcs #786

shawnlaffan opened this issue Mar 27, 2021 · 1 comment
Assignees
@shawnlaffan
Labels
indices
Milestone
Release_4.0

Comments

@shawnlaffan
Copy link
Owner

shawnlaffan commented Mar 27, 2021 •
edited
Loading

The NRI/NTI calcs take a long time, especially for large trees. Profiling shows several locations that can be made more efficient.

This is really a post-hoc issue report to log the updates in commit range 05c0f74..9666dcc

Edit: although the linked commits show the optimisation process kept going.

...and going.
@shawnlaffan shawnlaffan added this to the Release_4.0 milestone Mar 27, 2021
@shawnlaffan shawnlaffan self-assigned this Mar 27, 2021
shawnlaffan added a commit that referenced this issue Apr 4, 2021
@shawnlaffan
get_phylo_nri_nti_cache: store the cache on the tree
a62fe13 
This means it will be re-used each time the tree is used
across outputs, greatly increasing randomisations that
are run with the NRI/NTI calcs left in.

Updates #786
shawnlaffan added a commit that referenced this issue Apr 7, 2021
@shawnlaffan
get_last_shared_ancestor_for_nodes: generate default cache value only…
c45b40c 
… when needed

Otherwise we generate millions of anonymous hashes
only to destroy them immediately.

Should be a minor speed up.

Updates #786
shawnlaffan added a commit that referenced this issue Apr 7, 2021
@shawnlaffan
get_last_shared_ancestor_for_nodes: adjust search range at start
fbcad3c 
No need to repeatedly subtract array indices when it can
be adjusted once when the index is found.

Should be a minor speed up.

Updates #786
shawnlaffan added a commit that referenced this issue Apr 7, 2021
@shawnlaffan
NRI/NTI calcs: calculate LCA offset from end of array once per pair
ab85421 
Updates #786
shawnlaffan added a commit that referenced this issue Apr 9, 2021
@shawnlaffan
_calc_phylo_mpd_mntd: special case ultrametric trees
3ca4d6a 
We only need to calculate one path and double it
since the distances are the same for each path.

Updates #786
shawnlaffan added a commit that referenced this issue Apr 11, 2021
@shawnlaffan
NRI/NTI calcs: populate matrix for LCA when found and tree is ultrame…
05210f2 
…tric

This will avoid repeated ancestral searches.

Non-ultrametric is TODO.

Updates #786
shawnlaffan added a commit that referenced this issue Apr 11, 2021
@shawnlaffan
modify the NRI/NTI test file to use a non-ultrametric tree
f22f271 
This is in prep for some changes in _calc_phylo_mpd_mntd

Updates #786
shawnlaffan added a commit that referenced this issue Apr 11, 2021
@shawnlaffan
NRI/NTI calcs: populate matrix for LCA when found and tree is non-ult…
54ac21c 
…rametric

Updates #786
shawnlaffan added a commit that referenced this issue Apr 11, 2021
@shawnlaffan
NRI/NTI calcs: better matrix approach when tree is non-ultrametric
c3eda8f 
We weren't looping properly in the previous commit when there
were multifurcating branches, so were missing entries.

Update tests to trap this condition.

Updates #786
shawnlaffan added a commit that referenced this issue Apr 12, 2021
@shawnlaffan
factor out a repeated array lookup
7afa933 
Updates #786
shawnlaffan added a commit that referenced this issue Apr 12, 2021
@shawnlaffan
Use boolean assign instead of increment
b54e0a6 
Micro-optimisation for #786
shawnlaffan added a commit that referenced this issue Apr 12, 2021
@shawnlaffan
MPD/MNTD: use fewer arrays
cf9b69b 
We were using two arrays to track the same data.

Updates #786
shawnlaffan added a commit that referenced this issue Apr 12, 2021
@shawnlaffan
Avoid updating a variable we don't really need
559a43d 
Updates #786
shawnlaffan added a commit that referenced this issue Apr 12, 2021
@shawnlaffan
Refactor duplicated do-blocks into a sub
73522b7 
Make the code slightly shorter, but much clearer.

Updates #786
shawnlaffan added a commit that referenced this issue Apr 15, 2021
@shawnlaffan
NRI/NTI: populate the pairwise matrix only when needed
f013cf4 
This is for non-ultrametric trees.

Otherwise we penalise MPD/MNTD calls that
usually need a small subset of the values.

Updates #786
shawnlaffan added a commit that referenced this issue Apr 15, 2021
@shawnlaffan
MPD/MNTD: cache last common ancestor for non-ultrametric trees
b699f4e 
Finding the last common ancestor is a major bottleneck.

No need to do this for NRI/NTI as we can
calculate the results directly.

Updates #786
shawnlaffan added a commit that referenced this issue Apr 15, 2021
@shawnlaffan
Use the LCA cache properly
c2931b5 
An rejig the assignment loop so
it is slightly clearer (could
update the ultrametric loop as well).

Updates #786
shawnlaffan added a commit that referenced this issue Apr 15, 2021
@shawnlaffan
Fix metadata for get_phylo_LCA_matrix
1da5a9a 
Updates #786
shawnlaffan added a commit that referenced this issue Apr 15, 2021
@shawnlaffan
NRI/NTI: show GUI progress dialogue when caching LCA
aad3e5c 
Otherwise we hang for periods

Updates #786
shawnlaffan added a commit that referenced this issue Apr 15, 2021
@shawnlaffan
NRI/NTI: show GUI progress dialogue when caching non-ultrametric paths
21588e2 
Otherwise we hang for long periods

Updates #786
shawnlaffan added a commit that referenced this issue Apr 15, 2021
@shawnlaffan
Minor cleanup
211c070 
Updates #786
shawnlaffan added a commit that referenced this issue Apr 15, 2021
@shawnlaffan
NRI/NTI: show GUI progress dialogue when caching ultrametric paths
8f96aa5 
Otherwise we hang for long periods

Updates #786
shawnlaffan added a commit that referenced this issue Apr 20, 2021
@shawnlaffan
NRI/NTI: refactor last ancestor cache into its own sub
124e7be 
Updates #786
shawnlaffan added a commit that referenced this issue Apr 20, 2021
@shawnlaffan
NRI/NTI: refactor last ancestor path caching into its own sub
e62d412 
Updates #786
shawnlaffan added a commit that referenced this issue Apr 20, 2021
@shawnlaffan
NRI/NTI: refactor ultrametric last ancestor path caching into its own…
0fec104 
… sub

Updates #786
shawnlaffan added a commit that referenced this issue Apr 20, 2021
@shawnlaffan
remove redundant argument from sub and call
eb9bf08 
Updates #786
shawnlaffan added a commit that referenced this issue Apr 22, 2021
@shawnlaffan
Remove some unused variables
0a924c0 
Related to #786
shawnlaffan added a commit that referenced this issue Apr 22, 2021
@shawnlaffan
NRI/NTI Avoid some nested hash lookups
545e696 
Updates #786
shawnlaffan added a commit that referenced this issue Apr 22, 2021
@shawnlaffan
NRI/NTI: try to keep the path matrix triangular
e91ebfb 
This should speed up accesses.

Not applied to the ultrametric case as it
will greatly slow down the assignment.

Updates #786
shawnlaffan added a commit that referenced this issue Apr 22, 2021
@shawnlaffan
NRI/NTI: more efficient means of skipping self-self comparisons
74fc608 
Avoids a next-if condition inside the loop.

Updates #786
shawnlaffan added a commit that referenced this issue Apr 22, 2021
@shawnlaffan
Use an array splice instead of a delete-local on the hash
5938797 
This avoids the overhead of an array slice
in the loop.

Updates #786
shawnlaffan added a commit that referenced this issue Apr 28, 2021
@shawnlaffan
MPD/MNTD: refactor path length search into a sub
d852492 
Substantially cleans up the calling code.
Should not make too much difference for speed
given other optimisations mean most of the
matrix is pre-populated, so this is not called
directly very often (relatively speaking).

Updates #786
shawnlaffan added a commit that referenced this issue Apr 28, 2021
@shawnlaffan
MPD/MNTD: push directly onto the array
1797685 
Avoids a variable declaration.

Updates #786
shawnlaffan added a commit that referenced this issue Apr 28, 2021
@shawnlaffan
MPD/MNTD: convert for-loop to a map
2829086 
Updates #786
shawnlaffan added a commit that referenced this issue Apr 28, 2021
@shawnlaffan
MPD/MNTD: reorder some code
86a76b9 
Get the path lengths before the weights.

Updates #786
shawnlaffan added a commit that referenced this issue Apr 28, 2021
@shawnlaffan
More code re-ordering
6f51858 
Updates #786
@shawnlaffan shawnlaffan mentioned this issue Apr 30, 2021
Closed
shawnlaffan added a commit that referenced this issue Apr 30, 2021
@shawnlaffan
NRI/NTI: Avoid recalculation of most probably LCA depths
fa49008 
Fixes regression introduced in d852492

Updates #786
@shawnlaffan shawnlaffan mentioned this issue May 5, 2021
Closed
@shawnlaffan
Copy link
Owner Author

Mark as fixed.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@shawnlaffan shawnlaffan

Labels
indices
Projects
None yet
Milestone
Release_4.0
Development

No branches or pull requests
1 participant
@shawnlaffan