~launchpad-pqm/launchpad/devel

= Tunable Loops =

Some large jobs have to be done in smaller chunks, e.g. because you want to
report progress to a user, or you're holding locks that others may be waiting
for.  But you can't always afford to stop and look at your watch every
iteration of your loop: sometimes you need to decide how big your chunk will
be before you start processing it.

One way to solve this is to measure performance of your loop, and pick a chunk
size that will give you decent performance while also stopping at more or less
regular intervals to update your progress display, refresh your locks, or
whatever else you want to do.  But what if the Moon is in the House of Uranus
and the server slows down?  Conversely, you may be wasting time if you stop too
often.

The LoopTuner solves this.  You tell it what you want to do and how long each
chunk should take, and it will figure out how many items you need to process
per chunk to get close to your ideal time between stops.  Chunk sizes will
adjust themselves dynamically to actual performance.

    >>> import math
    >>> from zope.interface import implements
    >>> from lp.services.looptuner import ITunableLoop
    >>> from lp.services.looptuner import LoopTuner

The LoopTuner requires the operation you define for it to implement the
ITunableLoop interface.

    >>> class NotATunableLoop:
    ...     def isDone(self):
    ...         return True
    ...     def __call__(self, chunk_size):
    ...         "This never gets called"
    >>> LoopTuner(NotATunableLoop(), 1, 10)
    Traceback (most recent call last):
    ...
    AssertionError


== Chunk Size Convergence ==

Here's a very simple ITunableLoop.  It receives a list of timings to simulate
for its iterations (it finishes when the list runs out), and for every
iteration, prints out what happened to its chunk size parameter.

The printout includes a logarithmic order-of-magnitude indication, where "no
change" is zero, decreases are negative numbers, and increases show up as
positive numbers.  The expectations for these numbers are based on
observation, and could in principle still vary a bit with different CPU
architectures, compilers used for the Python interpreter, etc.

    >>> goal_seconds = 10.0
    >>> def print_change(last_chunk_size, new_chunk_size):
    ...     if last_chunk_size is None:
    ...         print "start"
    ...         return
    ...     change = "same"
    ...     if new_chunk_size > last_chunk_size:
    ...         change = "increased"
    ...     elif new_chunk_size < last_chunk_size:
    ...         change = "decreased"
    ...     ratio = new_chunk_size / last_chunk_size
    ...     order_of_magnitude = math.log10(ratio)
    ...     print "%s (%.1f)" % (change, order_of_magnitude)

    >>> class PlannedLoop:
    ...     implements(ITunableLoop)
    ...     def __init__(self, timings):
    ...         self.last_chunk_size = None
    ...         self.iteration = 0
    ...         self.timings = timings
    ...         self.clock = 0
    ...
    ...     def isDone(self):
    ...         done = self.iteration >= len(self.timings)
    ...         if done:
    ...             print "done"
    ...         return done
    ...
    ...     def __call__(self, chunk_size):
    ...         print_change(self.last_chunk_size, chunk_size)
    ...         self.last_chunk_size = chunk_size
    ...         self.clock += self.timings[self.iteration]
    ...         self.iteration += 1


In combination with that, we tweak LoopTuner to simulate the timings we gave
the PlannedLoop.  This is for testing only; in normal use you wouldn't need to
subclass the LoopTuner.

    >>> class TestTuner(LoopTuner):
    ...     def _time(self):
    ...         return float(self.operation.clock)


=== Trivial Case ===

If there's nothing to do, nothing happens.

    >>> body = PlannedLoop([])
    >>> loop = TestTuner(body, goal_seconds, 100)
    >>> loop.run()
    done


=== Ideal Case ===

A typical run using the ITunableLoop follows this pattern: the LoopTuner very
conservatively starts out with the minimum chunk size, finds that its first
iteration finishes well within its time goal, and starts jacking up the work
per iteration until it nears the ideal time per iteration.  Due to practical
variations, it keeps oscillating a bit.

    >>> body = PlannedLoop([5, 7, 8, 9, 10, 11, 10, 9, 10, 9, 10, 11, 10])
    >>> loop = TestTuner(body, goal_seconds, 100)
    >>> loop.run()
    start
    increased (0.2)
    increased (0.1)
    increased (0.1)
    increased (0.0)
    same (0.0)
    decreased (-0.0)
    same (0.0)
    increased (0.0)
    same (0.0)
    increased (0.0)
    same (0.0)
    decreased (-0.0)
    done


=== Slow Run ===

If our iterations consistently exceed their time goal, we stay stuck at the
minimum chunk size.

    >>> body = PlannedLoop([15, 11, 16, 20, 14, 15, 10, 12, 15])
    >>> loop = TestTuner(body, goal_seconds, 100)
    >>> loop.run()
    start
    same (0.0)
    same (0.0)
    same (0.0)
    same (0.0)
    same (0.0)
    same (0.0)
    same (0.0)
    same (0.0)
    done


=== Typical Run ===

