Repository: joke2k/faker

Issue:
ipv4 faker very slow
Hi! We updated from Faker 0.9.0 to 0.9.2 and noticed our tests speed decreased by 5X. We tracked the bug to the changes in the ipv4 faker done in commit 3b847f48bbfc33aed3e86cffcedbcfd1c0cccec5

### Steps to reproduce

1. checkout to commit 3b847f48bbfc33aed3e86cffcedbcfd1c0cccec5
1. run the following: `time python -c 'import faker; fake = faker.Faker(); [fake.ipv4() for _ in range(100)]'`
1. Check its output to see it was slow. in my laptop it took about 6 seconds.
1. Run `git checkout HEAD~1` to go to a working commit
1. Run the command of step 2 again and it will work much faster (in my case it took 0.4 seconds)

### Expected behavior

Generating ivp4 addresses should be fast

### Actual behavior

Generating ipv4 addresses is slow


Discussion:
fcurella: Thank you so much @malefice !

I think I'm OK with a higher memory usage as long as it's not crazy high and it's only if the user requests some IP address. In other words, I wouldn't compile the list on instantiation, but the first time it's needed.
malefice: Yeah, that is the plan. As for higher memory usage, it should be slightly higher at worst. We are talking about caching several lists with possibly a few hundred elements each, and they will only be generated during a cache miss. I just tested a rough implementation for private IPv4 networks, and generating 1000 such addresses from the same provider instance only takes 0.126s on my machine, and generating 100,000 only takes 1.4s. I will just need to polish/beautify it.
malefice: In the process of polishing my initial implementation to improve performance, I also found out that current IPV4 generation can be biased against IP addresses in larger subnets, leading to more recycled IP's from smaller subnets when generating in bulk. This is because the equal distribution is applied on the subnet level, regardless of how large each subnet is. To demonstrate, suppose that the resulting network list is the following:

- A - ip_network('10.0.0.0/8')
- B - ip_network('192.168.0.0/24')
- C - ip_network('192.168.1.0/24')
- D - ip_network('192.168.2.0/24')

Under the current code, each of the networks A, B, C, and D have a 25% chance of being selected, but each IP in network A only has a 1 in 16,777,216 chance of being selected if network A was already chosen. On the other hand, each IP in network B, C, and D has a 1 in 256 chance of being selected if the corresponding network was already chosen.

Each IP in network A then only has around a 1 in 67 million chance of being generated (25% of 1 in 16,777,216), but each IP in networks B, C, and D has around 1 in 1024 chance (25% of 1 in 256). This proves that the IP addresses generated are not equally distributed.

To fix this, I applied weights in the selection process, and the weights are simply the sizes of the subnets, and each IP regardless of subnet has a 1 in X chance of being selected, where X is the total number of addresses across all the subnets.

With this bias correction and the caching behavior, I can generate 1 million addresses using `ipv4()` in around 23 to 24 seconds on my machine. Comparing it to 1000 addresses in 17.8 seconds of the old implementation, this is a 740x to 750x performance improvement.
fcurella: NIce work @malefice ! ❤️ 

