Faster implementation to collapse consecutive ip-networks

[exhuma]

BPO	20826
Nosy	@ncoghlan, @pitrou, @ezio-melotti, @exhuma
Files	faster-collapse-addresses.patch testrig.zip: Testdata and scripts. faster_collapse.patch faster_collapse2.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-05-15.19:05:45.095>
created_at = <Date 2014-03-02.14:39:00.652>
labels = ['library', 'performance']
title = 'Faster implementation to collapse consecutive ip-networks'
updated_at = <Date 2014-05-15.19:05:45.094>
user = 'https://github.com/exhuma'

bugs.python.org fields:

activity = <Date 2014-05-15.19:05:45.094>
actor = 'pitrou'
assignee = 'pmoody'
closed = True
closed_date = <Date 2014-05-15.19:05:45.095>
closer = 'pitrou'
components = ['Library (Lib)']
creation = <Date 2014-03-02.14:39:00.652>
creator = 'exhuma'
dependencies = []
files = ['34267', '34583', '35228', '35233']
hgrepos = []
issue_num = 20826
keywords = ['patch']
message_count = 10.0
messages = ['212553', '213154', '214565', '218305', '218334', '218337', '218340', '218354', '218624', '218625']
nosy_count = 6.0
nosy_names = ['ncoghlan', 'pitrou', 'ezio.melotti', 'pmoody', 'python-dev', 'exhuma']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'commit review'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue20826'
versions = ['Python 3.5']

[exhuma]

This alternative implementation runs over the addresses collection only once, and "backtracks" only if necessary. Inspired by a "shift-reduce" approach.

Technically both are O(n), so the best case is always the same. But the old implementation runs over the *complete* list multiple times until it cannot make any more optimisations. The new implementation only repeats the optimisation on elements which require reconciliation.

Tests on a local machine have shown a considerable increase in speed on large collections of elements (iirc about twice as fast on average).

[pmoody]

Hey Exhuma, thanks for the patch.

Can you give me an example list on which this shift reduce approach works much better?

[exhuma]

Sorry for the late reply. I wanted to take some time and give a more detailed explanation. At least to the best of my abilities :)

I attached a zip-file with my quick-and-dirty test-rig. The zip contains:

• gendata.py -- The script I used to generate test-data
• testdata.lst -- My test-data set (for reproducability)
• tester.py -- A simple script using timeit.timeit.

I am not sure how sensitive the data is I am working with, so I prefer not to put any of the real data on a public forum. Instead, I wrote a small script which generates a data-set which makes the performance difference visible (gendata.py). The data which I processed actually created an even worse case, but it's difficult to reproduce. In my case, the data-set I used is in the file named testdata.lst.

I then ran the operation 5 times using timeit (tester.py).

Let me also outline an explanation to what it happening:

It is possible, that through one "merge" operation, a second may become possible. For the sake of readability, let's use IPv4 addresses, and consider the following list:

[a_1, a_2, ..., a_n, 192.168.1.0/31, 192.168.1.2/32, 192.168.1.3/32, b_1, b_2, ..., b_n]

This can be reduced to

[a_1, a_2, ..., a_n, 192.168.1.0/31, 192.168.1.2/31, b_1, b_2, ..., b_n]

Which in turn can then be reduced to:

[a_1, a_2, ..., a_n, 192.168.1.0/30, b_1, b_2, ..., b_n]

The current implementation, sets a boolean (optimized) to True if any merge has been performed. If yes, it re-runs through the whole list until no optimisation is done. Those re-runs also include [a1..an] and [b1..bn], which is unnecessary. With the given data-set, this gives the following result:

Execution time: 48.27790632040014 seconds
./python tester.py  244.29s user 0.06s system 99% cpu 4:04.51 total

With the shift/reduce approach, only as many nodes are visited as necessary. If a "reduce" is made, it "backtracks" as much as possible, but not further. So in the above example, nodes [a1..an] will only be visited once, and [b1..bn] will only be visited once the complete optimisation of the example addresses has been performed. With the given data-set, this gives the following result:

Execution time: 20.298685277199912 seconds
./python tester.py  104.20s user 0.14s system 99% cpu 1:44.58 total

If my thoughts are correct, both implementations should have a similar "best-case", but the "worst-case" differs significantly. I am not well-versed with the Big-O notation, especially the best/average/worst case difference. Neither am I good at math. But I believe both are strictly speaking O(n). But more precisely, O(k*n) where k is proportional the number of reconciliation steps needed (that is, if one merger makes another merger possible). But it is much smaller in the shift/reduce approach as only as many elements need to be revisited as necessary, instead of all of them.

[pitrou]

From a quick look, the algorithm is indeed correct, and it should perform better on average than the previous one.

Note: both algorithms are O(n**2) worst case, not O(n).

[pitrou]

Here is a much faster patch, around 30x faster than the original code.

With exhuma's data set and tester.py, the original code gives:

$ time python3.4 tester.py 
Execution time: 5.949284339199949 seconds

real 0m30.152s
user 0m30.104s
sys 0m0.016s

The patched code gives:

$ time ./python tester.py 
Execution time: 0.25444041779992405 seconds

real 0m1.695s
user 0m1.681s
sys 0m0.012s

exhuma, perhaps you want to test with other data sets?

[pitrou]

Uh, those measurements are wrong, sorry, since tester.py doesn't consume the iterator. When consuming the iterator, the patch is ~ 4x faster than the original code, which is more reasonable :-)

[pitrou]

It seems like the speed of Network.supernet() is a bottleneck here. bpo-16531 would probably allow making supernet() much faster.

[pitrou]

Updated patch, a bit faster yet. After bpo-16531 is committed, it is now ~15x faster than 3.4.

[python-dev]

New changeset 8867874a2b7d by Antoine Pitrou in branch 'default':
Issue bpo-20826: Optimize ipaddress.collapse_addresses().
http://hg.python.org/cpython/rev/8867874a2b7d

[pitrou]

I've now committed this. exhuma, if you have any further observations or results, don't hesitate to post them!