Skip to content

only check as many prefixlens as we need to in IPSet.__contains__ #239

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Draft
wants to merge 2 commits into
base: master
Choose a base branch
from
Draft

only check as many prefixlens as we need to in IPSet.__contains__ #239

wants to merge 2 commits into from

Conversation

jesopo
Copy link

@jesopo jesopo commented Nov 12, 2021 •
edited
Loading

this is a proof of concept. I'm aware self._update_prefixlens() will need to be called in more places. opinions wanted!

this minimises the amount of iterations __contains__ needs to do and it will still max out at the maximum prefix length of the IP version

@jesopo jesopo marked this pull request as draft November 12, 2021 16:28
@jesopo jesopo force-pushed the faster-ipset-contains branch from 10ae614 to b5afcc1 Compare November 12, 2021 16:37
@jstasiak
Copy link
Contributor

Hi @jesopo, thank you for the contribution. May I ask what issue does this change address?

@jesopo
Copy link
Author

jesopo commented Nov 13, 2021

it is simply an optimisation - if you have an IPSet of 4 IPv4 networks it does not make sense to iterate 32 times

@jesopo
Copy link
Author

jesopo commented Nov 13, 2021 •
edited
Loading 

✨ ~/src/netaddr/netaddr master % python3 -m timeit -n 5000 'import netaddr; "127.0.0.1/32" in netaddr.IPSet(["127.0.0.0/1"]);'
5000 loops, best of 5: 73.8 usec per loop
✨ ~/src/netaddr/netaddr master % git checkout faster-ipset-contains
Switched to branch 'faster-ipset-contains'
Your branch is up to date with 'origin/faster-ipset-contains'.
✨ ~/src/netaddr/netaddr faster-ipset-contains % python3 -m timeit -n 5000 'import netaddr; "127.0.0.1/32" in netaddr.IPSet(["127.0.0.0/1"]);'
5000 loops, best of 5: 23.2 usec per loop

@jesopo
Copy link
Author

jesopo commented Nov 17, 2021

it's even competitive in a worst case scenario (please excuse the messy CIDR calculations!)

✨ ~/src/netaddr/netaddr master % python3 -m timeit -n 50000 --setup 'from netaddr import IPSet, IPAddress, IPNetwork; n = IPSet([IPNetwork(f"{str(IPAddress(1<<32-i))}/{i}") for i in range(1,33)])' '"127.0.0.1/32" in n'
50000 loops, best of 5: 55.3 usec per loop
✨ ~/src/netaddr/netaddr master % git checkout faster-ipset-contains
Switched to branch 'faster-ipset-contains'
Your branch is up to date with 'origin/faster-ipset-contains'.
✨ ~/src/netaddr/netaddr faster-ipset-contains % python3 -m timeit -n 50000 --setup 'from netaddr import IPSet, IPAddress, IPNetwork; n = IPSet([IPNetwork(f"{str(IPAddress(1<<32-i))}/{i}") for i in range(1,33)])' '"127.0.0.1/32" in n'
50000 loops, best of 5: 62.2 usec per loop

the extra time here is caused by having to check the prefixlen you're looking at belongs to the right IP version - this can be resolved by storing prefixlens separated by version ahead of time

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@jesopo @jstasiak