Could you also write some tests for the `except` clauses missed [here](https://coveralls.io/builds/26824112/source?filename=faker%2Fproviders%2Finternet%2F__init__.py#L360)?



Patch:
diff --git a/faker/build_docs.py b/faker/build_docs.py
index 3afc4714..17a96d3d 100644
--- a/faker/build_docs.py
+++ b/faker/build_docs.py
@@ -15,6 +15,12 @@ def write(fh, s):
     return fh.write(s.encode('utf-8'))
 
 
+def write_base_provider(fh, doc, base_provider):
+    formatters = doc.get_provider_formatters(base_provider)
+    write(fh, ':github_url: hide\n\n')
+    write_provider(fh, doc, base_provider, formatters)
+
+
 def write_provider(fh, doc, provider, formatters, excludes=None):
 
     if excludes is None:
@@ -47,16 +53,21 @@ def write_provider(fh, doc, provider, formatters, excludes=None):
 def write_docs(*args, **kwargs):
     from faker import Faker, documentor
     from faker.config import DEFAULT_LOCALE, AVAILABLE_LOCALES
-
-    fake = Faker(locale=DEFAULT_LOCALE)
-
     from faker.providers import BaseProvider
-    base_provider_formatters = [f for f in dir(BaseProvider)]
 
+    fake = Faker(locale=DEFAULT_LOCALE)
     doc = documentor.Documentor(fake)
 
-    formatters = doc.get_formatters(with_args=True, with_defaults=True)
+    # Write docs for fakers.providers.BaseProvider
+    base_provider = BaseProvider(fake)
+    fname = os.path.join(DOCS_ROOT, 'providers', 'BaseProvider.rst')
+    with open(fname, 'wb') as fh:
+        write_base_provider(fh, doc, base_provider)
 
+    # Write docs for default locale providers
+    base_provider_formatters = [f for f in dir(BaseProvider)]
+    formatters = doc.get_formatters(with_args=True, with_defaults=True,
+                                    excludes=base_provider_formatters)
     for provider, fakers in formatters:
         provider_name = doc.get_provider_name(provider)
         fname = os.path.join(DOCS_ROOT, 'providers', '%s.rst' % provider_name)
@@ -64,15 +75,18 @@ def write_docs(*args, **kwargs):
             write(fh, ':github_url: hide\n\n')
             write_provider(fh, doc, provider, fakers)
 
+    # Write providers index page
     with open(os.path.join(DOCS_ROOT, 'providers.rst'), 'wb') as fh:
         write(fh, ':github_url: hide\n\n')
         write(fh, 'Providers\n')
         write(fh, '=========\n')
         write(fh, '.. toctree::\n')
         write(fh, '   :maxdepth: 2\n\n')
+        write(fh, '   providers/BaseProvider\n')
         [write(fh, '   providers/%s\n' % doc.get_provider_name(provider))
          for provider, fakers in formatters]
 
+    # Write docs for locale-specific providers
     AVAILABLE_LOCALES = sorted(AVAILABLE_LOCALES)
     for lang in AVAILABLE_LOCALES:
         fname = os.path.join(DOCS_ROOT, 'locales', '%s.rst' % lang)
@@ -90,6 +104,7 @@ def write_docs(*args, **kwargs):
                                           excludes=base_provider_formatters):
                 write_provider(fh, d, p, fs)
 
+    # Write locales index page
     with open(os.path.join(DOCS_ROOT, 'locales.rst'), 'wb') as fh:
         write(fh, ':github_url: hide\n\n')
         write(fh, 'Locales\n')
diff --git a/faker/documentor.py b/faker/documentor.py
index 034c38f0..378104ae 100644
--- a/faker/documentor.py
+++ b/faker/documentor.py
@@ -22,7 +22,6 @@ class Documentor(object):
         self.already_generated = []
 
     def get_formatters(self, locale=None, excludes=None, **kwargs):
-
         self.max_name_len = 0
         self.already_generated = [] if excludes is None else excludes[:]
         formatters = []
diff --git a/faker/providers/internet/__init__.py b/faker/providers/internet/__init__.py
index 91bc9f2f..d7775597 100644
--- a/faker/providers/internet/__init__.py
+++ b/faker/providers/internet/__init__.py
@@ -10,6 +10,7 @@ from ipaddress import ip_address, ip_network, IPV4LENGTH, IPV6LENGTH
 # from faker.generator import random
 # from faker.providers.lorem.la import Provider as Lorem
 from faker.utils.decorators import lowercase, slugify, slugify_unicode
+from faker.utils.distribution import choices_distribution
 
 
 localized = True
@@ -29,12 +30,6 @@ class _IPv4Constants:
         'c': ip_network('192.0.0.0/3'),
     }
 
