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

[Han Zhou]

On Fri, Apr 13, 2018 at 1:42 PM, Ben Pfaff <blp at ovn.org> wrote:
>
> 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.

Now I got your point! I will send V3 with this addressed. Thanks Ben!
>
> Thanks,
>
> Ben.