<jupyter_start><jupyter_text>The "Long Pole" Effect in Gradle's Test ExecutionWhen many tests with different runtimes are executed in parallel on multiple processors, the overall test runtime is that of the processor with the highest load as measured by the summed test execution times. Ideally, this approaches the quotient between total test runtime and number of processors.However, when one processor is assigned an unproportionally high load of tests, the overall runtime will be dominated by this processor: It will have to continue to work off tasks after all other processors have finished, thus becoming the "long pole" in the runtime. [This problem can occur in Gradle's parallel test execution](https://github.com/gradle/gradle/issues/2669).In this notebook, we take a look at how Gradle (in its current versions - 5.x and early 6) schedules tests and how the long pole problem emerges. We investigate an option to improve the situation.A point to make here is that Gradle does not split up a test class for parallelization, so the smallest unit which we distribute is the test class; as we will see below, if we have classes containing long(er)-running, integration-like tests, this increases the potential for running into the "long pole" problem. When we talk about a "test" below, this will usually translate to a test class (JUnit or similar).  SchedulingGradle statically pre-assigns tests to parallel processors using a round-robin approach. The allocation is based solely on the incoming order of the test classes; it does not take into account test size or other information:<jupyter_code>def roundRobin(tests, procCount):
    """ 
    Takes a list of test items and distributes them in a straight-forward round-robin
    fashion amongst the number of given processors.
    :return: a list of `procCount` lists L1 ...Lx, where each Li denotes the tests assigned
             to processor #x.
    """
    procs = [[] for _i in range(procCount)]

    for tIdx, test in enumerate(tests):
        pos = tIdx % procCount
        procs[pos].append(test)
    return procs<jupyter_output><empty_output><jupyter_text>E.g., with 20 tests and 5 processors, they would be allocated as follows:<jupyter_code>prettyPrintAllocations(roundRobin(range(20), 5))<jupyter_output>proc  0 >   0   5  10  15
proc  1 >   1   6  11  16
proc  2 >   2   7  12  17
proc  3 >   3   8  13  18
proc  4 >   4   9  14  19<jupyter_text>So, if tests **0**, **5**, and **10** happen to take very long, processor **0** would become the long pole in this scenario. If the test number is not a multiple of the number of processors, not all processors will get the same number of tests, but the difference in test numbers between two processors will be at most one:<jupyter_code>prettyPrintAllocations(roundRobin(range(8), 3))<jupyter_output>proc  0 >  0  3  6
proc  1 >  1  4  7
proc  2 >  2  5<jupyter_text>ExperimentsWe can take a statistical look at how round-robin scheduling affects the processor loads. Getting Runtime ExamplesFor test runtime data, we start with Gradle's own test classes. In Gradle's own `build.gradle.kts`, we modify the `allprojects` configuration to make the test classes log their runtimes: ```kotlintasks.withType {        outputs.upToDateWhen { false }        addTestListener(object : TestListener {            override fun beforeSuite(suite: TestDescriptor) {}            override fun beforeTest(testDescriptor: TestDescriptor) {}            override fun afterTest(testDescriptor: TestDescriptor, result: TestResult) {            }            override fun afterSuite(suite: TestDescriptor, result: TestResult) {                val duration = result.endTime - result.startTime                println(">>> $suite\t${duration}")            }        })    }``` The resulting times for a few test series are collected in the folder `gradle_test_stats` (see the scripts `timeGradleTests.sh` and `timesOnly.sh` for their generation). Sorting by runtime in descending order and averaging over the series gives an impression of the test classes' runtime distribution:<jupyter_code>timesFiles = pl.Path("gradle_test_stats").glob("*.times")
sums, seriesCount = None, 0
for tfName in timesFiles:
    with open(tfName) as tff:
        vals = sorted((int(l.strip()) for l in tff), reverse=True)
        sums = vals if sums is None else [v+s for v,s in zip(vals, sums)]
        seriesCount += 1
    plt.plot(vals)
plt.xlabel("tests sorted by runtime")
plt.ylabel("runtime / ms")
plt.show()
import statistics as stats
runtimes = [s/seriesCount for s in sums]
longest, median, shortest = runtimes[0], stats.median(runtimes), runtimes[-1]
print(f"Evaluated {seriesCount} overall test executions with {len(sums)} test classes each.\n"
      f"The total runtime for all test classes was {sum(runtimes)/1000:.2f} seconds on average.\n"
      f"On average, the longest class runtime was {longest/1000:.2f} seconds,\n"
      f"the shortest {shortest:.2f} milliseconds, "
      f"with a median of {median:.2f} milliseconds.")<jupyter_output>Evaluated 16 overall test executions with 2053 test classes each.
The total runtime for all test classes was 3348.34 seconds on average.
On average, the longest class runtime was 45.06 seconds,
the shortest 1.44 milliseconds, with a median of 388.00 milliseconds.<jupyter_text>The above graph should actually be made up of bars, since each x position is one test, but unfortunately that looked crappy. It looks like some kind of [exponential](https://en.wikipedia.org/wiki/Exponential_distribution) or power law distribution: Very few test of comparatively high runtimes, and a long tail of very short-running tests.If run entirely sequentially, we could expect the test classes to take approx. 55 minutes. Simulating Load DistributionGiven these runtimes, we can simulate what the resulting processor load distributions would be with round robin. Since the ordering in Gradle is currently agnostic with regard to size, we shuffle the test runtimes first. The result might look like this:<jupyter_code>import random
shuffledTimes = list(runtimes)
random.shuffle(shuffledTimes)

procCount = 4

prettyPrintStats(roundRobin(shuffledTimes, procCount))<jupyter_output>proc  0 > # 514 tests Σ 856.71 seconds
proc  1 > # 513 tests Σ 781.92 seconds
proc  2 > # 513 tests Σ 839.05 seconds
proc  3 > # 513 tests Σ 870.65 seconds<jupyter_text>The distribution among the processors will vary, but it will most likely not be even. We can sort the processors by assigned sums, and repeat the whole procedure a few times to get an impression of the skew:<jupyter_code>def repeatedlyAllocate(testTimes, procCount, seriesCount):
    """
        Shuffle the given test times and repeatedly allocate them to
        the given number of processors.
        
        :return: a list of 'procCount' elements,
                 where each list contains the 'seriesCount' test allocations to that processor
    """

    shuffledTimes = testTimes
    # for each processor, keep a list of the sum over the tests,
    # sorted by summed allocation
    pSortedSums = [[] for _ in range(procCount)]
    for _s in range(seriesCount):
        random.shuffle(shuffledTimes)
        # longest first:
        sortedSums = sorted([sum(l) for l in roundRobin(shuffledTimes, procCount)], reverse=True)
        for pList, s in zip(pSortedSums, sortedSums):
            pList.append(s)

    return pSortedSums
seriesCount = 2000
pSortedSums = repeatedlyAllocate(shuffledTimes, procCount, seriesCount)
plotDistributions(pSortedSums)
pSums = [sum(l) for l in pSortedSums]
processorTimes = [(s/1000)/seriesCount for s in pSums]

for pIdx, pTimes in enumerate(processorTimes):
    print(f"Proc {pIdx} > {pTimes:.2f} seconds average allocation")
diff = processorTimes[0]-processorTimes[-1]
print(f"On average, the longest-running proc took {diff:.2f} seconds ({diff/processorTimes[-1]:.1%}) longer than the shortest-running one.")<jupyter_output>Proc 0 > 921.08 seconds average allocation
Proc 1 > 858.83 seconds average allocation
Proc 2 > 811.70 seconds average allocation
Proc 3 > 756.72 seconds average allocation
On average, the longest-running proc took 164.37 seconds (21.7%) longer than the shortest-running one.<jupyter_text>There is a slight skew, although it (probably - since this depends on random values) does not seem that big. However, there are two _buts_ here: Bad RatiosThis was only the average ratio. The complete histogram over the ratios of highest load / smallest load for the different series looks like this:<jupyter_code>def plotAllocationRatioDistribution(pSortedSums, tooMuchThreshold=1.3):
    highestLoadProc, lowestLoadProc = pSortedSums[0], pSortedSums[-1]

    ratios = [h/l for h,l in zip(highestLoadProc, lowestLoadProc)]
    plt.hist(ratios)
    plt.xlabel("ratio highest/lowest processor load")
    plt.ylabel("count")
    plt.show()

    ratioOfTooMuchRatios = len([r for r in ratios if r >= tooMuchThreshold])/len(ratios)
    print(f"In {ratioOfTooMuchRatios:.2%} of the cases, the highest load is at least {tooMuchThreshold} times the lowest load.")
    print(f"The maximum ratio of highest to lowest load is {max(ratios):.2f}.")

plotAllocationRatioDistribution(pSortedSums)<jupyter_output><empty_output><jupyter_text>We can pick out and plot the worst allocation:<jupyter_code>_maxRatio, maxIndex = max((high/low, i) for i, (high, low) in enumerate(zip(pSortedSums[0], pSortedSums[-1])))
maxSkewAllocation = [[procList[maxIndex]] for procList in pSortedSums]
plotDistributions(maxSkewAllocation)<jupyter_output><empty_output><jupyter_text>In practice, AFAIK, for a given set of test classes, the order in which they are processed in Gradle is stable. So any particularly bad example of the test series above might be one constantly encountered for a given set of test classes. Apart from that, a single new test class can make the ordering and hence the class allocation and overall test runtime jump all of a sudden.  Longer testsThe Gradle test classes collection represents a rather ideal case: It contains very many test classes with mostly very short runtimes (<1 sec). The results look different when you add test classes with runtimes in the minutes. We can generate a collection of random times (with an admittedly somewhat arbitrarily chosen power law distribution) and add them to the mix:<jupyter_code>import numpy as np

longTestsCount = 100
maxDurationMs = 10 * 60 * 1000 # 10 mins in ms
minDurationMs = 45 * 1000 # 45 secs

longerRuntimes = [(maxDurationMs-minDurationMs)*v+minDurationMs for v in np.random.power(0.5, size=(longTestsCount,))]
plotTestRuntimeDistribution(longerRuntimes)<jupyter_output><empty_output><jupyter_text>Adding those to our Gradle tests gives the following overall test times distribution:<jupyter_code>allRuntimes = longerRuntimes + runtimes

plotTestRuntimeDistribution(allRuntimes)
print(f"Gradle test times = {sum(runtimes)/1000:.1f} secs")
print(f"Longer test times = {sum(longerRuntimes)/1000:.1f} secs")
print(f"Total  test times = {sum(allRuntimes)/1000:.1f} secs")<jupyter_output><empty_output><jupyter_text>And allocating these tests gives a higher load skew:<jupyter_code>allSortedSums = repeatedlyAllocate(allRuntimes, procCount, seriesCount)
plotDistributions(allSortedSums)
plotAllocationRatioDistribution(allSortedSums, tooMuchThreshold=1.5)
_maxRatio, maxIndex = max((high/low, i) for i, (high, low) in enumerate(zip(allSortedSums[0], allSortedSums[-1])))
maxSkewAllocation = [[procList[maxIndex]] for procList in allSortedSums]
plotDistributions(maxSkewAllocation)<jupyter_output><empty_output><jupyter_text>In all likelihood, that distribution looks "long-poley". (Or "short-poley" with a single lazy processor, or just extremely skewed, depending on how the random values came out.) At any rate, the lowest and highest loads are bound to be far more apart than they should be. Effect Of SortingGradle records test durations, so we can use that information to fix the ordering of the tests for allocation. [This has been proposed as a simple fix by the Gradle team themselves](https://github.com/gradle/gradle/issues/2669issuecomment-400261249).Trying it out is straight-forward:<jupyter_code>allRuntimesSorted = sorted(allRuntimes, reverse=True)
allocationBySorting = roundRobin(allRuntimesSorted, procCount)
prettyPrintStats(allocationBySorting)
summedAllocations = [[sum(procL)] for procL in allocationBySorting]
plotDistributions(summedAllocations)
roRoRatio = (summedAllocations[0]/summedAllocations[-1][0])[0]
print(f"For the allocation with sorting, the ratio between highest and lowest load is {roRoRatio:.2f} (or an increase of {roRoRatio-1:.2%}).")<jupyter_output>For the allocation with sorting, the ratio between highest and lowest load is 1.07 (or an increase of 7.16%).<jupyter_text>The allocation across the processors is clearly more even. We can also contrast this specific allocation with the set of random ones from the previous experiments:<jupyter_code>allRatios = [high/low for high, low in zip(allSortedSums[0], allSortedSums[-1])]
equalOrHigherRatios = [r for r in allRatios if r > roRoRatio]
print(f"Of the random allocations, {len(equalOrHigherRatios)/len(allRatios):.2%} have a worse highest/lowest load ratio than the allocation with sorting.")<jupyter_output>Of the random allocations, 99.50% have a worse highest/lowest load ratio than the allocation with sorting.<jupyter_text>It seems fair to say that sorting by size before allocating provides an enormous advantage.However, combining sorting with round robin has the flaw of introducing a systematic imbalance: Given *n* processors, we are partitioning the tests into consecutive subsequences of length *n* each. Since the tests are sorted by sice, each subsequence also begins with its largest test and ends with the smallest. And since each subsequence is assigned from processor *0* to processor *(n-1)*, the first processor always gets the largest test of each subsequence, and the last processor always the smallest.  Shifting Round RobinWe can break up the imbalance of sorted allocation with round robin through a minimal change: After every allocation of a test subsequence to the processors, we don't start the next allocation round on the same processor as the last round, but shift one processor ahead. E.g., nine tests allocated to three processors:In standard round robin, each block of three starts on processor 0:| test | 0 | 1 | 2 || 3 | 4 | 5 || 6 | 7 | 8 || -    | - | - | - || - | - | - || - | - | - || proc | 0 | 1 | 2 || 0 | 1 | 2 || 0 | 1 | 2 | In shifting round robin, the allocations of each block shift through the processors:| test | 0 | 1 | 2 || 3 | 4 | 5 || 6 | 7 | 8 || -    | - | - | - || - | - | - || - | - | - || proc | 0 | 1 | 2 || 1 | 2 | 0 || 2 | 0 | 1 |As a result, the processors each get a rotating share of each subsequence. E.g., the first processor will get the largest test of the first sequence, but the smallest of the second, and so on. The invariant of the number of tests being distributed as evenly as possible is maintained, but the sizes are "smeared" across the processors. A toy example with tests of simple, linearly increasing sizes illustrates the effect.Doing standard round robin with sorted tests first:<jupyter_code>allocation = roundRobin(sorted([100*i for i in range(1, 21)], reverse=True), 5)
prettyPrintAllocations(allocation)
print()
prettyPrintStats(allocation)
def shiftingRoundRobin(tests, procCount):
    """ 
    Takes a list of test items and distributes them in a shifting round-robin
    fashion amongst the number of given processors.
    :return: a list of `procCount` lists L1 ...Lx, where each Li denotes the tests assigned
             to processor #x.
    """
    
    procs = [[] for _i in range(procCount)]

    for tIdx, test in enumerate(tests):
        shift = (tIdx//procCount)%procCount
        pos = (shift + tIdx) % procCount
        procs[pos].append(test)
    return procs

allocation = shiftingRoundRobin(sorted([100*i for i in range(1, 21)], reverse=True), 5)
prettyPrintAllocations(allocation)
print()
prettyPrintStats(allocation)<jupyter_output>proc  0 >  2000  1100   700   300
proc  1 >  1900  1500   600   200
proc  2 >  1800  1400  1000   100
proc  3 >  1700  1300   900   500
proc  4 >  1600  1200   800   400

proc  0 > # 4 tests Σ 4.10 seconds
proc  1 > # 4 tests Σ 4.20 seconds
proc  2 > # 4 tests Σ 4.30 seconds
proc  3 > # 4 tests Σ 4.40 seconds
proc  4 > # 4 tests Σ 4.00 seconds<jupyter_text>With standard round robin, we get a ratio of 5.0 to 3.4 for highest / lowest processor load. With shifting round robin, this is reduced to 4.4 to 4.0. For our scenario with long tests, the effect is also noticeable:<jupyter_code>allRuntimesSorted = sorted(allRuntimes, reverse=True)
shiftingRoRoAllocation=shiftingRoundRobin(allRuntimesSorted, procCount)
prettyPrintStats(shiftingRoRoAllocation)
shiftingRatio = (shiftingRoRoAllocation[0]/shiftingRoRoAllocation[-1][0])[0]
print(f"For the allocation with sorting, the ratio between highest and lowest load is {shiftingRatio:.2f} (or an increase of {shiftingRatio-1:.2%}).")
allRatios = [high/low for high, low in zip(allSortedSums[0], allSortedSums[-1])]
equalOrHigherRatios = [r for r in allRatios if r > shiftingRatio]
print(f"Of the random allocations, {len(equalOrHigherRatios)/len(allRatios):.2%} have a worse highest/lowest load ratio than sorting + shifting.")<jupyter_output>For the allocation with sorting, the ratio between highest and lowest load is 1.06 (or an increase of 5.90%).
Of the random allocations, 99.75% have a worse highest/lowest load ratio than sorting + shifting.
{'fraction_non_alphanumeric': 0.0795706253194752, 'fraction_numerical': 0.02601238143920032, 'mean_word_length': 4.504220068771491, 'pattern_counts': {'":': 0, '<': 53, '<?xml version=': 0, '>': 85, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '15', 'dir': 'jupyter-structured-clean-dedup', 'id': '129138', 'license': 'MIT', 'n_tokens_mistral': 5398, 'n_tokens_neox': 4937, 'n_words': 2127, 'path': 'LongPoleTests.ipynb', 'repo_name': 'hansi-b/Long-Poles', 'size': '17607'}