Constructing Bleachermarks with dynamic Benchmarks

[johanrosenkilde]

It can be beneficial to specify an infinite list as benchmarks. Use cases include

1. Adaptatively run benchmarks for X seconds
2. Sequentially run benchmarks for X seconds, each benchmark run for Y seconds.

This issue is to discuss what a reasonable syntax for supporting this is, in the construct of Bleachermark and possibly elsewhere.

A related discussion is whether to (attempt to) protect the user from combining this with benchmarking strategies in a non-sensical way (e.g. interleaved benchmarking on an infinite list makes no sense).

[johanrosenkilde]

nthiery wrote in private email exchange:

A potential alternative to the syntax:

    def my_benchmark(n): return Benchmark([data_generator, sort])
    BleacherMark(my_benchmark, adaptative=True, total_time=...)

could be:

    BleacherMark([data_generator, sort], range=iterable, adaptative=True, ...)

Potential advantages:

• BleacherMark gets more information: it knows it's always the same pipeline.

• Passing a range gives flexibility. Typical useful values:

  • range(10)
  • NN (in Sage ...)
  • [2^n for n in range(10)]
  • (2^n for n in NN)

  adaptative="polynomial" could then provide a reasonable default
  value for the range, like (2^n for n in NN)

[johanrosenkilde]

Miguel and I discussed the following simple solution:

• A Bleachermark takes any iterable of iterables (we discussed aside that users should possibly not be forced to wrap pipelines in Benchmarks themselves).
• An iterable can be infinite. We provide a simple class for providing such an infinite list, e.g.

In [1]: def data_gen(n):
            # generation of input data
            return randomint(2^n)
In [2]: def f(x):
            # computation I wish to benchmark
            return sqrt(x)
In [3]: bs = InfiniteBenchmarkList([ data_gen, lambda n: f ])
In [4]: B = Bleachermark(bs)
In [5]: B.strategy("adaptive", hint="polynomial_time")

This is very close to nthiery's suggestion, but takes behaviour from optional arguments into more explicit structures. It's always a choice where to strike the balance between those two.

[miguelmarco]

I imagine that you mean something like this, right?:

In [1]: def data_gen(n):
            def genrandom(i):
                # generation of input data
                random.seed(i)
                return randomint(2^n)
            return genrandom
In [2]: def f(x):
            # computation I wish to benchmark
            return sqrt(x)
In [3]: bs = InfiniteBenchmarkList([ data_gen, f])