-    _linklocal_network = ip_network('169.254.0.0/16')
-
-    _loopback_network = ip_network('127.0.0.0/8')
-
-    _multicast_network = ip_network('224.0.0.0/4')
-
     # Three common private networks from class A, B and CIDR
     # to generate private addresses from.
     _private_networks = [
@@ -49,8 +44,8 @@ class _IPv4Constants:
     _excluded_networks = [
         ip_network('0.0.0.0/8'),
         ip_network('100.64.0.0/10'),
-        ip_network('127.0.0.0/8'),
-        ip_network('169.254.0.0/16'),
+        ip_network('127.0.0.0/8'),  # loopback network
+        ip_network('169.254.0.0/16'),  # linklocal network
         ip_network('192.0.0.0/24'),
         ip_network('192.0.2.0/24'),
         ip_network('192.31.196.0/24'),
@@ -60,12 +55,9 @@ class _IPv4Constants:
         ip_network('198.18.0.0/15'),
         ip_network('198.51.100.0/24'),
         ip_network('203.0.113.0/24'),
+        ip_network('224.0.0.0/4'),  # multicast network
         ip_network('240.0.0.0/4'),
         ip_network('255.255.255.255/32'),
-    ] + [
-        _linklocal_network,
-        _loopback_network,
-        _multicast_network,
     ]
 
 
@@ -251,14 +243,123 @@ class Provider(BaseProvider):
 
         return self.generator.parse(pattern)
 
-    def _random_ipv4_address_from_subnet(self, subnet, network=False):
+    def _get_all_networks_and_weights(self, address_class=None):
+        """
+        Produces a 2-tuple of valid IPv4 networks and corresponding relative weights
+
+        :param address_class: IPv4 address class (a, b, or c)
+        """
+        # If `address_class` has an unexpected value, use the whole IPv4 pool
+        if address_class in _IPv4Constants._network_classes.keys():
+            networks_attr = '_cached_all_class_{}_networks'.format(address_class)
+            all_networks = [_IPv4Constants._network_classes[address_class]]
+        else:
+            networks_attr = '_cached_all_networks'
+            all_networks = [ip_network('0.0.0.0/0')]
+
+        # Return cached network and weight data if available
+        weights_attr = '{}_weights'.format(networks_attr)
+        if hasattr(self, networks_attr) and hasattr(self, weights_attr):
+            return getattr(self, networks_attr), getattr(self, weights_attr)
+
+        # Otherwise, compute for list of networks (excluding special networks)
+        all_networks = self._exclude_ipv4_networks(
+            all_networks,
+            _IPv4Constants._excluded_networks,
+        )
+
+        # Then compute for list of corresponding relative weights
+        weights = [network.num_addresses for network in all_networks]
+
+        # Then cache and return results
+        setattr(self, networks_attr, all_networks)
+        setattr(self, weights_attr, weights)
+        return all_networks, weights
+
+    def _get_private_networks_and_weights(self, address_class=None):
+        """
+        Produces an OrderedDict of valid private IPv4 networks and corresponding relative weights
+
+        :param address_class: IPv4 address class (a, b, or c)
+        """
+        # If `address_class` has an unexpected value, choose a valid value at random
+        if address_class not in _IPv4Constants._network_classes.keys():
+            address_class = self.ipv4_network_class()
+
+        # Return cached network and weight data if available for a specific address class
+        networks_attr = '_cached_private_class_{}_networks'.format(address_class)
+        weights_attr = '{}_weights'.format(networks_attr)
+        if hasattr(self, networks_attr) and hasattr(self, weights_attr):
+            return getattr(self, networks_attr), getattr(self, weights_attr)
+
+        # Otherwise, compute for list of private networks (excluding special networks)
+        supernet = _IPv4Constants._network_classes[address_class]
+        private_networks = [
+            subnet for subnet in _IPv4Constants._private_networks
+            if subnet.overlaps(supernet)
+        ]
+        private_networks = self._exclude_ipv4_networks(
+            private_networks,
+            _IPv4Constants._excluded_networks,
+        )
+
+        # Then compute for list of corresponding relative weights
+        weights = [network.num_addresses for network in private_networks]
+
+        # Then cache and return results
+        setattr(self, networks_attr, private_networks)
+        setattr(self, weights_attr, weights)
+        return private_networks, weights
+
+    def _get_public_networks_and_weights(self, address_class=None):
+        """
+        Produces a 2-tuple of valid public IPv4 networks and corresponding relative weights
+
+        :param address_class: IPv4 address class (a, b, or c)
+        """
+        # If `address_class` has an unexpected value, choose a valid value at random
+        if address_class not in _IPv4Constants._network_classes.keys():
+            address_class = self.ipv4_network_class()
+
+        # Return cached network and weight data if available for a specific address class
+        networks_attr = '_cached_public_class_{}_networks'.format(address_class)
+        weights_attr = '{}_weights'.format(networks_attr)
+        if hasattr(self, networks_attr) and hasattr(self, weights_attr):
+            return getattr(self, networks_attr), getattr(self, weights_attr)
+
+        # Otherwise, compute for list of public networks (excluding private and special networks)
+        public_networks = [_IPv4Constants._network_classes[address_class]]
+        public_networks = self._exclude_ipv4_networks(
+            public_networks,
+            _IPv4Constants._private_networks +
+            _IPv4Constants._excluded_networks,
+        )
+
+        # Then compute for list of corresponding relative weights
+        weights = [network.num_addresses for network in public_networks]
+
+        # Then cache and return results
+        setattr(self, networks_attr, public_networks)
+        setattr(self, weights_attr, weights)
+        return public_networks, weights
+
+    def _random_ipv4_address_from_subnets(self, subnets, weights=None, network=False):
         """
         Produces a random IPv4 address or network with a valid CIDR
-        from within a given subnet.
+        from within the given subnets using a distribution described
+        by weights.
 
-        :param subnet: IPv4Network to choose from within
+        :param subnets: List of IPv4Networks to choose from within
+        :param weights: List of weights corresponding to the individual IPv4Networks
         :param network: Return a network address, and not an IP address
+        :return:
         """
+        # If the weights argument has an invalid value, default to equal distribution
+        try:
+            subnet = choices_distribution(subnets, weights, random=self.generator.random, length=1)[0]
+        except (AssertionError, TypeError):
+            subnet = self.generator.random.choice(subnets)
+
         address = str(
             subnet[self.generator.random.randint(
                 0, subnet.num_addresses - 1,
@@ -283,6 +384,7 @@ class Provider(BaseProvider):
         :param networks_to_exclude: List of IPv4 networks to exclude
         :returns: Flat list of IPv4 networks
         """
+        networks_to_exclude.sort(key=lambda x: x.prefixlen)
         for network_to_exclude in networks_to_exclude:
             def _exclude_ipv4_network(network):
                 """
@@ -327,7 +429,7 @@ class Provider(BaseProvider):
 
     def ipv4(self, network=False, address_class=None, private=None):
         """
-        Produce a random IPv4 address or network with a valid CIDR.
+        Returns a random IPv4 address or network with a valid CIDR.
 
         :param network: Network address
         :param address_class: IPv4 address class (a, b, or c)
@@ -340,25 +442,9 @@ class Provider(BaseProvider):
         elif private is False:
             return self.ipv4_public(address_class=address_class,
                                     network=network)
-
-        # if neither private nor public is required explicitly,
-        # generate from whole requested address space
-        if address_class:
-            all_networks = [_IPv4Constants._network_classes[address_class]]
         else:
-            # if no address class is choosen, use whole IPv4 pool
-            all_networks = [ip_network('0.0.0.0/0')]
-
-        # exclude special networks
-        all_networks = self._exclude_ipv4_networks(
-            all_networks,
-            _IPv4Constants._excluded_networks,
-        )
-
-        # choose random network from the list
-        random_network = self.generator.random.choice(all_networks)
-
-        return self._random_ipv4_address_from_subnet(random_network, network)
+            all_networks, weights = self._get_all_networks_and_weights(address_class=address_class)
+            return self._random_ipv4_address_from_subnets(all_networks, weights=weights, network=network)
 
     def ipv4_private(self, network=False, address_class=None):
         """
@@ -368,26 +454,8 @@ class Provider(BaseProvider):
         :param address_class: IPv4 address class (a, b, or c)
         :returns: Private IPv4
         """
-        # compute private networks from given class
-        supernet = _IPv4Constants._network_classes[
-            address_class or self.ipv4_network_class()
-        ]
-
-        private_networks = [
-            subnet for subnet in _IPv4Constants._private_networks
-            if subnet.overlaps(supernet)
-        ]
-
-        # exclude special networks
-        private_networks = self._exclude_ipv4_networks(
-            private_networks,
-            _IPv4Constants._excluded_networks,
-        )
-
-        # choose random private network from the list
-        private_network = self.generator.random.choice(private_networks)
-
-        return self._random_ipv4_address_from_subnet(private_network, network)
+        private_networks, weights = self._get_private_networks_and_weights(address_class=address_class)
+        return self._random_ipv4_address_from_subnets(private_networks, weights=weights, network=network)
 
     def ipv4_public(self, network=False, address_class=None):
         """
@@ -397,22 +465,8 @@ class Provider(BaseProvider):
         :param address_class: IPv4 address class (a, b, or c)
         :returns: Public IPv4
         """
-        # compute public networks
-        public_networks = [_IPv4Constants._network_classes[
-            address_class or self.ipv4_network_class()
-        ]]
-
-        # exclude private and excluded special networks
-        public_networks = self._exclude_ipv4_networks(
-            public_networks,
-            _IPv4Constants._private_networks +
-            _IPv4Constants._excluded_networks,
-        )
-
-        # choose random public network from the list
-        public_network = self.generator.random.choice(public_networks)
-
-        return self._random_ipv4_address_from_subnet(public_network, network)
+        public_networks, weights = self._get_public_networks_and_weights(address_class=address_class)
+        return self._random_ipv4_address_from_subnets(public_networks, weights=weights, network=network)
 
     def ipv6(self, network=False):
         """Produce a random IPv6 address or network with a valid CIDR"""


Test patch:
diff --git a/tests/test_factory.py b/tests/test_factory.py
index 110728cb..a87fc3bd 100644
--- a/tests/test_factory.py
+++ b/tests/test_factory.py
@@ -6,6 +6,10 @@ import re
 import string
 import sys
 import unittest
+try:
+    from unittest.mock import patch, PropertyMock
+except ImportError:
+    from mock import patch, PropertyMock
 
 from collections import OrderedDict
 from ipaddress import ip_address, ip_network
@@ -526,6 +530,41 @@ class FactoryTestCase(unittest.TestCase):
             email = factory.email()
             assert '@' in email
 
+    def test_ipv4_caching(self):
+        from faker.providers.internet import Provider, _IPv4Constants
+
+        # The extra [None] here is to test code path involving whole IPv4 pool
+        for address_class in list(_IPv4Constants._network_classes.keys()) + [None]:
+            if address_class is None:
+                networks_attr = '_cached_all_networks'
+            else:
+                networks_attr = '_cached_all_class_{}_networks'.format(address_class)
+            weights_attr = '{}_weights'.format(networks_attr)
+            provider = Provider(self.generator)
+
+            # First, test cache creation
+            assert not hasattr(provider, networks_attr)
+            assert not hasattr(provider, weights_attr)
+            provider.ipv4(address_class=address_class)
+            assert hasattr(provider, networks_attr)
+            assert hasattr(provider, weights_attr)
+
+            # Then, test cache access on subsequent calls
+            with patch.object(Provider, networks_attr, create=True,
+                              new_callable=PropertyMock) as mock_networks_cache:
+                with patch.object(Provider, weights_attr, create=True,
+                                  new_callable=PropertyMock) as mock_weights_cache:
+                    # Keep test fast by patching the cache attributes to return something simple
+                    mock_networks_cache.return_value = [ip_network('10.0.0.0/24')]
+                    mock_weights_cache.return_value = [10]
+                    for _ in range(100):
+                        provider.ipv4(address_class=address_class)
+
+                    # Python's hasattr() internally calls getattr()
+                    # So each call to ipv4() accesses the cache attributes twice
+                    assert mock_networks_cache.call_count == 200
+                    assert mock_weights_cache.call_count == 200
+
     def test_ipv4(self):
         from faker.providers.internet import Provider
 
@@ -565,6 +604,37 @@ class FactoryTestCase(unittest.TestCase):
             klass = provider.ipv4_network_class()
             assert klass in 'abc'
 
+    def test_ipv4_private_caching(self):
+        from faker.providers.internet import Provider, _IPv4Constants
+
+        for address_class in _IPv4Constants._network_classes.keys():
+            networks_attr = '_cached_private_class_{}_networks'.format(address_class)
+            weights_attr = '{}_weights'.format(networks_attr)
+            provider = Provider(self.generator)
+
+            # First, test cache creation
+            assert not hasattr(provider, networks_attr)
+            assert not hasattr(provider, weights_attr)
+            provider.ipv4_private(address_class=address_class)
+            assert hasattr(provider, networks_attr)
+            assert hasattr(provider, weights_attr)
+
+            # Then, test cache access on subsequent calls
+            with patch.object(Provider, networks_attr, create=True,
+                              new_callable=PropertyMock) as mock_networks_cache:
+                with patch.object(Provider, weights_attr, create=True,
+                                  new_callable=PropertyMock) as mock_weights_cache:
+                    # Keep test fast by patching the cache attributes to return something simple
+                    mock_networks_cache.return_value = [ip_network('10.0.0.0/24')]
+                    mock_weights_cache.return_value = [10]
+                    for _ in range(100):
+                        provider.ipv4_private(address_class=address_class)
+
+                    # Python's hasattr() internally calls getattr()
+                    # So each call to ipv4_private() accesses the cache attributes twice
+                    assert mock_networks_cache.call_count == 200
+                    assert mock_weights_cache.call_count == 200
+
     def test_ipv4_private(self):
         from faker.providers.internet import Provider
         provider = Provider(self.generator)
@@ -638,6 +708,37 @@ class FactoryTestCase(unittest.TestCase):
             assert ip_address(address) >= class_min
             assert ip_address(address) <= class_max
 
+    def test_ipv4_public_caching(self):
+        from faker.providers.internet import Provider, _IPv4Constants
+
+        for address_class in _IPv4Constants._network_classes.keys():
+            networks_attr = '_cached_public_class_{}_networks'.format(address_class)
+            weights_attr = '{}_weights'.format(networks_attr)
+            provider = Provider(self.generator)
+
+            # First, test cache creation
+            assert not hasattr(provider, networks_attr)
+            assert not hasattr(provider, weights_attr)
+            provider.ipv4_public(address_class=address_class)
+            assert hasattr(provider, networks_attr)
+            assert hasattr(provider, weights_attr)
+
+            # Then, test cache access on subsequent calls
+            with patch.object(Provider, networks_attr, create=True,
+                              new_callable=PropertyMock) as mock_networks_cache:
+                with patch.object(Provider, weights_attr, create=True,
+                                  new_callable=PropertyMock) as mock_weights_cache:
+                    # Keep test fast by patching the cache attributes to return something simple
+                    mock_networks_cache.return_value = [ip_network('10.0.0.0/24')]
+                    mock_weights_cache.return_value = [10]
+                    for _ in range(100):
+                        provider.ipv4_public(address_class=address_class)
+
+                    # Python's hasattr() internally calls getattr()
+                    # So each call to ipv4_public() accesses the cache attributes twice
+                    assert mock_networks_cache.call_count == 200
+                    assert mock_weights_cache.call_count == 200
+
     def test_ipv4_public(self):
         from faker.providers.internet import Provider
         provider = Provider(self.generator)
@@ -697,6 +798,39 @@ class FactoryTestCase(unittest.TestCase):
             assert len(address) <= 15
             assert not ip_address(address).is_private, address
 
+    def test_ipv4_distribution_selection(self):
+        from faker.providers.internet import Provider
+        from faker.utils.distribution import choices_distribution
+        provider = Provider(self.generator)
+
+        subnets = [ip_network('10.0.0.0/8'), ip_network('11.0.0.0/8')]
+        valid_weights = [1, 1]
+        list_of_invalid_weights = [
+            [1, 2, 3],   # List size does not match subnet list size
+            ['a', 'b'],  # List size matches, but elements are invalid
+            None,        # Not a list or valid iterable
+        ]
+
+        with patch('faker.providers.internet.choices_distribution',
+                   wraps=choices_distribution) as mock_choices_fn:
+            with patch('faker.generator.random.choice',
+                       wraps=random.choice) as mock_random_choice:
+                # If weights argument is valid, only `choices_distribution` should be called
+                provider._random_ipv4_address_from_subnets(subnets, valid_weights)
+                assert mock_choices_fn.call_count == 1
+                assert mock_random_choice.call_count == 0
+
+                # If weights argument is invalid, calls to `choices_distribution` will fail
+                # and calls to `random.choice` will be made as failover behavior
+                for invalid_weights in list_of_invalid_weights:
+                    # Reset mock objects for each iteration
+                    mock_random_choice.reset_mock()
+                    mock_choices_fn.reset_mock()
+
+                    provider._random_ipv4_address_from_subnets(subnets, invalid_weights)
+                    assert mock_choices_fn.call_count == 1
+                    assert mock_random_choice.call_count == 1
+
     def test_ipv6(self):
         from faker.providers.internet import Provider