What happens usually is that performance is relatively stable, so chunk size
converges to a steady state, but there are occasional spikes.  When one chunk
is suddenly very slow, the algorithm compensates for that so that if the drop
in performance was a fluke, the next chunk falls well short of its time goal.

    >>> body = PlannedLoop([5, 7, 8, 9, 10, 11, 9, 20, 7, 10, 10])
    >>> loop = TestTuner(body, goal_seconds, 100)
    >>> loop.run()
    start
    increased (0.2)
    increased (0.1)
    increased (0.1)
    increased (0.0)
    same (0.0)
    decreased (-0.0)
    increased (0.0)
    decreased (-0.1)
    increased (0.1)
    same (0.0)
    done


== Cost Functions ==

It's up to the ITunableLoop to define what "chunk size" really means.  It's an
arbitrary unit of work.  The only requirement for LoopTuner to do useful work
is that on the whole, performance should tend to increase with chunk size.

Here we illustrate how a tuned loop behaves with different cost functions
governing the relationship between chunk size and chunk processing time.

This variant of the LoopTuner simulates an overridable cost function:

    >>> class CostedLoop:
    ...     implements(ITunableLoop)
    ...     def __init__(self, cost_function, counter):
    ...         self.last_chunk_size = None
    ...         self.iteration = 0
    ...         self.cost_function = cost_function
    ...         self.counter = counter
    ...         self.clock = 0
    ...
    ...     def isDone(self):
    ...         done = (self.iteration >= self.counter)
    ...         if done:
    ...             print "done"
    ...         return done
    ...
    ...     def __call__(self, chunk_size):
    ...         print_change(self.last_chunk_size, chunk_size)
    ...         self.last_chunk_size = chunk_size
    ...         self.iteration += 1
    ...
    ...     def computeCost(self):
    ...         return self.cost_function(self.last_chunk_size)


    >>> class CostedTuner(LoopTuner):
    ...     def __init__(self, *argl, **argv):
    ...         self.clock = 0
    ...         LoopTuner.__init__(self, *argl, **argv)
    ...
    ...     def _time(self):
    ...         if self.operation.last_chunk_size is not None:
    ...             self.clock += self.operation.computeCost()
    ...         return self.clock

Below we'll see how the loop tuner adapts to various cost functions.


=== Constant Cost ===

We've already seen a constant-time loop body where every iteration took too
much time, and we got stuck on the minimum chunk size.  Now we look at the
converse case.

If iterations consistently take less than the ideal time, the algorithm will
"push the boundary," jacking up the workload until it manages to fill up the
per-iteration goal time.  This is good if, for instance, the cost function is
very flat, increasing very little with chunk size but with a relatively large
constant overhead.  In that case, doing more work per iteration means more
work done for every time we pay that constant overhead.  And usually, fewer
iterations overall.

Another case where chunk size may keep increasing is where chunk size turns
out not to affect performance at all.  Chunk size is capped to stop it from
spinning into infinity in that case, or if for some reason execution time
should turn out to vary inversely with chunk size.

    >>> body = CostedLoop((lambda c: goal_seconds/2), 20)
    >>> loop = CostedTuner(body, goal_seconds, 100, 1000)
    >>> loop.run()
    start
    increased (0.2)
    increased (0.2)
    increased (0.2)
    ...
    same (0.0)
    same (0.0)
    same (0.0)
    done


=== Linear Cost ===

The model behind LoopTuner assumes that the cost of an iteration will tend to
increase as a linear function of chunk size.  Constant cost is a degenerate
case of that; here we look at more meaningful linear functions.

==== Without Constant ====

If cost function is purely linear with zero overhead, we approach our time
goal asymptotically.  In principle we never quite get there.

    >>> body = CostedLoop((lambda c: c/20), 10)
    >>> loop = CostedTuner(body, goal_seconds, 100)
    >>> loop.run()
    start
    increased (0.2)
    increased (0.1)
    increased (0.0)
    ...
    increased (0.0)
    increased (0.0)
    done

    >>> body.computeCost() < goal_seconds
    True
    >>> body.computeCost() > goal_seconds*0.9
    True


==== With Constant ====

Here's a variant with a relatively flat linear cost function (25 units of work
per second), plus a large constant overhead of half the time goal.  It does
not achieve equilibrium in 10 iterations:

    >>> body = CostedLoop((lambda c: goal_seconds/2+c/25), 10)
    >>> loop = CostedTuner(body, goal_seconds, 100)
    >>> loop.run()
    start
    increased (0.0)
    increased (0.0)
    increased (0.0)
    ...
    increased (0.0)
    done
    >>> body.computeCost() < goal_seconds
    True

But once again it does get pretty close:

    >>> body.computeCost() > goal_seconds*0.9
    True


=== Exponential Cost ===

What if the relationship between chunk size and iteration time is much more
radical?


==== Low Exponent ====

Due to the way LoopTuner's approximation function works, an exponential cost
function will cause some oscillation where iteration time overshoots the goal,
compensates, then finally converges towards it.

