[ovs-dev] [PATCH ovn] ovn-northd-ddlog: Avoid N**2 blowup for N connected logical routers.

[Ben Pfaff]

On Fri, Jul 02, 2021 at 04:30:52PM +0200, Dumitru Ceara wrote:
> On 7/2/21 2:56 AM, Ben Pfaff wrote:
> > It's easy to implement "connected components" in raw DDlog, but it
> > takes N**2 time and space in the number of elements in a component.
> > This was a huge waste for a test case supplied by Dumitru Ceara that
> > had over 8000 logical routers.  This commit solves the problem by using
> > the "graph" transformer built in DDlog, which efficiently implements
> > connected components.
> > 
> > Signed-off-by: Ben Pfaff <blp at ovn.org>
> > Reported-by: Dumitru Ceara <dceara at redhat.com>
> > Reported-at: https://mail.openvswitch.org/pipermail/ovs-dev/2021-June/384519.html
> > ---
> > All the tests pass with this for me now, as long as
> > https://patchwork.ozlabs.org/project/ovn/patch/20210701124521.2095748-1-numans@ovn.org/
> > and
> > https://patchwork.ozlabs.org/project/ovn/patch/20210702005509.1626937-2-blp@ovn.org/
> > are applied to fix pre-existing issues.
> > 
> 
> This is very neat!  And it seems to work fine:
> 
> Acked-by: Dumitru Ceara <dceara at redhat.com>

Thanks!  I applied this to master.  I decided to translate your "seems
to work fine" into Tested-by, by the way.