That is, the InfiniteBenchmarkList is parametrized by n (that will correspond to the size of the input generated at the beginning of the pipeline. And each one of those benchmarks uses the runid (i) to set the random seed.

Is that what you meant?

[johanrosenkilde]

Haha, I mean the third option :-D

<what you wrote above>
In [3]: bs = InfiniteBenchmarkList([ data_gen, lambda n: f])

That is, InfiniteBenchmarkList wouldn't be able to distinguish f(x) from lambda n: f, so it couldn't know whether to apply n to it's arguments or not. So it should always do so, in which case you have to wrap a "constant" pipeline function in a lambda.

[miguelmarco]

Gotcha. What about a fourth option?:

In [3]: bs = InfiniteBenchmarkList(lambda n : [ data_gen(n),  f])

[johanrosenkilde]

Hmm, yes, possibly that's the easiest since that lambda already crept into my other suggestion. I was trying to avoid the lambdas. Also, this suggestion would allow returning different length pipelines for various n. But of course, we're semantically disallowing that anyway, so perhaps it's not imperative that we syntactically disallow it as well.

[nthiery]

    Hi,

The syntax I proposed was just one of potentially many; it's good to
explore around!

I like the:

    B.strategy("adaptive", hint="polynomial_time").

I am not sure I see the point of having to create an intermediate
InfiniteBenchmarkList object (at least from a user interface point of
view; it could of course be useful internally). Also specifying a
range seems more flexible; but maybe that can be added later, with
"Infinite" above meaning for now "indexed by natural integers".

I am not in favor of the lambda n: xxx: they introduces some
additional complexity for the caller and hide information to
bleachermark. For example, the fact that the pipeline is explicitly
always the same is actually a feature that bleachermark may actually
want to make use of.

Here is another variant:

In [1]: def data_gen(n):
            return randomint(2^n)
In [2]: def f(x):
            return sqrt(x)
In [3]: bs = InfiniteBenchmarkList([ data_gen, f])

In cases where one wants to make use of the run id, data_gen could
take an optional argument:

In [1]: def data_gen(n, run_id=i):
            random.seed(i)
            return randomint(2^n)

Then bleachermark would detect that optional argument by
introspection, and pass down the run id.

Cheers,

[johanrosenkilde]

I am not sure I see the point of having to create an intermediate
InfiniteBenchmarkList object (at least from a user interface point of
view; it could of course be useful internally). Also specifying a
range seems more flexible; but maybe that can be added later, with
"Infinite" above meaning for now "indexed by natural integers".

My idea is that if the user wants to use a range, he can just concretely
instantiate the list of pipelines with a comprehension: short and
pythonic. The construction for InfiniteBenchmarkList is basically as a
convenient way to make an (enriched) generating expression ranging over
NN (which is not available in pure Python).

I am not in favor of the lambda n: xxx: they introduces some
additional complexity for the caller and hide information to
bleachermark. For example, the fact that the pipeline is explicitly
always the same is actually a feature that bleachermark may actually
want to make use of.

We will probably want to disallow different-sized pipelines in a
Bleachermark in any case. We had a discussion about this, but assuming
that the pipeline always has the same length and same "semantics", we
can simplify a lot:

• We can assume the one set of labels across all benchmarks. So the
  labels will be stored in the Bleachermark.
• Data presentation is vastly simplified since the data fits much better
  in a tabular way.

We argued that we don't really lose out: when do you want to benchmark
across two very different pipelines while still comparing the data? It's
probably possible to come up with something, but in most of those cases
you could probably modulate your "1-pipeline-fits-all" to encompass
both. For instance, if comparing two algorithms, one which had an
intermediate "optimise data" step; the other algorithm could just be
said to have the trivial "optimise data" step.

Here is another variant:

In [1]: def data_gen(n):
            return randomint(2^n)
In [2]: def f(x):
            return sqrt(x)
In [3]: bs = InfiniteBenchmarkList([ data_gen, f])

How would I then construct an InfiniteBenchmarkList where the
f-functions also depend on n?

In cases where one wants to make use of the run id, data_gen could
take an optional argument:

In [1]: def data_gen(n, run_id=i):
            random.seed(i)
            return randomint(2^n)

Then bleachermark would detect that optional argument by
introspection, and pass down the run id.

That's a neat idea we might be able to use whatever structure we end up
with. I've been annoyed at those run_ids all along - Miguel and I
discussed for an hour or so whether to have them at all ;-)

Best,
Johan

[defeo]

I am having a very hard time following you guys. I feel I'm missing some common context you may have developed at SD75 while I was in a different room.

For example, I do not understand what you mean by "adaptive".

I do not understand why the list of Benchmarks should be infinite, whereas Nicolas' use case, if I understand correctly, simply asks to run the same pipeline with inputs coming from an arbitrary iterable, rather than just from [0,N].

A syntax B.run(range=<iterable>), with B.run(N=100) being an alias for B.run(range=range(100)), seems good enough to me.

[johanrosenkilde]

For example, I do not understand what you mean by "adaptive".

This was something Nicolas came up with: consider that you are trying to gauge
how (the running time of) some algorithm develops on larger and larger input. So you'd like to run the algorithm on a "representative set" of input sizes that allows you to plot a size/speed curve with nicely spaced points.

