Faster implementation to collapse non-consecutive ip-addresses

[cmn]

BPO	23266
Nosy	@pitrou, @serhiy-storchaka
Files	ipaddress_collapse_non_consecutive_performance.diff: The patch on ipaddress.py testrig.tar.gz: test rig for performance eval collapse.patch ipaddress_faster_collapse3.patch ipaddress_faster_collapse4.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 2015-01-18.22:43:28.773>
created_at = <Date 2015-01-18.12:32:34.139>
labels = ['library', 'performance']
title = 'Faster implementation to collapse non-consecutive ip-addresses'
updated_at = <Date 2015-01-20.23:48:27.416>
user = 'https://bugs.python.org/cmn'

bugs.python.org fields:

activity = <Date 2015-01-20.23:48:27.416>
actor = 'cmn'
assignee = 'none'
closed = True
closed_date = <Date 2015-01-18.22:43:28.773>
closer = 'serhiy.storchaka'
components = ['Library (Lib)']
creation = <Date 2015-01-18.12:32:34.139>
creator = 'cmn'
dependencies = []
files = ['37762', '37763', '37764', '37768', '37794']
hgrepos = []
issue_num = 23266
keywords = ['patch']
message_count = 15.0
messages = ['234239', '234240', '234241', '234242', '234245', '234253', '234254', '234282', '234283', '234286', '234287', '234288', '234382', '234389', '234410']
nosy_count = 5.0
nosy_names = ['pitrou', 'pmoody', 'python-dev', 'serhiy.storchaka', 'cmn']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue23266'
versions = ['Python 3.5']

[cmn]

I found the code used to collapse addresses to be very slow on a large number (64k) of island addresses which are not collapseable.

The code at

cpython/Lib/ipaddress.py

Line 349 in 0f164cc

# sort and dedup

was found to be guilty, especially the index lookup.
The patch changes the code to discard the index lookup and have _find_address_range return the number of items consumed.
That way the set operation to dedup the addresses can be dropped as well.

Numbers from the testrig I adapted from http://bugs.python.org/issue20826 with 8k non-consecutive addresses:

Execution time: 0.6893927365541458 seconds
vs.
Execution time: 12.116527611762285 seconds

MfG
Markus Kötter

[cmn]

Added the testrig.

[pitrou]

This is great, thank you. Can you sign the contributor's agreement?
https://www.python.org/psf/contrib/contrib-form/

[pitrou]

Here is an updated patch with a fix to the tests and docstrings.

[cmn]

I just signed the agreement, ewa@ is processing it.

[python-dev]

New changeset f7508a176a09 by Antoine Pitrou in branch 'default':
Issue bpo-23266: Much faster implementation of ipaddress.collapse_addresses() when there are many non-consecutive addresses.
https://hg.python.org/cpython/rev/f7508a176a09

[pitrou]

Ok, I've committed the patch. Thank you!

[serhiy-storchaka]

Deduplication should not be omitted. This slowed down collapsing of duplicated addresses.

$ ./python -m timeit -s "import ipaddress; ips = [ipaddress.ip_address('2001:db8::1000') for i in range(1000)]" -- "ipaddress.collapse_addresses(ips)"

Before f7508a176a09:
100 loops, best of 3: 13.4 msec per loop

After f7508a176a09:
10 loops, best of 3: 129 msec per loop

Proposed patch restores performance for duplicated addresses and simplifies the code using generators.

[pitrou]

Good catch. What is the performance on the benchmark posted here?

[serhiy-storchaka]

What is the performance on the benchmark posted here?

The same as with current code.

[pitrou]

Then +1. The patch looks fine to me.