From patchwork Thu Apr 1 23:20:56 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ben Pfaff X-Patchwork-Id: 1461448 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org (client-ip=2605:bc80:3010::133; helo=smtp2.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4FBK4K5qDfz9sV5 for ; Fri, 2 Apr 2021 10:23:29 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 3870540EC0; Thu, 1 Apr 2021 23:22:56 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id GVEKqouxDrud; Thu, 1 Apr 2021 23:22:51 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [IPv6:2605:bc80:3010:104::8cd3:938]) by smtp2.osuosl.org (Postfix) with ESMTP id 7724D406AA; Thu, 1 Apr 2021 23:22:49 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 43680C001A; Thu, 1 Apr 2021 23:22:46 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 1DC6BC000B for ; Thu, 1 Apr 2021 23:22:44 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 1F25D406A2 for ; Thu, 1 Apr 2021 23:21:47 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 7ZXtJAWKq4pF for ; Thu, 1 Apr 2021 23:21:44 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 Received: from relay5-d.mail.gandi.net (relay5-d.mail.gandi.net [217.70.183.197]) by smtp2.osuosl.org (Postfix) with ESMTPS id E30F740620 for ; Thu, 1 Apr 2021 23:21:40 +0000 (UTC) X-Originating-IP: 75.54.222.30 Received: from sigfpe.attlocal.net (75-54-222-30.lightspeed.rdcyca.sbcglobal.net [75.54.222.30]) (Authenticated sender: blp@ovn.org) by relay5-d.mail.gandi.net (Postfix) with ESMTPSA id 412FE1C0006; Thu, 1 Apr 2021 23:21:37 +0000 (UTC) From: Ben Pfaff To: dev@openvswitch.org Date: Thu, 1 Apr 2021 16:20:56 -0700 Message-Id: <20210401232108.3902274-15-blp@ovn.org> X-Mailer: git-send-email 2.29.2 In-Reply-To: <20210401232108.3902274-1-blp@ovn.org> References: <20210401232108.3902274-1-blp@ovn.org> MIME-Version: 1.0 Cc: Leonid Ryzhyk , Ben Pfaff Subject: [ovs-dev] [PATCH v2 14/26] ovn-northd-ddlog: Workaround for slow group_by. X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" From: Leonid Ryzhyk This patch is a workaround for a performance issue in the DDlog compiler. The issue will hopefully be resolved in a future version of DDlog, but for now we need this and possibly a few other similar fixes. Here is one affected rule: ``` sb::Out_Port_Group(._uuid = hash128(sb_name), .name = sb_name, .ports = port_names) :- nb::Port_Group(._uuid = _uuid, .name = nb_name, .ports = pg_ports), var port_uuid = FlatMap(pg_ports), &SwitchPort(.lsp = lsp@nb::Logical_Switch_Port{._uuid = port_uuid, .name = port_name}, .sw = &Switch{.ls = nb::Logical_Switch{._uuid = ls_uuid}}), TunKeyAllocation(.datapath = ls_uuid, .tunkey = tunkey), var sb_name = "${tunkey}_${nb_name}", var port_names = port_name.group_by((_uuid, sb_name)).to_set(). ``` The first literal in the body of the rule binds variable `pg_ports` to the array of ports in the port group. This is a potentially large array that immediately gets flattened by the `FlatMap` operator. Since the `pg_ports` variable is not used in the remainder of the rule, DDlog normally would not propagate it through the rest of the rule. Unfortunately, due to a subtle semantic quirk, the behavior is different when there is a `group_by` operator further down in the rule, in which case unused variables are still propagated through the rule, which involves expensive copies. The workaround I implemented factors the first two terms in the rule into a separate `PortGroupPort` relation, so that the ports array no longer occurs in the new version of the rule: ``` sb::Out_Port_Group(._uuid = hash128(sb_name), .name = sb_name, .ports = port_names) :- PortGroupPort(.pg_uuid = _uuid, .pg_name = nb_name, .port = port_uuid), &SwitchPort(.lsp = lsp@nb::Logical_Switch_Port{._uuid = port_uuid, .name = port_name}, .sw = &Switch{.ls = nb::Logical_Switch{._uuid = ls_uuid}}), TunKeyAllocation(.datapath = ls_uuid, .tunkey = tunkey), var sb_name = "${tunkey}_${nb_name}", var port_names = port_name.group_by((_uuid, sb_name)).to_set(). ``` Again, benchmarking is likely to reveal more instances of this. A proper fix will require a change to the DDlog compiler. Signed-off-by: Leonid Ryzhyk Signed-off-by: Ben Pfaff --- northd/ovn_northd.dl | 19 +++++++++++++------ 1 file changed, 13 insertions(+), 6 deletions(-) diff --git a/northd/ovn_northd.dl b/northd/ovn_northd.dl index 80d8598bd7dc..5a7a11295964 100644 --- a/northd/ovn_northd.dl +++ b/northd/ovn_northd.dl @@ -712,11 +712,10 @@ sb::Out_Address_Set(._uuid = hash128("svc_monitor_mac"), SvcMonitorMac(svc_monitor_mac). sb::Out_Address_Set(hash128(as_name), as_name, pg_ip4addrs.union()) :- - nb::Port_Group(.ports = pg_ports, .name = pg_name), + PortGroupPort(.pg_name = pg_name, .port = port_uuid), var as_name = pg_name ++ "_ip4", // avoid name collisions with user-defined Address_Sets not nb::Address_Set(.name = as_name), - var port_uuid = FlatMap(pg_ports), PortStaticAddresses(.lsport = port_uuid, .ip4addrs = stat), SwitchPortNewDynamicAddress(&SwitchPort{.lsp = nb::Logical_Switch_Port{._uuid = port_uuid}}, dyn_addr), @@ -738,11 +737,10 @@ sb::Out_Address_Set(hash128(as_name), as_name, set_empty()) :- not nb::Address_Set(.name = as_name). sb::Out_Address_Set(hash128(as_name), as_name, pg_ip6addrs.union()) :- - nb::Port_Group(.ports = pg_ports, .name = pg_name), + PortGroupPort(.pg_name = pg_name, .port = port_uuid), var as_name = pg_name ++ "_ip6", // avoid name collisions with user-defined Address_Sets not nb::Address_Set(.name = as_name), - var port_uuid = FlatMap(pg_ports), PortStaticAddresses(.lsport = port_uuid, .ip6addrs = stat), SwitchPortNewDynamicAddress(&SwitchPort{.lsp = nb::Logical_Switch_Port{._uuid = port_uuid}}, dyn_addr), @@ -771,9 +769,18 @@ sb::Out_Address_Set(hash128(as_name), as_name, set_empty()) :- * SB Port_Group.name uniqueness constraint, ovn-northd populates the field * with the value: _. */ + +relation PortGroupPort( + pg_uuid: uuid, + pg_name: string, + port: uuid) + +PortGroupPort(pg_uuid, pg_name, port) :- + nb::Port_Group(._uuid = pg_uuid, .name = pg_name, .ports = pg_ports), + var port = FlatMap(pg_ports). + sb::Out_Port_Group(._uuid = hash128(sb_name), .name = sb_name, .ports = port_names) :- - nb::Port_Group(._uuid = _uuid, .name = nb_name, .ports = pg_ports), - var port_uuid = FlatMap(pg_ports), + PortGroupPort(.pg_uuid = _uuid, .pg_name = nb_name, .port = port_uuid), &SwitchPort(.lsp = lsp@nb::Logical_Switch_Port{._uuid = port_uuid, .name = port_name}, .sw = &Switch{.ls = nb::Logical_Switch{._uuid = ls_uuid}}),