Opened 11 years ago
Last modified 6 years ago
#512 new optimization
Optimize 'Move groups' for speed
Reported by: | westram | Owned by: | devel |
---|---|---|---|
Priority: | major | Milestone: | wishlist |
Component: | ARB_NTREE | Version: | SVN |
Keywords: | Cc: |
Description (last modified by westram)
Used algorithm
- is far too slow,
- doesn't scale well.
- seems similar to building a consensus (which is much faster; see )
Compare current runtimes:
| #species | time moveNodeInfo | time consensusTree |
??? | 40k | 10 min | 14 sec |
SILVA128 SSURef NR99 | 645k | ~110 hours | 80 min |
(~ := quite precise estimation at 3% with [17190])
(Note: runtime of consensus generation is much faster, because selecting one branch does exclude many other branches from the branch pool)
Optimization notes:
- most time spent is in bitstring-compare (BCMP)
- already tried vectorization of BCMP (while working on #780; w/o success due to array-indexing)
- attempt to avoid BCMPs:
there is no need to calc BCMP- if MINPEN≥BESTPEN, with
- BESTPEN = lowest penalty for currently checked group so far
- MINPEN = minimum penalty to expect
e.g.: if treesize=500, sourcesize=100 and destsize=10
→ min. normal penalty = 90 = |100-10| = |sourcesize-destsize|
→ min. keeled penalty = 390 = |100-490| = |sourcesize-(treesize-destsize)|
⇒ MINPEN = 90
- if "move marked only" is active and group does not contain marked species (requires #792)
- if MINPEN≥BESTPEN, with
Change History (9)
comment:1 Changed 8 years ago by westram
- Description modified (diff)
comment:2 Changed 8 years ago by westram
- Description modified (diff)
comment:3 Changed 8 years ago by westram
- Description modified (diff)
- Milestone set to wishlist
comment:4 Changed 8 years ago by westram
- Description modified (diff)
comment:5 Changed 7 years ago by westram
- Priority changed from normal to major
comment:6 Changed 7 years ago by westram
- Description modified (diff)
comment:7 Changed 6 years ago by westram
- Description modified (diff)
comment:8 Changed 6 years ago by westram
- Description modified (diff)
- Summary changed from Optimize 'Move node info' for speed to Optimize 'Move groups' for speed
comment:9 Changed 6 years ago by westram
- Description modified (diff)
Note: See
TracTickets for help on using
tickets.