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 tree (which is much faster; see table)

Compare current runtimes:


DB

#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 tree 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
      (this description is too simple; would have worked like that with old hardcoded penalty, as used before #780; check-out whether sth similar is possible with user-defined penalties)
    • if "move marked only" is active and group does not contain marked species (requires #792)

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.