Page MenuHomePhabricator

Disperse task subpriorities in blocks

Authored by epriestley on May 19 2017, 5:09 AM.



Ref T7664. The current algorithm for moving task subpriorities can end up stuck in a real sticky swamp in some unusual situations.

Instead, use an algorithm which works like this:

  • When we notice two tasks are too close together, look at the area around those tasks (just a few paces).
  • If things look pretty empty, we can just spread the tasks out a little bit.
  • But, if things are still real crowded, take another look further.
  • Keep doing that until we're looking at a real nice big spot which doesn't have too many tasks in it in total, even if they're all in one place right now.
  • Then, move 'em out!


  • Just swallow our pride and do the gross INSERT INTO ... "", "", "", "", "", "", ... ON DUPLICATE KEY UPDATE to bulk update.
  • Fix an issue where a single move could cause two different subpriority recalculations.
Test Plan
  • Changed ManiphesTaskTestCase->testTaskAdjacentBlocks() to insert 1,000 tasks with identical subpriorities, saw them spread out in 11 queries instead of >1,000.
  • Dragged tons of tasks around on workboards.
  • Ran unit tests.

Diff Detail

rP Phabricator
Automatic diff as part of commit; lint not applicable.
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

epriestley created this revision.May 19 2017, 5:09 AM
epriestley updated this revision to Diff 43194.May 19 2017, 5:23 AM

Often, we end up with a larger range than we need to put the minimum amount of space between tasks.

When we do, distribute the tasks evenly over the range, rather than putting them at the beginning of the range with the minimum amount of space between them. This limits the chance that we'll end up just moving tasks back and forth because we distributed tasks so they end up in exactly-maximum-density blocks.

epriestley updated this revision to Diff 43195.May 19 2017, 5:37 AM
  • Slightly more precise comment wording.
chad accepted this revision.May 19 2017, 1:34 PM

Oh man

This revision is now accepted and ready to land.May 19 2017, 1:34 PM

I'm going to hold this until after release cut and bulk up the test coverage a bit, the we can kick the tires on this install for a little while before it goes out into the wild.

The fundamental "approximate a double-linked list using doubles" approach here still doesn't feel particularly great and I think probably never will, but this version of the dispersal code feels much more like a real algorithm than previous iterations did.

  • Remove withSubpriorityBetween() query stuff.
  • Add some additional tests (moving to beginning/end, moving to current position).
This revision was automatically updated to reflect the committed changes.