If the cost function is highly regular and predictable, the oscillation will
be a neat alternation of oversized and undersized chunks.

We use math.pow here, since __builtin__.pow is overridden by twisted.conch.

    >>> body = CostedLoop(lambda c: math.pow(1.2, c), 50)
    >>> loop = CostedTuner(body, goal_seconds, 1)
    >>> loop.run()
    start
    increased (0.7)
    increased (0.4)
    ...
    decreased (-0.0)
    increased (0.0)
    decreased (-0.0)
    increased (0.0)
    ...
    same (0.0)
    ...
    same (0.0)
    ...
    done


==== High Exponent ====

With more extreme exponential behaviour, the overshoot increases but the
effect remains the same:

We use math.pow here, since __builtin__.pow is overridden by twisted.conch.

    >>> body = CostedLoop(lambda c: math.pow(3, c), 50)
    >>> loop = CostedTuner(body, goal_seconds, 1)
    >>> loop.run()
    start
    increased (0.3)
    ...
    decreased (-0.0)
    increased (0.0)
    decreased (-0.0)
    increased (0.0)
    ...
    same (0.0)
    ...
    same (0.0)
    ...
    done

Most practical algorithms will be closer to the linear cost function than they
are to the exponential one.


== Loop cooldown ==

LoopTuner allows inserting a delay between two consecutive operation runs.

Overriding _coolDown method can be used to avoid an actual cooldown,
but still print out what would happen.

    >>> class CooldownTuner(LoopTuner):
    ...     def _coolDown(self, bedtime):
    ...         if self.cooldown_time is None or self.cooldown_time <= 0.0:
    ...             print "No cooldown"
    ...         else:
    ...             print "Cooldown for %.1f seconds." % self.cooldown_time
    ...         return bedtime

SimpleLoop is a loop that does a constant number of iterations, regardless
of the actual run-time.

    >>> class SimpleLoop:
    ...     implements(ITunableLoop)
    ...     def __init__(self, iterations):
    ...         self.total_iterations = iterations
    ...         self.iteration = 0
    ...         self.clock = 0
    ...
    ...     def isDone(self):
    ...         done = (self.iteration >= self.total_iterations)
    ...         if done:
    ...             print "done"
    ...         return done
    ...
    ...     def __call__(self, chunk_size):
    ...         print "Processing %d items." % (chunk_size)
    ...         self.iteration += 1

Aim for a low goal_seconds (to reduce test runtime), and only 3 iterations.

    >>> goal_seconds = 0.01
    >>> body = SimpleLoop(3)
    >>> loop = CooldownTuner(body, goal_seconds, 1, cooldown_time=0.1)
    >>> loop.run()
    Processing...
    Cooldown for 0.1 seconds.
    Processing...
    Cooldown for 0.1 seconds.
    Processing...
    Cooldown for 0.1 seconds.
    done

=== Cooldown bedtime ===

A private _coolDown method on LoopTuner sleeps for cooldown_time, and
returns time after sleep is done.

    >>> import time
    >>> cooldown_loop = LoopTuner(body, goal_seconds, cooldown_time=0.2)
    >>> old_time = time.time()
    >>> new_time = cooldown_loop._coolDown(old_time)
    >>> print new_time > old_time
    True

If no cooldown_time is specified, there's no sleep, and exactly the same
time is returned.

    >>> no_cooldown_loop = LoopTuner(body, goal_seconds, cooldown_time=None)
    >>> old_time = time.time()
    >>> new_time = no_cooldown_loop._coolDown(old_time)
    >>> print new_time == old_time
    True

== Abort Timeout ==

LoopTuner allows a timeout to be specified. If the loop runs for longer
than this timeout, it is aborted and a WARNING logged.

    >>> body = PlannedLoop([5, 7, 8, 9, 10, 11, 9, 20, 7, 10, 10])
    >>> loop = TestTuner(body, goal_seconds, 100, abort_time=20)
    >>> loop.run()
    start
    same (0.0)
    same (0.0)
    WARNING:...:Task aborted after 20 seconds.


== Cleanup ==

    Loops can define a clean up hook to clean up opened resources.
    We need this because loops can be aborted mid run, so we cannot rely
    on clean up code in the isDone() method, and __del__ is fragile and
    can never be relied on.

    >>> class PlannedLoopWithCleanup(PlannedLoop):
    ...     def cleanUp(self):
    ...         print 'clean up'

    >>> body = PlannedLoopWithCleanup([])
    >>> loop = TestTuner(body, goal_seconds, 100)
    >>> loop.run()
    done
    clean up

    >>> body = PlannedLoopWithCleanup([5, 7, 8, 9, 10, 11, 9, 20, 7, 10, 10])
    >>> loop = TestTuner(body, goal_seconds, 100, abort_time=20)
    >>> loop.run()
    start
    same (0.0)
    same (0.0)
    WARNING:...:Task aborted after 20 seconds.
    clean up