Multi-threaded Binary Search
From arrizza.org wikiJump to navigation Jump to search
- You want to perform a binary search through an ordered array of possibilities.
- Each of the items in the array to evaluate for "pass" or "fail" needs a long time.
- You want to find the highest value that is a "pass".
Example, you have a bug in revision 312 of your code. You know it was ok at revision 289. What is the highest revision that passes? Say it takes 5 minutes to check each revision.
Instead of one thread going through the array, have multiple threads.
e.g. say there are 3 developers (i.e. "threads") A, B, C
set 2 variables currentLow and currentHigh (289 and 312 respectively) set B to search at midpoint between currentLow and currentHigh set A to search at midpoint between currentLow and B set C to search at midpoint between B and currentHigh loop until done TODO: when does it stop? TODO: what if currentLow and currentHigh are only 1 or 2 apart? TODO: check if does values at currentLow and currentHigh? if A fails Stop B & C immediately set currentHigh to A A, B, C choose again if B fails Stop C immediately (A continues) set currentHigh to B rename A as "B" (so B is always the middle one) A chooses midpoint between currentLow and B C chooses midpoint between B and currentHigh if C fails Stop A & B immediately set currentLow to C A, B, C choose again if A passes Set currentLow to A Set A to midpoint between currentLow and B if B passes Stop A immediately (C continues) set currentLow to B set B to midpoint between currentLow and C set A to midpoint between currentLow and B if C passes Stop A & B immediately Set currentLow to C All three choose again