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
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!

Hi 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.

Thanks,
Han
_______________________________________________
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev

Reply via email to