The twist: 1) perhaps you don't know in advance how the function develops (n,
n^2, n^3, 2^n?), and you don't know how long you are willing to run the
computaiton. What you'd like is to just start running the benchmarks, go get a
cup of coffee, come back and interrupt the computation and inspect.

That's what's covered by "Adaptive" and why it makes sense to consider an infinite benchmark list (unbounded input size).

Best,
Johan

[johanrosenkilde]

The way we are considering it, two pipelines that differ only in the size of the "data" that is generated by the first pipeline element, they should be two Benchmarks, run in the same Bleachermark. A "benchmark" is really "a single instance of problem, algorithm (pipeline) and input size" which is called many times only to average over random inputs (of the given size).

Every time we call the first function of a benchmark's pipeline we are serving it a run_id. But this is only supposed to seed a random generator, look up a line number in a data input file, or similar. In particular, don't use it for encoding size of problem. That's abuse.

Thus Bleachermark.run(range=<iterable>) really has no sense. The range could range over run_id but that would only increase the probability that people will abuse the run_id for encoding sizes and such :-)

[defeo]

Ok, I'm starting to get it.

The construction for InfiniteBenchmarkList is basically as a convenient way to make an (enriched) generating expression ranging over NN (which is not available in pure Python).

Isn't this pure python ?

Bleachermark([data_gen(2^n), f] for n in itertools.count())

However something like InfinteBenchmarkList could be a handy utility function to generate the above.

Every time we call the first function of a benchmark's pipeline we are serving it a run_id. But this is only supposed to seed a random generator, look up a line number in a data input file, or similar. In particular, don't use it for encoding size of problem. That's abuse.

In this case, wouldn't it be safer to pass an instance of random.Random to the pipeline? That would prevent any abuse.

Or maybe, less brutal, a hex string.

[nthiery]

On Tue, Sep 13, 2016 at 12:28:59AM -0700, Johan Rosenkilde wrote:

The way we are considering it, two pipelines that differ only in the
size of the "data" that is generated by the first pipeline element,
they should be two Benchmarks, run in the same Bleachermark. A
"benchmark" is really "a single instance of problem, algorithm
(pipeline) and input size" which is called many times only to average
over random inputs (of the given size).

+1

Every time we call the first function of a benchmark's pipeline we are
serving it a run_id. But this is only supposed to seed a random
generator, look up a line number in a data input file, or similar. In
particular, don't use it for encoding size of problem. That's abuse.

+1

Luckily I did not mean to abuse that run_id :-) Let me try to clarify
this with a documentation. Note that this is about the semantic, not
the specific syntax:

BlearcherMark(pipeline, range=iterable)

    pipeline -- a pipeline of functions
    iterable -- an iterable of data

Return a collection of benchmarks sharing the same pipeline and
differing only by the data fed to the first item of the pipeline.

The first item `f` of the pipeline shall take a mandatory
argument. It can also accept a ``run_id`` optional argument.
Typically `f` takes as mandatory input a size (e.g represented by a
non negative integer) and generates some random data for that size.

EXAMPLES::

    sage: B = BleacherMark([random_list, sort], range=NN)
    sage: B.run(adaptative=True, hint="polynomial")

    sage: def data_gen(n, run_id=None):
    ....:     random.seed(run_id)
    ....:     return ...(n)
    sage: B = BleacherMark([data_gen, f], range=...)

Cheers,

[nthiery]

On Tue, Sep 13, 2016 at 05:17:15AM -0700, Luca De Feo wrote:

Bleachermark([data_gen(2^n), f] for n in itertools.count())

Side note: with this syntax BleacherMark can't know that all
benchmarks share the same pipeline.

Yes, itertools.count() is a reasonable alternative to NN in Python, as
long as BleacherMark does not try to detect that the range is NN to do
something specific in that case.

[defeo]

Side note: with this syntax BleacherMark can't know that all benchmarks share the same pipeline.

What more can (realistically) BleacherMark do when it knows, compared to when it does not?