2to3 Fix_imports optimization

[nedds]

BPO	3218
Nosy	@benjaminp
Files	pytree.py: New version of pytree fix_imports.py: New version of fix_imports.py fix_imports.diff: Corrected changes fix_imports.diff: Diff for fix_imports, pytree, and test suite changes

^{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 2008-08-25.15:08:21.940>
created_at = <Date 2008-06-27.18:19:05.777>
labels = ['expert-2to3', 'performance']
title = '2to3 Fix_imports optimization'
updated_at = <Date 2008-08-25.15:08:21.939>
user = 'https://bugs.python.org/nedds'

bugs.python.org fields:

activity = <Date 2008-08-25.15:08:21.939>
actor = 'benjamin.peterson'
assignee = 'collinwinter'
closed = True
closed_date = <Date 2008-08-25.15:08:21.940>
closer = 'benjamin.peterson'
components = ['2to3 (2.x to 3.x conversion tool)']
creation = <Date 2008-06-27.18:19:05.777>
creator = 'nedds'
dependencies = []
files = ['10751', '10756', '10791', '10922']
hgrepos = []
issue_num = 3218
keywords = ['patch']
message_count = 12.0
messages = ['68840', '68860', '69051', '69055', '69635', '69655', '69806', '69807', '69855', '69861', '69864', '69865']
nosy_count = 3.0
nosy_names = ['collinwinter', 'benjamin.peterson', 'nedds']
pr_nums = []
priority = 'high'
resolution = 'accepted'
stage = None
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue3218'
versions = []

[nedds]

This is an optimization in pytree.py specifically for the bare_name
pattern from fix_imports.py. It also has the isinstance change I
previously suggested piggybacked onto it. Because the bare_name pattern
is so massive (764 nodes!), it is very slow to call _recursive_matches
on it. This fix has a special bare_name_matches fix that uses an
iterative matching solution specifically tailored to the bare_name
pattern. From preliminary testing, it appears to be roughly 25-30%
faster than the previous version of 2to3. If I uncomment the fix_imports
test, it fails 6 of them, but they are the same ones failed by the
current version of 2to3 and it fails them in the same way, so I think it
works. As with my previous isinstance chance, a one line change to
test_pytree is required.

[nedds]

Here are the changes we talked about to fix_imports.py which remove the
functionality for members. This causes a substantial performance boost,
as fix_imports was the main bottleneck for 2to3.

[collinwinter]

The change to pytree.py doesn't add much speed benefit over the
fix_imports.py change, and causes a test to fail.

The fix_imports.py change, on the other hand, takes the test suite run
time from 8m31s down to 1m45s -- this needs to go in!

That said, I don't think the change is correct: you remove the portion
of the pattern that matches "from foo import bar, baz, x, y as z", as
well as the portion that matches "foo.bar" in the body of the code,
where foo is a module to be renamed. These should be added back, but
with support for member matching removed.

[nedds]

Here is a diff for the both the fix_imports changes which I corrected,
and the pytree changes. The pytree changes were a lot more significant
before the fix_imports change, but I think they are still a decent
improvement. I think I have now restored the functionality you wanted
without the members, although I'm not quite sure I made the patterns
exactly right. I tested the from a import b as c, as well as in text
foo.bar references, and they seemed to be corrected properly.

[collinwinter]

fix_imports.diff fails to apply cleanly against HEAD of fix_imports.py.
Also, fix_imports2 now inherits from fix_imports, so it needs to be
fixed as well.

+ yield """power< module_name=%r
+ trailer<'.' import_as_names< any > > any* >
+ """ % old_module

Why are you using import_as_names here? That's meant to match a series
of "NAME [as NAME]" in import statements, where this part of the pattern
is meant to match usages of "urllib.foo()" in the code.

[nedds]

Yeah that import_as_names definitely shouldn't be there. I don't know
what I was thinking at the time, but that should just be an any I
believe. I'll clean this up today or tomorrow, update fix_imports2 as
well, and try to fix the tests for fix_imports.

[benjaminp]

I've fixed the tests, so you can cross that one off your list. However,
the buildbots are now failing because lib2to3 takes too long to test.
How soon can we have this optimization applied?

[nedds]

I can hopefully have it all fixed up by tonight or tomorrow.

[benjaminp]

Can we expect this in the next 2 hours? It's fine if not, I just need to
know whether the 2to3 tests should be disabled for the beta.

[nedds]

It should be done tonight, but probably not until around 11 central
time. Sorry for the delay.

[nedds]

Sorry I couldn't have this done earlier today. I updated the test suite,
and this is now passing all tests. Collin, could you verify that is has
all the functionality you were expecting? If the member functionality
turns out to actually be important for any of the modules in
fix_imports, it probably makes the most sense to break them out into
their own fixer. As an added note, I think there is still further room
to optimize fix_imports, specifically the very large pattern it still
generates, so I'm going to work on that at some point.

[benjaminp]

Thanks very much for getting this done! I checked in the changes in
r65053, so they can make beta 2. I'm leaving the issue open, though, in
case Collin wants to make more changes.