Decrease iterating overhead in timeit

[serhiy-storchaka]

BPO	21988
Nosy	@gvanrossum, @tim-one, @arigo, @birkenfeld, @rhettinger, @pitrou, @vstinner, @stevendaprano, @alex, @bitdancer, @serhiy-storchaka, @gvanrossum
Files	timeit_unroll_loops.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2014-07-17.03:30:19.089>
created_at = <Date 2014-07-16.09:06:24.500>
labels = ['type-feature', 'library']
title = 'Decrease iterating overhead in timeit'
updated_at = <Date 2014-07-22.12:10:22.220>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2014-07-22.12:10:22.220>
actor = 'serhiy.storchaka'
assignee = 'none'
closed = True
closed_date = <Date 2014-07-17.03:30:19.089>
closer = 'gvanrossum'
components = ['Library (Lib)']
creation = <Date 2014-07-16.09:06:24.500>
creator = 'serhiy.storchaka'
dependencies = []
files = ['35966']
hgrepos = []
issue_num = 21988
keywords = ['patch']
message_count = 14.0
messages = ['223185', '223187', '223190', '223212', '223213', '223215', '223216', '223231', '223240', '223311', '223312', '223313', '223433', '223666']
nosy_count = 12.0
nosy_names = ['gvanrossum', 'tim.peters', 'arigo', 'georg.brandl', 'rhettinger', 'pitrou', 'vstinner', 'steven.daprano', 'alex', 'r.david.murray', 'serhiy.storchaka', 'Guido.van.Rossum']
pr_nums = []
priority = 'normal'
resolution = 'wont fix'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue21988'
versions = ['Python 3.5']

[serhiy-storchaka]

Currently timeit has significant iterating overhead when tests fast statements. Such overhead makes hard to measure effects of microoptimizations. To decrease overhead and get more precise results we should repeat tested statement many times:

$ ./python -m timeit -s "x=10"  "x+x"
1000000 loops, best of 3: 0.2 usec per loop
$ ./python -m timeit -s "x=10"  "x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x; x+x"
100000 loops, best of 3: 14.6 usec per loop

Proposed patch makes it automatically for user. It unrolls and vectorize the loop, and decreases iterating overhead 1000 times:

$ ./python -m timeit -s "x=10"  "x+x"
10000000 loops, best of 3: 0.141 usec per loop

An user gets precision value without explicit cumbersome repeating.

[stevendaprano]

Looks good, but I think it is better to have an "unroll" option rather than do it automatically. I'm okay with the default being to unroll, but sometimes I want to compare the speed between different versions of Python, and having unroll=False to ensure the same behaviour between versions would be good.

[pitrou]

Indeed, what's good for CPython may be quite annoying for e.g. a JIT-enabled Python implementation. I wonder what the PyPy developers think about this.

[alex]

I think this is likely to make timeit less representative of how code actually performs in the real world on systems with a JIT. This is because of the cost of sequential operations is not strictly "additive" on PyPy.

If you have statements a and b, and you run a; b on PyPy, the performance of a; b is usually faster than the sum of a, b, assuming they are not 100% independent.

This is because the JIT will be able to remove type checks that were already performed. Since this just repeats the same statement, the cost of the unrolled iterations beyond the first will be massively lower in many cases, producing confusing results.

[pitrou]

Thanks, then I guess I'm -1 on the patch.

[arigo]

The opposite argument might be relevant too: in some cases, a tracing JIT compiler seeing a long block of code might perform artificially worse. If each repeated line creates a branching path with two outcomes of roughly equal likeliness, then if the line is repeated 20 times, the JIT will need to compile 2**20 different paths before it has fully warmed up. In practice, it will never fully warm up and will run with the constant huge overhead of finding and compiling more paths.

[arigo]

...but I don't think PyPy should be by itself a good enough reason to reject this patch. It would be fine if timeit detects which interpreter it runs on, and only tries to unroll on CPython, for example.

[stevendaprano]

On Wed, Jul 16, 2014 at 02:49:31PM +0000, Armin Rigo wrote:

...but I don't think PyPy should be by itself a good enough reason to
reject this patch. It would be fine if timeit detects which
interpreter it runs on, and only tries to unroll on CPython, for
example.

I would *much* rather a parameter to timeit which controls whether or
not to unroll, rather than timeit trying to guess whether you want it to
unroll or not. PyPy can default to off, CPython to on, and other
implementations can choose whichever default makes sense for them.

[pitrou]

Le 16/07/2014 12:43, Steven D'Aprano a écrit :

I would *much* rather a parameter to timeit which controls whether or
not to unroll, rather than timeit trying to guess whether you want it to
unroll or not. PyPy can default to off, CPython to on, and other
implementations can choose whichever default makes sense for them.

I think it is overkill. Apart from rather silly microbenchmarks, there
isn't much point in adding the loop unrolling facility. In real world,
even cheap operations such as "x = x + 1" will be surrounded by less
cheap operations, so if an improvement cannot yield tangible benefits
inside a simple for loop, then it doesn't deserve to be committed.

[tim-one]

I'm afraid "microoptimizations" aren't worth measuring to begin with, since, well, they're "micro" ;-) Seriously, switch compilers, compilation flags, or move to a new release of a single compiler, and a micro-optimization often turns into a micro-pessimization. If I _want_ to measure something unrolled, I'll unroll it myself. But since I almost never want to measure something unrolled anyway, an option to do so would just be "yet another attractive nuisance" to me.

[gvanrossum]

I don't see the value in this complication. Please close as won't fix.

[gvanrossum]

(Had to switch identities to close it.)