On Fri, Apr 13, 2018 at 2:40 PM, Han Zhou <zhou...@gmail.com> wrote:
> On Fri, Apr 13, 2018 at 1:42 PM, Ben Pfaff <b...@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 <b...@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
> > > > big (and they will eventually even if they do not today, because
> > > > I think that it would be better to expand the allocations
> > >
> > > Sorry that I didn't find it a problem. For each group, there are i
> > > 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
> > > and some can be ipv6).
> > > Although there are nested loops, this implementation iterates each
> > > ipv6 address only once, so if the total number of ipv4 and ipv6
> > > are n, then it should be O(n). Please correct me if I missed
> > 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!
V3 is here: https://patchwork.ozlabs.org/patch/898123/
All comments are addressed except that I kept the xcalloc() there as
initial allocation for the exponential allocations. Please take a look.
dev mailing list