[ovs-dev] [PATCH v2 2/2] ovn: Support address sets generated from port groups

Ben Pfaff blp at ovn.org
Fri Apr 13 20:42:20 UTC 2018

On Fri, Apr 13, 2018 at 01:33:26PM -0700, Han Zhou wrote:
> On Fri, Apr 13, 2018 at 12:54 PM, Ben Pfaff <blp at ovn.org> wrote:
> > I think that sync_address_sets() is O(n**2) in n_ipv4_addrs and
> > n_ipv6_addrs, because of the allocation strategy.  If port groups get
> > big (and they will eventually even if they do not today, because scale)
> > I think that it would be better to expand the allocations exponentially.
> Sorry that I didn't find it a problem. For each group, there are i ports,
> and for each port there are j address groups (e.g. mac ip1 ip2 ip3 ...),
> and for each address group there are k addresses (some of them can be ipv4
> and some can be ipv6).
> Although there are nested loops, this implementation iterates each ipv4 and
> ipv6 address only once, so if the total number of ipv4 and ipv6 addresses
> are n, then it should be O(n). Please correct me if I missed something here.

I agree that the function visits and inserts each ipv4 and ipv6 address
once, which is O(n).  The issue is that xrealloc() has to copy all of
the addresses each time.  Suppose, for example, that there are 50
addresses in an address set, 1 per port.  This yields a sequence of 50
xrealloc() calls that copy 0, 1, 2, ..., 49 addresses, respectively,
which is O(n**2) copies.  The usual solution is to expand the array by
(roughly) doubling, so that there are only 0 + 1 + 2 + 4 + 8 + 16 + 32
copies total, which is O(n) copies.



More information about the dev mailing list